G intern电面面经# JobHunting - 待字闺中
j*1
1 楼
回报本版，新鲜G的电面面经，顺便求bless。
(1) Suppose each request has some data, calculate the average bandwidth in
the last 1 second, 1minute, 1 hour.
这题跟careercup那道recent average request很像。
首先，不能有错误，只想出来了use a queue as moving window, and then take
average over last 1 sec, 1 minute, 1 hour. Maintain the queue by deleting
all requests information outside the 1 hour window.
其次，允许一定的错误量。这样就可以用circular array. For example, take a
circular array to store the bandwidth in each second, sample_per_sec[3600].
Then circular filling in the array. The average in last hour is the average
of the array.
(2) Existence of an integer in a sorted array.
O(log(n)) binary search.
Existence of an integer in a linked list.
貌似只能O(n)。
Visit webpages and count specific words in each webpage in a graph.
DFS/BFS, and need to take care of cycles. 这里我用了一个list to
store visited pages to avoid double counting，不知道有没有更好的data
structure
貌似G的电面variance很大啊，这些题比什么四位解码，2-d knapsack好多了。同时抱
怨一下google doc比f的collabedit难用多了。。
code有minor bug，不过都fix了，求bless能过：）
(1) Suppose each request has some data, calculate the average bandwidth in
the last 1 second, 1minute, 1 hour.
这题跟careercup那道recent average request很像。
首先，不能有错误，只想出来了use a queue as moving window, and then take
average over last 1 sec, 1 minute, 1 hour. Maintain the queue by deleting
all requests information outside the 1 hour window.
其次，允许一定的错误量。这样就可以用circular array. For example, take a
circular array to store the bandwidth in each second, sample_per_sec[3600].
Then circular filling in the array. The average in last hour is the average
of the array.
(2) Existence of an integer in a sorted array.
O(log(n)) binary search.
Existence of an integer in a linked list.
貌似只能O(n)。
Visit webpages and count specific words in each webpage in a graph.
DFS/BFS, and need to take care of cycles. 这里我用了一个list to
store visited pages to avoid double counting，不知道有没有更好的data
structure
貌似G的电面variance很大啊，这些题比什么四位解码，2-d knapsack好多了。同时抱
怨一下google doc比f的collabedit难用多了。。
code有minor bug，不过都fix了，求bless能过：）
