狗家l3 MTV onsite面经

最近在等transfer，报一个狗家l3的onsite面经和timeline，希望对大家有用。也希望大家能给些大米啊！积分低得无法看帖回帖啊
11/13 onsite11/18 过HC
11/21 team match 成功
11/22 收到offer （详情：）

四轮coding + 一轮behavior，全程被要求写c++，可能因为我的工作主要是c++，最后match的也是c++的组

第一轮：感觉很高级一个的三哥。很nice
给一个file，file的每行代表 parent id， child id， value。指代一个树里一个node的关系。要求建一个forest然后forest里每个tree都valid
首先是设计一个class存这些信息，写一个member function读file然后建forest。建树的时候要考

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

rt做了

总之就第二轮感觉很糟糕因为要了很多hints，followup也没写完，当时觉得很不好，以为一轮游了，下午有点佛系。但hr说总体反馈不错，可能因为我一直全程保持职业微笑，强行尬聊最后被面试官放过。。。





补充内容 (2019-12-14 06:24):
补充：
第一轮： child id 就是 node 本身的 id
第五轮： array里的数字不重复

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

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

spirit_room 发表于 2019-12-15 08:07
个人感觉，就是对每一个prefix_sum放到一个multi set中，在放之前利用二分查找找lower_bound of prefix_s ...

这样可以处理array里面有负数的情况吗？第一问的时候用hashmap可以是因为求的是val = preSum - k, 正好。现在这个是所有小于 preSum - k 的值, 感觉不好找. example:

array:
[1, 3, -7,  9]
k: 2
preSum array:
[1, 4, -3, 6]

如果preSum处理到最后一个元素， preSum =6, val  = preSum - k = 4，你找到lowerbound是4 （index : 1）, 然后怎么做？

xuzhenzhen2real 发表于 2019-12-15 13:47
明白了明白了，谢谢！请问一下multiset是怎么维护顺序的？每次有新的presum的话是logN插入的吗？我用的是 ...

我发现multiset中是没法进行iterator 加减法的，也就没法快速求出在这个iterator后边有几个数字。那这个题也只能自己维护一个二叉树了，树的节点中要记录右子树的元素个数，这样在查询的过程中能计算出大于某个数的元素个数。整体感觉有点麻烦，还不如直接brute force了

感谢分享，请问楼主，第五轮第一题前半部分的数字和后半部分的数字有可能重复吗或者还有没有别的什么约束条件？

几年经验？

第二题好像很简单

第一题中有parent id和child id，但没有自己的id怎么处理？难道每个的node的value是不一致的？

spirit_room 发表于 2019/12/14 05:11:57
第一题中有parent id和child id，但没有自己的id怎么处理？难道每个的node的value是不一致的？

啊，child id就是node自己的id，我没说清楚，sry

spirit_room 发表于 2019/12/14 05:02:19
第二题好像很简单

是啊，当时一时没想到用hashmap，没有用最优的方法做出来。面完以后觉得凉了半截

yangmyfly 发表于 2019/12/14 04:38:10
几年经验？

面的时候1.5年

帅帅的哭豆包儿 发表于 2019/12/14 04:35:59
感谢分享，请问楼主，第五轮第一题前半部分的数字和后半部分的数字有可能重复吗或者还有没有别的什么约束条件？

是没有重复的～～～其他好像没有了

请问楼主如果第二题follow up less than k怎么做？没想到O n的解法，谢谢啦～