t********e
发帖数: 1169 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celebrity。用O(n)时间找到此celebrity。
4. 给中序后续，构建树。
其他的每轮都问了简历。
感觉答的都不错，没什么难度。不知道为啥就被拒了。总之感觉很奇怪，不过也无所谓
了。
希望对大家有帮助。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31342084.html
>
贡献一道cs面试题，虽然我的面试机会极少。 ：D
设计一个函数，返回一组数字的组合，combination，
不同的是，你每调用它一次，它就返回下一个组合，而不是一次全返回。
注：你不能一次算完，把他们存起来，而必须临时算！
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31347263.html
>
IT company, 全都是brain teaser, 有点老。
1. 50个黑球50个百球，2个罐，要求你放这100个球在这2个罐，使得别人随机从2个
罐中任意拿一个球是黑球的几率达到最大。
2. heard on the street 上的男人出轨题，简单逻辑推理。
3. 这个没答上来，后来给了提示做出来了，但是回头想想还是不对。上来请教一下
。
2个人商量好策略，然后一个从52张牌里面随机抽5张，看牌，考虑。。。然后排在
桌上，摊开前4张，第5张面朝下，由第二个人判断第5张牌。 问这个策略。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31347264.html
>
这周一面的，一共5个人，碰到的题目不太难：
1. 写atoi函数，
测nodepad
2. 古老的三角形问题：输入3边，看是什么三角形。
一个mobile device可以从服务器上传和下载图像，怎么测试这个系统？
3. lunch meeting之后回办公室打开电脑，说他们现在开发的某产品有问题，每次要
loading很久,差不多10秒的样子。问怎么测试并找出这个bug？ 这个把我难住了，胡乱
讲了一通，然后说太困难了；于是他换了个题目，画了一个plotter软件的界面，问怎
么测。
coding的题目是Path Walk，给一条路径，写一个函数来走通它。其实这个题目我没
搞明白什么意思，先沟通了很久，最后开始写（还是不太明白。汗...），写完了觉得
不正确，正想再改改，被打住了，说给个test case一起来看看程序怎么执行。每句代
码跑了一通，却发现code写正确了:-)
4. 一开始是个IQ题，把一堆数字填到格子里，满足一些条件，比如1和2不能相邻。
测一个记事薄软件。有scheduler和notifier两部分，可以从scheduler输入时间和
内容，然后notifier到预定时间会给出提醒。
coding题目很容易，找到单链表倒数第N个节点。
5. 最后是hiring manager，问了一些behavior问题，然后打开一个网站，问怎么测试。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31348374.html
>
在onsite面试中实际遇到的。
1.template中用typename和用class有什么区别？
2.unix下执行shell脚本和执行可执行文件有什么区别？哪个更快，为什么？脚本语言
程序（如javascript)和可执行文件程序有什么区别？shell和这两者却别呢？
3.如何对const data member做assignment?
class A{
const int a;
public:
A():a(0){};
A(int m_a):a(m_a){};
};
int main(){
A a(1);
A b;
b = a; //how to implement assignment for this?
}
4.如果把base class对象赋给derived class对象,会怎么样？compiler报错还是执行错
误？
class A{
public:
int a;
};
class B:public A{
public:
int b;
};
int main(){
A a;
B b;
b = a; //what happend?
cout << b.b << endl;
B* b2;
b2 = &a; //how about this?
cout << b->b << endl;
}
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31348607.html
>
两波两小时，第一波老白＋老印，小兵
1. 介绍Recent Project
2. 两个C的程序问题
先是char*指针问题
char *dosth()
{
char s[256];
char * p = r;
p = "some new string":
}
然后问了一堆变量的值，比如 s, *s, *(s+2), &p, etc.
另外一个switch程序找错，没有加break之类，还有就是return local variable地址的
问题
3. 手写fab(n)函数，不是算，而是输出，递归或者循环都可，不过递归不高效大家应
该知道
4. 逻辑问题：八个水罐称重
5. 一堆关于OO概念的问题，多态，继承，封装，接口和抽象类的区别，复写和重载（
包括C++具体怎么实现的）
6. 反馈问题
第二波一个项目经理
一来就是比较高难度的，给你一个字节数组（注意取值范围），数组长度可能非常长，
如何找到第一个只出现了一次的数字。开始没什么思路，和他讨论了一会，边问还边问
复杂度和数据结构的问题，后来发现应该进行数出现次数，这样复杂度就是２ｎ，结果
出来了要求手写出代码。
然后就是一个智力问题，三个囚犯黑帽白帽，之前没见过，所以用了不少时间才想出来
，大家可以搜搜，有现成的。 最后反问问题后结束。
虽然每个问题都答出来了，不过最后还是功亏一篑。不是很清楚什么原因，哪位同学能
够指点一下？现在继续回归闺中状态中。不过感觉彭博问题的重复概率很大，希望对后
来的同学能够有所帮助：）
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31350186.html
>
1, C vs C++
2, struct in C v.s. in C++ v.s. class in C++
3, virtual function, pure virtual function, abstract class
what is the advantages of using virtual function
4, new v.s. malloc()
5, memory for a process (code, static data, stack, heap)
6, how to know the stack is growing in the direction of address increasing
or decreasing
7, virtual memory
Pasted from <http://www.mitbbs.com/article/JobHunting/31354737_3.html
>
nsite 只见了2个人，估计over了，总结一下教训。
题目不难，主要一共3道题，都算比较基础的题。
1.reverse words in a sentence，使用如下函数。
char* reverseWord(const char* str)
2.an interger array containing millions of elements with min 0 and max 1000,
how to sort it?
3.covert interger number to date string, for example, 20090130 -> "01/30/
2009"
说说教训：
第一道被输入const给搞死了。先是没有注意const,直接按照常规非const做，没有写完
就被叫停了；然后是被平时强调的malloc后必须及时delete规则搞死，坚持认为在函数
里malloc一块内存然后在函数外delete是不好的习惯；最后当面试者提出如果定义一块
内存
，如char tmp[2048]，然后使用会怎么样？自己提到可以在函数外strcpy函数返回结果
，却忘了
arr大小实际是无法指定的，所以这种方法是不可接受的。总之，很多的trick在里
面没有注意到。
第二道使用couting sort应该就可以。面试者要求描述算法，不需写代码。
第三道自己的做法是先取得30,然后01，然后2009然后组合成一个string。问题是这样
的话，月和日的01前的0可能会丢失，使得最后结果可能不对。后来想正确的做法应该
是先把整形转成string,然后使用substr并组合。另外，面试者问有stl有什么可以替换
itoa，自己答不出来。后来查了下，应该是可以使用stringstream来实现，如下：
stringstream ss;
ss << intVal;
ss.str()就是我们要的结果。
Pasted from <http://www.mitbbs.com/article/JobHunting/31356298_3.html
>
现在版上的文章好像已经以H1申请为主了，不知道多少人还对面经感兴趣。不过想想还
是写一下好，要不自己过几天可能就忘光了，呵呵。
申请工作：Software Developer，Mobile Application组
问题问的很多很杂，基本上不难。不过后来想想，也没有全都答对。大概包括：
* 为什么对Amazon感兴趣。
* 自己最近的Project。
* 说出自己会的编程语言并打分（1－5）。
* 有没有开发Mobile application的经验。
* 几个常见Data structure的Lookup操作的时间复杂度。
* HTTP post和get的区别。
* Design Pattern: Singleton, Factory, Lazy initialization。
* Multi-threaded programming, deadlock之类。
* 对Unix环境是否熟悉，几个常见命令，ls, ps之类。
* Reflection的概念，Java reflection，C++里面是不是有reflection。
* 如何实现Garbage Collection。Reference counting的缺点(cycle)，如何解决，JVM
有没有解决。
* C++里面virtual destructor的用途，于一般virtual function的区别。
* 写一个函数实现两个整数相除，不用"/"和"%"，返回商和余数。写完读给他听。
* 算法设计：一个Galaxy，每个星星用一个三围座标表示，找出离地球最近的1000个。
（后来发现这也是老题了）
Pasted from <http://www.mitbbs.com/article/JobHunting/31368921_3.html
>
have read many posts here although not really helpful this time, here is
something about bloomberg's phone interview question
1. How to implement garbage collector ( what data structure)
2. How to implement c++ smart pointer
3. Pro and Con of multi process and multi-thread
4. How many stack/heap does a multi-thread program with 10 threads have?
there are some other questions I don't remember.
☆─────────────────────────────────────☆
yellpine (fresh CS master looking for referral) 于 (Wed Mar 4 16:42:52
2009) 提到:
4. How many stack/heap does a multi-thread program with 10 threads have?
who can help me with this?
10 stacks? 1 heap?
Pasted from <http://www.mitbbs.com/article/JobHunting/31373641_3.html
>
估计没有多少人感兴趣,
不过还是说一说.
面的是ELASTIC COMPUTING CLOUD组的SE,我是做网络的,对他们的这个cloud service有
些兴趣,以为会问算法和系统的问题,结果问了一个OOD的问题,
说一个大楼,10层,4个电梯,怎么设计类来实现这样一个系统?
题目career cup上有,不过没想到他会问这个,ECC又不是做应用的.刚好是我的弱项,一
直做research,对算法和语言还算了解,对应用系统和设计那是一片空白.面的是一塌糊
涂. 有要面amazon的参考一下.
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31376671.html
>
S Master
Windows Live Experience 组：
我一直催HR，今天给我打电话说拒了。 汗了--自我感觉还挺好的。
拒了 也把经验给大家分享一下，在版上受益这么多，回报一下大家。
一共见了5个人， 两个SDET， 两个SDET lead， 最后一个director。题目都很简单
1.美国人。上来随便聊聊，然后出了个coding 题目 一个数组，找出第一个重复的数
我给了三种方法，最后用hash写的，然后问test case之类的
2.印度人
上来问我会什么C#还是C++，我说C#会的多一些。然后他上来问了四五个简单的 语法
问题。正好我还都会，心理还窃喜着呢。coding 也很简单，给一个01字符串，转化成
整数。写完后 test case。 第二个题目是两个函数互相调用，无限循环了，然我找出
毛病，问怎么解决。
然后午饭跟这个印度人吃，随便聊聊。 就过了
3.欧洲人，不知道哪国。
女的， 人很好，跟她聊的最开心。coding 题目是个没见过的，double bytes
string实现delete键功能。这个比较难解释，她开始也跟我解释了很长时间。 就是删
除字符的时候如何确定是删一个字节还是删两个字节的问题。我给出算法，然后她有提
示有哪些特殊情况要考虑，也做出来了。然后她就问我给一个一般的application 如何
测试，又随便说了一通，结束了
4.美国人 senior test lead
coding 很简单，给一个句子，把里边所有的单词自身reverse
然后给我看他们的产品，问我怎么测试。聊的也挺好
5.欧洲人 director
面到这个人的时候，我都快累趴下了，都不想面了，实在是累。心理还想着，offer拿
不拿得着无所谓，别把老子给累死了。（看来真得努力锻炼身体，不然面试都挺不住）
题目也很简单，找1--100的素数。我就给了最简单的方法，然后我说要 check一些边界
情况，他说不用了。然后让我做到他的椅子上，打开excel，问我怎么测设置字体这个
feature。说完了问我有什么问题没有
面完后觉得还不错，因为去之前心态还不错，现在就业情况不好
也怕，没打算毕业。
后来回到学校我就一直催HR赶紧给我结果，今天就给催出来了 呵呵
我说打算postpone到年底毕业，他说到时候可以直接再联系他（有个屁用啊 呵呵）
在学校继续呆着吧，呵呵，把身体锻炼好，面试也是一个体力活。
写出来 希望对大家能有点帮助。
Pasted from <http://www.mitbbs.com/article/JobHunting/31383513_3.html
>
iantianz (tiantianz) 于 (Thu Mar 12 15:23:30 2009) 提到:
刚刚电面了一家中型软件公司的summer intern，问了一个算法题：
给你一本dictionary，任意给你七个letters，让你找出包含这七个字母的、最长的单
词。
条件：可以pre-processing，这样每次给你不同的letters时，可以very effcient
我当时想了好久也没给出完整答案。。。
naive 的解法当然就是每次scan dictionary，每次 O（n）。。。
pre-peocessing那就是建index，但index怎么建？怎么操作？
Pasted from <http://www.mitbbs.com/article/JobHunting/31387661_3.html
>
MichaelChen (Michael) 于 (Thu Mar 12 17:05:44 2009) 提到:
上学期ON CAMPUS的INTERVIEW,PENDING了几个月给了ON SITE
两周前去的，面的FULL TIME SDE。
见了5个人
1.REVERSE LINKLIST.
2.给了N个数，值域[1,N-1]，如何找出第一个重复的数
3.算POLYNOMIAL，比如5x^4+6x^3-7x^2-8=?
4.给一个URL,如何把空格这种字符转换成%20这种
5.给一个LINKLIST,VALUE的指针指向其他NODE，复制他
今天RECRUITER发邮件通知给OFFER了，漫长的两周。。。希望收回OFFER这种事不要发
生。。
准备基本就是看MITBBS精华区，programming interview exposed和careercup，希望大
家都好运，ms应该还是在招人。
Pasted from <http://www.mitbbs.com/article/JobHunting/31387663_3.html
>
攒rp，最近遇到的面试题。。。
C++：effective c++上的东西若干；exception相关；继承和子父类指针若干. 十五分
钟左右。
算法/编程：1. 大文件随机sample，one pass. 2. sodoku solver. 3. logn解x^y,
4. DP题 5. 1Billion query里选出时间最近5分钟内最frequent的1000个，one pass
（我以前在amazon见到过这题）。6.两个排序数组找共同中值。递归和非递归解法。7.
斐波那契数列。100层楼梯下楼，可以一步也可以两步，多少种下法？递归和非递归。
8 贝叶斯后验概率。9。多少人在一起，生日可能出现重复概率大于0.5？（算法导论原
题，我只记得个答案，直接说了。。。）10. 一个数组，找最大值比较次数？同时找最
大值和最小值比较次数？找最大值和次最大值比较次数？（他问我是否知道这题，我说
是作业题。后来和师兄聊说是这他常拿来用的面试题。）
系统设计和经验：1 设计一个库，提供timer的功能。deltalist/hash，或类似linux
kernal的 timer 设计。效率要比较高。2. 一个类似chord的DHT设计。3. 你有一个奇
怪的程序，有时有bug，有时没有，说出尽可能多的可能原因。4. printf来debug有何
不妥。5. process和thread。process之间的IPC有那些种？process间是否也可以share
memory.何时选thread或process。
Pasted from <http://www.mitbbs.com/article/JobHunting/31393101_3.html
>
职位是 junior financial engineer, 公司是一hedge fund,其实面完就感觉不太好，
一共见了6个人，有两个人问得技术问题答得不太好，也怪自己事先准备面试下的功夫
不太到家，准备得重点没有把握好。以下是一些能想起来的问题：
1。C++ 中的virtual destructor是啥？ 为啥要用？
2。quick sort， merge sort的复杂度。
3。 Structure 和class的区别是什么？ （我晕，这个我居然给答反了）
4。关于C++ 处理异常的方法 。 （基本上一头雾水）
5。Monte Carlo method in american style option pricing。 （我说的用least
square regression method,blah......)
6. Int_0^T W(t) dW(t) （ 一看见这个，贼激动阿，熟悉的ito' s formula)
7. Stonivich intergral 是啥？ 为什么用Ito's 不用 stonivich? (不知道拼得对不
对）
8. 一个国家所有的人如果生了一个男孩以后就停止生育，生了女孩以后就继续生，直
到生出男孩才停止生育，问多年以后男孩多还是女孩多？ （要联系上stopping time的
概念）。
9。什么是AR model? 啥时候用AR model?
10. American option 的up bound? (我说是stock price,被直接鄙视了，说更精确的
，只好答没有研究过，当时一头雾水）。
以上的是我能记得的一些问题，还有一些关于数据结构的问题我就彻底歇菜了，从来没
有这方面的背景，也就不记得他的问题了。
还有就是，关于自己的简历上面的Project 工作经历，一定要熟练再熟练，有些人问得
那叫一个细啊，而且基本上我所有的Project都被人问到了。这次面试的前4个人主要问
计算机和金融方面的技术问题，第5个HR，问些personality的问题，最后是hiring
manager,因为之前电话面试过我，就没有问问题，简单聊聊。整个面试花了５个小时，
雷死了，脑子到后面都已经不转了。虽然结果让人遗憾，不过就当是学习了，贴点信息
和大家共享下，希望自己能早日找到工作，也希望还在努力找工作的XDJM们再加把劲，
大家一起加油。
Pasted from <http://www.mitbbs.com/article/JobHunting/31406731_3.html
>
CS方向，希望对大家准备面试有帮助
1. 用stack class来实现queue，具体用几个stack不限。完了以后问怎么实现thread
safety，然后是怎么测试。
2. 实现strstr(str1, str2)，如果str2是str1的子串，返回true，否则返回false。实
现完了以后问如何测试。
3. 给定一个integer array with both positive and negative numbers，return a
contiguous subarray with the largest sum. 我本来想用dynamic programming实现
，但面试官希望按照他的一个更heuristic的思路来解，最后勉强搞定。
4. 给定一个排好序的linked list，删除其中所有的重复元素。比如给定1->2->3->3->
4->4->5，返回1->2->5。给定1->1->1->2->3，返回2->3。看起来简单，一边写一边发
现许多细节需要小心应对，好在最后搞定。
5. 给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3
分钟。但第三个烤箱有一个slot出了点问题，每次只能烤面包的一面。所以这个烤箱三
分钟后只能算烤好一片半面包，你需要把那半片翻个面，在同一个slot里再烤一次才算
一片完整的。现在给你这三个烤箱，问烤好21片面包最少需要多少时间？如果是2100片
呢？如果是任意给定的N片，要求O(1)时间内给出最少需要的时间。
6. 给你三根棍子，每根都需要一个小时才烧完，但每根燃烧的速度都不一样，也不均
匀。问只有这三根棍子和火柴，如何精确的得到1小时45分钟的计时？
7. 在一个party上，每个人可能认识别人，也可能不认识。现在其中有一个人是名人，
定义就是所有的人都认识他，但他不认识其余的任何人。现在要求你去找出这个名人来
。但你只可以通过一个方法，就是问A是不是认识B，回答是表示A认识B，不是表示A不
认识B。你可以任意去问这样的问题，问最少需要多少次能找出这个名人？思路有了之
后要求写代码实现，可以调用knows(A, B)，代表上面的那个问题。实现完了以后问如
何测试
8. 测试copy这个命令。然后自己问了一些clarifying questions，搞清了实际上是
copy src dest。src可以是文件，也可以是目录。dest可以存在，也可以不存在。
Pasted from <http://www.mitbbs.com/article/JobHunting/31410833_3.html
>
OO设计题，怎么做一个十字路口的traffic light.
2. 怎么不用recursion 做二叉树in order 遍历。
Pasted from <http://www.mitbbs.com/article/JobHunting/31421129_3.html
>
1. Write a function that returns a node in a tree given two parameters:
pointer to the root node and the in order traversal number of the node we
want to return. The only information stored in the tree is the number of
children for each node.
2. Input a message and a text, find if the message can be composed by the
text.
If the text is in a magazine (two pages/a paper), how to design an algorithm
?
Pasted from <http://www.mitbbs.com/article/JobHunting/31422009_3.html
>
1
When casting an object of a polymorphic class from a base calss type, which
one of the following casts
performs the task only if the cast is valid?
a. static_cast
b. (void*)
c. dynamic_cast
d. const_cast
e. reinterpret_cast
2. class A
{
public: void f();
protected: A() {}
A(const A&) {}
};
why are the default and copy constructors declared as protected?
a. to ensure that instance of A can not be created via new by a more derived
class
b. to ensure that instance of A can only be created by subclasses of A
c. to ensure that isntance of A can not be copied
d. to ensure that A cannot be used as a base class.
e. to ensure that A cannot be instantiated on the stack
3. template
int Product(T1 a, T2 b, T3 c)
{
return a*b*c;
}
what is wrong with the sample code above?
a. templates must be class definitions
b. the template parameters should be separated by commas.
c. the template definition is missing a pair of braces.
d. template parameters must be pointer types.
e. the * operator has not been defined for T1, T2, and T3.
4. class FOO
{
char * buf;
public:
Foo (const char *b = "default")
{
if (b)
{ buf = new char[std::strlen(b) + 1];
std::strcpy(buf, b);
}
else
buf=0;
}
~Foo() { delete[] buf; }
};
Foo func (Foo f)
{
return f;
}
when the function fun is called, the program may crash or exhibit unexpected
behavior, what is the reason ofr this problem?
a. the destructor may attempt to delete the string literal "default"
b. the destructor needs to check that the value of buf is not 0.
c. the class does not allocate a long enough buffer.
d. the function needs to return Foo& instead of Foo.
e the class needs to specify a copy constructor and assignment operator.
Pasted from <http://www.mitbbs.com/article/JobHunting/31426509_3.html
>
1．请书写一个程序，将整型变量 x 中数字左右翻转后存到另外一个整型变量 y中，例
如 x = 12345 时，y为 54321，x = ‐123 时，y为‐321。其中 x 的个位不为 0。
void reverse (int x, int* y);
(1) 请实现该函数，以上函数原型是用 C语言写的，你可以用你熟悉的语言；
(2) 请写出一段代码验证该函数在各种情况下的正确性。
2．对集合{1, 2, 3, …, n}中的数进行全排列，可以得到 n!个不同的排列方式。现在
我们用字母序把它们列出来，并一一标上序号，如当 n=3 时：
0．123
1．132
2．213
3．231
4．312
5．321
现在，请书写一个函数 void print (int n, int k)， （函数原型是用 C语言写的，
你可以用你熟悉的语言）在已知 n和序号 k 的情况下，输出对应的排列，并简要阐述
思路。
3．一维数轴上有 n 条线段，它们的端点都是已知的。请设计一个算法，计算出这些线
段的并集在数轴上所覆盖的长度，并分析时间复杂度。例如，线段 A 的坐标为[4, 8]
，线段 B 的坐标为[1, 5.1]， 那么它们共同覆盖的长度为 7。 请尽量找出最优化的
算法， 解释算法即可，不必写代码。
Pasted from <http://www.mitbbs.com/article/JobHunting/31428195_3.html
>
Given a sorted integer array and a number, find all the pairs that sum up to
the number.
这个很简单，但现在多了一个条件
What if the array is sorted by absolute value, for example {1, -2, 4, -9},
find the answer in O(N).
这样有什么好的思路么？
Pasted from <http://www.mitbbs.com/article/JobHunting/31430593_3.html
>
How do you find sequences of consecutive integers in a list that add to a
particular number.
Array里面正负数都有.
这个能在O(n)时间内解决吗？
Pasted from <http://www.mitbbs.com/article/JobHunting/31431861_3.html
>
A m*n matrix of integer, all rows and columns are sorted in ascending order.
Find the most efficient way to print out all numbers in ascending order.
Pasted from <http://www.mitbbs.com/article/JobHunting/31434325_3.html
>
一次面世Google，问到hash table是怎么实现的。我说了一个取尾数(round)的方法
，他说这个方法很navie，工业界一般用其他的方法，比方说STL的map。
我想了半天没有想出来，到这里问问。hash table具体怎么实现的啊？
Pasted from <http://www.mitbbs.com/article/JobHunting/31434401_3.html
>
49 辆赛车. Assume for each one, it travels the track in the same amount of t
ime every time. Also assume no two finish the track in the same amount of ti
me. Suppose you have 7 tracks, but no timer. Design races to find the 25-th
fastest with minimal number of races.
Pasted from <http://www.mitbbs.com/article/JobHunting/31434523_3.html
>
ime span: 38:39
interviewers: 2 -- 1 indian, 1 american
How do you know the bloomberg?
What position do you expect?
What language do you want to answer with? (I choose C.)
What kind of questions do you meet for the online assessment?
what is static in C? how is it implemented by the compiler?
write the definition of a function that returns both the max and min.
why do you use the condition variable?
how to implement a lock?
Under what condition must you use linked list instead of array?
what data structure can you use to store elements dynamically and access
them efficiently?
The complexity of finding any element in a linked list in the worst case.
multi-thread library programming: did you write your multi-thread library
with p-thread? is there any problem you have with you library?
did you do your projects on linux? If you want to find a string in a file,
what command should you use?
do you know vector in C++?
a question about real-time programming (I forgot)
what is buffer overflow?
一些问题是针对我的简历里面提到的内容，所以，简历里面的内容要尽量的吃透。
Pasted from <http://www.mitbbs.com/article/JobHunting/31434685_3.html
>
Given two classes:
class B
{
public:
B(args_1);
B(args_2);
// and many constructors with different arg lists
};
class D : public B
{
public:
D(args_1) : B(args_1) {}
D(args_2) : B(args_2) {}
// and many constructors with different signatures similarly implemented
// some additional stuff specific to D
};
Assume that the arg list for B's constructors are quite long and may be
revised pretty often in the future, in which case D's constructors have
to be recoded correspondingly. Duplicating the update by copy-and-paste
will certainly work here. Can you propose a better way so that the
update can be done in one place without copy-and-paste duplication?
Pasted from <http://www.mitbbs.com/article/JobHunting/31434891_3.html
>
Given a large string (haystack), find a substring (needle) on it.
感觉这道题不就是scan一遍吗？
有什么time and space complexity上面的trick吗？
Pasted from <http://www.mitbbs.com/article/JobHunting/31435419_3.html
>
准备了很久，看了很久算法的书。。 结果被问了一个怎么 optimize memcpy()..傻
眼了。。碰到了女老印，倒霉～～～～
Pasted from <http://www.mitbbs.com/article/JobHunting/31435587_3.html
>
规问题后，问了个code的问题：
给一个substr，如何判断它在不在给定的str里面。
substr有两个新的符号可能在里面：
（1）* : 0-n个任意字符
（2）? ： 1个任意字符
太紧张了，所以面试者简化了题目，说去掉“？”，然后让code和测试：基本框架出来
了，但是好多特殊情况没有处理到，比如substr以“？”起头。
后来又问如果加入“*”有没有思路，刚说了两句就out of time了。
唉，失败了，不知道有没有下文。
Pasted from <http://www.mitbbs.com/article/JobHunting/31436721_3.html
>
给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不
满意。
这个已经 lineal了？难道还有更快的？
Pasted from <http://www.mitbbs.com/article/JobHunting/31437417_3.html
>
given a 32 bit number N and 2 numbers(A & B) that determine 2 different bit
pos
itions of N how do you make all the bits between A and B equal to another
given
integer k.
given (A,B is in the range [0 to 31] and
k<=2^(B-A+1) ( so that k fits between B-A+1 bits). Give an O(1) solution for
th
is
e.g if N=9 ( 1001) ,A=0 ,B=2,K=5(101 then the result should be 1101 (1.e 13)
这个题是什么意思啊？
Pasted from <http://www.mitbbs.com/article/JobHunting/31437907_3.html
>
在做careercup上面的题目, 有两个问题没有看懂, 希望有人指点下
1 一个BST, 给定一个值, 打印出所有的path,使path上所有节点的值等于给定值;
2 一个tree, 如何高效的找出最长的path?
☆─────────────────────────────────────☆
mitbbs59 (59) 于 (Fri Jul 3 15:35:37 2009, 美东) 提到:
这都是amazon的题目吧
1.sum of all nodes in a path = givenValue
2.http://www.careercup.com/question?id=87897
Pasted from <http://www.mitbbs.com/article/JobHunting/31441709_3.html
>
是现场写code的面试。
第一道是写一个函数，两个参数（String prefix, String s）, 返回true如果s有
prefix
第二道是写一个函数，两个参数（int[] a, int sum), 找出数组里加起来是sum的几个数
我第一题算是答出来了，第二题没做完，没有好的思路。。。
大人指教一下
Pasted from <http://www.mitbbs.com/article/JobHunting/31446979_3.html
>
Went to Adobe to interview a Senior SW Engineer position,
总的interview的不错， 但被下面问题问倒了，让回去想想，
Q1:
"We need to compare thousands text files with each other, they are not big,
less than 100K each. They are in a directories tree, with a few levels of
subdirectories, how to speed up the comparing process ?"
My answers: We can read them all of these files into memory once so that we
can reduce the number of diso I/O.
[Feedback: That is a good appoach].
Q2: How to read these files into memory (on MS Windows platform ) ? how do
you maintain directory structure in memory ?
My answer: I talked some garbage ....
Q3: If someone already wrote the code in slow way, read each file from disk,
do some thing, close the file, read another one, etc. Can you make a "
portable layer API" libary so that with minimal effort, old code can still
work but much faster ? (of course, we need to recompile the code).
Please help with Q2 and Q3, thanks a lot. | t********e
发帖数: 1169 | 2 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celebrity。用O(n)时间找到此celebrity。
4. 给中序后续，构建树。
其他的每轮都问了简历。
感觉答的都不错，没什么难度。不知道为啥就被拒了。总之感觉很奇怪，不过也无所谓
了。
希望对大家有帮助。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31342084.html
>
贡献一道cs面试题，虽然我的面试机会极少。 ：D
设计一个函数，返回一组数字的组合，combination，
不同的是，你每调用它一次，它就返回下一个组合，而不是一次全返回。
注：你不能一次算完，把他们存起来，而必须临时算！
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31347263.html
>
IT company, 全都是brain teaser, 有点老。
1. 50个黑球50个百球，2个罐，要求你放这100个球在这2个罐，使得别人随机从2个
罐中任意拿一个球是黑球的几率达到最大。
2. heard on the street 上的男人出轨题，简单逻辑推理。
3. 这个没答上来，后来给了提示做出来了，但是回头想想还是不对。上来请教一下
。
2个人商量好策略，然后一个从52张牌里面随机抽5张，看牌，考虑。。。然后排在
桌上，摊开前4张，第5张面朝下，由第二个人判断第5张牌。 问这个策略。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31347264.html
>
这周一面的，一共5个人，碰到的题目不太难：
1. 写atoi函数，
测nodepad
2. 古老的三角形问题：输入3边，看是什么三角形。
一个mobile device可以从服务器上传和下载图像，怎么测试这个系统？
3. lunch meeting之后回办公室打开电脑，说他们现在开发的某产品有问题，每次要
loading很久,差不多10秒的样子。问怎么测试并找出这个bug？ 这个把我难住了，胡乱
讲了一通，然后说太困难了；于是他换了个题目，画了一个plotter软件的界面，问怎
么测。
coding的题目是Path Walk，给一条路径，写一个函数来走通它。其实这个题目我没
搞明白什么意思，先沟通了很久，最后开始写（还是不太明白。汗...），写完了觉得
不正确，正想再改改，被打住了，说给个test case一起来看看程序怎么执行。每句代
码跑了一通，却发现code写正确了:-)
4. 一开始是个IQ题，把一堆数字填到格子里，满足一些条件，比如1和2不能相邻。
测一个记事薄软件。有scheduler和notifier两部分，可以从scheduler输入时间和
内容，然后notifier到预定时间会给出提醒。
coding题目很容易，找到单链表倒数第N个节点。
5. 最后是hiring manager，问了一些behavior问题，然后打开一个网站，问怎么测试。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31348374.html
>
在onsite面试中实际遇到的。
1.template中用typename和用class有什么区别？
2.unix下执行shell脚本和执行可执行文件有什么区别？哪个更快，为什么？脚本语言
程序（如javascript)和可执行文件程序有什么区别？shell和这两者却别呢？
3.如何对const data member做assignment?
class A{
const int a;
public:
A():a(0){};
A(int m_a):a(m_a){};
};
int main(){
A a(1);
A b;
b = a; //how to implement assignment for this?
}
4.如果把base class对象赋给derived class对象,会怎么样？compiler报错还是执行错
误？
class A{
public:
int a;
};
class B:public A{
public:
int b;
};
int main(){
A a;
B b;
b = a; //what happend?
cout << b.b << endl;
B* b2;
b2 = &a; //how about this?
cout << b->b << endl;
}
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31348607.html
>
两波两小时，第一波老白＋老印，小兵
1. 介绍Recent Project
2. 两个C的程序问题
先是char*指针问题
char *dosth()
{
char s[256];
char * p = r;
p = "some new string":
}
然后问了一堆变量的值，比如 s, *s, *(s+2), &p, etc.
另外一个switch程序找错，没有加break之类，还有就是return local variable地址的
问题
3. 手写fab(n)函数，不是算，而是输出，递归或者循环都可，不过递归不高效大家应
该知道
4. 逻辑问题：八个水罐称重
5. 一堆关于OO概念的问题，多态，继承，封装，接口和抽象类的区别，复写和重载（
包括C++具体怎么实现的）
6. 反馈问题
第二波一个项目经理
一来就是比较高难度的，给你一个字节数组（注意取值范围），数组长度可能非常长，
如何找到第一个只出现了一次的数字。开始没什么思路，和他讨论了一会，边问还边问
复杂度和数据结构的问题，后来发现应该进行数出现次数，这样复杂度就是２ｎ，结果
出来了要求手写出代码。
然后就是一个智力问题，三个囚犯黑帽白帽，之前没见过，所以用了不少时间才想出来
，大家可以搜搜，有现成的。 最后反问问题后结束。
虽然每个问题都答出来了，不过最后还是功亏一篑。不是很清楚什么原因，哪位同学能
够指点一下？现在继续回归闺中状态中。不过感觉彭博问题的重复概率很大，希望对后
来的同学能够有所帮助：）
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31350186.html
>
1, C vs C++
2, struct in C v.s. in C++ v.s. class in C++
3, virtual function, pure virtual function, abstract class
what is the advantages of using virtual function
4, new v.s. malloc()
5, memory for a process (code, static data, stack, heap)
6, how to know the stack is growing in the direction of address increasing
or decreasing
7, virtual memory
Pasted from <http://www.mitbbs.com/article/JobHunting/31354737_3.html
>
nsite 只见了2个人，估计over了，总结一下教训。
题目不难，主要一共3道题，都算比较基础的题。
1.reverse words in a sentence，使用如下函数。
char* reverseWord(const char* str)
2.an interger array containing millions of elements with min 0 and max 1000,
how to sort it?
3.covert interger number to date string, for example, 20090130 -> "01/30/
2009"
说说教训：
第一道被输入const给搞死了。先是没有注意const,直接按照常规非const做，没有写完
就被叫停了；然后是被平时强调的malloc后必须及时delete规则搞死，坚持认为在函数
里malloc一块内存然后在函数外delete是不好的习惯；最后当面试者提出如果定义一块
内存
，如char tmp[2048]，然后使用会怎么样？自己提到可以在函数外strcpy函数返回结果
，却忘了
arr大小实际是无法指定的，所以这种方法是不可接受的。总之，很多的trick在里
面没有注意到。
第二道使用couting sort应该就可以。面试者要求描述算法，不需写代码。
第三道自己的做法是先取得30,然后01，然后2009然后组合成一个string。问题是这样
的话，月和日的01前的0可能会丢失，使得最后结果可能不对。后来想正确的做法应该
是先把整形转成string,然后使用substr并组合。另外，面试者问有stl有什么可以替换
itoa，自己答不出来。后来查了下，应该是可以使用stringstream来实现，如下：
stringstream ss;
ss << intVal;
ss.str()就是我们要的结果。
Pasted from <http://www.mitbbs.com/article/JobHunting/31356298_3.html
>
现在版上的文章好像已经以H1申请为主了，不知道多少人还对面经感兴趣。不过想想还
是写一下好，要不自己过几天可能就忘光了，呵呵。
申请工作：Software Developer，Mobile Application组
问题问的很多很杂，基本上不难。不过后来想想，也没有全都答对。大概包括：
* 为什么对Amazon感兴趣。
* 自己最近的Project。
* 说出自己会的编程语言并打分（1－5）。
* 有没有开发Mobile application的经验。
* 几个常见Data structure的Lookup操作的时间复杂度。
* HTTP post和get的区别。
* Design Pattern: Singleton, Factory, Lazy initialization。
* Multi-threaded programming, deadlock之类。
* 对Unix环境是否熟悉，几个常见命令，ls, ps之类。
* Reflection的概念，Java reflection，C++里面是不是有reflection。
* 如何实现Garbage Collection。Reference counting的缺点(cycle)，如何解决，JVM
有没有解决。
* C++里面virtual destructor的用途，于一般virtual function的区别。
* 写一个函数实现两个整数相除，不用"/"和"%"，返回商和余数。写完读给他听。
* 算法设计：一个Galaxy，每个星星用一个三围座标表示，找出离地球最近的1000个。
（后来发现这也是老题了）
Pasted from <http://www.mitbbs.com/article/JobHunting/31368921_3.html
>
have read many posts here although not really helpful this time, here is
something about bloomberg's phone interview question
1. How to implement garbage collector ( what data structure)
2. How to implement c++ smart pointer
3. Pro and Con of multi process and multi-thread
4. How many stack/heap does a multi-thread program with 10 threads have?
there are some other questions I don't remember.
☆─────────────────────────────────────☆
yellpine (fresh CS master looking for referral) 于 (Wed Mar 4 16:42:52
2009) 提到:
4. How many stack/heap does a multi-thread program with 10 threads have?
who can help me with this?
10 stacks? 1 heap?
Pasted from <http://www.mitbbs.com/article/JobHunting/31373641_3.html
>
估计没有多少人感兴趣,
不过还是说一说.
面的是ELASTIC COMPUTING CLOUD组的SE,我是做网络的,对他们的这个cloud service有
些兴趣,以为会问算法和系统的问题,结果问了一个OOD的问题,
说一个大楼,10层,4个电梯,怎么设计类来实现这样一个系统?
题目career cup上有,不过没想到他会问这个,ECC又不是做应用的.刚好是我的弱项,一
直做research,对算法和语言还算了解,对应用系统和设计那是一片空白.面的是一塌糊
涂. 有要面amazon的参考一下.
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31376671.html
>
S Master
Windows Live Experience 组：
我一直催HR，今天给我打电话说拒了。 汗了--自我感觉还挺好的。
拒了 也把经验给大家分享一下，在版上受益这么多，回报一下大家。
一共见了5个人， 两个SDET， 两个SDET lead， 最后一个director。题目都很简单
1.美国人。上来随便聊聊，然后出了个coding 题目 一个数组，找出第一个重复的数
我给了三种方法，最后用hash写的，然后问test case之类的
2.印度人
上来问我会什么C#还是C++，我说C#会的多一些。然后他上来问了四五个简单的 语法
问题。正好我还都会，心理还窃喜着呢。coding 也很简单，给一个01字符串，转化成
整数。写完后 test case。 第二个题目是两个函数互相调用，无限循环了，然我找出
毛病，问怎么解决。
然后午饭跟这个印度人吃，随便聊聊。 就过了
3.欧洲人，不知道哪国。
女的， 人很好，跟她聊的最开心。coding 题目是个没见过的，double bytes
string实现delete键功能。这个比较难解释，她开始也跟我解释了很长时间。 就是删
除字符的时候如何确定是删一个字节还是删两个字节的问题。我给出算法，然后她有提
示有哪些特殊情况要考虑，也做出来了。然后她就问我给一个一般的application 如何
测试，又随便说了一通，结束了
4.美国人 senior test lead
coding 很简单，给一个句子，把里边所有的单词自身reverse
然后给我看他们的产品，问我怎么测试。聊的也挺好
5.欧洲人 director
面到这个人的时候，我都快累趴下了，都不想面了，实在是累。心理还想着，offer拿
不拿得着无所谓，别把老子给累死了。（看来真得努力锻炼身体，不然面试都挺不住）
题目也很简单，找1--100的素数。我就给了最简单的方法，然后我说要 check一些边界
情况，他说不用了。然后让我做到他的椅子上，打开excel，问我怎么测设置字体这个
feature。说完了问我有什么问题没有
面完后觉得还不错，因为去之前心态还不错，现在就业情况不好
也怕，没打算毕业。
后来回到学校我就一直催HR赶紧给我结果，今天就给催出来了 呵呵
我说打算postpone到年底毕业，他说到时候可以直接再联系他（有个屁用啊 呵呵）
在学校继续呆着吧，呵呵，把身体锻炼好，面试也是一个体力活。
写出来 希望对大家能有点帮助。
Pasted from <http://www.mitbbs.com/article/JobHunting/31383513_3.html
>
iantianz (tiantianz) 于 (Thu Mar 12 15:23:30 2009) 提到:
刚刚电面了一家中型软件公司的summer intern，问了一个算法题：
给你一本dictionary，任意给你七个letters，让你找出包含这七个字母的、最长的单
词。
条件：可以pre-processing，这样每次给你不同的letters时，可以very effcient
我当时想了好久也没给出完整答案。。。
naive 的解法当然就是每次scan dictionary，每次 O（n）。。。
pre-peocessing那就是建index，但index怎么建？怎么操作？
Pasted from <http://www.mitbbs.com/article/JobHunting/31387661_3.html
>
MichaelChen (Michael) 于 (Thu Mar 12 17:05:44 2009) 提到:
上学期ON CAMPUS的INTERVIEW,PENDING了几个月给了ON SITE
两周前去的，面的FULL TIME SDE。
见了5个人
1.REVERSE LINKLIST.
2.给了N个数，值域[1,N-1]，如何找出第一个重复的数
3.算POLYNOMIAL，比如5x^4+6x^3-7x^2-8=?
4.给一个URL,如何把空格这种字符转换成%20这种
5.给一个LINKLIST,VALUE的指针指向其他NODE，复制他
今天RECRUITER发邮件通知给OFFER了，漫长的两周。。。希望收回OFFER这种事不要发
生。。
准备基本就是看MITBBS精华区，programming interview exposed和careercup，希望大
家都好运，ms应该还是在招人。
Pasted from <http://www.mitbbs.com/article/JobHunting/31387663_3.html
>
攒rp，最近遇到的面试题。。。
C++：effective c++上的东西若干；exception相关；继承和子父类指针若干. 十五分
钟左右。
算法/编程：1. 大文件随机sample，one pass. 2. sodoku solver. 3. logn解x^y,
4. DP题 5. 1Billion query里选出时间最近5分钟内最frequent的1000个，one pass
（我以前在amazon见到过这题）。6.两个排序数组找共同中值。递归和非递归解法。7.
斐波那契数列。100层楼梯下楼，可以一步也可以两步，多少种下法？递归和非递归。
8 贝叶斯后验概率。9。多少人在一起，生日可能出现重复概率大于0.5？（算法导论原
题，我只记得个答案，直接说了。。。）10. 一个数组，找最大值比较次数？同时找最
大值和最小值比较次数？找最大值和次最大值比较次数？（他问我是否知道这题，我说
是作业题。后来和师兄聊说是这他常拿来用的面试题。）
系统设计和经验：1 设计一个库，提供timer的功能。deltalist/hash，或类似linux
kernal的 timer 设计。效率要比较高。2. 一个类似chord的DHT设计。3. 你有一个奇
怪的程序，有时有bug，有时没有，说出尽可能多的可能原因。4. printf来debug有何
不妥。5. process和thread。process之间的IPC有那些种？process间是否也可以share
memory.何时选thread或process。
Pasted from <http://www.mitbbs.com/article/JobHunting/31393101_3.html
>
职位是 junior financial engineer, 公司是一hedge fund,其实面完就感觉不太好，
一共见了6个人，有两个人问得技术问题答得不太好，也怪自己事先准备面试下的功夫
不太到家，准备得重点没有把握好。以下是一些能想起来的问题：
1。C++ 中的virtual destructor是啥？ 为啥要用？
2。quick sort， merge sort的复杂度。
3。 Structure 和class的区别是什么？ （我晕，这个我居然给答反了）
4。关于C++ 处理异常的方法 。 （基本上一头雾水）
5。Monte Carlo method in american style option pricing。 （我说的用least
square regression method,blah......)
6. Int_0^T W(t) dW(t) （ 一看见这个，贼激动阿，熟悉的ito' s formula)
7. Stonivich intergral 是啥？ 为什么用Ito's 不用 stonivich? (不知道拼得对不
对）
8. 一个国家所有的人如果生了一个男孩以后就停止生育，生了女孩以后就继续生，直
到生出男孩才停止生育，问多年以后男孩多还是女孩多？ （要联系上stopping time的
概念）。
9。什么是AR model? 啥时候用AR model?
10. American option 的up bound? (我说是stock price,被直接鄙视了，说更精确的
，只好答没有研究过，当时一头雾水）。
以上的是我能记得的一些问题，还有一些关于数据结构的问题我就彻底歇菜了，从来没
有这方面的背景，也就不记得他的问题了。
还有就是，关于自己的简历上面的Project 工作经历，一定要熟练再熟练，有些人问得
那叫一个细啊，而且基本上我所有的Project都被人问到了。这次面试的前4个人主要问
计算机和金融方面的技术问题，第5个HR，问些personality的问题，最后是hiring
manager,因为之前电话面试过我，就没有问问题，简单聊聊。整个面试花了５个小时，
雷死了，脑子到后面都已经不转了。虽然结果让人遗憾，不过就当是学习了，贴点信息
和大家共享下，希望自己能早日找到工作，也希望还在努力找工作的XDJM们再加把劲，
大家一起加油。
Pasted from <http://www.mitbbs.com/article/JobHunting/31406731_3.html
>
CS方向，希望对大家准备面试有帮助
1. 用stack class来实现queue，具体用几个stack不限。完了以后问怎么实现thread
safety，然后是怎么测试。
2. 实现strstr(str1, str2)，如果str2是str1的子串，返回true，否则返回false。实
现完了以后问如何测试。
3. 给定一个integer array with both positive and negative numbers，return a
contiguous subarray with the largest sum. 我本来想用dynamic programming实现
，但面试官希望按照他的一个更heuristic的思路来解，最后勉强搞定。
4. 给定一个排好序的linked list，删除其中所有的重复元素。比如给定1->2->3->3->
4->4->5，返回1->2->5。给定1->1->1->2->3，返回2->3。看起来简单，一边写一边发
现许多细节需要小心应对，好在最后搞定。
5. 给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3
分钟。但第三个烤箱有一个slot出了点问题，每次只能烤面包的一面。所以这个烤箱三
分钟后只能算烤好一片半面包，你需要把那半片翻个面，在同一个slot里再烤一次才算
一片完整的。现在给你这三个烤箱，问烤好21片面包最少需要多少时间？如果是2100片
呢？如果是任意给定的N片，要求O(1)时间内给出最少需要的时间。
6. 给你三根棍子，每根都需要一个小时才烧完，但每根燃烧的速度都不一样，也不均
匀。问只有这三根棍子和火柴，如何精确的得到1小时45分钟的计时？
7. 在一个party上，每个人可能认识别人，也可能不认识。现在其中有一个人是名人，
定义就是所有的人都认识他，但他不认识其余的任何人。现在要求你去找出这个名人来
。但你只可以通过一个方法，就是问A是不是认识B，回答是表示A认识B，不是表示A不
认识B。你可以任意去问这样的问题，问最少需要多少次能找出这个名人？思路有了之
后要求写代码实现，可以调用knows(A, B)，代表上面的那个问题。实现完了以后问如
何测试
8. 测试copy这个命令。然后自己问了一些clarifying questions，搞清了实际上是
copy src dest。src可以是文件，也可以是目录。dest可以存在，也可以不存在。
Pasted from <http://www.mitbbs.com/article/JobHunting/31410833_3.html
>
OO设计题，怎么做一个十字路口的traffic light.
2. 怎么不用recursion 做二叉树in order 遍历。
Pasted from <http://www.mitbbs.com/article/JobHunting/31421129_3.html
>
1. Write a function that returns a node in a tree given two parameters:
pointer to the root node and the in order traversal number of the node we
want to return. The only information stored in the tree is the number of
children for each node.
2. Input a message and a text, find if the message can be composed by the
text.
If the text is in a magazine (two pages/a paper), how to design an algorithm
?
Pasted from <http://www.mitbbs.com/article/JobHunting/31422009_3.html
>
1
When casting an object of a polymorphic class from a base calss type, which
one of the following casts
performs the task only if the cast is valid?
a. static_cast
b. (void*)
c. dynamic_cast
d. const_cast
e. reinterpret_cast
2. class A
{
public: void f();
protected: A() {}
A(const A&) {}
};
why are the default and copy constructors declared as protected?
a. to ensure that instance of A can not be created via new by a more derived
class
b. to ensure that instance of A can only be created by subclasses of A
c. to ensure that isntance of A can not be copied
d. to ensure that A cannot be used as a base class.
e. to ensure that A cannot be instantiated on the stack
3. template
int Product(T1 a, T2 b, T3 c)
{
return a*b*c;
}
what is wrong with the sample code above?
a. templates must be class definitions
b. the template parameters should be separated by commas.
c. the template definition is missing a pair of braces.
d. template parameters must be pointer types.
e. the * operator has not been defined for T1, T2, and T3.
4. class FOO
{
char * buf;
public:
Foo (const char *b = "default")
{
if (b)
{ buf = new char[std::strlen(b) + 1];
std::strcpy(buf, b);
}
else
buf=0;
}
~Foo() { delete[] buf; }
};
Foo func (Foo f)
{
return f;
}
when the function fun is called, the program may crash or exhibit unexpected
behavior, what is the reason ofr this problem?
a. the destructor may attempt to delete the string literal "default"
b. the destructor needs to check that the value of buf is not 0.
c. the class does not allocate a long enough buffer.
d. the function needs to return Foo& instead of Foo.
e the class needs to specify a copy constructor and assignment operator.
Pasted from <http://www.mitbbs.com/article/JobHunting/31426509_3.html
>
1．请书写一个程序，将整型变量 x 中数字左右翻转后存到另外一个整型变量 y中，例
如 x = 12345 时，y为 54321，x = ‐123 时，y为‐321。其中 x 的个位不为 0。
void reverse (int x, int* y);
(1) 请实现该函数，以上函数原型是用 C语言写的，你可以用你熟悉的语言；
(2) 请写出一段代码验证该函数在各种情况下的正确性。
2．对集合{1, 2, 3, …, n}中的数进行全排列，可以得到 n!个不同的排列方式。现在
我们用字母序把它们列出来，并一一标上序号，如当 n=3 时：
0．123
1．132
2．213
3．231
4．312
5．321
现在，请书写一个函数 void print (int n, int k)， （函数原型是用 C语言写的，
你可以用你熟悉的语言）在已知 n和序号 k 的情况下，输出对应的排列，并简要阐述
思路。
3．一维数轴上有 n 条线段，它们的端点都是已知的。请设计一个算法，计算出这些线
段的并集在数轴上所覆盖的长度，并分析时间复杂度。例如，线段 A 的坐标为[4, 8]
，线段 B 的坐标为[1, 5.1]， 那么它们共同覆盖的长度为 7。 请尽量找出最优化的
算法， 解释算法即可，不必写代码。
Pasted from <http://www.mitbbs.com/article/JobHunting/31428195_3.html
>
Given a sorted integer array and a number, find all the pairs that sum up to
the number.
这个很简单，但现在多了一个条件
What if the array is sorted by absolute value, for example {1, -2, 4, -9},
find the answer in O(N).
这样有什么好的思路么？
Pasted from <http://www.mitbbs.com/article/JobHunting/31430593_3.html
>
How do you find sequences of consecutive integers in a list that add to a
particular number.
Array里面正负数都有.
这个能在O(n)时间内解决吗？
Pasted from <http://www.mitbbs.com/article/JobHunting/31431861_3.html
>
A m*n matrix of integer, all rows and columns are sorted in ascending order.
Find the most efficient way to print out all numbers in ascending order.
Pasted from <http://www.mitbbs.com/article/JobHunting/31434325_3.html
>
一次面世Google，问到hash table是怎么实现的。我说了一个取尾数(round)的方法
，他说这个方法很navie，工业界一般用其他的方法，比方说STL的map。
我想了半天没有想出来，到这里问问。hash table具体怎么实现的啊？
Pasted from <http://www.mitbbs.com/article/JobHunting/31434401_3.html
>
49 辆赛车. Assume for each one, it travels the track in the same amount of t
ime every time. Also assume no two finish the track in the same amount of ti
me. Suppose you have 7 tracks, but no timer. Design races to find the 25-th
fastest with minimal number of races.
Pasted from <http://www.mitbbs.com/article/JobHunting/31434523_3.html
>
ime span: 38:39
interviewers: 2 -- 1 indian, 1 american
How do you know the bloomberg?
What position do you expect?
What language do you want to answer with? (I choose C.)
What kind of questions do you meet for the online assessment?
what is static in C? how is it implemented by the compiler?
write the definition of a function that returns both the max and min.
why do you use the condition variable?
how to implement a lock?
Under what condition must you use linked list instead of array?
what data structure can you use to store elements dynamically and access
them efficiently?
The complexity of finding any element in a linked list in the worst case.
multi-thread library programming: did you write your multi-thread library
with p-thread? is there any problem you have with you library?
did you do your projects on linux? If you want to find a string in a file,
what command should you use?
do you know vector in C++?
a question about real-time programming (I forgot)
what is buffer overflow?
一些问题是针对我的简历里面提到的内容，所以，简历里面的内容要尽量的吃透。
Pasted from <http://www.mitbbs.com/article/JobHunting/31434685_3.html
>
Given two classes:
class B
{
public:
B(args_1);
B(args_2);
// and many constructors with different arg lists
};
class D : public B
{
public:
D(args_1) : B(args_1) {}
D(args_2) : B(args_2) {}
// and many constructors with different signatures similarly implemented
// some additional stuff specific to D
};
Assume that the arg list for B's constructors are quite long and may be
revised pretty often in the future, in which case D's constructors have
to be recoded correspondingly. Duplicating the update by copy-and-paste
will certainly work here. Can you propose a better way so that the
update can be done in one place without copy-and-paste duplication?
Pasted from <http://www.mitbbs.com/article/JobHunting/31434891_3.html
>
Given a large string (haystack), find a substring (needle) on it.
感觉这道题不就是scan一遍吗？
有什么time and space complexity上面的trick吗？
Pasted from <http://www.mitbbs.com/article/JobHunting/31435419_3.html
>
准备了很久，看了很久算法的书。。 结果被问了一个怎么 optimize memcpy()..傻
眼了。。碰到了女老印，倒霉～～～～
Pasted from <http://www.mitbbs.com/article/JobHunting/31435587_3.html
>
规问题后，问了个code的问题：
给一个substr，如何判断它在不在给定的str里面。
substr有两个新的符号可能在里面：
（1）* : 0-n个任意字符
（2）? ： 1个任意字符
太紧张了，所以面试者简化了题目，说去掉“？”，然后让code和测试：基本框架出来
了，但是好多特殊情况没有处理到，比如substr以“？”起头。
后来又问如果加入“*”有没有思路，刚说了两句就out of time了。
唉，失败了，不知道有没有下文。
Pasted from <http://www.mitbbs.com/article/JobHunting/31436721_3.html
>
给定 X[1..n] and Y[1..m] 两个 arrays，已经sort好了.
如何找到X Y的median？我说用merge sort，要O(m+n/2)时间。面试官明显不
满意。
这个已经 lineal了？难道还有更快的？
Pasted from <http://www.mitbbs.com/article/JobHunting/31437417_3.html
>
given a 32 bit number N and 2 numbers(A & B) that determine 2 different bit
pos
itions of N how do you make all the bits between A and B equal to another
given
integer k.
given (A,B is in the range [0 to 31] and
k<=2^(B-A+1) ( so that k fits between B-A+1 bits). Give an O(1) solution for
th
is
e.g if N=9 ( 1001) ,A=0 ,B=2,K=5(101 then the result should be 1101 (1.e 13)
这个题是什么意思啊？
Pasted from <http://www.mitbbs.com/article/JobHunting/31437907_3.html
>
在做careercup上面的题目, 有两个问题没有看懂, 希望有人指点下
1 一个BST, 给定一个值, 打印出所有的path,使path上所有节点的值等于给定值;
2 一个tree, 如何高效的找出最长的path?
☆─────────────────────────────────────☆
mitbbs59 (59) 于 (Fri Jul 3 15:35:37 2009, 美东) 提到:
这都是amazon的题目吧
1.sum of all nodes in a path = givenValue
2.http://www.careercup.com/question?id=87897
Pasted from <http://www.mitbbs.com/article/JobHunting/31441709_3.html
>
是现场写code的面试。
第一道是写一个函数，两个参数（String prefix, String s）, 返回true如果s有
prefix
第二道是写一个函数，两个参数（int[] a, int sum), 找出数组里加起来是sum的几个数
我第一题算是答出来了，第二题没做完，没有好的思路。。。
大人指教一下
Pasted from <http://www.mitbbs.com/article/JobHunting/31446979_3.html
>
Went to Adobe to interview a Senior SW Engineer position,
总的interview的不错， 但被下面问题问倒了，让回去想想，
Q1:
"We need to compare thousands text files with each other, they are not big,
less than 100K each. They are in a directories tree, with a few levels of
subdirectories, how to speed up the comparing process ?"
My answers: We can read them all of these files into memory once so that we
can reduce the number of diso I/O.
[Feedback: That is a good appoach].
Q2: How to read these files into memory (on MS Windows platform ) ? how do
you maintain directory structure in memory ?
My answer: I talked some garbage ....
Q3: If someone already wrote the code in slow way, read each file from disk,
do some thing, close the file, read another one, etc. Can you make a "
portable layer API" libary so that with minimal effort, old code can still
work but much faster ? (of course, we need to recompile the code).
Please help with Q2 and Q3, thanks a lot. |
|
