Pocket Gems面经 - 我的博客 - ITeye技术网站

Pocket Gems面经 - 我的博客 - ITeye技术网站

FOLLOW UP: Top k frequent elements in a stream Kth most frequent number Input : An array of n numbers, and a number k Output : An array of n numbers where example： [1, 3, 5, 7, 3, 4, 2, 9],  k = 3 [5, 7, 7, 7, 4, 9, 9, 9]     时间复杂度。     2. parse一个字符串表示的三元表达式，输出一个树结构。三元表达式中不含括号，每个变量名都是一个字母，并且保证合法。例如： a?b:c a?b?c:d:e a?b:c?d:e      a / \ 于是这才开始真正用心思考这个题目本身。很快想到得用递归了，然后有两个要点： 于是呼隆呼隆写完，然后interviewer要分析最坏时间复杂度。首先列出最坏情况： a ? (...) : b 再列出最坏情况的递归表达式 T(n) = 2 * T(n - 4)，因为中间括号部分长度是n - 4，而且匹配":"时遍历了一遍，然后递归又遍历了一遍。这时 T(n) = O(2^n)。 然后问能不能优化，这才发现中间部分遍历了两次，所以应该一开始遍历就用hash table存下所有的 ? : 匹配关系，然后再遍历一遍，常数时间就能找到每个子树的起止点了。这样总复杂度是O(n)。这里就没让写代码，因为来不及了，只这样说了下思路。     Sliding Window （给你一个数组和一个数k，k是滑动窗口的大小，滑动窗口每次向右移动一个index，输出是一个新的数组，记录每次窗口里的最小值）   example:      1   1. asian guy, 直接read code, 是String变成一个Tree， input: "   1     /   \    2       3"   1   2. asian girl, word break I, and find top k frequency number.  3. american guy,

Read full article from Pocket Gems面经 - 我的博客 - ITeye技术网站