Google ONSITE + timeline

timeline: 8/26内推,9/5 hr 联系约chat,9/13chat之后发了oa,9/15做oa,9/16过oa,安排onsite,10/14 onsite,10/21 收到邮件过hc

1.给一个tree,每个tree有一个char value,和一个string,找到tree里面所有有这个string的node。followup:求一个graph里,edge可以正或者负,startnode到endnode的最小cost ,只要说出算法名。
2. 一个unsorted array, 可以做K个operation,operation可以从前pop,从后pop,要求pop出来的k个数sum最大。followup,如果再给个k长度的list,每个element代表一个weight,怎么求最大的weight*element
3. 电脑传染问题,所有电脑都被传染了,每天每台电脑可以传染左右两台电脑,给一个solution,每天只能clear一台电脑,判断这个solution是否有效。follow up:如果只有一台电脑被传染了,它每天会random传染左右两边的随机一台电脑,判断这个solution是不是无论如何都有效。
4. 给一个board,和所有valid word的坐标,然后找到一条路,用所有valid word组成可以正好覆盖整个board