求祝福， Google phone screen exposed# JobHunting - 待字闺中
g*u
1 楼
求祝福，刚面完Google第一轮。
电话面试没有NDA，所以把记得的题目记下来
太紧张了，发挥的很差。。。
Interviewer迟了3分钟， 没什么口音，估计是老美。面试一开始就上Google doc，
上来就要求写2个factorial的实现。
写了factorial的定义，马上写了个recursive的实现，说了边界检查，说了overflow，
然后开始写， 结果， 居然一急之下把base case给忘写了（哭死）。。。第二个写了
个iterative的实现，解释tail recursion可以马上改写成iterative的
接着是问一个非常大的文件里面有很多string，每行一个，问如何去重？ 说了hash和
sort的2种方法，比较了time and space complexity
接着是问了 set of strings, how to sort？问了memmory的限制，问了string的长度
分布，提出可以quick sort， 要求说明原理和时间空间复杂度，被追问还有其他方法
， 脑子犯傻，说了radix sort(大忌， 不要说自己不彻底清楚的东西)，说了基本原理
，但是在复杂度上说的是O(n),撞墙了，自己之前还说跟longest的string length成比
，但是复杂度上说是O(n)（应该是O(kn),k是longest的string的length）....
下一个问题debug，为什么程序里面加了printf的时候bug会消失？说了extra code会改
变code lay out，被追问其他原因，说了有可能overwrite return address， 接着依然被追
问，然后我问程序是single thread还是multi-thread，假设是multi-thread，说了一
通race condition的问题；
然后对方一阵敲字，安静15秒，他说自己在想问题（汗。。。）
下一个问题是假设有n个国家， 对应有人口；要求采样的出现比例如人口成比例--》马
上的想法是构建一个array，然后每个国家出现的次数与人口成正比，假设a国人口是b
国的3倍，那么a在array出现3次，b出现一次；然后在array里面uniform sampling就可
以；被追问如果a是b的2.5倍怎么办？ 马上提出第二方案，计算 population_i/sun_{
population_j}，然后利用一个在[0,1]间unifrom的rand来采样，解释了一回原理
下一个问题是 what will happen after we type in URL?
说了DNS的查询流程，说了packet的构成，几个header（ethernet,ip, tcp），问tcp
header里面有什么，接着问sequence number是干什么的（自己答的是reorder packets
,现在想起来可以用来cogestion control???），然后问的是http和https的区别是什么
，为什么是这样的...
结束了37分钟。。
最后就是我问问题结束...
求bless....
电话面试没有NDA，所以把记得的题目记下来
太紧张了，发挥的很差。。。
Interviewer迟了3分钟， 没什么口音，估计是老美。面试一开始就上Google doc，
上来就要求写2个factorial的实现。
写了factorial的定义，马上写了个recursive的实现，说了边界检查，说了overflow，
然后开始写， 结果， 居然一急之下把base case给忘写了（哭死）。。。第二个写了
个iterative的实现，解释tail recursion可以马上改写成iterative的
接着是问一个非常大的文件里面有很多string，每行一个，问如何去重？ 说了hash和
sort的2种方法，比较了time and space complexity
接着是问了 set of strings, how to sort？问了memmory的限制，问了string的长度
分布，提出可以quick sort， 要求说明原理和时间空间复杂度，被追问还有其他方法
， 脑子犯傻，说了radix sort(大忌， 不要说自己不彻底清楚的东西)，说了基本原理
，但是在复杂度上说的是O(n),撞墙了，自己之前还说跟longest的string length成比
，但是复杂度上说是O(n)（应该是O(kn),k是longest的string的length）....
下一个问题debug，为什么程序里面加了printf的时候bug会消失？说了extra code会改
变code lay out，被追问其他原因，说了有可能overwrite return address， 接着依然被追
问，然后我问程序是single thread还是multi-thread，假设是multi-thread，说了一
通race condition的问题；
然后对方一阵敲字，安静15秒，他说自己在想问题（汗。。。）
下一个问题是假设有n个国家， 对应有人口；要求采样的出现比例如人口成比例--》马
上的想法是构建一个array，然后每个国家出现的次数与人口成正比，假设a国人口是b
国的3倍，那么a在array出现3次，b出现一次；然后在array里面uniform sampling就可
以；被追问如果a是b的2.5倍怎么办？ 马上提出第二方案，计算 population_i/sun_{
population_j}，然后利用一个在[0,1]间unifrom的rand来采样，解释了一回原理
下一个问题是 what will happen after we type in URL?
说了DNS的查询流程，说了packet的构成，几个header（ethernet,ip, tcp），问tcp
header里面有什么，接着问sequence number是干什么的（自己答的是reorder packets
,现在想起来可以用来cogestion control???），然后问的是http和https的区别是什么
，为什么是这样的...
结束了37分钟。。
最后就是我问问题结束...
求bless....
