领英onsite

littlebearull 发表于 2016-9-28 19:29
请问楼主，第四题考虑这种情况吗？就是中间有些节点只有1个，2个或3个邻居。那样的话，就不能只根据一行的 ...

四种情况（只有一个，两个，三个，四个邻居）都有。但是你只用考虑一行（不断把当前行的上面一行和下面一行移到当前行的尾部）。每走到一个点，检测有没有上点，有的话加塞到当前点的右边，并把本来的右边连到加塞的右边。同理处理下点。

alucardzhou 发表于 2016-9-29 18:20
四种情况（只有一个，两个，三个，四个邻居）都有。但是你只用考虑一行（不断把当前行的上面一行和下面一 ...

不好意思，我还是不太明白。比如（参考下图）第一行，1-2-3-4，然后第二行的5-6-7-8，第一行和第二行之间，只有3和7相连。（1）。那怎么取第一行的下一行呢？难道从1遍历到3，然后取3的下邻居（即7），再由7向左遍历到5？但这样还是有问题呀，可能6和7之间不连通，7只能通过第三行的邻居比如10，通过9和6连通，那样的话，我觉得复杂度就太高了吧。
（2）。比如当前在第一行，到3的时候，已经把下节点7加入到结果中了，那既然已经把第二行加到4的后面了，那遍历第二行的时候，岂不是又重新遍历了一遍7吗？
问题有点多，还望楼主解答一下，多谢！
1--2--3--4
        |
5--6  7--8
    |   |
    9-10

假设从5开始
1--2--3--4
        |
5--6  7--8
    |   |
    9-10


1--2--3--4
        |
        7--8
        |
5-6-9-10

     1--2--3--4
              |
5-6-9-10-7--8


5-6-9-10-7-1--2--3--4-8
Done

littlebearull 发表于 2016-9-29 11:48
不好意思，我还是不太明白。比如（参考下图）第一行，1-2-3-4，然后第二行的5-6-7-8，第一行和第二行之间 ...

哦哦，你这是从1开始啊。
也一样
1--2--3--4
        |
5--6  7--8
    |   |
    9-10

1--2--3－7-8-4
     5--6 ｜
         |   |
         9-10

            5--6
                |
1--2--3－7-9-10-8-4

1--2--3－7-9－5-6-10-8-4

littlebearull 发表于 2016-9-29 11:48
不好意思，我还是不太明白。比如（参考下图）第一行，1-2-3-4，然后第二行的5-6-7-8，第一行和第二行之间 ...

其实不用太担心的，考官会给你足够的hint来指导你，点拨你。
只需顺着他的思路走下去，一般就会做通。
我做这题的时候就是在考官的循序善诱下完成的。
而且时间刚刚好。


当然有的考官也呵呵。
比如我面罗马数字那题，那考官一开始说数字上限是九千九百九十九.

我说，大哥我书读得少，你别骗我。请你教我写一个过四千的.
他写了两笔，发现确实不对劲。就把上限改正常了。

alucardzhou 发表于 2016-9-30 01:38
哦哦，你这是从1开始啊。
也一样
1--2--3--4

从倒数第三步开始，7下面连着10，为什么后来就变成7-9-5-6了呢？从第二步，按您之前说的，不断地取上一行和下一行放在行尾，因为1和2没有上下邻居，所以在3处，取得下一行即为7，那就是说，要根据7来遍历第二行，对吧。但是7跟6不连通，所以还要继续找7的下邻居10. 也就是说，我们不一定能实现按行遍历，因为这取决于节点之间的连通性。比如，6和7如果连着的话，那我们是可以根据7来遍历第二行的。但楼主又说，在每个节点处，要查看其上下邻居，也就说，到7的时候，即使6和7连通，我们也还是先选择10。那如何确保每个节点只被遍历了一遍呢？还是所，在遍历的过程中，要随时更新每个节点的4个邻居？
我今天脑子可能进水了，就纠结在这道题上了，就是想不明白，哎。。。。

littlebearull 发表于 2016-9-29 19:59
从倒数第三步开始，7下面连着10，为什么后来就变成7-9-5-6了呢？从第二步，按您之前说的，不断地取上一行 ...

你给的例子是特别情况，即时它们（5-6 还有7-8）看起来在同层，由于被切断了。我们只能分别处理。
说更详细就是，每次只处理，上指针所指链的“左端”到“右端”，以及下指针所指链的“左端”到“右端”
处理方法都试切下来，放在当前点和其next之间。

alucardzhou 发表于 2016-9-30 09:20
你给的例子是特别情况，即时它们（5-6 还有7-8）看起来在同层，由于被切断了。我们只能分别处理。
说更 ...

嗯嗯，是的是的！太感谢楼主了！解释得非常详尽，原谅我迟钝的大脑，

patpat，楼主已经非常厉害了，没想到是这样的结果。Linkedin找人的bar是有多高啊，

littlebearull 发表于 2016-10-7 10:51
patpat，楼主已经非常厉害了，没想到是这样的结果。Linkedin找人的bar是有多高啊，

其实更多觉得是没和面试官看对眼。