MS，Google，VMWare，Nvidia 美国总部招聘面试题

给一个整数数组，其中包含重复的数字，例如1，2，4，2，5，重复的就是2。设计算法找出重复的数。
建议：Hashtable

给出一个inode，写一段代码遍历这个inode包含的所有文件及目录
建议：递归

给出随机字符组成的两个字符串，判断是否由相同的字符组成。例如abbffgg==fgbagfb
建议：Hashtable

写一迷宫探路的程序，使用多线程加快探路速度

写一个判断找出字符串中最长的对称字串。例如：ababba中最长的对称子串为abba

写一个字符串匹配的程，包括?（一个字符）和*（任意个字符）。例如：a?*bba和afbba匹配

写一个查找子串的函数。例如：实现C函数中的strstr函数

建造一座桥，如何设计，怎样测试

在地球和火星上各有一个设备，地球上发送1+1，火星上计算结果并传回地球。但是地球接到的是3，问哪些情况可能导致这个问题

Linux2.4和2.6有啥区别

spinlock和semaphore有啥区别

deadlock是咋回事

page和segment有啥区别

spinlock在linux里面如何实现，x86架构里面spinlock如何实现

在控制台打ls命令，从输入命令到屏幕上显示结果，Linux中如何是处理的，具体流程是什么

给一个没排序的整数数组和一个值，找出数组中那两个数之和等于这个值，算法复杂度

用C如何模拟C++中的class。父类和继承子类的析构函数如何实现？

给四个硬币放在四个位置1234，初始状态是正反反正，给三个操作：1.翻转第一个硬币2.把每个硬币向右移动一位。例如：
1234》4123。3.把第二，第三个银币同时翻转。问如何使用最少的操作将银币翻成反反正正。如何处理100个硬币，初始状态随机？
建议：最短路径算法，每个节点往外发三条边

排序有哪几种算法，时间，空间复杂度，稳定性，O(n)的算法

给几篇扫描的手写文章，用这些文章里的各个单词的图片拼成另一篇文章，这篇文章的内容已给出，每个图只能用一次。如果使用哈希表，如何处理哈希函数的不平衡？有的词用的很多，那么这个词在哈希表的对应位置会链上很多图片，而有的词用得少，那么在哈希表的对应位置只有很少图片。

给一个数，如何count这个数的二进制表示里面有多少个1.例如5=101，有2个1。各种算法的时间空间复杂度，在不同的CPU架构下性能比较。

如何在stack上分配内存。相对malloc在heap上分配。
建议：函数alloca

线程和进程的区别，相同进程的2个线程AB，线程A如何访问直接线程B的数据？

volatile关键字有啥意义？哪些情况使用？

SCSI设备在处理DMA时有什么要注意的地方
建议：31或32位mask

Linux系统调用如何开始
建议：中断门

网络设备处理收到的package有什么处理方式
建议：中断+poll

给8个0/1信号，和四个加法器。加法器的输入是三位信号，两位数据，一位进位。输出两位，一位数据，一位进位。例如输入数据位1，1，进位0，输出数据位0，进位1。输入数据1，0，进位1，输出数据1，进位0。
要求输出1的个数。例如输入11110000，输出0100（4）

C语言里面^号什么意思

给一个函数，里面只有一个int数组包含10个数a[0...9]，并给这个数组的每个数减4，但是减的时候给第11个数a[10]（下标溢出）也减了4，在某些架构中可能会发生什么？
建议：死循环。修改返回地址，程序在调用（call）完这个函数以后返回到call指令的地址，而不是call指令接下去的指令的地址

一个函数中有两段代码，第一段汇编使用powerpc的"add."指令，接下去一段C使用if判断某个条件是否成立，但是尽管if的条件肯定为true，有时if却判断条件不成立，为什么？
建议：add.修改condition寄存器CR0状态，if判断条件时使用同一个寄存器，编译器重排指令导致if执行时CR0的值并不是if条件计算出的值。

评论

1 楼 lordhong 2008-02-11  

太难了。。。