狗家onsite挂经

cszhazha 发表于 2017-12-2 14:44
第一题
很直接的解法，优化循环情况

你说的情况是循环的一种，这种情况下确实可以直接退出循环

最后一个概率题可不可以用二分查找法，每次取中间点，然后生成随机数。如果是0就往左继续做，1就往右，直到上下标重合返回

如果概率是p不是50%的话，就取距左边界距离与上下标之间总距离之比为p的点来做

补充内容 (2017-12-9 01:56):
我错了，应该不行……

“脱了高跟鞋，把脸埋在膝盖里哭了一会儿” ----- 看着心疼。

请问lz是收到hr update了吗 地里很多人都说感觉不好最后都有offer了的情况也不少 所以不要那么快灰心

父子结点赋值的follow up可以用topological sort，没有父结点的值不变，加到队列，把队列中结点的子结点的父结点数减1，减到0后子结点也加入队列，同时比较父子结点的值，保证子结点比父结点值大即可

lz 有点当年班里第一名 经常考完说 哎，，考的很差 考的很不好。然后哭一下，到最后 回回是第一的感觉 。 funny

dongsancu 发表于 2017-12-9 03:42
父子结点赋值的follow up可以用topological sort，没有父结点的值不变，加到队列，把队列中结点的子结点的 ...

我觉得拓扑排序可以！不过可能是我理解的不太对，能请问一下这个和层级遍历记录父节点的优势吗？层级遍历也是要查每一个父链接的edge，这个也是要查每一个edge，如果一个图每个节点都有巨多父节点，好像还是时间复杂度很大？

dongsancu 发表于 2017-12-9 03:42
父子结点赋值的follow up可以用topological sort，没有父结点的值不变，加到队列，把队列中结点的子结点的 ...

不是说没有指向父节点的指针吗。。这个咋搞，如果有指向父节点指针，BFS, DFS都行双向扫一遍

cammilajiang 发表于 2017-12-9 04:27
我觉得拓扑排序可以！不过可能是我理解的不太对，能请问一下这个和层级遍历记录父节点的优势吗？层级遍历 ...

图遍历anyway你都要visit每个edge和node的 不管是BFS DFS复杂度都是V+E

You did pretty well I think your offer is on the way