G 家面经

原帖地址:mitbbs

求 bless :)

面了四个人.

第一个人: 关于 quadtree 的

比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
否则的话,需要把这个 image等分成四份,如下图

__________ __________
| | 等分成四份就变成 | | |
| | |____|___|
| | | | |
|________| |____|___|

分成四份以后每个小份就是一个 sub-quadtree

问题1 : 为这个 quadtree里面的 node 设计 data structure

然后的问题是关于两个 quadtree 的 intersection, 有两个 quadtree, 它们描述的
image 是两个相同的 area
比如 都是 [0 1] x [0 1] 这个相同的二维区域的image.

问题二: 写一个函数,返回两个 quadtree的intersection,

这个intersection的规则是: 如果一个区域在 第一个quadtree 里面是
白的,这个相同的区域在 第二个 quadtree里面是黑的,那么intersection
就是白的,简单的说白是 0, 黑是 1, intersection就是两个bit 的 AND

第二个人:

问题 1: construct binary search tree from a sorted array ( leet code 的原
题)
问题 2: storm8的 online test 的升级版。

一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值

一看这个就傻了. 两个人的,太难了。 面试官让我先算一个人的算法,
这个
easy.

然后他就问两个人怎么搞,我当时首先想到的是,会不会是 greedy, 先算
第一个人的,然后把第一个人走过的路径上的每个点上的钱变成0,再算第
二个
人的。我当时试图证明这个 greedy是正确的,但也证明不出来。

面试官说你能举出一个反例证明你的 greedy 不 work也行,我当时就试了试
1 2 3
4 5 6
7 8 9

跑了一下 greedy的算法。 但是这个似乎不能做为一个反例。

时间到之前没想出反例.

第三个人:

问题1 : binary search. 我问他 如果 target miss/hit 怎么处理,他说 you
told
me. 我就说 比如 1 2 2 4, target = 3, 那么应该返回 index 3,
如果 target 是 2, 就应该返回 index 2. 他说 OK。 然后我写了,他亲自
跑了一个
test case

问题2 : 写一个 hashtabe, 实现两个方法 find, insert

第四个人:

问题1 : google的 search bar 里面敲入 一些字母的时候, 会出来一些提示,问
怎么
实现,我说用 prefix tree. 然后就问, 比如 输入 ca, 出来的可能是
cat,
california, 问有什么方法可以加快 search, 可不可以提前 search, 我说
可以
提前 search cat 和 california, 等到用户确定是什么的时候,再输出相
应的
search的结果, 这样会快一点。

问题2 : 一个服务器上有一个很大的 integer array A, 客户端会 每次通过 两

index start, end, 来拿到 A[start, …, end] 这个 sub array 上的
minimum, 如何在服务器上实现快速的找出 A[start, …, end] 的最小
值.