狗家新鲜面经

刚刚面完的狗家ng，发个面经攒攒人品

1. BQ轮，三个问题，每个都会有一两个followup，主要的主题就是teamwork和best project
2. 一种比较特殊的tree，没有left和right，只存着parent

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

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

好累，到最后脑子已经混沌了。遇到的几个面试官人都非常非常好，互动多，友好热情，stuck后会及时给hint。总体面试体验挺不错的。

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

是不是头和尾相同的dijkstra?

第三题感觉把64个cell放在list里，shuffle后分配一下应该就行了吧，follow up的话，就是四个角先random配对，然后是边上的点random 配对，然后所有点配好对后pair放进list里去shuffle，还是等分成四分应该就行了吧，就算是要scale up, 那肯定还是要给足够的空间存m*n吧

第三题我觉得可以这么搞

先分格子，后随机染色

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

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

楼主辛苦了

第四題可以麻煩再講清楚一點嗎? 是2D arrray裡不是0就是1嗎?

seamelody 发表于 2021-04-14 18:58:20
第四題可以麻煩再講清楚一點嗎? 是2D arrray裡不是0就是1嗎?

是的 只有0和1

赞一个很有用的信息！

Dawnwss 发表于 2021-4-15 10:14
是的 只有0和1

是 邀惡妻妻嗎?

seamelody 发表于 2021-04-14 19:18:50
是 邀惡妻妻嗎?

还真是 可惜我没做过哈哈

楼主辛苦了，给楼主加米了。

请问楼主第三题和followup什么思路？

第五题是有向图还是无向图？

多谢楼主

bigboss789 发表于 2021-04-14 19:35:43
楼主辛苦了，给楼主加米了。

请问楼主第三题和followup什么思路？

第五题是有向图

第三题非followup我用的是random.choice，followup没做出来（捂脸 如果有人有思路的话求解

请问第四题是lc的幺儿齐齐吗？