微策略面试题.docx

面筋一：1. 什么是逻辑地址，物理地址，虚拟内存，TLB, Cache(操作系统引申：什么是page fault, 页面置换算法, Dirty bit，什么是中断，中断过程）；2. A是一个类，如何让A a = new A()编译不过，引申问解释singleton, 实现；3. 找包含N个元素的数组里第K大的元素（引申：快速排序，找中数元素，找前K大的元素），时间复杂度；4. 给定一个N个整数元素的数组，元素分别为A1, A2, A3.AN, 将数组变为A1 A3 =1/2.面筋二：笔试分2部分第一部分 四道问题 200分1.acb-bca=abc(记不准了，MS是这个样子) a,b,c都是数字0-9中的一个数，求a,b,c2.三个baskets, 一个里面装满oranges,一个里面装满apples,一个里面装的是oranges+apples。三个baskets外面都贴有label，但是label都是错的。让你只从一个篮子里面拿一个水果，怎么判断三个baskets里面装的是什么3.一个5 gallons buckets 一个3gallons buckets，如何如何取得4gallons water.4.essay: why you choose field of technology?全英文，答题也要用英文。第2部分 分四个catelogies, 自己选两个catelogies做算法部分1.C+中virtual function的作用，virtual constructor是什么2.21个coins ,有一个heavier，用天平用最少的次数称出来testing 部分就是写两个测试用例其他的两个部分一个是DATABASE 一个是os.都是很基础的东西面试考的都是一些逻辑题目1、昨天笔试的buckets问题这次是一个9GALLONS，一个4gallons，想要6gallons的water.2、随后一个 如果一个A gallons bucket,一个B gallons bucket,让你得到c gallons water怎么办。3、天平那个题目，这次是N个小球，其中有一个是重的，要用多少次。（这个见过 做出来了）4、4个人过桥，一个手电筒，那个题目。如果4个人的速度是TA=TB=TC=TD 要用多少时间。呵呵，貌似应聘测试的一般是两个部分一是英文测试，三选一，写一篇短文，例如Most important discoveries are accidential: seeking for one question,and find the answer to the other question.无所谓对错，只要给出理由就ok （看来英文作文的练习也是必不可少的呢）二是逻辑推理（俺的经验也不多，本科也没找过工作，不过腾讯的应聘测试的题目貌似也是逻辑推理居多，我同学应聘的开发倒是全技术的。）1 用多少网球可以把一辆公车填满2 2007的2007次方的最后一位数字是什么3有四张牌,牌的一面分别的E G 4 5如果说牌的一面是元音字母,那个另一面是偶数,要验证这条原则是不是正确应该翻开哪张牌?提示元音是EOAIU.4是常见的一个手电过桥题,四个人速度是10 6 3 1 问最短过桥时间5两个水桶分别装5加仑和3加仑水,问怎么得到4加仑水,没有其他容器没有标记攻工具(这个题目以前他也出过一样的)63个房间分别有3个人,怎么能遇见最高那个,原则是你可以进其中任意一间,如果你觉得他最高就说yes,然后游戏中止,如果说no就可以去另一间要求给出策略和概率(这个没有想得太明白 也不知道自己写的对不对)764个球,一个偏重,问最少用天平称几次可以找到?(这个也是他常出的题小变了一下)8 一个立方体 六面涂了颜色,将它分成1000个小立方体,问至少有两面涂有颜色的小立方体有多少个9 小船过河 有两组人三个M 三个C (单词不认识hoho) 小船最多可以载两个人,原则是河一边的M的人数不能多于另一边C人数.10 题目比较长,主要是说有个检验三个数是不是可以构成三角形的函数,每个选项中分别有四组数,问哪个选项中的几组数可以最好的检验这个函数,这个题猜的 不能确定应该要注意什么11abc d e fg h i这9个字母分别唯一的表示1到9中的数字,且每行和每列的三个数之和为13问c+e+g=?面筋三：一面1.两个数组，从两个里面分别选出两个数，其和等于20102.一百层楼，两个玻璃杯，怎么找到杯子会被摔破的最低楼层.二面1.二叉查找树，给你两个结点，如何找他们的最近共同祖先结点；如果是二叉树，又怎样?2.36匹马，6个跑道，怎么用最少的比赛次数，找到跑的最近的三匹马.三面1.virtual memory2.逻辑地址,物理地址3.说出你知道的排序方法,复杂度,特点比较,给出一些例子,让你选用排序算法.4.一个数组,找出出现次数最多的数;如果数组有序,不用hashmap,怎么做,写出完整代码.四面1.手机上的每个数字按键下面都有三个字母(一个数字对应三个字母),给出一个数字序列,输出这个序列所代表的所有可能的字母序列,写出代码.2.n个数字,值在范围在1n,但其中可能有重复出现的数字,如何判断有没有重复出现的数?3.三个房间,里面有三个人,让你选出最高的人.条件:你只能选当前房间里面的人或者你还未进过的房间里面的人.(给出你的直觉判断,不要求证明)面筋四：1.判断字符串是否是回文2. 1 2 3 . 1000找出所有和为1000的子序列3.层次遍历的递归写法4.一条河，两岸各有一个城市，修一座与岸垂直的桥，如何修A、B距离最短5.java garbage collector6.difference between array and list7.difference between process and roduce your roduce yourself多态虚函数介绍 虚拟内存、虚拟地址、物理地址 字符串逆转数组中查找出现次数最多的数字用栈实现队列求一个数这种bit为1的个数引用指针的区别面筋五：一面：1.给你一个数组，给你一个常量，如何找出两个数a1, a2， 且a1 + a2 = 这个常量2.给你10阶台阶，每次能走1阶或者2阶，问到第10级台阶，有多少种方法3.先序遍历的非递归解法二面： 1.给一个有向图，知道该有向图中各个节点的入度和出度，如何将这个有向图中的所有环2.给你1到1000这个序列，即1, 2, 3, 4, 5, 6,999,1000，找出该序列中的所有连续 子序列，每个子序列的和都等于1000，注意是笔算，不是说算法3.大富翁游戏，从0号位置开始，第20号位置有一颗地雷，问你安全越过这颗地雷的概率 有多少？（有一个骰子，即每次可以选16步）4.给你3个跑道，然后有N匹马，问至少要使用多少次这个跑道，我们才能对于N匹马跑步 速度的排序。后来有问我假如去掉一个跑道，算法时间复杂度是多少？5.在河面上有一些荷叶，这些荷叶上面有一只青蛙，在河里有一条鱼，这条鱼不知道这只 青蛙现在在哪里，每次这条鱼可以选择一个荷叶，从下往上越出水面，要是这只青蛙在这 片荷叶上，那么这条鱼就能吃掉这只青蛙。这只青蛙也有选择，它能感知到这条鱼要越出 睡眠（但是不知道要从哪里出来），这只青蛙能选择左右相邻的一片荷叶跳过去（不能选 择停留在原地，在最左边或者最右边的荷叶只有一种跳的选择），问你有什么策略可以待 到这只青蛙。三面： 1. f(n) = f(n - 1) + f(n - 2)问这个函数若不用任何优化，时间复杂度和空间复杂度 是多少？2. 自我介绍 class A virtual void g(); virtual void h(); int mA;class B: A virtual void g(); virtual void i(); int mB;问你，假如要你设计编译器的话，你会怎么布置A和B的内存布局3.garbage collection，让你实现这样的VM功能，你会怎么设计，会遇到什么问题？poland老外面的，人很好，但是问题也很犀利，对于你的设计，他不会鄙视，反而当你考 虑太复杂的时候会让你先从简单问题开始。会提示你，会Challenge 你，建议最后问你要问什么问题的时候，问点技术上想知道的问 题，因为他是Archetect，有这些经验，而且机会难得，他会仔细跟你讲解他的感受四面：我没有问道任何技术问题，就和他聊了一下面筋六：一面：1.try catch finally2.垃圾回收3.几种访问权限的区别4.一个数组，存了n个数，每个数在1-N，其中有两个数相等，其他都不等，找这个相等的数5.扔硬币，字为A，人头为B，得到A、B各为50%，给出一种情况，的A、B、C，使得他们都是1/3二面：1.数组和链表的区别2.接口和抽象类的区别3.中断4.虚函数5.垃圾回收6.二叉树定义7.台阶问题8.N!后有几个零9.一个数组，给定一个数X，问数组里是否存在两个是a，b，使得a+b=X三面：1.过河问题2.100个球，50红，50蓝，两个盒，把球都放进去，一个人可以随便从哪个盒子里拿球，如果他取到蓝，我就win，如果他取到红，他就赢了，如何放这些球让我win的几率更大3.烧绳问题，求1/4的时间4.接口和类的区别5.二叉树定义、中序遍历（递归）6.垃圾回收7.dom和sax区别四面：1.就聊聊微策略面试的一些常问智力题：第一题，如果有三个房间，分别有三个人，编号为1、2、3，需要你选出个子最高的人（目测就能看出来），但是有个条件，当你看完1号房间的人后，你要决定是否看2号房间的人，一旦看了，就只能选2号房以后的人，既2号或3号，同理，看完2号房，如果想看3号房，就只能选3了，问题是，使用怎样的策略可以是你选到身高最高的人的概率最大，这个概率是多少。 第二题：有两个沙漏，当把开关打开，沙漏里的沙子会从一头留到另一头里，转过来又会留回来，第一个沙漏从打开到把里面的沙子全部流入到下面花7分钟，第二个花4分钟，问如何准确度量出9分钟（注意，和两个水桶准确量出N桶水的题目不一样），我考虑了一下，答了一个结果，他说对，但不是最好，因为我没有从操作的一开始就计算时间，要我重做。想到最后也没想出来，就说sorry了，挂了电话没有五秒钟就想出来了，赶紧打电话，告诉面试官我的答案，他说，好的，我会考虑。第三题：一个钟表，3：15时，时针分针成几度，引申题目，H：M时，成几度。（测试的时候边界条件很重要）。第四题：四个人过河，分别过用1，2，5，10分钟，每次只能过两个人，同时要有人把手电筒送回来，问最短多长时间能过去，引申题目，四个人分别用时间ta，tb，tc，td，并且满足TaTbTcTd，怎么过河，这道题目比较简单。第三题，ABC-CBA=CAB，问A，B，C分别代表哪个数字，具体式子可能记错了，但是大概题目就是这样。第五题：有三种颜色的球，红色13个，绿色16个，黄色17个，有一个方法可以使球变色，拿出两个不同颜色的球，就能变成第三种颜色，如拿出一个红色，一个黄色，就会变成两个绿色的球。问有没有可能把这些球变成同一种颜色，如果可能，怎么做，如果不可能，为什么。引申，x个红球，y个绿球，z个黄球，当x，y，z满足什么关系时，一定有解决方案，否则无解。第二题，两个骰子，扔10次，至少有一次点数为12的概率是多少