狗家l3 MTV onsite面经

xuzhenzhen2real 发表于 2019-12-15 13:55
最后一题是不是利口三三

最后一题是
1095. Find in Mountain Array

第四题能说详细点么，怎么插入node？

spirit_room 发表于 2019/12/15 15:21:47
第四题能说详细点么，怎么插入node？

就是一个方程，传入的是这个node的ptr，和一个value，要把这个value当作要插入的值。插入node的ptr在树里的相邻的右侧的位置～～我是遍历树的时候保持一个level的值就可以track这个ptr的右侧

spirit_room 发表于 2019/12/15 13:47:46
最后一题，感觉要搞3遍二分查找，第一遍找到peak，第二遍在前半部分找，第二遍在后半部分找，还有更好方法吗？

找右...

我当时也是这么做的啊，面试官貌似觉得okay就move到下一题了

spirit_room 发表于 2019/12/15 13:12:05
第一题跟leetcode 608有点像

请问楼主是怎么做的？怎么分出左右子树的，没提到是二叉树啊

啊，是我说错了，抱歉。应该是所有的子树，我当时做的时候也不小心当作左右子树了，面试官纠正了我哈哈

verse1994 发表于 2019-12-15 18:34
就是一个方程，传入的是这个node的ptr，和一个value，要把这个value当作要插入的值。插入node的ptr在树里 ...

右侧，是不是就是同一个父节点下当前node的右边兄弟节点？

spirit_room 发表于 2019/12/16 11:56:39
右侧，是不是就是同一个父节点下当前node的右边兄弟节点？

不是不是 是整个树同一个level的右侧 不一定是一个父节点～～

verse1994 发表于 2019-12-16 13:43
不是不是 是整个树同一个level的右侧 不一定是一个父节点～～

麻烦楼主问一下楼主，是不是原题只给了此节点，没给根节点，不然我只想到从根节点bfs比较简单些。。。这个follow up插入右边的话，要给新加入的点连接父节点吗？如果树没有children数量限制的话，直接在当前节点后加入一个node然后连接到同一个父节点是不是就可以了？但是如果是二叉树的话就需要建立一个linkedlist 然后一个一个改父节点和子节点（这样感觉array也可以了就），另外如果这层满了的话，要怎么操作呢？ 问题有点多，谢谢楼主啦

帅帅的哭豆包儿 发表于 2019/12/17 13:48:21

麻烦楼主问一下楼主，是不是原题只给了此节点，没给根节点，不然我只想到从根节点bfs比较简单些。。。这个follow ...

没关系！他说只能是二叉树，如果这层满的话就不能加了。这个是我在讨论corner case的时候提到的～～

verse1994 发表于 2019-12-17 16:37
没关系！他说只能是二叉树，如果这层满的话就不能加了。这个是我在讨论corner case的时候提到的～～

谢谢你的回复，麻烦再问一下，在右侧插入新的node 有没有什么好的方法来更新子节点和父节点的关系？还有如何更快速的判断这层是不是满了？