bm55755
(华晨宝马)
1
第一轮 东欧大哥 给定二叉树的root和level，假如在level上的节点从左到右是1,2,3,4 要求输出1 4 2 3. 我用的BFS, 要求不断优化空间复杂度，优化到最后是用双向链表。 最后五分钟的时候问了一个 follow up，如果每个节点都有一个parent指针，怎么在不用额外空间的情况下输出某一层的节点，好像BFS和DFS 都不是想要的答案 T T
第二轮中国小哥，给一堆connection，有朋友关系也有敌人关系，敌人的敌人也是朋友，然后给两个人 要要求出他们的关系。 我用的是hashmap 存双向的敌人的关系，这样就可以很快的求出敌人的敌人，在把所有的朋友关系用union find存。 最后小哥问能不能不存双向的敌人关系，没有想出好的方法
第三轮，青蛙过马路，马路上有车会过，青蛙可以选择待在原地，向前，向后，输出一个可能的过马路的方式，我用的DFS, 面试说可以有一helper返回某个时间某个位置是不是有车
第四轮, 中国小姐姐，贪食蛇
第五轮，经验丰富的亚裔大叔，讨论了很久简历，然后redundant connection II，我说可以用 union find 做，他说从来没有听说过，然后给他解释了一通，他表示可行，分析了下时间复杂度
Recruiter说feedback还可以，可以team match，希望team match能顺利
请问第五轮的输入是a list of directed edges还是undirected edges ?
请问第一轮BFS怎么做啊？难道需要 additional list先save 这层node 然后 再reorder ？
第二题请问需要考虑敌人的朋友或者朋友的敌人这样的关系吗
klz2468
(克鲁兹)
6
第二轮是不是就是高频汇率变形，直接floyd一遍？
朋友有传递性吗？就是朋友的朋友也算朋友吗
cf36987
(野火春风)
7
谢谢楼主分享。但第一题要求没看懂，假如树的第三层从左到右是1,2,3,4,5,6,7,8，输出顺序应该是什么？
bean
8
多谢分享.
第一题,保存当前level的所有节点,然后从两头取? followup看过几次了,感觉是按照某种特定顺序traverse.记录left访问过没有.
第二题,看起来跟汇率转换很像. 敌人之前就是-1,那么敌人的敌人就是-1*-1=1. 不确定是不是followup要问的.
第四题,是否是刷题网原题?
问下LZ,在职面试,recruiter有提说要面system design?
bm55755
(华晨宝马)
9
是 directed edge, redundant connection II
bm55755
(华晨宝马)
10
直接用 doublyLinkedList 替代Queue做BFS，遍历完 N - 1层的，第N层的Node就在doublyLinkedList里面了，然后再从左右两边交替取Node，都是 O(1)操作