🐶两轮店面，新人求大米准备VO，么么哒

楼主面的L4，两次店面分别在二月底和三月初。


共有两题，第一题没刷到过，题目又比较fancy，所以懵逼了，全程被面试官牵着鼻子走，虽然最后code写出来了，但全程不确定这个算法能够解出来。感谢天，感谢地，因为一开始有technical issue，HR又给了我一次店面机会。
第二题也没用弄出最优解，写了一个workable solution之后跟面试官讨论优化到最后一秒，也没真正想出来。

==================
1. 给一个树，也可以说是图，每次删除这个图上的一个叶子节点，并把跟这个叶子节点相连的父节点放到一个数组中去，直到这个图只剩下两个节点，就不再删除。问题是给这个数组，反向推导出图的结构。
这个题是刷题网 散摇铃 的反向版本，但是那时候我还没有刷到。一旦想清楚怎么做之后，代码实现并不难。但当时我整个人都不好了，被可以用少量的信息得到更多的信息这件

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

这么复杂的代码我可写不了，有点泄气，时间到了就不了了之了。事后不抱希望，没想到可以move on。




补充内容 (2022-04-03 06:20 +8:00):
刚刚发现，第二题是 刷题网 义务无私 ，一道会员题

匿名者 发表于 2022-3-24 14:27
楼主能讲下这题的思路吗 还有删节点的规则是按编号从小到大删么？ 比如说有N个点，就以1,2,3..N-2的顺序 ...

这也是我面试的时候困惑的点，不知道这个算法每次删哪个叶子节点。我当时问这样的树是不是有很多种，他说是的，只用返回其中一个就好了。事后觉得题目只用恢复树的结构，不用恢复编号？

面试官引导的算法是，input list里面的元素一开始是parent，到某种程度就会变成叶子。两个步骤：
1.先找初始叶子节点（最外层的叶子），把最外层的叶子和它们的parent连起来。
2. 关键是如何找到内层叶子节点，可以用一个counter对input list里面的element计数，每将一个元素和叶子连起来，counter减1，当counter为0的时候，说明这个parent变成了新的leaf，把它加到leaf sets里去。直到看过所有的input list里的元素，这时候leaf sets里还有两个点，就是最内层的两个节点。

代码并不复杂。甚至回过头来想也并不难……但就是当下想不到。可以看刷题网 三衣领 的题解，非常算法之美了。

匿名者 发表于 2022-3-23 08:17
恭喜贺喜!
第一题能否给个例子?我也被震撼了,感觉这不就是leetcode 的树初始化吗? 我知道有几个版本, # 代 ...

"""
N = 7, 树有7个节点，编号为1-7，一个删图的算法如下。
1. delete 1
    1-----5-----6------7-----4  [5]
              |        |
             2       3

2. delete 2
             5-----6------7-----4      [5, 5]
              |        |
             2       3

3. delete 3
             5------6------7-----4     [5， 5， 6]
                        |
                       3

4. delete 4
                5------6------7-----4    [5， 5， 6， 7]
                    
         
5. delete 5
                5------6------7             [5， 5， 6， 7， 6]

6. stop
                          6------7             [5， 5， 6， 7， 6]

现在给出[5， 5， 6， 7， 6]这个数组，要求恢复原始树结构。

第二题遍历每个word，依次把每个字符换成特殊字符比如 “*”， 存入hash table， check 之前有否出现过。 如果完全一样的word不算， 可以先set 一下数列。

恭喜贺喜!
第一题能否给个例子?我也被震撼了,感觉这不就是leetcode 的树初始化吗? 我知道有几个版本, # 代表空子节点. 现在狗家的倒置树一定忽略了一些情况吧?

匿名者 发表于 2022-3-23 12:58
第二题遍历每个word，依次把每个字符换成特殊字符比如 “*”， 存入hash table， check 之前有否出现过。  ...

结束之后我想到了这个解法，但是跟我这个解法时空复杂度还是一个量级的，不知道有没有更好的

匿名者 发表于 2022-3-23 12:09
"""
N = 7, 树有7个节点，编号为1-7，一个删图的算法如下。
1. delete 1

楼主能讲下这题的思路吗 还有删节点的规则是按编号从小到大删么？ 比如说有N个点，就以1,2,3..N-2的顺序删？

匿名者 发表于 2022-3-23 09:58
第二题遍历每个word，依次把每个字符换成特殊字符比如 “*”， 存入hash table， check 之前有否出现过。  ...

这个空间复杂度会不会太大了