狗家新鲜面经

匿名者 发表于 2021-4-16 00:02
你说的那题的node里面有left和right，但是面试题里的node只有parent_index（就是这个node的parent的index

请问第一题是不是，就扫一遍array, 如果发现一个点的parent是在remove set里，那它就是一颗树的root。还有其他需要注意的吗？多谢。

匿名者 发表于 2021-4-27 03:15
请问第一题是不是，就扫一遍array, 如果发现一个点的parent是在remove set里，那它就是一颗树的root。还 ...

开始可能不是一棵树，所以要用union find找到所有的root，然后判断root要不要删，不要的加进去，然后就是你说的了，不知道还有没有漏啥

请问楼主最后面试结果怎么样？

匿名用户 发表于 2021-04-14 19:54:35
我用的是BFS，因为BFS第一个找到的cycle就是最短的（忘了说 一定是包含特定某个node的cycle

是不是头和尾相同的dijkstra?

第三题我觉得可以这么搞

先分格子，后随机染色

分格子的话，从四周向中间，一圈一圈来，每一圈一个一个来，然后选择横着或者竖着拓展。对于每一个格子，它的中心方向或者下一个格子的方向应该总有一个是available的？

补充内容 (2021-05-10 16:55 +08:00):
又想了一下，更好的方法是，从一个角开始，分层扫一横排和一竖排，随机分配第二个格子是更还是竖，如果最后一个格子是单个的，入侵下一层。
8×8的上边左边 -》7×7的上边左边。。。
唯一不可能入侵下一层的情况是2×2，（被另一个方向入侵下一层的挡住了）但这个是不可能出现的。
最后也不可能剩下一个单独的格子，因为棋盘是偶数的，剩最后一个说明之前剩了另一个，而这种画法之前是不可能剩另一个的。

匿名者 发表于 2021-4-15 10:54
我用的是BFS，因为BFS第一个找到的cycle就是最短的（忘了说 一定是包含特定某个node的cycle

请问下楼主如何用BFS找SHORTEST cycle的基础上，还要确定是否包含某个certain node啊。还有个问题就是如果shortest cycle不包含that certain node，那怎么找next larger cycle that might have that node呀？ 谢谢楼主~

bigboss789 发表于 2021-4-14 22:03
哦， 就是说题目指定比如说是从node 1出发，找最短的cycle吗？ 因为如果是有向图， 用BFS找cycle可能会出 ...

''因为如果是有向图， 用BFS找cycle可能会出问题。 如果一个node有两个indegree， BFS可能会误认为是cycle''

请问可以举一个有2个indegree的例子吗？不太理解为什么会影响bfs

fangzheng 发表于 2021-5-28 02:59
''因为如果是有向图， 用BFS找cycle可能会出问题。 如果一个node有两个indegree， BFS可能会误认为是cyc ...

这个题目我没太想清楚用BFS怎么找有向图的最短cycle。 BFS找cycle无非就是visit一个node，发现这个node是visited。那么就可能有圈。那么下面这个图:
0 -> {1,2}
2 -> {3}
3 -> {1}
图大概长下面这样。这个图其实是没cycle的。但是用BFS就会误认为有cycle。

0 -> 1
|       ^
|        |
2-> 3

还是说这里说的BFS其实是用Topo排序？  

请问这题你什么思路？

bigboss789 发表于 2021-5-27 21:26
这个题目我没太想清楚用BFS怎么找有向图的最短cycle。 BFS找cycle无非就是visit一个node，发现这个node是 ...

visited存一个map（node -> parent)

queue同理也存一个pair（self， parent）起点start第一次入队时parent标为null，出现环的条件是队内看到self==start && parent != null这样的一个pair

这个时候在visited中把这个环路的path找出来 bfs保证最短。

不知道这样是否make sense？