狗家面经 求解答

发一个狗家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的不算)。 也求个最优解吧

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

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

第三题可以 union find?

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

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

弱弱的问一下LZ,第一题是啥意思?是要设计一个stream么?还是设计一个图型界面的cursor,x,y 坐标之类的?

我也感觉第三题union find。 分别维护dad表和mom表, 判断a和b关系要做两个表的find 有关返回true

第四题可以参考我的日程表2吧, 先存上boss的schedule重叠的部分, 然后把你的schedule扔到boss重叠表中做个binarySearch。 希望大佬指正。。。。

第四题是问true or false,最优解应该是用interval tree解决