一 : 微软面试题：5个海盗分100枚金币
微软面试题：5个海盗分100枚金币
二 : 死理性派教你做微软面试题
经常能在网上看到各种不知真假，却被转烂了的“超变态但很经典的微软面试题”。那微软这样的大公司，到底有多喜欢“蹂躏”面试者的智商呢？本文就从一套广为流传的的“10个最著名微软面试题”中选取了几个最经典的，来和它们较量较量。
闲话少叙，解题吧。
你的丈夫有外遇吗一座小镇里有100对夫妇，他们都遵守一个奇怪的风俗：如果妻子发现丈夫背叛了她，那她就会在当天夜里杀死自己的丈夫。小镇里的女人都知道别人丈夫的秘密，却不会说出来。换言之，每个女人只知道除自己丈夫之外其他男人的外遇情况。突然有一天镇长宣布，至少有一个男人背叛了他的妻子，假设镇长说的是真话，所有人都相信镇长所说的，那么接下来将会发生什么？
我们不妨先假设只有1个男人背叛了他的妻子，这时那个男人的妻子会猛然发现自己竟然不知道任何男人有外遇的消息（而其他99个女人知道的都是1个男人背叛了自己的妻子，即真相），对此唯一的解释便是有且只有一个有外遇的男人，就是自己的丈夫。所以她会在当天夜里杀死自己的丈夫。然后，没有然后了。
那如果有2个男人呢？这时小镇里有98个女人知道真相，但另外2个女人只知道1个男人有外遇，并不能确定自己的丈夫是否也有外遇。所以在镇长宣布此事的当天，全镇相安无事。但到了第2天，当这2个女人发现对方都未处死自己的老公时，就会意识到不止一个男人有外遇了。那便是有2个男人有外遇，这样的话，其中1个肯定是自己的丈夫。于是，这2个女人会同时在夜里处死自己的丈夫。
以此类推，很容易归纳出来，如果小镇里有n个不忠的丈夫，他们都会在镇长宣布后的第n天夜里被处死。
实际上，有时候虽然只有极少量的信息，但只要仔细分析，一样可以得出有效的结论。上述这个谜题相信有很多人见过，类似的还有著名的 蓝眼睛岛问题 ，只是这个更加复杂一点。
隔离监狱中的100个犯人在一所监狱中，关押了100个相互隔离的犯人。典狱长每天随机选择一名犯人（他可能被重复选中多次），扔到一间小黑屋中关禁闭。这个房间中只有一个电灯和开关，除了小黑屋中的人，谁都看不到这盏灯，更无法控制它。关进去的人则可以打开或关闭电灯，也可以选择什么都不干。犯人们随时可以叫停这场游戏并告诉典狱长：“所有犯人都被关过小黑屋。”如果这句话是真的，所有犯人将会被释放；但如果这句话是假的，他们全部会被处死。在游戏开始前，犯人们被允许聚在一起商议对策，他们该怎么做才能保证自己一定能够被释放呢？
首先我们随意选择一个犯人A作为计数者。
现在让除了A以外的任何一个犯人进入小黑屋后，都将严格遵循下面这个法则：
如果他以前从来没有打开过这盏电灯，并且现在这盏电灯是关着的，那么打开它，除此以外不作任何事情。而如果典狱长选择的是A，并且当他进入这个房间以后房间里的电灯是开着的，那么他就把电灯关掉，并在自己的计数里加1。当他的计数达到99之日（从1开始），便是所有犯人重获自由之时。
工作分金问题有个工人将为你工作七天，你用一块金条来支付工资。每天工作结束以后你都要给工人发工资，但你只能在这块金条上折两次。应该如何选择金条上的折断位置，以及支付工资的方法？
这个问题并不困难，但如果工人为你工作X天，你该怎么分割这块金条呢？
让我们先来回答最初的问题，为读者做个启发。把金条分成如下三份：第一份是原金条的 1／7（编号为1号金条）；第二份是原金条的 2／7（2号金条）；第三份是 4／7（3号金条）。接下来的7天你将这样支付工资：
第1天：给工人1号金条（此时你有2号和3号金条，工人有1号金条）第2天：给工人2号金条，并取回1号金条（此时你有1号和3号金条，工人有2号金条）第3天：给工人1号金条（此时你有3号金条，工人有1号和2号金条）第4天：给工人3号金条，并取回1号和2号金条（此时你有1号和2号金条，工人有3号金条）第5天：给工人1号金条（此时你有2号金条，工人有1号和3号金条）第6天：给工人2号金条，并取回1号金条（此时你有1号金条，工人有2号和3号金条）第7天：给工人1号金条，事成收工。
有过一些编程经验的读者可能会马上意识到，这其实正是二进制的原理。 1，2，4 三个十进制数的二进制形式分别是 1，10，100，用这三个数可以表示 [0，7] 区间（换成二进制形式即 [000，111] 区间）里的所有整数。
同样的道理可以计算出，如果有工人为你工作X天，而你依然打算用一块金条来支付工资的话，那么最少需要在金条上折断（ log 2 [X+1] - 1 ） 处。
寻找次品
你有10只装满了球的盒子，其中有一只盒子里装的是次品。已知正常的球每个重 10g，而次品球每个重 9g。如何只使用一次电子秤，就找出哪只盒子装的是次品？
我们在面对这类称重找次品的问题时，第一想法通常是从每个盒子中拿出一个球来称重。然而，这道题的关键恰恰是从不同的盒子里取出不同数目的球。
我们先把 10 只盒子从 0 到 9 编号，然后从每只盒子中取出与这只盒子编号数目相等的球来，举例来说，0号盒子里不需要取球， 1 号盒子里拿出 1 只球， 2 号盒子里拿出 2 只球，等等。
然后我们这些球一起放到电子秤上。假如所有的球都是正品，那么电子秤上的读数应该是450g；但是因为这堆球里可能有次品，所以实际读数是 ( 450 - x )g ，其中x是次品球的个数，同时这个个数又恰好次品盒子的编号。
过桥问题四个人需要在夜间度过一座摇摇晃晃的吊桥。不幸的是，他们只有一个火把，而这座桥又太危险了，他们无法在不借助火把的情况下度过这座危桥。而更不幸的是，这座桥又不怎么结实，最多允许两个人同时度桥。四个人过桥的速度各不相同，分别是：1分钟，2分钟，7分钟，10分钟。显然，两人同时度桥，耗时就取决于最慢的人。那么，他们全部度过这座桥所需的时间最短是多少？
大部分人的第一想法往往是利用一个最快的人反复度桥来接送其他人，这样需要的时间是 2 + 1 + 7 + 1 + 10 = 21 分钟。的确很快，但是实际上还有更快的方法。
很容易想到的是，我们应该能让 7 和 10 一起过桥。但是接下来呢？难道让其中1个人再回去一趟吗？不，这样的话就太耗时了。如何解决这个问题呢？我们可以提前让1个脚程较快的家伙在桥的对岸等着。因此就有方案如下：
先让 1 和 2 一起过桥。耗时2分钟。让 1 拿着火把回来。耗时1分钟。让 7 和 10 一起过桥，耗时10分钟。让 2 拿着火把回来。耗时2分钟。最后再让 1 和 2 一起过桥。耗时2分钟。最后总耗时为 2 + 1 + 10 + 2 + 2 = 17 分钟。表针问题
一天中时钟的时针和分针重叠几次？
直觉也许会告诉你24次，但事实并非如此，我们不妨来算一下。
当分针和时针从 12：00 处开始走动后，T个小时的时间里时钟的分针走T圈，时针则是 T／12 圈，两个表针第一次重合的时候分针比时针领先整整一圈，也就是 T = T／12 + 1 ，此时 T = 12／11 ，也就是表针在 12／11 时（比 1：05 稍微晚一些）第一次重叠。把重叠的次数换成N，然后把式子中的T换成24，我们就可以得到：
24=2+N显然，N=22
即两个表针在一天内重叠22次。它们从来不会在上午或者下午的11点重合，因为它们要同时到达表盘的12点方向。
看到这里，各位读者是对打进微软内部更有把握了呢？
本文改编自：MY TECH INTERVIEWS。原文点 这里
三 : 微软面试题汇总
1、有一个整数数组，请求出两两之差绝对值最小的值，记住，只要得出最小值即可，不需要求出是哪两个数。［www.61k.com)
View Code
1 using System;
2 using System.Linq;
3 using System.Collections.Generic;
4 namespace ConsoleApplication1
5 {
6 class Program
7 {
8 static Random Rand = new Random();
9
10 static void Main(string[] args)
11 {
12 int count = 10000;
13 List<int> Input = new List<int>();
14 // for (int i = 0; i < count; i++)
15 // {
16 // Input.Add(Rand.Next(int.MinValue, int.MaxValue));
17 // }
18 Input.Add(1); Input.Add(2); Input.Add(3); Input.Add(4); Input.Add(5); Input.Add(19);
19
20 ulong re = PigeonNest(Input, ulong.MaxValue);
21 Console.WriteLine(re);
22 Console.WriteLine(ulong.MaxValue);
23 Console.WriteLine(Input.Min());
24 }
25
26 //鸽巢原理。
27 static ulong PigeonNest(List<int> List, ulong MinResult)
28 {
29 switch (List.Count)
30 {
31 case 0:
32 case 1:
33 return MinResult;
34 case 2:
35 return ABS(List[0], List[1]);
36 default:
37 break;
38 }
39 int min = List.Min();
40 //确定桶的大小。
41 int width = (int)Math.Ceiling((double)(List.Max() - min) / List.Count);
42 //不可能比1还小了。
43 if (width == 1) { return 1ul; }
44 //把数据丢到桶里。
45 Dictionary<int, NumbersInfo> EachNestNum = new Dictionary<int, NumbersInfo>();
46 foreach (int n in List)
47 {
48 int Key = Convert.ToInt32(Math.Ceiling((double)(n - min) / width));
49 if (!EachNestNum.ContainsKey(Key))
50 {
51 EachNestNum.Add(Key, new NumbersInfo(Key));
52 }
53 EachNestNum[Key].Add(n);
54 }
55 //找到所有桶里，和相邻两桶的最大最小值距离，三个数中最近的。
56 foreach (int Key in EachNestNum.Keys)
57 {
58 MinResult = Min(MinResult, EachNestNum[Key].minresult(EachNestNum, MinResult));
59 }
60 return MinResult;
61 }
62 class NumbersInfo
63 {
64 public NumbersInfo(int k)
65 { key = k; }
66 private List<int> List = new List<int>();
67 private int key;
68 public int max = int.MinValue;
69 public int min = int.MaxValue;
70 public int count { get { return List.Count; } }
71 public ulong minresult(Dictionary<int, NumbersInfo> EachNestNum, ulong re)
72 {
73 //在三个数中选最小的。
74 //当命中数大于1的时候，递归这个过程。由于迅速收敛，故复杂度忽略不计。
75 if (List.Count > 1)
76 {
77 re = PigeonNest(List, re);
78 }
79 if (EachNestNum.ContainsKey(key - 1))
80 {
81 re = Min(ABS(EachNestNum[key].min, EachNestNum[key - 1].max), re);
82 }
83 if (EachNestNum.ContainsKey(key + 1))
84 {
85 re = Min(ABS(EachNestNum[key].max, EachNestNum[key + 1].min), re);
86 }
87 return re;
88 }
89 public void Add(int x)
90 {
91 List.Add(x);
92 if (x > max) { max = x; }
93 if (x < min) { min = x; }
94 }
95 }
96
97
98 static ulong ABS(int x, int y)
99 {
100 //三分。
101 switch (x.CompareTo(y))
102 {
103 case -1:
104 return (ulong)y - (ulong)x;
105 case 1:
106 return (ulong)x - (ulong)y;
107 }
108 return 0ul;
109
110 }
111
112 static ulong Min(ulong x, ulong y)
113 {
114 if (x > y) { return y; }
115 return x;
116 }
117 }
118 }
2、平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点
平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。
先把N个点按x排序。
斜率k最大值为max(斜率(point[i],point[i+1])) 0 <=i <n-2。
复杂度Nlog(N)。
以3个点为例,按照x排序后为ABC,假如3点共线,则斜率一样,假如不共线,则可以证明AB或BC中,一定有一个点的斜率大于AC,一个点的斜率小于AC。
3、写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整型的函数）
View Code
1 long strtoint(char *str,int length){
2 if(length > 1) {
3 return str[0]=='-' ? strtoint(str, length-1)*10-(str[length-1]-'0') : strtoint(str, length-1)*10+str[length-1]-'0';
4 } else {
5 return str[0]=='-' ? -1/10 : str[0]-'0';
6 }
7 }4、怎样编写一个程序，把一个有序整数数组放到二叉树中？
View Code
1 #include <iostream>
2
3 using namespace std;
4
5 typedef struct Node
6 {
7 int v;
8 struct Node *lchild;
9 struct Node *rchild;
10 }Node;
11
12 void Insert(Node *&n, int v) {
13 if (NULL == n)
14 {
15 n = (Node*)malloc(sizeof(Node));
16 n->v = v; n->lchild = n->rchild = NULL;
17 return;
18 }
19 if (v < n->v)
20 {
21 Insert(n->lchild, v);
22 }
23 else
24 {
25 Insert(n->rchild, v);
26 }
27 }
28
29 void Print(Node *r)
30 {
31 if (NULL == r)
32 {
33 return;
34 }
35 Print(r->lchild);
36 cout << r->v << endl;
37 Print(r->rchild);
38 }
39
40 Node *root = NULL;
41
42 void Print1(int a[], int low, int high)
43 {
44 if (low > high) return;
45 int mid = (low+high)/2;
46 Insert(root, mid);
47 Print1(a, low, mid-1);
48 Print1(a, mid+1, high);
49 }
50
51 int main()
52 {
53 // Node *root = NULL;
54 // for (int i = 0; i < 3; i++)
55 // {
56 // Insert(root, i);
57 // }
58
59 int a[6];
60 for (int i = 0; i < 6; i++)
61 {
62 a[i] = i;
63 }
64
65 Print1(a, 0, 5);
66
67 // Êä³ö²éÕÒ¶þ²æÊ÷
68 Print(root);
69
70 return 0;
71 }
5、怎样从顶部开始逐层打印二叉树结点数据？请编程。
View Code
1 void Print2(Node *root)
2 {
3 queue<Node*> q;
4 q.push(root);
5
6 while(!q.empty())
7 {
8 Node *t = q.front();
9 q.pop();
10 cout << t->v;
11 if (t->lchild) q.push(t->lchild);
12 if (t->rchild) q.push(t->rchild);
13 }
14 cout << endl;
15 }
6、编程实现两个正整数的除法
View Code
1 #include <iostream>
2
3 using namespace std;
4
5 int div1(const int x, const int y) {
6 int left_num = x;
7 int result = 0;
8 while (left_num >= y) {
9 int multi = 1;
10 while (y * multi <= (left_num>>1)) {
11 multi = multi << 1;
12 }
13 result += multi;
14 left_num -= y * multi;
15 }
16 return result;
17 }
18
19 int main()
20 {
21 cout << div1(11, 3) << endl;
22 return 0;
23 }
7、在排序数组中，找出给定数字的出现次数。比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
View Code
1 #include <iostream>
2
3 using namespace std;
4
5 void equal_range1(int a[], int len, int x)
6 {
7 int low=0, high=len-1;
8 int mid;
9 while (low<=high)
10 {
11 mid=(low+high)/2;
12 if (x==a[mid]) {cout << mid << endl; break;}
13 else if (x<mid) high=mid-1;
14 else low=mid+1;
15 }
16 if (low>high)
17 {
18 cout << "ûÓÐÕÒµ½" << x << endl;
19 }
20 else
21 {
22 int k=mid-1;
23 while (k>=0&&a[k]==x)
24 {
25 cout << k-- << endl;
26 }
27 k=mid+1;
28 while (k<=len-1&&a[k]==x)
29 {
30 cout << k++ << endl;
31 }
32 }
33 }
34
35 int main()
36 {
37 int a[] = {1,2,2,2,2,3,4};
38 equal_range1(a, 7, 2);
39 return 0;
40 }
8、一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。
插入排序-》最大值-最小值<=4
9、一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
View Code
1 void find1(Node *h, int value1, Node *&r)
2 {
3 if (NULL==h)
4 {
5 return;
6 }
7 if (value1 >= h->v)
8 {
9 find1(h->rchild, value1, r);
10 }
11 else
12 {
13 r=h;
14 find1(h->lchild, value1, r);
15 }
16 }
10、
四 : 微策略面试题87
面筋一：
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 < A2 > A3 < A4.....
的锯齿状数组；时间复杂度；
5. 给定一个N个整数元素的数组，元素分别为A1, A2, A3....AN，每个元素分别对应一个权重W1（小于
1的float）, W2,W3....WN, 其和为1.找出其中一个元素Ak,使所有小于Ak的元素的权重之和小于1、2，所有大于Ak的元素的权重之和>=1/2.
面筋二：
笔试分2部分
第一部分 四道问题 200分
1.acb-bca=abc(记不准了，MS是这个样子) a,b,c都是数字0-9中的一个数，求a,b,c
2.三个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加仑水,没有其他容器没有标记攻工具(这个题目以前他也出过一样的)
6 3个房间分别有3个人,怎么能遇见最高那个,原则是你可以进其中任意一间,
如果你觉得他最高就说yes,然后游戏中止,如果说no就可以去另一间要求给出策略
和概率(这个没有想得太明白 也不知道自己写的对不对)
7 64个球,一个偏重,问最少用天平称几次可以找到?(这个也是他常出的题小变了一下)
8 一个立方体 六面涂了颜色,将它分成1000个小立方体,问至少有两面涂有颜色的小立方体有多少个 9 小船过河 有两组人三个M 三个C (单词不认识hoho) 小船最多可以载两个人,原则是河一边的M的人数不能多于另一边C人数.
10 题目比较长,主要是说有个检验三个数是不是可以构成三角形的函数,每个选项中分别有四组数,问哪个选项中的几组数可以最好的检验这个函数,这个题猜的 不能确定
应该要注意什么
11 a b c
d
e f g
h
i
这9个字母分别唯一的表示1到9中的数字,且每行和每列的三个数之和为13
问c+e+g=?
面筋三：
一面
1.两个数组，从两个里面分别选出两个数，其和等于2010
2.一百层楼，两个玻璃杯，怎么找到杯子会被摔破的最低楼层.
二面
1.二叉查找树，给你两个结点，如何找他们的最近共同祖先结点；如果是二叉树，又怎样?
2.36匹马，6个跑道，怎么用最少的比赛次数，找到跑的最近的三匹马.
三面
1.virtual memory
2.逻辑地址,物理地址
3.说出你知道的排序方法,复杂度,特点比较,给出一些例子,让你选用排序算法.
4.一个数组,找出出现次数最多的数;如果数组有序,不用hashmap,怎么做,写出完整代码.
四面
1.手机上的每个数字按键下面都有三个字母(一个数字对应三个字母),给出一个数字序列,输出这个序列所代表的所有可能的字母序列,写出代码.
2.n个数字,值在范围在1~n,但其中可能有重复出现的数字,如何判断有没有重复出现的数?
3.三个房间,里面有三个人,让你选出最高的人.条件:你只能选当前房间里面的人或者你还未进过的房间里面的人.(给出你的直觉判断,不要求证明)
面筋四：
1.判断字符串是否是回文
2. 1 2 3 ... 1000 找出所有和为1000的子序列
3.层次遍历的递归写法
4.一条河，两岸各有一个城市，修一座与岸垂直的桥，如何修A、B距离最短
5.java garbage collector
6.difference between array and list
7.difference between process and thread
8.introduce your project
9.introduce 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号位置有一颗地雷，问你安全越过这颗地雷的概率 有多少？（有一个骰子，即每次可以选1~6步）
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 finally
2.垃圾回收
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，并且满足Ta<Tb<Tc<Td，怎么过河，这道题目比较简单。第三题，ABC-CBA=CAB，问A，B，C分别代表哪个数字，具体式子可能记错了，但是大概题目就是这样。
第五题：有三种颜色的球，红色13个，绿色16个，黄色17个，有一个方法可以使球变色，拿出两个不同颜色的球，就能变成第三种颜色，如拿出一个红色，一个黄色，就会变成两个绿色的球。问有没有可能把这些球变成同一种颜色，如果可能，怎么做，如果不可能，为什么。引申，x个红球，y个绿球，z个黄球，当x，y，z满足什么关系时，一定有解决方案，否则无解。第二题，两个骰子，扔10次，至少有一次点数为12的概率是多少，引申，M个骰子，扔N次，至少有一次点数为6*M的概率是多少。
微策略面试题87_微策略
其它：
1、英文写作，童年中最美好的记忆。
2、已序双向有序链表插入，要求保持已序
3、find M 长和N 长字符串中的common letters <o(M*N)
4、奇数个整数N 个，只有一个数重复odd 次，其他的重复even，找出那个odd 次的整数
5、建立一个data structure 表示没有括号的表达式，而且找出所有等价（equivalent）的
表达式
3×5 == 5×3 2+3 == 3+2
6、N Queue 问题
五 : 微软应聘面试试题大家谈
名牌有名牌的理由，就连招聘也与众不同。微软公司的招聘一向都是人们议论的话题，说它百般刁难的有之，说它独出机杼的有之。在这里笔者试着把微软在招聘过程中所用过的几则试题拿出来让大家发表意见，看看这些考题究竟想考察应聘者什么样的素质。
一般来说，微软的面试问题分为４类：谜语类试题、数学型试题、智力性试题、应用程序类试题。先举两个谜语类试题：
１、美国有多少辆汽车？
２、将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁？
小张（复旦大学管理学院９９级学生）：这两道试题并不难，我想他可能只是想考察一下应聘者的应变能力，亦即在短时间内快速应对不规范问题的能力。
孙先生（某大型跨国企业员工）：很明显，这是两道答案开放的试题。我想它是为了考察应聘者能否对一个问题进行符合逻辑的创造性的思考，并迅速通过这种思考寻求到解决问题的办法。至于答案，发问者显然并不关心。
裘副教授（复旦大学）：问题是开放性的，但指向性也很明显。应聘者是否能在很短的时间对出其不意的问题作出反应，并能够有逻辑地回答这样的问题，发问者同样希望能够得到出其不意的答案。有不少人通过在网上搜集这种试题来准备答案，显然大违发问者的本意。重复的答案都不是好答案。
下面是两道数学型的试题：
１、１０００ 有几位数，为什么？
２、编一个程序求质数的和，例如ｆ ７ ＝１＋３＋５＋７＋１１＋１３＋１７＝５８。
小陆（复旦大学物理系９９级学生）：数学试题与应用程序试题是微软面试中指向性最明显的一类试题。这些试题就是考察应聘者的数学能力与计算机能力。
师女士（某咨询公司高级顾问）：微软是一家电脑软件公司，当然要求其员工有一定的计算机和数学能力，面试中自然就会考察这类能力。微软的上述面试题目就考察了应聘人员对基础知识的掌握程度、对基础知识的应用能力，甚至暗含了对计算机基本原理的考察。所以，这样的面试题目的确很“毒辣”，足以筛选到合适的人。
下面是智力题：
１、烧一根不均匀的绳需用一个小时，如何用它来判断半个小时？
小何（复旦大学计算机系００级硕士研究生）：我觉得我很难理解微软这一部分的试题，我大多数时候并不知道他考察我什么，有时候我甚至觉得它仅仅是脑筋急转弯。不过，我记得李开复在央视的节目里说过，他们的考察内容是应聘者的可塑性。
石先生（某大型国企职工）：我认为这一部分的问题有很大的随意性，主要是考察应聘者的智商，但是因为问题的不同又有不同的考察方向，比如第一个问题就考察了应聘者的逆向思维能力，第二个就考察了应聘者的观察能力与细致程度。
于先生（某外资公司人事主管）：我不知道微软出这些题目的用意，但在我看来，智力题是微软面试中最好的考察方式。不仅考察的指向不同，就连问题的答案有时候也能给人以启发。比如上述第二个问题，如果你能找到答案，它就会帮你理解企业的资源使用组合方式，经过优化以后可以发挥不同的作用。不同的管理者就会使用不同的组合方式，当然结果就会不一样！
本文标题：微软面试题-微软面试题：5个海盗分100枚金币61阅读| 精彩专题| 最新文章| 热门文章| 苏ICP备13036349号-1