谷歌ONSITE

五道题:

  1. 给一组STRING, 要求根据这组数据,随机组成STRING, 满足:1. 首字符分布一致, 2. 尾字符分布一致,3.后面跟随的一个字符也分布一致
    比如, [‘abc’, ‘aefd’, ‘effect’, ‘noted’ ], 首字符能是 (‘a’, ‘e’, ‘n’), 尾字符只能是(‘c’, ‘d’, ‘t’, ‘d’), ‘a’ 后面可以跟 (‘b’, ‘e’), ‘e’ 后面跟(‘f’,‘c’,‘d’)…
    我用HASHTABLE做的, 如何控制分布一致,我觉得是出现一次就减一次?
  2. 给一串字符, 比如’abcde’, (0,1) 属于group 1, (2,3) group 2, (4) group 3 , (0,3) group 4, 要求给出最小chunk , 以及其属于的组: (0,1): 1,4, (2,3); 2,4 …
  3. Trie implement of add and search
  4. node of a BST’s next bigger one
  5. combine element of a increasing array : input [1,2,2,3,4], output [1,4,3,4]

11月底

第一道的做法,好像大家意见各不相同

第一题分布频率有要求吗?首字母a出现了两次。
最后输出是什么,举个例子吧

开始说要求分布和给出的一致, 那么首字母就是 a 两次,e 一次, n 一次, 后来觉得我做的不顺利,就说输出就一个string吧。

‘aed’

感觉可以做成图,outgoing path要加weight

第5题,用了3个pointer 做的

这题好像不是很难吧,思路上。可能要bug free有点难