狗家onsite面经

接上个链接: https://www.1point3acres.com/bbs/thread-743843-2-1.html
感谢大家

4轮算法 + 1BQ
另外三轮的算法:

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

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

感觉第三题应该编码时候加上字符串的长度信息？就类似于尔期衣？

楼主这是妥妥的四道Hard。。。  就算是都做过每轮都很难写完啊。这面试也太坑了吧。。。

请问楼主，第一是先用dict里面的word建立trie， 然后进来一个word， dfs的方式去和trie里面所有的路径算edit distance， 小于K的放入Treeset里面排序？
第三题， serilize和deserlize的时候要character by character？

多谢楼主。

iSomnambulate 发表于 2021-04-07 11:32:07
另外想问下lz第一题用Trie为什么可以优化呀，感觉每次还是得遍历每个word来比较才行

如果两个单词w1和w2有共同prefix，那么他们和w3算edit distance的dp矩阵有大部分可以重用

请问线段那题有什么技巧吗

匿名者 发表于 2021-4-7 23:49
请问线段那题有什么技巧吗

线段这题应该就是range module

另外想问下lz第一题用Trie为什么可以优化呀，感觉每次还是得遍历每个word来比较才行

已加米。楼主是NG吗？这几道题可都够硬的

ydog5 发表于 2021-04-07 11:52:12
已加米。楼主是NG吗？这几道题可都够硬的

NG，面完整个人都木了

匿名用户 发表于 2021-04-07 13:55:50
NG，面完整个人都木了

不得不说狗家的题还是有点水平的。他这个follow-up也比较难答

匿名者 发表于 2021-4-8 04:47
如果两个单词w1和w2有共同prefix，那么他们和w3算edit distance的dp矩阵有大部分可以重用

soga，但是想想代码的复杂度，面试时间内要写完真的好难 ><等于两道hard combine了，要我就直接写遍历全部的然后口头跟面试官说说Trie的优化
还想问下那dp存哪里呢？我只能想到难道Trie的每个node都有一个对应的dp吗？如果这样岂不是空间复杂度挺高的