Google Onsite

多谢楼主，很棒的面经！！

想请问楼主第一题第一个follow up 输入是[(1, 10), (3, 20), (2, 30)], [(2, 5), (3,20), (1,35)], 最后应该输出[(2, 35), (3, 40), (1,45)] 应该怎么merge得到啊? O(N)的复杂度么

匿名者 发表于 2020-3-31 11:29
想请问楼主第一题第一个follow up 输入是[(1, 10), (3, 20), (2, 30)], [(2, 5), (3,20), (1,35)], 最后应 ...

第一个follow up 我可能没写清楚
sorted是说 按照id sort 也就是说 你给的输入 其实不是sorted
[(1, 10), (2, 30), (3, 20)], [(1, 35), (2, 5), (3, 20)] 这样merge你会吗?
时间复杂度的话 应该是 O(M + N), M 和 N代表两个input list 的长度
不知道这样有没有说清楚~

Rinnkai2020 发表于 2020-3-30 23:39
多谢楼主，很棒的面经！！

谢谢~~祝你成功~

第四题的follow up时间复杂度是多少？对每一个单词，需要把所有加一个字符和减一个字符的可能性都查一遍？

djmiss 发表于 2020-4-3 02:13
第四题的follow up时间复杂度是多少？对每一个单词，需要把所有加一个字符和减一个字符的可能性都查一遍？

时间复杂度不变
对 减一个字符 一样长度 加一个字符 都要查一遍 但这个不影响时间复杂度

第四题用不着trie吧？no matter what 也需要每个单词遍历一次

notelonmusk 发表于 2020-4-7 04:47
第四题用不着trie吧？no matter what 也需要每个单词遍历一次

我写的只是我的做法~不是说答案就是这个哦~

ywangriley 发表于 2020-4-7 11:53
谢谢分享。第一题的3和4是要你用max heap吗？第四题为什么不是直接把单词和单词的前n-1个字母放到set里用O( ...

第一题 3和4 想问的其实是generator
第四题的话 也可以吧? 不过要仔细想一下各种case
不过set的O(1)只是相对于list和tuple的O(N) 它在内部hash的时候 还是遍历了整个string