狗家新鲜现场

狗家新鲜现场表演，求加米～

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

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

狗家面试给人体验很一般，算法每轮45分钟，面试官大概率会迟到几分钟然后再问一堆问题，真正做题的时间其实不多。不过面试官也是流水作业也可以理解吧。

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

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

第四题如果我没理解错的话，是一个二维数组对吗？
每一行是正方体的所有的字符。也就是每一行里面只能挑一个字符使用。

dfs可以优化的点是：
先build一个map: 字符->vector of row idx
对应每个字符，在那些row出现。

然后dfs的时候就可以剪枝(先挑出现行数只有1的字符)
以及有了map, dfs就不必遍历所有的情况。

hsierra 发表于 2020-11-6 20:45
第四题如果我没理解错的话，是一个二维数组对吗？
每一行是正方体的所有的字符。也就是每一行里面只能挑一 ...

赞，这样就变成了一道backtrack, 可以把index结果放到set里面就行了。找到size == word length直接返回

楼主几年经验，面的是几级？

edyyy 发表于 2020-11-02 23:43:57
楼主几年经验，面的是几级？

6年，面的L5

请问第四题 除了DFS 还有什么方法优化吗？

1934220965 发表于 2020-11-04 15:41:23
请问第四题 除了DFS 还有什么方法优化吗？

我当时没有想出来更好的，简单扯了一下memorization但并不能解决复杂度的问题。不知道地理同学有没有什么更好的解法。

楼主 第四题 你觉得用Trie 可以吗？ 正方体的index 就是Trie的层， 再search 那个单词。。。这样时间复杂度就是O（单词的长度）

zhangyangseu 发表于 2020-11-05 07:41:42
楼主 第四题 你觉得用Trie 可以吗？ 正方体的index 就是Trie的层， 再search 那个单词。。。这样时间复杂度就是O（单词的长度）

可是build trie的复杂度应该和dfs是一样的吧

积分不够看不到 求好心人分享一下！

hsierra 发表于 2020-11-06 20:45:01
第四题如果我没理解错的话，是一个二维数组对吗？
每一行是正方体的所有的字符。也就是每一行里面只能挑一个字符使用。

是二维数组没错。

感觉你说的很有道理。谢谢。

面试时候没有想清楚，就每层六个面都走一遍。对理解还是不够深入，惭愧。