google题

发信人: xiaoyouyi (yy), 信区: JobHunting
标  题: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 04:06:43 2014, 美东)

假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。

发信人: blaze (狂且), 信区: JobHunting
标  题: Re: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 14:12:05 2014, 美东)

Just dp:
f是dp函数的值，表示从当前的点走到目标最少需要多少能量。

w是当前点上的权重，可以是正的或者负的。

f(m, n) = 0

f(i, j) = min(
  max(f(i+1, j) - w(i+1,j), 0),
  max(f(i, j+1) - w(i, j+1), 0)
)


每个点计算当前点到目标的最 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情 况取最小作为当前点的最小能量要求即可。



发信人: CodeSwim (CodeSwim), 信区: JobHunting
标  题: GG面经
发信站: BBS 未名空间站 (Tue Jan 20 12:55:43 2015, 美东)

前两天面了GG, 刚收到feedback说通过. 下面是面经:
白人小伙, 一上来什么都没说,直接开题.

第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有
match的字符串.
给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表
达式的做法; 面试官说用trie来实现吧. 先构建trie, 然后把搜索函数写出来. 没什么
好说的 从头开始写. 完成后写了个简单的test case, 和他一起过了一遍;

第二题, deep copy linked list. 给了两种方案, 一是hashmap based Time O(n) +
Space O(n); 一是直接对List拆分deep拷贝 然后再恢复原list Time O(n) + Space O(
1)。
面试官让分析了下两种方法的优劣. 然后说实现下第二种吧. 我刚把思路说完正打算写
代码, 然后考官打断说时间不太够了,实现第一种吧. 于是一口气写完. 给了个test
case过了一遍. 最后考官问代码里有没有问题, 我又从头仔细和他过了一遍,没发现.
问他给点提示, 他说他也没发现... 于是让问问题. 结束.