狗家面经 求解答

Job Hunting Interview
, , , , ,
1

发一个狗家onsite， 顺便求一些最优解答

  1. text editor， movecursorright(), movecursorleft(), insertcharacter(), backspace(). Follow up, undo
  2. valida parenthesis, 给一个N，代表parenthesis的个数，求所有valid结果
  3. lowest common ancestor， 给一堆nodes，包含node.mom, node.dad. 求找到两个noodeA, nodeB有没有血缘关系。 （求个最优解法， 我答得是找到所有A的ancestor放到map里， 然后recursive搜索B的ancestor，如果在map里就有关系。感觉不是最优）
  4. triple booking， boss的schedule是listofinterval[10:00-12:00, 9:00-11:00, 11:00-12:00], 可能有许多重叠。 然后你有only 1 interval [start - end], 求你的interval跟boss的schedule有没有triple booking出现 （boss本身triple booking的不算）。 也求个最优解吧
2

第四题可以用lc的我的日历做？

3

第一题双向链表，第二题蠡口廿二，第三题不是树所以感觉没有更好解法了

4

第三题可以 union find?

5

第三题我觉得可以用bi-direction BFS来做。先遍历A再遍历B的问题是会加入多余的node。用两个hash table分别存A的BFS外围和B的BFS外围，双方交替扩展并更新自己的外围hash table，如果发现外围有重合则返回true。时间复杂度应该是差不多的，但是可能会更快些。

6

请问第四题的triple指什么呀 重叠?