标 题: 面完fb,结果已经出来了，share下被拒的原因（请转jobhunting版 (转载)
发信站: BBS 未名空间站 (Wed Nov 19 21:05:36 2014, 美东)
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 面完fb,结果已经出来了，share下被拒的原因（请转jobhunting版
发信站: BBS 未名空间站 (Tue Nov 18 20:46:44 2014, 美东)
考了下古，发现这位哥们的转贴，基本可以确认是一个人，基本可以确定这个是我被拒
的原因
同样迟到了大概5分钟，闲扯了十分钟左右，然后read4,确实很简单，但是给的题目非
常不清楚，所以完全没有考虑buffer里面留下的部分，中间我问了除了输出int,需不需
要考虑读出的字符放在哪里，被他含混过去了。自己没做过底层的东西，竟然也没有看
到这个帖子，细节基本一致，因为题目很简单，所以35分钟内完成，全程毫无任何提示
，所有问他的问题基本上都回答得非常模糊，非常有误导性。之后让问fb问题，自己回
答了六周的ramp 什么着，我明明没问。。。最后拍照
我比下面这位哥们唯一好点的地方，我记下了这个人的名字的大致发音,自己查了下
linkedin, 应该是R--it---u---raj Kir---ti
希望以后面fb的诸位，千万小心入口buff需要变动位置，函数外创建类，类里头存上次
buff读入的byte数，然后做移动。
顺便求个bless面l和g的时候别再碰到烙印
===============================================
发信人: will5 (绽放), 信区: JobHunting
标 题: FB临门一脚挂了,那种郁闷悔恨的感觉.
发信站: BBS 未名空间站 (Thu Oct 17 17:55:34 2013, 美东)
上次onsite,4轮,自己感觉很好.
HR回信也说: went well so far but still need last code question interview to
end the process
要安排电话面试
结果我说:电面不好,我要求onsite,今天上午就onsite了.
结果, 一看是一个严肃的老印,基本听不懂其在说什么
就一道题:
实现 int Read(int Size, char * buffer) using int Read4(char * buffer)
这题思路很简单的,我当时给了2种方法结果在他的引导上走上了一条不归路,第一次实
现有bug, 没考虑buffer里面留下的部分....汗 ...各种改...(这题原来有过类似的
readLine, 但是自己觉得应该简单没有动手仔细写过, 结果在press下不能写好, 还是
实力不够!!!)
最后老印拍了照,明显要回去Negative的节奏
也许看到了老印,第一感觉就不妙吧,有了心理暗示, 过程中沟通也不是很顺畅. 面到40
分钟的时候,老印就不出题了, 直接叫问问题.汗
郁闷, 悔恨, 临门一脚, 我是中国足球队吗, 对自己的能力深深的怀疑!!!
再补充几个细节:
1) 此老印说之前在很多公司做过 现在在做Ads这一块. 前面闲扯的时间差不多有78分
钟, 本身他出来接我的时候也迟到了几分钟
2) 在35分钟左右的时候,他就说你问我问题吧, 你就问问我fb的process吧? 我汗, 我
说好的,那你介绍介绍吧, 无非就是6 weeks的ramp up什么的,这些我都知道了,明显是
拖时间到点.
3) 他送我出去的时候,还说:今天只面我一个吗? 我去, 你都送我出来了, 还这样问
4) 全程毫无提示
虽然不能归结为被黑了,但是和之前的 3个老美(或者欧洲) 一个台湾GG 的风格完全不
同, 这四轮过程非常愉快.
也许有人会问, 既然那四轮很好,为什么要加面一轮, 原因在这里:
1. 我没有经过电面,直接onsite的,也许会被认为缺一些coding的考察吧
2.上次四轮, 最后一轮, 第一个问题是: N个平面上点,找离原点最近的K个, 我本来要
给三种方法: 1. N*Log(K) 2.KLog(N) 3.select K 结果说了第一种之后,看他反应不错
,我就问写code吗?他说ok,然后就写完了用priority queue. 当时脑袋蒙了想起select
K的最优解决是 5中取1(不是一般快排的取pivot的方法), 我没信心完全写出code, 就
没说select K的算法.事实上用quicksort写也是很容易的.
至少用priority_queue 写完之后没bug, 后来又写 shift sorted array做binary
search, 写的太快了给人是背答案的感觉,也没bug. 第三个题是实现Heap(其实就是他
对前面的priority_queue有疑问,他说他对priority_queue不熟悉)push pop top, 实现
了最后支出一个小bug,fix
所以我觉得第四轮有一些疑惑再加上没有电面, 加面一轮到是可以理解.
生活没有假设, 也许上次onsite最后一轮直接给最优而不是走了保守策略, 可能也ok了
, 也许这轮onsite像原来希望的交流很smooth(这也是我没有选择telephone interview
的原因)话也会ok的, 也许遇到了困难我能很calm down的去解决问题, 最后结果也可能
不错.
Anyway, 只能move on了, 也祝愿后来的面试的人能多点运气,能一气呵成, 拿到offer!
Bless大家!
Wednesday, November 19, 2014
Monday, November 17, 2014
“our profile was actually reviewed at our hiring committee in the US this
morning and I just received the results. The committee has actually decided
they need some additional data through a couple more interviews.
Accordingly, I'd like to set up 2 more interviews for you, these interviews
will be focused on system design and open ended questions.”
看了版上大家讨论的题目，发现我的第一轮onsite 真的好水，和大家的题目完全不在
一个档次上。一个 DP 也没有。。 也没有我最担心的 system design。 开始还庆幸。
结果 hc 没有水过。。 另外有一道 mapreduce 的题目我做的 也不好。想了很久，最
后才弄出来。
我还想请教一下，二轮onsite 要有怎样的表现才能过关？一定要出彩 还是要保守一点
。有经验的同学，给个建议啊。
等全部面玩后，不管结果，一定发上完整面筋。
我整理了板上差不多和system design 搭点边的题目，有一起准备的 ，讨论一下。都
是复制的前人成果。欢迎大家补充
1. 大规模系统设计的问题，比如load balancing, server communication, data
consistence等等，而且他会一直深入细节，让你设计一些出错处理什么之类的.
2. 每个任务之间有dependency，怎么安排任务顺序，使得执行任务i的时候，所有被
depend的任务已经执行过了。
3. 用Java设计一个餐馆。有厨师，服务生，客户等等类。设计时我太注意细节了，忘
了考虑多线程。最后在面试管提醒下大致说了一下多线程实现的方案。
4. udp和tcp的区别，什么时候用tcp，什么时候用udp。tcp是否允许接受重复packet。
cookie是什么在进行操作，一个网站最多有几个cookie。
5. 做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
6. 实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工作。
可能整个工作过程的某个时段这台机器得到的url set跟另一台机器得到的url set不一
样，我们又不希望重复劳动。怎么办？
7. 一个非常sparse的matrix，2^64 × 2^64, 设计一个class，内有get(int x, int y
), set(int x, int y, int value)。 用什么数据结构存储它？有哪些选择，各自的
get啊, set的complexity是什么。
8. Design a class library for writing card games.
9. 然后让我设计一个分布式文件系统，给定
path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给
定path name，怎么知道哪个node拥有这个文件。我提出需要实现一个lookup function
，它可以是一个hash function，也可以是一个lookup table。如果是lookup table，
为了让所有client sync，可以考虑额外做一个lookup cluster。然后Interviewer很纠
结，既然可以用hash function，为什么还搞得那么复杂。我就告诉他hash function的
缺点。假定一开始有N个node，hash function把M个文件uniformly distribute到N个
node上。某天发现capacity不够，加了一个node。首先，要通知所有的client machine
，configuration 改变了。如果不想重启client machine的process，这不是一个
trivial job。其次，文件到node的mapping也变了。比如，本来按照hash function，
一个文件是放在node 1。加了一个node 后，它可能就map到node 2了。平均来说，N/(N
+1)的文件需要move到新的node。这个data migration还是很大的。然后我就提出一些
hash function的design，可以减少data migration。
最后他提了一个问题，说要实现一个function，要统计distributed file system所有
目录的大小。前提是，一个目录下的文件可能放在不同的node上。我说这个不就是在每
个node上统计，然后发到一个merge吗。他说对，但是又问用什么data structure来表
示。我说这就是hash table，key就是directory name，value就是大小。因为
directory本身是树结构，这个hash table的key可以用tree来组织。最后让我实现一个
function，把我说得这个data structure serialize成byte array。因为这个byte
array就是网络传输的data。我用了depth first traverse。不过等我程序写完，才发
现，用breath first traverse会更方便，code也会很简洁。
10. 他是要我用pthread实现thread pool，以及thread job management。先是
define class interface，然后用pthread的mutex和semaphore实现了consumer/
producer queue。这个queue允许users（producers)加入thread jobs，thread
managers(consumers)拿出thread jobs，并执行。
11. Consider you are constructing a system for data synchronization, what
problem will you face, and how you solve it? (I did not do well on this
question, since for my understanding, the data synchronization is normally
among process, or among different users, like the one in source code version
control (Git/repo). I finally understand after 15 mins, he wants to know
about multi-threads synchronization.
12.
然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥，有的
人心里装了一个答案，问的很模糊，你不答到他那个答案他就是不满意。不知道如何解
决这种情况。大概问答过程如下：
He: how would you design a distributed key-value store
Me: DHT or just using clusters
He: details?
Me: we have a large number of machines. first we use a hash function to
retrieve machine ID from the key. Then we connect to the machine and use
another hash function to retrieve the address from the key. Then fetch data
from that address.
He (seems not satisfied): how much space do you need on the master machine?
Me: It depends. If we can use a hash function to derive the IP address of
the machine, we don't need extra space. Otherwise, we need a table to store
key-IP pairs which is XXX large.
He: say more about how you would get the value on one machine
Me: we have two levels of cache, then memory, then disk. We go down to lower
levels if we can't retrieve the value on higher levels. (seems like not
what he expected)
He: how would you fetch the value on the disk? Please fill in a function
char* getData(char *key) { ... }
Me: don't know what he asked is different from what I answered. Ask him a
lot of questions, but haven't got anything useful
He: Think about what the file system is like
Me: Talked about things I know about file systems. Ask him whether he would
like me to write that function based on file system or redesign everything.
He: should be based on file systems.
Me: go from "/", keep iteratively searching for the current directory using
the key, until we hit a file not a directory. Then open that file and read
value and return the value.
整个过程，感觉跟他预想的不一样，跟我预想的也不一样。一直觉得key-value pairs
应该是用分布式的no sql的DB来实现的，没想到要去读file。另外自己对于disk读取的
底层API也不了解，所以答题的时候基本凭想象来答，觉得怎样应该算是reasonable的
。这可能是导致杯具的原因。
有两点教训就是。一，不要觉得自己是new grad就可以只写code，答两道数学题，他们
真的什么都考，特别是这种large scale的，什么问题都可以问。二，两个面试之间一
定要take a break，就算不上厕所也要去一趟洗手间让大脑休息一下，我就是到最后两
个有些晕了，没答好杯具了。
DHT B+ tree
13. 固定时间内某网站只允许访问有限次，如何让index次数尽可能的少，又不错过更
新。
14. Table reservation system. 并行的, 这个用semaphore或mutex tasking的算法
不行么?
15. Design Patterns
morning and I just received the results. The committee has actually decided
they need some additional data through a couple more interviews.
Accordingly, I'd like to set up 2 more interviews for you, these interviews
will be focused on system design and open ended questions.”
看了版上大家讨论的题目，发现我的第一轮onsite 真的好水，和大家的题目完全不在
一个档次上。一个 DP 也没有。。 也没有我最担心的 system design。 开始还庆幸。
结果 hc 没有水过。。 另外有一道 mapreduce 的题目我做的 也不好。想了很久，最
后才弄出来。
我还想请教一下，二轮onsite 要有怎样的表现才能过关？一定要出彩 还是要保守一点
。有经验的同学，给个建议啊。
等全部面玩后，不管结果，一定发上完整面筋。
我整理了板上差不多和system design 搭点边的题目，有一起准备的 ，讨论一下。都
是复制的前人成果。欢迎大家补充
1. 大规模系统设计的问题，比如load balancing, server communication, data
consistence等等，而且他会一直深入细节，让你设计一些出错处理什么之类的.
2. 每个任务之间有dependency，怎么安排任务顺序，使得执行任务i的时候，所有被
depend的任务已经执行过了。
3. 用Java设计一个餐馆。有厨师，服务生，客户等等类。设计时我太注意细节了，忘
了考虑多线程。最后在面试管提醒下大致说了一下多线程实现的方案。
4. udp和tcp的区别，什么时候用tcp，什么时候用udp。tcp是否允许接受重复packet。
cookie是什么在进行操作，一个网站最多有几个cookie。
5. 做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
6. 实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工作。
可能整个工作过程的某个时段这台机器得到的url set跟另一台机器得到的url set不一
样，我们又不希望重复劳动。怎么办？
7. 一个非常sparse的matrix，2^64 × 2^64, 设计一个class，内有get(int x, int y
), set(int x, int y, int value)。 用什么数据结构存储它？有哪些选择，各自的
get啊, set的complexity是什么。
8. Design a class library for writing card games.
9. 然后让我设计一个分布式文件系统，给定
path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给
定path name，怎么知道哪个node拥有这个文件。我提出需要实现一个lookup function
，它可以是一个hash function，也可以是一个lookup table。如果是lookup table，
为了让所有client sync，可以考虑额外做一个lookup cluster。然后Interviewer很纠
结，既然可以用hash function，为什么还搞得那么复杂。我就告诉他hash function的
缺点。假定一开始有N个node，hash function把M个文件uniformly distribute到N个
node上。某天发现capacity不够，加了一个node。首先，要通知所有的client machine
，configuration 改变了。如果不想重启client machine的process，这不是一个
trivial job。其次，文件到node的mapping也变了。比如，本来按照hash function，
一个文件是放在node 1。加了一个node 后，它可能就map到node 2了。平均来说，N/(N
+1)的文件需要move到新的node。这个data migration还是很大的。然后我就提出一些
hash function的design，可以减少data migration。
最后他提了一个问题，说要实现一个function，要统计distributed file system所有
目录的大小。前提是，一个目录下的文件可能放在不同的node上。我说这个不就是在每
个node上统计，然后发到一个merge吗。他说对，但是又问用什么data structure来表
示。我说这就是hash table，key就是directory name，value就是大小。因为
directory本身是树结构，这个hash table的key可以用tree来组织。最后让我实现一个
function，把我说得这个data structure serialize成byte array。因为这个byte
array就是网络传输的data。我用了depth first traverse。不过等我程序写完，才发
现，用breath first traverse会更方便，code也会很简洁。
10. 他是要我用pthread实现thread pool，以及thread job management。先是
define class interface，然后用pthread的mutex和semaphore实现了consumer/
producer queue。这个queue允许users（producers)加入thread jobs，thread
managers(consumers)拿出thread jobs，并执行。
11. Consider you are constructing a system for data synchronization, what
problem will you face, and how you solve it? (I did not do well on this
question, since for my understanding, the data synchronization is normally
among process, or among different users, like the one in source code version
control (Git/repo). I finally understand after 15 mins, he wants to know
about multi-threads synchronization.
12.
然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥，有的
人心里装了一个答案，问的很模糊，你不答到他那个答案他就是不满意。不知道如何解
决这种情况。大概问答过程如下：
He: how would you design a distributed key-value store
Me: DHT or just using clusters
He: details?
Me: we have a large number of machines. first we use a hash function to
retrieve machine ID from the key. Then we connect to the machine and use
another hash function to retrieve the address from the key. Then fetch data
from that address.
He (seems not satisfied): how much space do you need on the master machine?
Me: It depends. If we can use a hash function to derive the IP address of
the machine, we don't need extra space. Otherwise, we need a table to store
key-IP pairs which is XXX large.
He: say more about how you would get the value on one machine
Me: we have two levels of cache, then memory, then disk. We go down to lower
levels if we can't retrieve the value on higher levels. (seems like not
what he expected)
He: how would you fetch the value on the disk? Please fill in a function
char* getData(char *key) { ... }
Me: don't know what he asked is different from what I answered. Ask him a
lot of questions, but haven't got anything useful
He: Think about what the file system is like
Me: Talked about things I know about file systems. Ask him whether he would
like me to write that function based on file system or redesign everything.
He: should be based on file systems.
Me: go from "/", keep iteratively searching for the current directory using
the key, until we hit a file not a directory. Then open that file and read
value and return the value.
整个过程，感觉跟他预想的不一样，跟我预想的也不一样。一直觉得key-value pairs
应该是用分布式的no sql的DB来实现的，没想到要去读file。另外自己对于disk读取的
底层API也不了解，所以答题的时候基本凭想象来答，觉得怎样应该算是reasonable的
。这可能是导致杯具的原因。
有两点教训就是。一，不要觉得自己是new grad就可以只写code，答两道数学题，他们
真的什么都考，特别是这种large scale的，什么问题都可以问。二，两个面试之间一
定要take a break，就算不上厕所也要去一趟洗手间让大脑休息一下，我就是到最后两
个有些晕了，没答好杯具了。
DHT B+ tree
13. 固定时间内某网站只允许访问有限次，如何让index次数尽可能的少，又不错过更
新。
14. Table reservation system. 并行的, 这个用semaphore或mutex tasking的算法
不行么?
15. Design Patterns
Saturday, November 8, 2014
Design question
design an architecture for a network file transfer system for very large
files, for say Netflix Video Transfer.
files, for say Netflix Video Transfer.
Yahoo
第0轮：做coding exercise,一个小时，实际5分钟就搞完了，后面一直在写testcase
给三个参数，s,l,d,分别代表小砖长度，大砖长度，目标长度，砖的数量无限，问有无
可能达到目标长，返回true or false;
比如1,2,5 返回true,因为1+2+2=5
我的code:
if(s > l || s <= 0 || l <= 0 || d <= 0)
throw new Exception ();
for(int i = 0; i <= d; i += l)
if((d - i) % s == 0)
return true;
return false;
第一轮：1.上来先问我这code的问题，感觉面试官没看懂，拿了一堆类似1，X , Y的数
据测我程序，我都看不下去了，小砖长度为1，我第一次循环直接就true了啊，有毛好
测的。。后来我提示了一下，他测了个2，5, 8..还是第一次就出结果。。有意思么。。
2.matrix rotate 90度。。非常基本的题，先让我跟他讲思路，怎么讲感觉他
都不理解，后来终于趁他若有所思的时候开始写code了，写完了他还不懂，又是4*4的
矩阵，每个element都要跑一遍给他看，简直无语，看完好像还是没懂我是啥意思
3.design 数据库，纯建一个表就完事了，加点key,foreign key什么的
4.merge two sorted linklist，这次他总算看懂我代码了，啥也没问
第二轮：1.OO design。design Duck。Duck has many species，different species
有不同的叫声，但是飞翔和游泳是一样的。我就搞了个抽象类继承下什么的。后来变成
有N种飞行，问我怎么改，我SB了，写了N种飞行method在父类里，另外还有个主fly
method，根据鸟的fly类型在主fly method里调用不同的method；然后他告诉我应该定
义一个fly class.这个没答好
2.basic questions: deadlock, how to synchronize, database join,
singleton 这个基本不难，就问的点比较杂
第三轮：1.has a Random5() which generate random number from 1-5. Write a
function generate 1-125
我的code:
int Random125(){
int result=0;
result+=25*(Random5()-1);
result+=5*(Random5()-1);
result+=(Random5()-1);
if(result==0)
return 125;
return result;
}
然后这面试官又说我这个不是evenly random，说中间的数出现的多，两边的数出
现的少。。我擦，这不可能啊。。解释了很久面试官不信不耐烦了搞下一题了
2.问我怎么处理推特这样的大规模读写数据的请求，系统设计吧相当于。
最后说到cache上，我拿LRU解决的，所以就implement LinkedHashMap，然后写
了个LRU算法。。最后问还有没有改进
这个我基本都答上来了，还行
间隔着问些简历上的东西，我就不说了
CEO review,希望不出什么意外= =！
给三个参数，s,l,d,分别代表小砖长度，大砖长度，目标长度，砖的数量无限，问有无
可能达到目标长，返回true or false;
比如1,2,5 返回true,因为1+2+2=5
我的code:
if(s > l || s <= 0 || l <= 0 || d <= 0)
throw new Exception ();
for(int i = 0; i <= d; i += l)
if((d - i) % s == 0)
return true;
return false;
第一轮：1.上来先问我这code的问题，感觉面试官没看懂，拿了一堆类似1，X , Y的数
据测我程序，我都看不下去了，小砖长度为1，我第一次循环直接就true了啊，有毛好
测的。。后来我提示了一下，他测了个2，5, 8..还是第一次就出结果。。有意思么。。
2.matrix rotate 90度。。非常基本的题，先让我跟他讲思路，怎么讲感觉他
都不理解，后来终于趁他若有所思的时候开始写code了，写完了他还不懂，又是4*4的
矩阵，每个element都要跑一遍给他看，简直无语，看完好像还是没懂我是啥意思
3.design 数据库，纯建一个表就完事了，加点key,foreign key什么的
4.merge two sorted linklist，这次他总算看懂我代码了，啥也没问
第二轮：1.OO design。design Duck。Duck has many species，different species
有不同的叫声，但是飞翔和游泳是一样的。我就搞了个抽象类继承下什么的。后来变成
有N种飞行，问我怎么改，我SB了，写了N种飞行method在父类里，另外还有个主fly
method，根据鸟的fly类型在主fly method里调用不同的method；然后他告诉我应该定
义一个fly class.这个没答好
2.basic questions: deadlock, how to synchronize, database join,
singleton 这个基本不难，就问的点比较杂
第三轮：1.has a Random5() which generate random number from 1-5. Write a
function generate 1-125
我的code:
int Random125(){
int result=0;
result+=25*(Random5()-1);
result+=5*(Random5()-1);
result+=(Random5()-1);
if(result==0)
return 125;
return result;
}
然后这面试官又说我这个不是evenly random，说中间的数出现的多，两边的数出
现的少。。我擦，这不可能啊。。解释了很久面试官不信不耐烦了搞下一题了
2.问我怎么处理推特这样的大规模读写数据的请求，系统设计吧相当于。
最后说到cache上，我拿LRU解决的，所以就implement LinkedHashMap，然后写
了个LRU算法。。最后问还有没有改进
这个我基本都答上来了，还行
间隔着问些简历上的东西，我就不说了
CEO review,希望不出什么意外= =！
Thursday, November 6, 2014
1. 给一个二叉树 返回镜像 (Binary Tree Mirror)
2. Implement a thread-safe blocking queue.
3. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
4. 给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？我先说
HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。不知道
还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING ALGORITHM
好象不是很合适吧。
5.后缀波兰表达式STRING转换为中缀表达式的STRING。
这题本来很简单，但我可能算错了。纠结的地方是a,b,+,c,/
到底是 (c/(a+b)) 还是 ((a+b)/c)
6. Implement pow(double a, int b)
7. 接着给Amazon的favorite, 2-sum to fixed number, 我不喜欢写这个题。就直接告
诉他：两种答案，hashtable, 2个指针，我都写过，你要哪种？他挺理解，说，既然你
写过，给我讲一下性能差别，然后就放过了。
8. 算逆波兰表达式。又是一个细节题，我知道会写错。小心翼翼地写，一边写一边解
释，最后还是有小错。
9. 判断一个input string是不是valid number
10. Implement List Interface.
11. Search a 2D sorted array
12. coding就问了在数组中那个查找那个出现概率不小于1/2的数。后来做延伸到找K个
这样的数，不过那个面试者显然搞错了，说要求找top K个出现次数>=N/K (N是数组大
小)的数，这样唯一可能性就只有K个数每个都出现N/K次。开始被让晕了，后来发现这
个问 题。
13. 给两个已排序数组，要求返回他们的交集和并集.我就用两个指针分别指向两个数
组，从左向右扫一遍.我也说了hash的方法.对方又问能不能用merge的方法，我回答能
，但是不觉得复杂度更低。
14. 题目描述起来很简单，就是给出一个数，找出所有Unique的组合。 比如： 2 ：
１＋１
３： １＋２， １＋１＋１
４： １＋３， １＋２， １＋１＋１＋１， ２＋２
15. 2. 数组连续最大和,
上面的都回答完后，还有不少时间，又让实现最大乘积，这个没做好。从来没写过，现
写的时候出了不少问题，最后也只是写了个主体,我说 有些细节我没时间了，说说得了
。感觉面试官也没什么idea，因为我问她0的情况你觉得怎么处理好，她也只说了些需
要reset什么的。有空准备写一下这个。整体感觉还可以，如果因为这个题就悲剧了也
没什么好说的。
16. /** Compute the value of an expression in Reverse Polish order.
Supported operators are "+", "-", "*" and "/".
* Reverse Polish is a postfix mathematical notation in which each operator
immediately follows its operands.
* Each operand may be a number or another expression.
* For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be
written as 4 1 + 2 * or 2 4 1 + *
Calculate value? we use stack to do
17. search in transposed array
18. 两种方法写Singleton
19. 问了Mutex, Semaphore
20. implement memmove(void* src, void* dec, size_t num_bytes)
21. 输入是个stream
class input_stream
{
// Character or -1
int read();
}
每次call read（），返回一个char，如果到头了就是返回-
21. Roman To Integer
22. Text Justification
23. String to integer
24. Insert interval
25. Celebrity Problem
2. Implement a thread-safe blocking queue.
3. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
4. 给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？我先说
HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。不知道
还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING ALGORITHM
好象不是很合适吧。
5.后缀波兰表达式STRING转换为中缀表达式的STRING。
这题本来很简单，但我可能算错了。纠结的地方是a,b,+,c,/
到底是 (c/(a+b)) 还是 ((a+b)/c)
6. Implement pow(double a, int b)
7. 接着给Amazon的favorite, 2-sum to fixed number, 我不喜欢写这个题。就直接告
诉他：两种答案，hashtable, 2个指针，我都写过，你要哪种？他挺理解，说，既然你
写过，给我讲一下性能差别，然后就放过了。
8. 算逆波兰表达式。又是一个细节题，我知道会写错。小心翼翼地写，一边写一边解
释，最后还是有小错。
9. 判断一个input string是不是valid number
10. Implement List Interface.
11. Search a 2D sorted array
12. coding就问了在数组中那个查找那个出现概率不小于1/2的数。后来做延伸到找K个
这样的数，不过那个面试者显然搞错了，说要求找top K个出现次数>=N/K (N是数组大
小)的数，这样唯一可能性就只有K个数每个都出现N/K次。开始被让晕了，后来发现这
个问 题。
13. 给两个已排序数组，要求返回他们的交集和并集.我就用两个指针分别指向两个数
组，从左向右扫一遍.我也说了hash的方法.对方又问能不能用merge的方法，我回答能
，但是不觉得复杂度更低。
14. 题目描述起来很简单，就是给出一个数，找出所有Unique的组合。 比如： 2 ：
１＋１
３： １＋２， １＋１＋１
４： １＋３， １＋２， １＋１＋１＋１， ２＋２
15. 2. 数组连续最大和,
上面的都回答完后，还有不少时间，又让实现最大乘积，这个没做好。从来没写过，现
写的时候出了不少问题，最后也只是写了个主体,我说 有些细节我没时间了，说说得了
。感觉面试官也没什么idea，因为我问她0的情况你觉得怎么处理好，她也只说了些需
要reset什么的。有空准备写一下这个。整体感觉还可以，如果因为这个题就悲剧了也
没什么好说的。
16. /** Compute the value of an expression in Reverse Polish order.
Supported operators are "+", "-", "*" and "/".
* Reverse Polish is a postfix mathematical notation in which each operator
immediately follows its operands.
* Each operand may be a number or another expression.
* For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be
written as 4 1 + 2 * or 2 4 1 + *
Calculate value? we use stack to do
17. search in transposed array
18. 两种方法写Singleton
19. 问了Mutex, Semaphore
20. implement memmove(void* src, void* dec, size_t num_bytes)
21. 输入是个stream
class input_stream
{
// Character or -1
int read();
}
每次call read（），返回一个char，如果到头了就是返回-
21. Roman To Integer
22. Text Justification
23. String to integer
24. Insert interval
25. Celebrity Problem
Subscribe to:
Posts (Atom)