人在英国，申请的是美国的Research Scientist (System & Infra) - PhD grad
据说跨国申请需两轮店面
店面1 天竺小哥做dating app的
蠡口伊久酒
蠡口爸爸
店面2 又一个天竺小哥
蠡口伊期仨
Follow up: 普通树怎么办，有parent指针怎么办
在伦敦的onsite
三轮轮coding一轮design
面试1 bq+coding
可是面试官突然生病没办法来，于是被coordinator临时找了个面试官把bq面试移到了下午最后一场
于是被HR带着在脸书大楼里面闲逛了45分钟
面试2 coding 巴西小哥
Print a linked list in reverse order, you can’t change the linked list
- 先给出Time O(n) Space O(n) 的方法 - 用栈
- 再给出 Space O(1)的方法，时间复杂度 O(n^2). 1point3acres
- 如果内存容量有限，假设为k，k<n, 那么怎么最快实现算法
中午俄国小哥带着吃饭
面试3 coding 英国小哥
Coding 1:
Coding 2:
蠡口 340: Longest Substring with At Most K Distinct Characters
面试4 design 波兰妹纸
Design an API that returns 20 nearest places near you. 100M places and 100M users.
面试5 迟来的bq 英国绅士大叔 （能看出来是临时找的）
本以为会被问到coding，结果他说他没有准备问题，就全部闲聊bq吧
- 如果内存容量有限，假设为k，k<n, 那么怎么最快实现算法
是不是先存a个Node, 每个Node间隔(k-a), 然后再用(k-a) size 的 stack 遍历? runtime 是 O(n)
我的解法是使用k个checkpoint，每隔[n/k]存到栈上，每次从前一个check point遍历到目前的check point，时间复杂度是 O((n/k)^2)*O(k) = O(n^2/k) = O(n)*O(n/k) 所以比线性的稍微差一点
请问下这么做的原理是什么 ？ 因为内存小于链表长度 每次就只能load一部分链表吗？这样的话就应该从最后一个segment开始
load 进内存然后倒序输出？
另外得到这k个checkpoint也需要遍历链表吧？
原理就是最大限度使用栈的空间吧，记住之前我来过的node，具体步骤是：
第一步：遍历链表并每隔m个node就push到stack上，时间复杂度 O(n) 空间复杂度 O(n/m)
第二步：每次从stack上pop出一个node，并记住前一个checkpoint，调用 slowPrint(current, prev) O(n/m)
slowPrint: 第一次跳m次到最后，第二次跳m-1次，第m次跳0步，时间复杂度 O(m^2)
所以总共时间复杂度 O(n)+O(n/m)*O(m^2) = O(mn) or O(n^2/k)
请问楼主 sys & infra 的research scientist 面试有问专业相关的问题吗？还是主要是coding
另外这个职位只招new graduate吗 做过postdoc的可以申请吗
我目前就是postdoc，申请的是new graduate，可能是因为我做postdoc时间不长吧。。
不过onsite的BQ那一轮会问为什么不继续做postdoc而选择facebook，我的回答是industry的平台更大视野更广更适合我做研究
他们没有问专业相关的问题，毕竟面试我的人都是其他领域的engineer，所以基本上都是general coding