发现一个有趣现象# PDA - 掌中宝
t*s
1 楼
找工作算告一段落了，这一个多月从版上学到了很多，非常感谢大家，也分享点儿自己
的情况。本人cs fresh phd，投了F和G，准备主要是leetcode，做了50题左右，还有就
是板上的面经。强烈推荐leetcode，特别是对于准备时间有限的同学，基本覆盖了各式
各样的题。虽然最后面试没遇到做过的coding题，但基本都差不多。
0. 给定一个双向链表，以及一个数组。数组里存着一部分链表节点的指针。问数组里
的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
怎么做。算法复杂度分别是什么。
1. coke machines。大中小三个可乐机，每按一次出可乐量分别在[Amin,Amax], [Bmin
, Bmax], [Cmin, Cmax]之间，但不能确定具体容量是多少，现在想通过按这三个可乐
机，达到容量为[D, E]之间的可乐，问能否做到。也就是能否找到非负整数x, y, z使
得x*Amin+y*Bmin+z*Cmin>=D并且x*Amax+y*Bmax+z*Cmax<=E。感觉是个扩展的背包问题
，我给了穷举法和DP的解法，不过面试官最后说有个复杂度不依赖于D和E的解法，现在
也不知道怎么做。
2. 二叉树遍历。每个节点有left/right/parent指针，只允许使用O(1)空间而不用栈。
3. 含有大量URL的文件里查找频率最高的K个URL。先给单机哈希表的解法，内存不够的
情况，给了按哈希值把大文件拆成小文件的解法。接着被问并行化，给了MapReduce的
解法。接着被问哈希表相关的计算题，M个slots的哈希表（哈希值范围是1~M，用链表
处理冲突），往里放了N个元素，假设他们的哈希值是随机的均匀分布，问slots里元素
个数的分布，也就是balls and bins的问题。不用coding。
4. 链表的插入，删除等，基本没算法，而是看coding的细节。
5. 多线程和多进程。包括哪些状态是线程间共享的哪些状态是每个线程自己的等等。
不用coding。
6. 设计题。设计web crawler。包括网页的存储，crawler任务调度等。不用coding。
package方面F和G差不多。
G: 127k base, 15% bonus, 45k sign-on, 300 GSU.
F: 130k base, 10% semi-annual bonus, 100k sign-on, $180k RSU.
祝大家面试顺利拿到好offer！
的情况。本人cs fresh phd，投了F和G，准备主要是leetcode，做了50题左右，还有就
是板上的面经。强烈推荐leetcode，特别是对于准备时间有限的同学，基本覆盖了各式
各样的题。虽然最后面试没遇到做过的coding题，但基本都差不多。
0. 给定一个双向链表，以及一个数组。数组里存着一部分链表节点的指针。问数组里
的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
怎么做。算法复杂度分别是什么。
1. coke machines。大中小三个可乐机，每按一次出可乐量分别在[Amin,Amax], [Bmin
, Bmax], [Cmin, Cmax]之间，但不能确定具体容量是多少，现在想通过按这三个可乐
机，达到容量为[D, E]之间的可乐，问能否做到。也就是能否找到非负整数x, y, z使
得x*Amin+y*Bmin+z*Cmin>=D并且x*Amax+y*Bmax+z*Cmax<=E。感觉是个扩展的背包问题
，我给了穷举法和DP的解法，不过面试官最后说有个复杂度不依赖于D和E的解法，现在
也不知道怎么做。
2. 二叉树遍历。每个节点有left/right/parent指针，只允许使用O(1)空间而不用栈。
3. 含有大量URL的文件里查找频率最高的K个URL。先给单机哈希表的解法，内存不够的
情况，给了按哈希值把大文件拆成小文件的解法。接着被问并行化，给了MapReduce的
解法。接着被问哈希表相关的计算题，M个slots的哈希表（哈希值范围是1~M，用链表
处理冲突），往里放了N个元素，假设他们的哈希值是随机的均匀分布，问slots里元素
个数的分布，也就是balls and bins的问题。不用coding。
4. 链表的插入，删除等，基本没算法，而是看coding的细节。
5. 多线程和多进程。包括哪些状态是线程间共享的哪些状态是每个线程自己的等等。
不用coding。
6. 设计题。设计web crawler。包括网页的存储，crawler任务调度等。不用coding。
package方面F和G差不多。
G: 127k base, 15% bonus, 45k sign-on, 300 GSU.
F: 130k base, 10% semi-annual bonus, 100k sign-on, $180k RSU.
祝大家面试顺利拿到好offer！
