今天刚收到recruiter电话说过了hc，上来发个timeline和面经
Timeline
9/16 Refer
9/27 OA
10/19 Schedule Onsite
10/31 Onsite
11/16 HC
-
给你一个chatting log file，format大概是这样的：
A: bla
B: bla bla. 1point3acres
C: bla bla bla. check 1point3acres for more.
要你找出说话最多（看word number) 的K个人
而且代码要从读file开始写 -
给你n个log file, 里面每一行的格式都是 timestamp: content （timestamp是从小到大排好的）
现在让你把这n个log file合并成一个大log file（也是要timestamp从小到大排）
限制条件就是content很大，每个log file也很大 （不能全部读到memory里面）
这一题你就可以assume一些function存在，比如readTimeStamp，copyContent之类的，只要跟面试官解释清楚这个function的作用就好. check 1point3acres for more. -
一个类似24点的游戏，假设牌桌上有无数张1-10的牌，然后你手上的牌的总和是k，现在你可以随机到牌桌上抽牌加到总和里，如果你手上牌的总和在20-25之间就是win，如果总和超过25就是lose，现在让你求lose的概率。
这一题我好像在地里见到过但是当时那个楼主说他没有做出来，所以我就也附上一下我的大概解法。
首先因为每张牌都是无数张，所以抽任何一张牌的概率都是0.1。然后就是要考虑到有很多重复的情况，所以用dp或者recursion with memoization其实都可以。
我是用dp做的，从后往前推，所有的结束可能就是20 - 29 其中P(20)到P(25)= 0， P(26)到P(29) = 1。那么P(19) = 0.1P(20) + 0.1P(21)+… 以此类推，最后算到P(k)
followup：假设每张牌是n张
这就比较麻烦了，因为抽牌的概率跟当前牌桌上每张牌的数量有关，所以用dp比较难做，我就改用recursion with memoization。不仅要存手上牌的总和还要存牌桌上每张牌的数量。 -
给你一串input，比如：
A -> B
B -> C
X -> Y
Z -> X
。
。
。
然后让你设计一个data structure来存这些关系，最后读完了以后呢要输出这些关系链：[A -> B -> C, Z -> X -> Y]
如果遇到invalid的case就直接raise error，比如你已经有了A->B->C，这时候给你一个D->C或者B->D就是invalid的。
followup我感觉就是他看你什么case没有cover就提出来然后问你怎么改你的代码和data structure
比如遇到A->B两次，再比如遇到环
这题相当开放，面试官说他遇到过4，5种不同的解法，总之就是最好保证insert是O(1), reconstruct是O(n)
最后祝大家都能有好消息！
补充内容 (2018-11-19 01:02):
第四题好像说是关系链有点误导大家，它题目的意思更像是directed graph，然后每次读进来的都是一条edge，要求是你的graph里只能有链条，不能有branch，不能有cycle，所以假设你有A->B->C，这时候又来了一个A->C算错