google 2018四月onsite面筋

凯伦小龙虾 发表于 2018-4-18 02:06
是的，我提出说我可以index 所有query然后random n个，但面试官说好像不能存，而且最好不要有延迟。如果 ...

我觉得这题应该需要query 在每秒内的分布情况。楼主似乎假设了query在一秒内是均匀分布的。否则的话，有个极端情况就是1000个query都在前0.5秒内，剩下的0.5秒没有query。如果我没有理解错的话，按楼主1/n秒产生一个true的算法，只能产生0.5n个true。

markpen 发表于 2018-4-18 03:12
我觉得这题应该需要query 在每秒内的分布情况。楼主似乎假设了query在一秒内是均匀分布的。否则的话，有 ...

是的。面试官当时只是说保证rate不被打破，而且不能存之前的信息，所以我当时就有点懵，不清楚怎么做可以解决你提的这个问题哈，有什么好的想法么，求指导

凯伦小龙虾 发表于 2018-4-18 03:17
是的。面试官当时只是说保证rate不被打破，而且不能存之前的信息，所以我当时就有点懵，不清楚怎么做可以 ...

看了最近的面经，我觉得面试官是想要设计一个类似Rate Limiter 的东西，true 表示接收， false 表示拒绝。这样想的话，楼主的做法似乎没有什么问题。

恭喜楼主，太厉害了！

其实没太懂第三题的意思，请问什么叫isAllowed()呢？是谁call的？

凯伦小龙虾 发表于 2018-4-17 22:44
就是说每次出来一个char，我都会从root开始找看有没有符合，如果符合的话，我就把当前这个trienode指针ap ...

这个题如果把词典的word逆序后建Trie树，再用一个vector存最近遇到的max_length_of_word_in_dict个char，每次来一个char就逆序构造string到Trie中查找，就可以避免存多个TrieNode*的情况
因为你存TrieNode*至多也要存max_length_of_word_in_dict个，所以空间复杂度没区别。

恭喜楼主！求文档，tian7838526 at 163.com，多谢楼主！

楼主，现在有什么消息了吗？

alanlxl 发表于 2018-4-20 14:02
这个题如果把词典的word逆序后建Trie树，再用一个vector存最近遇到的max_length_of_word_in_dict个char， ...

学习了，这样的确挺好的，谢谢分享！

请问美女，第二问说，面试管说那就假设总是有left subtree的，然后就用pre和post去construct了？没有inorder就是没法建吧，求问如何用pre和post建，面试官的话我没看懂，多谢~~~我下周一NY onsite，十分感谢