EMC面试题
1、两个人往圆桌上放硬币，最后谁没有地方放，谁就为输家。你先放，请问有致胜方法吗？
先放在圆心处。
2、有两堆东西，一份有4个、一份有7个，两个人开始拿东西，一次可拿任意多个，但只能从一份中拿。现规定：如果最后剩下1个，而且轮到谁拿谁就输了，现在你先拿，请问有致胜方法吗？
在7个中拿2个，
3、打开一个网站的整个传输流程
以下是程序设计，用C/C++
1、请你实现一个交换数值类型变量的函数；（2）如果不用中间变量如何实现；（3）不用中间变量的交换算法的最好解决是什么？
2、C++语法问题
3、汉诺塔完成时的移动次数；如果移动时必须通过中介柱子，移动次数又是多少？
4、手机上的每个数字对应几个字母，给你一串数字，请你输出所有可能的字母串。要求是最好的算法
5、如果给我一个项目,去解决上海heavy traffic的问题,我会怎么去解决?
6、怎么反转一个链表
7、地上有很多硬币,有很多机器人在处理硬币,如果是反面,就把硬币翻转;如果是正面就随机抛一下,一直进行下去,问最后地上硬币正反面的比例如何。
8、一个字符串里的字符,由小写改成大写
(1)关于操作系统中cache的管理。规则是先舍弃使用次数最多的cache块。共有大约1000块cache。要求设计一个数据结构来支持以下操作，以使每种操作都能达到o(1)的时间复杂度。（n表示正在使用的cache块，N表示cache的数量）
1.n
2.访问cache，包括访问后的调整。
3.n=N时，需要使用一个cache。
(2)这个是笔试时的题目，我没搞定。
比较S1和S2的大小：
S1 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ......
S2 = 根号（10/16）
下面是在提示下做出来的题目：
(1)一个N*N的对称矩阵，每行每列都是数字1~N的一种全排列。例如：
1 2 1 2 3
2 1 2 3 1
3 1 2
注意，3*3矩阵的一条对角线也是1、2、3的一个全排列，而2*2的矩阵则不是。请问，什么样的N，能使N*N的矩阵在满足题目条件的情况下必然有一条对角线是1~N的一个全排列。
A.3的幂
B.奇数
C.除了2以外的质数
D.N=3
E.以上全对
1. 有一个村庄，村庄里各户人家直到生出女孩来就不再生小孩了，而生男孩女孩的概率各是1/2。请问这个村庄男孩女孩的比例是多少
a. 2:3
b. 3:2
c. 1:1
d. 2:1
e. 1:2
2. 有一家人，老公、老婆、儿子还有老公的妈妈，其中有
一个是律师，一个是医生
如果医生比律师年轻，则医生与律师没有血缘关系
如果医生的女的，那么医生和律师有血缘关系
如果律师是男的，医生也是男的
请问我们能确定这家人里的那一个人
a. 老公是医生
b. 老婆是医生
c. 儿子是医生
d. 老公的妈妈是医生
e. 以上都不对
3. 实验室里有1000个一模一样的瓶子，但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话，会在一个星期的时候死去，其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药
a. 9
b. 10
c. 32
d. 999
e. 以上都不对
4. 有ABCDEF六个城市，每一个城市都和其他所有城市直接相连，问从A——B有多少种连接方式。路径不允许在两个城市之间往返。（这题的选项可能有的数记错了）
a. 78
b. 84
c. 65
d. 43
e. 以上都不对
然后说一下读程序题。就程序本身来说都是很简单的程序，基本学过C语言的话，读懂语句应该没有问题的。有好几道都是算数列的，还有几道是 char 型数组，还有算循环次数的题目。只有两道题记得比较清楚，题目都是以程序形式给出的，我就把程序的大概意思按照我的理解写出来，可能有错，所以仅供参考。
1. 菲波那契数列 1,1,2,3,5,8,13……的第40位除以第39位得多少？即，N40/N39=？
a. 1.666666
b. 1.618xxx(后面几位记不清了)
c. 1.600000
d. 以上都不对
2. 数列 0,1,3,6,10,15,21……从a0加到a10000得多少？
a. 50005000
b. 50000000
c. 49995000
d. 50000
e. 以上都不对
计算机基础知识的题目也不少，主要考点有B-tree，冒泡排序，堆栈，dual-link和单向link，小数点后的数十进制到二进制的转化，ox进制，按位异或，C 和C++ 的 struct有什么区别，什么样的排序算法效率高，什么样的排序算法节省空间，还有一些网络存储磁盘阵列的很基础的题目。都不难，只可惜没学过什么，或者说学了都忘了，所以就凭感觉了，看那个选项顺眼就选那个。
第二部分的编程题是要把N5 ->N4 ->N3 ->N2 ->N1的序列用一种自己熟悉的编程语言转化成N1 ->N2 ->N3 ->N4 ->N5。看起来是要用到指针的，由于我都忘干净了，所以啥也没写。
差不多客观题就这些了，不是特别难，也不简单
全部
用英文，试卷纸，答卷纸；解答也要求用英文。
一共4大题：
一、单选（选对1分，选错倒扣0.25，不选0分），一共26题，每题5个选项
1，问能用8位二进制数的最小的10进制数
2，10101010101写成10进制和16进制分别是多少
3，数列题，16进制，0x64,0x190,0x384,0x640,0x9C4
4，数列题，16进制，0x1,0x8,0x1B,0x40,0x7D
5，因式分解，9x^2-49
6，7 概率题，说3个人，每人一个口袋，里面4个球，1red，3blue
然后就是拿球的概率，超简单，都是乘法定律。
8，问int **a[10]; 的意思
9，问int *(*a)[10];
10, int (*a[10])();
11－13 问的是replace算法，给出了5个进程，和他们的loaded，last accessed的时间
问下列算法，会替换哪个进程
11， NRU
12， FIFO
13， LRU
14，6个driver，n个process，每个process需要2个driver，问which n, deadlock
free in the best case
选项记不清了，好像n＝3，n<=3, n<6, n = 6，none of above
15 64^(2/3)
16 问N个noodles，每次找两个ends，连起来，直到no ends，问expacted number of
loops
17 一段C程序，主要考察const char*, const
18 一大段话，选True or False，进程调度，有关priority inversion
19 common solution to avoid priority inversion
20 很简单的C程序，问result
21 还是C程序，主要问sizeof()
22 C程序，问常量定义和函数调用中的print("%d",__LINE__);
23，24 C程序，考察 N1 >>= 1 和 N2 = (n1 & 1)
25, 26 也是很简单的C程序，选择题
二、information question,两道选择，EMC的R&D center at Beijing and Shanghai，
1，你首选工作地点：（ft，－Shanghai）
2，second choice（ft again，－Beijing）
三、Bonus question，下个C/C 的函数
从单链表中找到一个cycle
四、简答，in English
starvtion 和 deadlock 的异同
第一个部分叫客观题。就是32道选择题。基本都是靠C程序的。感觉就是那些大一考的很搞脑子的算法。有道题目算到最后发觉就是在算10！。但是手头没有计算机，所以阶乘也得手算。虽然只有10个数字，但阶乘毕竟是阶乘。有道题目看完算法就知道是在算1+……+10000。可是怎么算等差数列的和已经忘记了。好在记得可以换算成5000个10001相加。于是也有了答案。
有几道题目考排序算法。问你当碰到最坏情况序列的时候用哪个排序算法有最快速度，问你如果考虑最佳空间使用率你会使用以下什么排序算法。这个时候我才发觉数据结构原来还是有用的，虽然考试的时候那些个算法都滚瓜烂熟，但现在屁也想不出来。只好空着不做。因为做对1题给1分，不做1题给0分，但做错1题扣1/4分。每道
题目有5个选项，命中率是1/5，比1/4小。所以如果你5个选项里没有一个能确定那就别选。如果你能排除一个选项，那你可以拼一下去选剩下的4个之一。如果你能确定答案在2个选项之中，那就一定要选。这道题50%拿1分，也就是0.5分，50%扣1/4分，总体来说是赚的。顺便说下，所有的题目都用E文写的。所以当看到32题给的数字方阵很喜欢，但题目中几个关键字都是术语，看不明白的时候。只有痛苦的放弃这1分了。
有很大篇幅的题目都在算二、八、十、十六进制。还好着方面是我的强项。这4个进制中间无论怎么换，我都是很在行的。那时学的比较买力。所以基本上考到进制问题的时候，都能在2分钟内解决题目。下面来说说题目中有点意思的东西。
问:给个X，那么我们用X2代表X的平方。举例说，X=110（2进制），也就是十进制6。那X2=100100。也就是36。注意X本来最后是一个0，X2最后是2个0。问以下哪个正确——任意X2最后都是00、任意X2最后都是00、10、11、01其中之一还有些乱七八糟的答案。最后一个答案是以上都不是。我选了它。
十进制数结尾也就是0~9这10个数字。这些个数字的平方取最低位，得到0、1、4、5、6、9。这些数字的二进制最后2位只可能是00、10或01。而没有这个答案。所以只好选了最最不像答案的以上都不是。
问：有个地方喜欢女孩。每对父母都会尽力生小孩，直到他们生出第一个女孩为止。如果生男生女概率是50%的话，问你这个地方的男女比例会是多少。
乍看之下，觉得这些个题目一定是EMC在美国笔试用的。而在美国，题目一定是有个地方喜欢生男孩……。到了中国要适合国情，避下嫌，所以改女孩了。回过来说题目。我也不知道正确答案是什么。但直觉告诉我是1：1。于是找了个理由说服自己选1：1——假设有对父母生了10个小孩，前9个是男的，最后一个女的。那我们就给前9个男孩每人找个虚拟的父母，这样一来，所有的父母就只会有1个小孩，大体上来说他们就是遵循50%的概率了。那比例自然是1：1了。不知道这个理由算不算正常，不过当时是说服我自己了，于是选了1：1。
问：有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。
选项是9只、10只、32只、999只、以上都不是。
我先想9只，但是无论怎么都考虑不出这个方案。然后想10只，突然想到可以把100桶酒放到1起，让1只老鼠吃，那就只要10只。但怎么分别这100桶里面哪桶呢？于是直觉告诉我答案是32。很快的在草稿纸上算了2个乘
法。31*31=961 32*32=1024。就更加确定是32了。为什么呢？我不知道。当时只想了那么多，32的平方是大于1000而最小的整数。一直到昨天晚上，哦不，是今天凌晨我躺在床上后，我给出了选32的理由（睡觉和厕所一直给我灵感）——
如果有N*N桶酒，那么我们把这N*N桶酒放置成一个N*N方阵。选N只老鼠，让每只老鼠老鼠任选1行和1列，把所有的酒给它吃。当然只喝一滴就可以了。N只老鼠都选不同的行和列喝。然后结果你们自己想吧。因为我想到这里，觉得选32没错了，不用浪费脑细胞了，于是没有继续想。剩下的999当然能1下就确定出毒酒，但绝对不是最少的方案。“以上都不是”看上去就不会选。所以答案就是32了。
考试的第2个部分叫主观题。4道选择加2个简答。
4道选择是：1.本次我们提供了2个职位，你愿意哪个作为第一志愿？（我选R&D software engineer）2.你愿意选这2个职位中哪个为第二志愿？（上帝，就这么浪费题目的啊，选剩下的technology solution associate）3.你愿意在以下哪个城市工作？（上海）4.愿意培训中心给你来信么？（傻瓜才不愿意。哦，没这个选项，我选愿意。）
2个简答题是：单链表倒序程序，你的5年发展计划（E文回答）。
单链表倒序，呵呵，似曾相识。在英华达是作为可选题目出的。在这里成了大题。似乎软件公司热中于这个算法。简单，又有复杂逻辑顺序。算法是老早就忘记的了，还好脑子比较好使，最后还是写出来了，有没有BUG就等他们去测试了。
5年发展计划，在中芝问的是3年计划。所以我去EMC之前准备的是3年计划，最后2年就随便撑了点东西。等考试出来，再回想自己写过什么的时候，发觉写的都是废话，BULL SHIT！好吧，反正都写了，看运气吧。觉得自己有50%的机会被叫去一面。继续祈祷
本篇是对上一篇EMC笔试题目的附加。因为我又想起来一些题目了。
问：A B C
D
E F G
H
I
A~I代表1~9中的数字之一。如果要让A+B+C=C+D+E=E+F+G=G+H+I=13，那E是几？
我选5。直觉。没有细算，因为没有太多时间考虑。现在想想又可能是7。管它呢，大家想想。
（1.4.2）
问：
There are 4 people: Mr. Cooper, his wife, their son and Mr. Coopers mother. One is a doctor and another is a lawyer.
1) If the doctor is younger than the lawyer, then the doctor and the lawyer are not blood relatives.
2)If the doctor is a woman then the doctor and the lawyer are blood relatives.
3) If the lawyer is a man, then the doctor is a man.
Whose occupation do you know?
我选Mr.Cooper is the doctor。而且这个肯定是正确答案。因为我刚才想不起来题目是什么了，就去GOOGLE查了，结果查到了这个题目，答案就是COOPER！
问：有个长度为40的数列，第一和第二个都是1。第三个是前2个和，第4个是第2、3的和。依次类推。问第40个除第39个等于多少？(这个数列有名字的,但是我忘记了饿， 好象是F开头的。费伯那？)
选项：1.66666、1.600000、1.6038……、1、以上都不是。
我选1.6038……具体多少不记得了。猜的。
1。经过最少多少次比较能找出1000个元素中second smallest的一个
2。六个城市两两相连，现在从A城市出发，连接每个城市一次且不重复的路径有多少条
3。个位是8且是square of an integer的2-digit number有几个
4。假设你要做一个practical building，which shape has the largest ratio of volume to surface area?
A.Tetrahedron
B.4-side pyramid
C.Cube
D.Sphere
E.Hemisphere
这题我记住你了！选项一个都不认识！我饮恨！找到一道不需要大学知识的我容易吗……
5。10个口袋每个有100个金币，其中一个口袋每个金币9grams，其余正常的金币都是10grams。有个天平，问最少几次可以找出那个口袋
6。四个人过*，分别10、5、2、1分钟，晚上只有一个***，每次最多两人同时，时间以慢的那个为准。问最少多长时间全部过完
7。有个cylindrical coffee mug，no cover，with bottom。问倒进去多少咖啡时the whole system has lowest gravity center
A.NULL
B.FuLL
C.Half full
D.More than half full
E.Less than half full
8。有100扇门开始都是关着的，有个人从1喊到100，每喊到一个数字the door numbered multiple of this number就改变一次状态（开/关）问喊完100有几个门还关着
1what you want to do about your career in five years?what you want to do in five years?
2Use a languge to write a structure to store the data using the least memey space.
3客观选择题目，大约有十来页吧
4which facts do we conside to judge the OS is good or bad?
1。
class a{
public:
a() {cout<<"a!"<
virtual void disp(){cout<<" a::disp()!"<
virtual ~a(){cout<<"~a!"<
};
class b:public a{
public:
b(){cout<<"b!"<
~b(){cout<<"~b!"<
};
class c:public b{
public:
c(){cout<<"c!"<
void disp(){cout<<"c::disp()!"<
~c(){cout<<"~c!"<
};
void main()
{
a *p=new c();
p->disp();
delete p;
}
输出结果：
a!
b!
c!
c::disp()!
~c!
~b!
~a!
若a构造函数a()前没有virtual关键字，输出为a::disp()!
若a析构函数~a()前没有virtual关键字，输出为~a!而不是～c!～b!～a!
2。写一个函数 int p(int i, int N);
能够输出i到N再到i，即以参数1,7调用函数，输出结果为
1
2
3
4
5
6
7
6
5
4
3
2
1
要求只用一个语句完成，不允许用?:等n多操作符和关键字。只能用一个printf库函数
include
int p(int i, int N)
{
return (printf("%d\n", i))
&& ( i
&& (p(i+1, N)
|| (!printf("%d\n", i))));
}
int main(void)
{
p(1,7);
}
Given a singly linked list please write a function in C or C language
to fing a cycle in the list .
第三大题
Describe the similarities and differences between starvation and deadlock.
指针，宏，栈空间分配， 操作符优先级，概率，OS中的换页算法...
附加题一个是操作系统中的两个概念，一个是算法有关的
1.7×(1/7) = 1是什么率？
2.Whats database view?
3.4*(3*2) = (4*3)*2是什么率？
4.ABCDEF六城市两两相连，问从A到B经过其他城市有且只有一次的路径有多少个？
9.对代码中syntax进行分析用到的什么文法？
10.问要进行stable的sorting，会避免使用哪种算法？
17.0.15625写成二进制是什么
18.问1,2,3,5,8,13...这个数列，第58个除以第57个得多少？1.618
19.问关于fopen(“w”)的问题（主要是覆盖而不是追加）
20.问一连串cat和sort命令后输出
22.问RAID0的作用
23.火星上到处是硬币，随便拿起一个，如果是头朝上的就翻成字朝上的，如果是字朝上的就抛出，落地后有各一半的机会头朝上或字朝上。再随便拿起包括刚才那个在内的所有硬币中的一个，重复前述步骤。问，很多很多次后字朝上和头朝上的硬币比例？2:1
24.问RAID5的作用
25.麦当劳有6块9块20块鸡的袋子，问大于等于N块的鸡都能正好用前述袋子装走的最小N是多少？44
26.问又要考虑安全又要充分利用带宽的网络中，是先加密后压缩，还是先压缩后加密?
27.问要使一群人存在2人同月出生概率不低于50％的最小人数是多少？5
28.c++中不可重载的运算符是？（?:）
29.TCP/IP不存在那个层？（secure layer）
主要体会是，一些基础知识平时要注意积累，特别是面向对象、RAIN、网络，很多笔试都有考到，智力题的话注意积累经验。
第三部分是三道程序题。要求至少答两道，有时间也可以答三道。
1.写一个画圆的函数
int drawCircle(int x, int y, int radius);
要求：要让圆看起来连续圆滑，要画多余4×radius个点。
画点使用int drawPoint(int x,int y)函数
2.写出一段c++程序的输出。主要考察重载、多态、继承
class A
{
A() { cout << "A::A" << endl; }
~A(){ cout << "A::~A"<< endl; }
virtual f1() { cout << "A::f1" << endl; }
f2() { cout << "A::f2" << endl; }
};
class B: public A
{
B() { cout << "B::B" << endl; }
~B(){ cout << "B::~B"<< endl; }
f1() { cout << "B::f1" << endl; }
f2() { cout << "B::f2" << endl; }
};
class C: public C
{
C() { cout << "C::C" << endl; }
~C(){ cout << "C::~C"<< endl; }
f1() { cout << "C::f1" << endl; }
f2() { cout << "C::f2" << endl; }
};
main()
{
C c;
A *p = &c;
c.f1();
c.f2();
p->f1();
p->f2();
p = new C();
delete p;
}
（主要是子类实例定义是父类生成函数的调用顺序、清理时撤销函数的调用顺序，重载和多态的区别，还有就是栈上变量在函数退出时的清理，比如c在main函数退出时自动清理，要调用撤销函数）
3.函数声明如下
int func(int i ,int N);
其中i <= N，功能输出i递增到N再递减到i的整数，每行输出一个数。比如func(1,5)就是 1
2
3
4
5
4
3
2
1
要求是只用一条语句（函数体就一个分号）完成功能。要求：
不能有逗号，不能有新变量声明，不能用?:，不能用循环，不能用char int 什么什么的保留字符
我写的是
int func(int i ,int N)
{
reutrn printf("%d\n",i) + ((N-i)!=0&&(func(i+1,N) + printf("%d\n",i)));
}
除以59的余数是多少。——这道题我是硬算的，费了不少时间 。
int a=1000000000, b=2000000000; a=a+b;b=a-b;a=a-b; 最后a，b是多少？
如何判别一个数是unsigned —— 我选的a>=0 && ~a>=0 ？？
100层楼，两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能试出这个层数。
25匹马，每次比赛可选5匹马赛出次序（无法计时）。问至少要比赛多少次才能确定跑得最快，次快和第三快的三匹马。
七场,过程如下:
1\25马分５组跑完，这样各组都有１.２.３.４.５名的排列,类似于如下的排列,这样就是跑了5次了，
2\再把各组第一名组成一个组跑,这样产生的第一名一定是整个25个马中的第一名.
3\余下的第二名的产生,只能是B和1这两个马.
4\余下第三名的产生,只可能为C和2\1或者a和2和B,这样,将B C 1 2 a 这五个马组成..于是共计7场
ＡＢＣＤ E
１２３４５
a b c d e
...
上台阶，每次可走一台阶和两台阶，问上10个台阶有多少种走
法？
还有道考概率的题，光问题描述就写了半页纸，题讲什么忘了，当时依稀感觉好像又进了考研英语的考场。
第二部分大题三道，一道15分，
1：插入一个节点到一个有序链表。
2：循环的有序数组（比如1，2，3，4，5，-3，-2，-1这种数列）里查找一个数
3：在一个正整数序列中求和最大的非相邻子序列（序列任两元素在原序列里都不相邻）
第三部分写个200－350 words的essay：你认为近两百年来最重要的三项发明是什么，说出你的理由，第二部分的大题花时间太多，瞎写的electricity, nuclear weapon, computer。