Yelp phone + onsite面经

原帖地址:mitbbs

这周二的时候onsite的。

phone是skype面,一位白人,预定是45分钟。先聊了30分钟简历,然后面试官给了一题
Anagram,很简单,用python解了。followup是不用sort,如何判断两个string是不是
anagram,用int[256]就可以。

Onsite面,先是recruiter带着参观了公司10分钟。

Onsite第一面,印度小哥,说是做transaction的,给了一道fib,分别写了递归和迭代
解,然后问了各自的时间复杂度,空间复杂度。下一道题是power set,求是否存在一
个power set满足某个sum,因为整个set都是正数,所以可以剪枝,然后问了一下时间
复杂度。因为做得比较快,小哥有给了一道sqrt,我给了两个解法,一个二分,一个牛
顿法。印度小哥很满意,问了一下问题就离开了。

Onsite第二面。给一个map,key是class,value是一个list,list里包括这个class对
应的所有lectures的时间段。然后再给一个class的list,求是否能在这个map里,对每
个class至少找到一个时间段,而且各时间段之间不冲突。
比如{'class100':[1-2,3-4], 'class120':[1-2]},那么可以挑class120的[1-2]和
class100的[3-4],他们之间互相不会有冲突。DFS解就可以了,但这一面面得不太好。

Onsite第三面,给两个function, 一个decode(str) -> int,一个encode(int) -> str
,字符串只包含字母和数字。然后写一个function,tryDecode(mutated_str) -> int
,输入是一个经过变化的str,所有的字母都变成了小写。用这个mutated_str去还原之
前所有可能的字符串,然后尝试decode,如果decode都不成功返回-1, 如果有任一成功
就返回这个int。用DFS解就好,最后问了一下时间复杂度。

Onsite第四面,一位白人资深经理。先问简历,问之前Project。然后给了一个简单的
DB设计,many To many。下一题是,先说了tail的工作原:使用fseek到文件末,然后往
回走到需要的行数,再打印出最后的几行。共有fseek, fsize, fgetch可以使用,
fgetch是返回下一个char,并且cursor往下走一个。使用这三个function,从一个很大
的(Tb, Pb)的文件里随机返回一行。所有行之间能被返回的概率可以不等,但每一行都
有被返回的概率。

总体感受:他家氛围比较安静。祝各位好运!