最新IT名企面试.doc

《最新IT名企面试.doc》由会员分享，可在线阅读，更多相关《最新IT名企面试.doc（86页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-dateIT名企面试IT名企面试微软在IT界依然是数一数二的企业了，不少人的梦想都是进入微软公司。那么在这之前的面试以及笔试就需要进行一下准备了。那么这里就来看看小编为大家总结的微软笔试题吧。微软笔试题：写程序找出二叉树的深度一个树的深度等于max（左子树深度，右子树深度）+1。可以使用递归实现。假设节点为定义为1. structNode 2. Node*left; 3. N

2、ode*right; 4. ; 5. intGetDepth(Node*root) 6. if(NULL=root) 7. return0; 8. 9. intleft_depth=GetDepth(root-left); 10. intright_depth=GetDepth(root-right); 11. returnleft_depthright_depth?left_depth+1:right_depth+1; 12. 微软笔试题：利用天平砝码，三次将140克的盐 分成50、90克两份？有一个天平，2克和7克砝码各一个。如何利用天平砝码在三次内将140克盐分成50，90克两份。第一种

3、方法：第一次:先称 7+2克盐 (相当于有三个法码2,7,9)第二次:称2+7+9=18克盐 (相当于有2,7,9,18四个法码)第三次:称7+18=x+2,得出x是23，23+9+18=50克盐.剩下就是90克了.第二种方法：1.先把140克盐分为两份，每份70克2.在把70克分为两份，每份35克3.然后把两个砝码放在天平两边，把35克面粉分成两份也放在两边（15+7=20+2）现在有四堆面粉70，35，15，20，分别组合得到70+20=9035+15=50微软笔试题：地球上有多少个满足这样条件的点站在地球上的某一点，向南走一公里，然后向东走一公里，最后向北走一公里，回到了原点。地球上有多

4、少个满足这样条件的点?北极点满足这个条件。距离南极点很近的一个圈上也满足这个条件。在这个圆圈上，向南走一公里，然后向东走一公里恰好绕南极点一圈，向北走一公里回到原点。所以地球上总共有无数点满足这个条件。或者首先，在地球表面上，南北走向是沿着经度方向，东西是沿着纬度方向。如果你一直往北走就会达到北极点，往南走就到了南极点。因此，向南走一公里，然后向东走一公里，最后向北走一公里，回到了原点，一种情况就是，出发点是在北极点，这样向南走一公里，然后向东走任意几公里，最后向北走一公里，最后都会回到北极点；其次，可以这么认为如果从A点向南走一公里到达B点，那么若向东走一公里能回到B，那么最后向北走一公里，

5、就能回到了原点A。这样就可以先找出在南北极点附近找出绕一周只有1公里的圈，那么这个圈落在南极附近时，只要往北推1公里，此时该圈上的点都能满足；若这个圈落在北极附近时，能不能往北推1公里我就不分析了。反正在南极附近能找到任意多个点就能回到这个问题了微软笔试题：正确标注水果篮有三个水果篮。其中一个里面只有苹果，一个里面只有橘子，另外一个既有苹果又有橘子。每个水果篮上都有标签，但标签都是错的。如何检查某个水果篮中的一个水果，然后正确标注每个水果篮？从标注成既有苹果也有橘子的水果篮中选取一个进行检查。如果是橘子，则此篮中只有橘子；标有橘子的水果篮中只有苹果；标有苹果的水果篮中既有苹果也有橘子。如果是苹

6、果，则此篮中只有苹果；标有苹果的水果篮中只有橘子；标有橘子的水果篮中既有苹果也有橘子。微软笔试题：不利用浮点运算，画一个圆不利用浮点运算，在屏幕上画一个圆 (x*2 + y*2 = r*2，其中 r 为正整数)。考虑到圆的对称性，我们只需考虑第一象限即可。等价于找到一条连接点（0，r）到点（r，0）的一条曲线，曲线上的点距圆心（0，0）的距离最接近 r。我们可以从点（0，r）开始，搜索右（1，r），下（0，r-1），右下（1，r-1）三个点到圆心的距离，选择距圆心距离最接近 r 的点作为下一个点。反复进行这种运算，直至到达点（r，0）。由于不能利用浮点运算，所以距离的比较只能在距离平方的基础上

7、进行。也就是比较 x*2 + y*2 和 r*2之间的差值。微软笔试题：将一个句子按单词反序将一个句子按单词反序。比如 “hi baidu com mianshiti”，反序后变为 “mianshiti com baidu hi”。可以分两步走：第一步按找字母反序，“hi baidu com mianshiti” 变为 “itihsnaim moc udiab ih”。第二部将每个单词中的字母反序，“itihsnaim moc udiab ih” 变成 “mianshiti com baidu hi”。这个方法可以在原字符串上进行，只需要几个整数变量来保持指针即可，空间复杂度低。微软笔试题：计

8、算n bit的整数中有多少bit 为1设此整数为x。方法1：让此整数除以2，如果余数为1，说明最后一位是1，统计值加1。将除得的结果进行上面运算，直到结果为0。方法2：考虑除法复杂度有些高，可以使用移位操作代替除法。将 x 和 1 进行按位与操作（x&1），如果结果为1，说明最后一位是1，统计值加1。将x 向右一位（x 1），重复上面过程，直到移位后结果为0。方法3：如果需要统计很多数字，并且内存足够大，可以考虑将每个数对应的bit为1的数量记录下来，这样每次计算只是一次查找操作。1. intn=0;while(x) 2. 3. xx=x&(x-1); 4. n+; 5. 6. returnn

9、;微软笔试题：快速求取一个整数的7倍乘法相对比较慢，所以快速的方法就是将这个乘法转换成加减法和移位操作。可以将此整数先左移三位（8）然后再减去原值：X =B时，就完成了重新排序。i指向最后一个小写字符，j寻找小写字符。1. voidswapString(char*str,intlen) 2. 3. inti=-1; 4. intj=0; 5. for(j=0;jlen;j+) 6. 7. if(strj=a) 8. 9. i+; 10. swap(stri,strj); 11. 12. 13. 谷歌笔试题：在重男轻女的国家里，男女的比例是多少？在一个重男轻女的国家里，每个家庭都想生男孩，如果他

10、们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少？还是1：1。在所有出生的第一个小孩中，男女比例是1：1；在所有出生的第二个小孩中，男女比例是1：1；. 在所有出生的第n个小孩中，男女比例还是1：1。所以总的男女比例是1：1。谷歌笔试题：如何拷贝特殊链表有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand，如何拷贝这个特殊链表？拷贝pNext指针非常容易，所以题目的难点是如何拷贝pRand指针。假设原来链表为A1 - A2 -. - An，新拷贝链表是B1 - B2 -.- Bn。为了能够快速的找到pRa

11、nd指向的节点，并把对应的关系拷贝到B中。我们可以将两个链表合并成A1 - B1 - A2 - B2 - . - An - Bn。从A1节点出发，很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx，将B1的pRand指向Bx也就完成了B1节点pRand的拷贝。依次类推。当所有节点的pRand都拷贝完成后，再将合并链表分成两个链表就可以了。1. classListNode 2. 3. intvalue; 4. ListNode*p_next; 5. ListNOde*p_rand; 6. publicListNode(intv,ListNode*next,ListNode*rand):

12、value(v),p_next(next),p_rand(rand) 7. 8. 9. ; 10. ListNode*copyList(ListNode*p) 11. 12. if(p!=null) 13. 14. /*构建交叉数组p0-q0-p1-q1-p2-q2.*/ 15. ListNOde*ppre=p; 16. ListNode*post=-next; 17. while(pre!=null) 18. 19. pre-next=newListNode(pre-value,post,pre-p_rand-p_next); 20. pre=last; 21. lastlast=last-

13、p_next; 22. 23. /*拆分成被拷贝数组和拷贝数组p0-p1-p2.;q0-q1-q2.*/ 24. ppre=p; 25. ListNode*res=p-p_next; 26. while(res-p_next!=null) 27. 28. p-p_next=res-p_next; 29. res-p_next=res-p_next-p_next; 30. 31. returnres; 32. else 33. 34. returnp; 35. 36. 如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设为常概率条件下)假设

14、10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是(1-x)3，也就是0.05。所以得到方程(1-x)3 = 0.05解方程得到x大约是0.63。谷歌笔试题：从25匹马中找出最快的3匹最少需要7次。首先将马分成a,b,c,d,e 5个组，每组5匹，每组单独比赛。然后将每组的第一名放在一起比赛。假设结果如下a0,a1,a2,a3,a4b0,b1,b2,b3,b4c0,c1,c2,c3,c4d0,d1,d2,d3,d4e0,e1,e2,e3,e4其中a, b,c,d,e小组都是按照名次排列（速度a0a1a2a3a4, b0b1.)。并第6次比赛的

15、结果为a0b0c0d0e0。那么第6次比赛结束后，我们知道最快的一匹为a0。我们知道第2名的马一定是a1或者b0，所以在接下来的比赛中要包含这两匹马。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是说第2名和第3名一定在a1，a2，b0，b1和c0当中，所以在第7场比赛中包括这5匹马就可以得到第2名和第3名。所以7次比赛就可以获得前3名的马。谷歌笔试题：设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。1. 使用数组存储。插入数字时，在O(1)时间内将该数字插入到数组最后。获取中数时，在O(n)时间内找到中数。（选数组

16、的第一个数和其它数比较，并根据比较结果的大小分成两组，那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分，直到找到中数。）2. 使用排序数组存储。插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。获得中数时，在O(1)复杂度内找到中数。3. 使用大根堆和小根堆存储。使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。获取中数时，在O(1)时间内找到中数。给定一个固定长度的数组，将递增整数序列写入这个数组。当

17、写到数组尾部时，返回数组开始重新写，并覆盖先前写过的数。请在这个特殊数组中找出给定的整数。假设数组为a0, 1, ., N-1。我们可以采用类似二分查找的策略。首先比较a0和aN/2，如果a0 缓存谷歌笔试题：给定一个排序数组，如何构造一个二叉排序树？采用递归算法。选取数组中间的一个元素作为根节点，左边的元素构造左子树，右边的节点构造有子树。谷歌笔试题：数组中是否有两个数的和为101.比较任意两个数的和是否为10。如for (int i = 0; i n; +i) for (int j = i+1; j n; +j) . 复杂度为O(n*n)。2.将数组排序后，对每个数m，使用二分查找在数组中

18、寻找10-m。复杂度为O(nlogn)。3.将数组存储到hash_set中去，对每个数m，在hash_set中寻找10-m。复杂度为O(n)。4.如果数组很大，超过内存的容量，可以按照hash(max(m, 10-m)%g，将数据分到g个小的group中。然后对每个小的group进行单独处理。复杂度为O(n)。谷歌笔试题：找到两个字符串的公共字符，并按照其中一个的排序写一函数f(a,b)，它带有两个字符串参数并返回一串字符，该字符串只包含在两个串中都有的并按照在a中的顺序。写一个版本算法复杂度O(N2)和一个O(N)O(N2)：对于a中的每个字符，遍历b中的每个字符，如果相同，则拷贝到新字符串

19、中。O(N)：首先使用b中的字符建立一个hash_map，对于a中的每个字符，检测hash_map中是否存在，如果存在则拷贝到新字符串中。给定一个整数序列，其中有些是负数，有些是正数，从该序列中找出最大和的子序列。比如：-5，20，-4，10，-18，子序列20，-4，10具有最大和26。1. intGetMaxSubArraySum(int*array,intarray_len) 2. intcurrent_sum=0; 3. intmax_sum=0; 4. for(inti=0;imax_sum) 7. max_sum=current_sum; 8. elseif(current_sum

20、0) 9. current_sum=0; 10. 11. 12. returnmax_sum; 13. 14. 15. 或者 16. 17. intmaxsum(intn,intlist) 18. 19. intret,sum=0; 20. inti; 21. for(ret=listi=0;i0?sum:0)+listi,ret=(sumret?sum:ret); 23. returnret; 24. 谷歌笔试题：海盗分金问题有5个海盗，按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决，如果多数（所有人中的多数）反对，那他就会被杀死。他应该提出怎样的方案，

21、既让自己拿到尽可能多的金币又不会被杀死？分配方案是98，0，1，0，1。5级海盗会不会被杀死，取决于5级海盗死后其他海盗是否会获得更多的利益。如果可以获得更多的利益，则肯定会反对，如果会获得更少的利益，则肯定会支持，如果利益没有变化，则反对或支持都可以。如果5级海盗死了，则有4级海盗分配，4级海盗面临同样的问题，需要看自己死后的利益分配变化。然后是3级海盗，2级海盗。2级海盗无论提出什么方案，都不会有多数人反对（自己支持，另一个人反对不能构成多数反对）。所以2级海盗肯定会提出100，0的分配方案，自己独享所有金币。猜到2级海盗的分配方案后，3级海盗会提出99，0，1的分配方案。这样1级海盗因获

22、得了比2级海盗方案中更多的金币，所以会支持3级海盗的方案。猜到3级海盗的分配方案后，4级海盗会提出99，0，1，0的分配方案。这样2级海盗获得了比3级海盗方案中更多的金币，所以会支持4级海盗的方案。猜到4级海盗的分配方案后，5级海盗会提出98，0，1，0，1的分配方案。这样1级海盗和3级海盗获得了比4级海盗方案中更多的金币，所以会支持5级海盗的方案。谷歌笔试题：4人过桥问题4 个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分钟的手电筒。通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。这四个人过索桥的速度都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三

23、个5分钟，最慢的那个要10分钟。他们怎样才能在17分钟内全部走过索桥？1）第一个和第二个一起过去，用掉2分钟；2）第一个回来，用掉1分钟；3）第三个和第四个一起过去，用掉10分钟；4）第二个回来，用掉2分钟；5）第一个和第二个一起过去，用掉2分钟。总共用掉17分钟。谷歌笔试题：如何从8只球中找出比较重的一个你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅称两次将那个重一些的球找出来。解答：先取6个，天平上一边3个，同重则称剩余2个即可；不同重，则取重的3个中的2个来称。分析：此题可以通过倒推法来解决。如果我们知道重球在某两个球中，则可以通过天平两边各放一个，比较重量

24、发现重球。如果我们知道重球在某三个球中，则可以通过天平两边各放一个，如果一样重，则第三个球是重球，否则天平上较重的即是重球。如果我们知道重球在大于等于四个球中，则不能通过一次称重发现重球。所以通过第一次称重，我们必须将重球限定在某两个或三个球当中。另外，天平两端放的球数应该相等，否则结果基本没有意义。满足两端球相等的所有可能的比较方法左，右1， 12， 23， 34， 4再考虑到必须将重球限定在2或3个球中，第一次只能采取3，3的比较方法。此题还可以扩展一下：在m只大小相同的球中，m-1只重量相同，另外一只比较重。问需要用天平称多少次才能将重球找出来？从上面的分析中可以知道，称一次最多可以-

25、将重球从3个球中找出来。- 将重球从9个球中限定在3个球中。- 将重球从27个球中限定在9个球中。.所以，称n次最多可以将重球从3n中找出来。倒推回去也就可以获得m个球需要称多少次。或者我们用i+表示第i个球比较重。共有8种可能性：1+; 2+; 3+; 4+; 5+; 6+; 7+; 8+;将1 2 3 与4 5 6 放在天秤上称，如果左边中，则可以将重球确定在1 2 3中，即可能性为：1+ 2+ 3+ 然后将1和2放在天秤两边称，如果左边重则重球为1，如果右边重，重球为2，如果平衡重球为3。如果平衡：7+ 8+ 将7和8放在天秤两边称，可以判断重球为7还是8如果右边重：4+ 5+ 6+ 同

26、球1 2 3的情况。雅虎笔试题 21. (单选)ATM网络采用固定长厦的信元传送数据，信元长度为2ATM是Asynchronous Transfer Mode（ATM）异步传输模式, ATM是在LAN或WAN上传送声音、视频图像和数据的宽带技术。它是一项信元中继技术，数据分组大小固定。ATM采用面向连接的传输方式，将数据分割成固定长度的信元，通过虚连接进行交换。1. 1024B 2. 53B 3. 128B 4. 64B雅虎笔试题 22. (单选)TCP/IP参考模型中的主机-网络层对应于OSI RM中的41. 网络层 2. 物理层 3. 数据链路层 4. 物理层与数据链路层雅虎笔试题 23.

27、 (单选)计算机网络最突出的优点是：41. 计算精度高 2. 内存容量大 3. 运算速度快 4. 连网的计算机能够相互共享资源雅虎笔试题 24. (单选)计算机网络分为局域网、城域网与广域网，其划分的依据是：21. 数据传输所使用的介质 2. 网络的作用范围 3. 网络的控制方式 4. 网络的拓扑结构雅虎笔试题 25. (单选)用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较多少次？31. 5 2. 2 3. 4 4. 1 雅虎笔试题 31. (单选)根据线程安全的相关知识，分析以下代码，当调用test方法时i10时是否会引起死锁?21. public void tes

28、t(int i) 2. 3. lock(this) 4. 5. if (i10) 6. 7. i-; 8. test(i); 9. 10. 11. 1. 会锁死2. 不会锁死雅虎笔试题 32. (单选)以下描述错误的是（）31. 在C+中支持抽象类而在C#中不支持抽象类。2. C+中可在头文件中声明类的成员而在CPP文件中定义类的成员，在C#中没有头文件并且在同一处声明和定义类的成员。3. 在C#中可使用 new 修饰符显式隐藏从基类继承的成员。4. 在C#中要在派生类中重新定义基类的虚函数必须在前面加Override。雅虎笔试题 33. (单选)1. intmyArray3=newint3n

29、ewint35,6,2,newint56,9,7,8,3,newint23,2;myArray322的值是（）。41. 9 2. 2 3. 6 4. 越界雅虎笔试题 34. (单选)在C#中利用Socket进行网络通信编程的一般步骤是：建立Socket侦听、（ ）、利用Socket接收和发送数据。41. 建立Socket连接 2. 获得端口号；3. 获得IP地址； 4. 获得主机名；雅虎笔试题 35. (单选)如果设treeView1=new TreeView(),TreeNode node=new TreeNode(根结点 )，则treeView1.Nodes.Add(node)返回的是一个

30、 ()类型的值。21. TreeNode； 2. int； 3. string； 4. TreeView；雅虎笔试题 36. (单选)声明一个委托public delegate int myCallBack(int x); 则用该委托产生的回调方法的原型应该是21. void myCallBack(int x) 2. int receive(int num)3. string receive(int x) 4. 不确定的雅虎笔试题 37. (单选)关于ASP.NET中的代码隐藏文件的描述正确的是11. Web窗体页的程序的逻辑由代码组成，这些代码的创建用于与窗体交互。编程逻辑唯一与用户界面不同

31、的文件中。该文件称作为“代码隐藏”文件，如果用C创建，该文件2. 项目中所有Web窗体页的代码隐藏文件都被编译成.EXE文件3. 项目中所有的Web窗体页的代码隐藏文件都被编译成项目动态链接库（.dll）文件4. 以上都不正确雅虎笔试题 38. (单选)What compiler switch creates an xml file from the xml comments in the files in anassembly?21. /text 2. /doc 3. /xml 4. /help雅虎笔试题 39. (单选)下面的代码实现了设计模式中的什么模式31. Factory 2. Ab

32、stract Factory 3. Singleton 4. Builder雅虎笔试题 40. (单选)1. class Class1public static int Count = 0;static Class1()Count+;public Class1()Count+;Class1 o1 = new Class1();Class1 o2 = new Class1();请问，Class1.Count的值是多少？(3)1. 1 2. 2 3. 3 4. 4雅虎笔试题 41. (单选)1. abstract class BaseClasspublic virtual void MethodA

33、()Console.WriteLine(BaseClass);public virtual void MethodB()class Class1: BaseClasspublic void MethodA()Console.WriteLine(Class1);public override void MethodB()class Class2: Class1new public void MethodB()class MainClasspublic static void Main(string args)Class2 o = new Class2();o.MethodA(); 请问，此程序输

34、出结果是:31. BaseClass 2. BassClass Class13. Class1 4. Class1 BassClass雅虎笔试题 42. (单选)11. public static void Main(string args)int i = 2000;object o = i;i = 2001;int j =(int) o;Console.WriteLine(i=0,o=1, j=2,i,o,j);1. i=2001,o=2000,j=2000 2. i=2001,o=2001,j=2001 3. i=2000,o=2001,j=2000 4. i=2001,o=2000,j=2001雅虎笔试题 43. (多选)您要创建ASP.NET应用程序用于运行AllWin公司内部的Web站点，这个应用程序包含了50个页面。您想要配置这个应用程序以便当发生一个HTTP代码错误时它可以显示一个自定义的错误页面给用户。您想要花最小的代价完成这些目标，您应该怎么做？(多选)141. 在这个应用程序的Global.asax文件