由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G 家面经
相关主题
Construct Binary Tree from Inorder and Postorder Traversal这题到底是啥意思
FB 面经长年潜水,回馈FLG面经
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。地图上分割成不同区域这个设计题的核心是什么来着?
请教个G题目请问一道面试题
G家最新电面问个题,用递归方法
怎样求common divisor 最快一道linked list编程题
却看妻子愁何在,漫卷诗书喜欲狂ms面试题
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb这题谁知道答案?
相关话题的讨论汇总
话题: dp话题: int话题: qtreenode话题: matrix话题: max
进入JobHunting版参与讨论
1 (共1页)
j*****y
发帖数: 1071
1
求 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] 的最小
值.



h*******e
发帖数: 1377
2
2个人那个双向广搜啊。
j*****y
发帖数: 1071
3
怎么做阿?

【在 h*******e 的大作中提到】
: 2个人那个双向广搜啊。
j******2
发帖数: 362
4
先赞再看!
j******2
发帖数: 362
5
并狠狠地bless
j*****y
发帖数: 1071
6
多谢 :)

【在 j******2 的大作中提到】
: 并狠狠地bless
f*******t
发帖数: 7549
7
好难的题,bless
j*****y
发帖数: 1071
8
多谢 :)

【在 f*******t 的大作中提到】
: 好难的题,bless
p*****2
发帖数: 21240
9

是不是不应该变成0,应该变成-1,也就是2不能再走了?

【在 j*****y 的大作中提到】
: 怎么做阿?
B*******1
发帖数: 2454
10
我也觉得。给我就跪了。

★ 发自iPhone App: ChineseWeb 7.8

【在 f*******t 的大作中提到】
: 好难的题,bless
相关主题
怎样求common divisor 最快这题到底是啥意思
却看妻子愁何在,漫卷诗书喜欲狂长年潜水,回馈FLG面经
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb地图上分割成不同区域这个设计题的核心是什么来着?
进入JobHunting版参与讨论
p*****2
发帖数: 21240
11

这个不行。不能一个先走。要两个一起走才可以。

【在 p*****2 的大作中提到】
:
: 是不是不应该变成0,应该变成-1,也就是2不能再走了?

p*****2
发帖数: 21240
12
想到了。不能一个先走。
两个一起走,因为每一个可以走两个方向,那么两个人一起走就有4种可能。选择4种里
边的最大钱数的那个就可以了。
w****a
发帖数: 710
13
楼主什么背景?这个题难度比普通的G家面经大啊。
p*****2
发帖数: 21240
14

感觉不能一个先走。
a***o
发帖数: 1182
15
好像是,不能往下走

【在 p*****2 的大作中提到】
:
: 感觉不能一个先走。

p*****2
发帖数: 21240
16

可能也不一定。再想想。

【在 p*****2 的大作中提到】
: 想到了。不能一个先走。
: 两个一起走,因为每一个可以走两个方向,那么两个人一起走就有4种可能。选择4种里
: 边的最大钱数的那个就可以了。

j*****y
发帖数: 1071
17
我也想过先用 recursive 的 方法 show一下 idea, 但是这个 recursive的 structure
还是不好弄阿

【在 p*****2 的大作中提到】
: 想到了。不能一个先走。
: 两个一起走,因为每一个可以走两个方向,那么两个人一起走就有4种可能。选择4种里
: 边的最大钱数的那个就可以了。

j*****y
发帖数: 1071
18
问题的关键不是先走,后走或者同时走
怎么的顺序走都可以,关键是要求出两个人拿到的钱
的和的最大数目

【在 p*****2 的大作中提到】
:
: 可能也不一定。再想想。

j*****y
发帖数: 1071
19
那道 dp的题目感觉是个新题。没见过.

【在 w****a 的大作中提到】
: 楼主什么背景?这个题难度比普通的G家面经大啊。
j*****y
发帖数: 1071
20
背景很弱, phd + 1 年。而且还不是科班cs

【在 w****a 的大作中提到】
: 楼主什么背景?这个题难度比普通的G家面经大啊。
相关主题
请问一道面试题ms面试题
问个题,用递归方法这题谁知道答案?
一道linked list编程题Amazon的LRU设计题
进入JobHunting版参与讨论
B*******1
发帖数: 2454
21
是烙印出的?

★ 发自iPhone App: ChineseWeb 7.8

【在 j*****y 的大作中提到】
: 背景很弱, phd + 1 年。而且还不是科班cs
w****a
发帖数: 710
22
Bless!楼主答的应该都没啥问题吧。
prefix tree让你code没?
快速找范围内min值你怎么答的?
a***o
发帖数: 1182
23
证明出来了
一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
交点,然后绕道,根据方向,和是相加的
楼主说的greedy是错的
比如这种:
40 40 0
50 50 50
0 40 40
左下角的是起点,右上角的是终点

【在 p*****2 的大作中提到】
:
: 可能也不一定。再想想。

p******9
发帖数: 47
24
按对角线进行动态规划,两个人都需要n + m - 1步才能走到终到,每一步两个人都在
一条斜对角线上,所以可以进行动态规划,分为n + m - 1步,每一步有n^2状态,n^3
可解。
p*****2
发帖数: 21240
25
粗略的想了一下。感觉是个4维DP
dp[i][j][x][y] 是A走到(i,j), B走到(x)(y)能够拿到的最大钱数
dp[i][j][x][y]=max(dp[i+1][j][x+1][y], dp[i+1][j][x][y-1] 一共四种情况
+ if(i==x && j==y) x(i)(j) else x(i)(j)+x(x)(y)
最后返回dp(0)(n-1)(0)(n-1)
p******9
发帖数: 47
p*****2
发帖数: 21240
27

感觉可以走相同的点。至少如果那个点的钱数是0

【在 a***o 的大作中提到】
: 证明出来了
: 一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
: 交点,然后绕道,根据方向,和是相加的
: 楼主说的greedy是错的
: 比如这种:
: 40 40 0
: 50 50 50
: 0 40 40
: 左下角的是起点,右上角的是终点

f*****e
发帖数: 2992
28
握手!差不多想法。有些细节不同。
最后一题:minimum
就是记录local minimum的位置。然后对local minimum的位置建
balanced binary search tree。
直接binary search 位置也行。

【在 p*****2 的大作中提到】
: 粗略的想了一下。感觉是个4维DP
: dp[i][j][x][y] 是A走到(i,j), B走到(x)(y)能够拿到的最大钱数
: dp[i][j][x][y]=max(dp[i+1][j][x+1][y], dp[i+1][j][x][y-1] 一共四种情况
: + if(i==x && j==y) x(i)(j) else x(i)(j)+x(x)(y)
: 最后返回dp(0)(n-1)(0)(n-1)

p*****2
发帖数: 21240
29

交叉点的钱数也许是0,所以走相同的点无所谓

【在 a***o 的大作中提到】
: 证明出来了
: 一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
: 交点,然后绕道,根据方向,和是相加的
: 楼主说的greedy是错的
: 比如这种:
: 40 40 0
: 50 50 50
: 0 40 40
: 左下角的是起点,右上角的是终点

j*****y
发帖数: 1071
30
prefix tree没让 code,
快速找 min, 给了两个方法,第一个没有第二个好.
given A[1,...,n]
方法1 : compute B[1,...,n]
where B[i] = min {A[j], 1 <=j <= i}
这个方法效率不好。
方法 2: compute B[1,...,n]
where B[i] = j such that for any k, i <= k <= j
, we have A[k] >= A[i] and A[j + 1] < A[i]
方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法
二的 search min
int minimum(int start, int index)
的时候,出了些 边界上的 error

【在 w****a 的大作中提到】
: Bless!楼主答的应该都没啥问题吧。
: prefix tree让你code没?
: 快速找范围内min值你怎么答的?

相关主题
【哪里有C++比较好的LinkedList实现?】FB 面经
问道google面试题linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。
Construct Binary Tree from Inorder and Postorder Traversal请教个G题目
进入JobHunting版参与讨论
p*****2
发帖数: 21240
31

嗯。感觉greedy不行,还是得用DP,考虑所有情况。

【在 f*****e 的大作中提到】
: 握手!差不多想法。有些细节不同。
: 最后一题:minimum
: 就是记录local minimum的位置。然后对local minimum的位置建
: balanced binary search tree。
: 直接binary search 位置也行。

a***o
发帖数: 1182
32
如果绕道的那个点不是0的话有所谓呀

【在 p*****2 的大作中提到】
:
: 嗯。感觉greedy不行,还是得用DP,考虑所有情况。

f*****e
发帖数: 2992
33
right!

【在 p*****2 的大作中提到】
:
: 嗯。感觉greedy不行,还是得用DP,考虑所有情况。

s****0
发帖数: 117
34
在两条路相交的时候要特殊处理一下就行了,对不对?
p*****2
发帖数: 21240
35

我的意思是解法可以不考虑这种情况。考虑的话反而变复杂了。DP把所有情况都考虑了
,管你是不是走了相同的点。

【在 a***o 的大作中提到】
: 如果绕道的那个点不是0的话有所谓呀
a***o
发帖数: 1182
36
O(n^4) ...

【在 p*****2 的大作中提到】
:
: 我的意思是解法可以不考虑这种情况。考虑的话反而变复杂了。DP把所有情况都考虑了
: ,管你是不是走了相同的点。

p******9
发帖数: 47
37
按对角线一步一步走 可以优化到O(n^3)时间,O(n^2)空间
p*****2
发帖数: 21240
38

上边有个n^3的DP,你看看,我还没仔细看。

【在 a***o 的大作中提到】
: O(n^4) ...
f*****e
发帖数: 2992
39
storm8的 online test 的升级版
for(int j = 0; j < m; j++) // row from bottom to top
for(int i = 0; i < n; i++) // column from left to right
for(int k = 0; k <=j; k++) // calculate diagnal '\' elements
dp2[i][j][i+k][j-k] = max{of the 4 combinations};
// k = 0 is what we want, other values of k are prepared for later
calculation of the 4 combinations (left, left), (left, down), (down, left),
(down, down)
O(n*(1+...+m))=O(nm^2)=O(MN*min(M,N)), m = min(M, N)
-------(i,j)-->-->-->-->(n,m)
| | \ \ \ \ \ \ \
| | \ \ \ \ \ \ \
| | \ \ \ \ \ \
------(i,y)-----(i+k,j-k)
| | | \ \ \ \
| | | \ \ \
| | | \ \
----------------------------

【在 p*****2 的大作中提到】
:
: 上边有个n^3的DP,你看看,我还没仔细看。

b*********h
发帖数: 103
40
两个人那个...noip 2000 就考过了...经典 dp
相关主题
请教个G题目却看妻子愁何在,漫卷诗书喜欲狂
G家最新电面interview question: Given a list of points in 2D and a single reference point, find k nearest neighb
怎样求common divisor 最快这题到底是啥意思
进入JobHunting版参与讨论
P*******b
发帖数: 1001
41
bless!
第一题intersection的函数应该长什么样?
TreeNode* intersection(TreeNode* root1, TreeNode* root2)
返回新的树,这样对吗?

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

s****0
发帖数: 117
42
zkss

【在 b*********h 的大作中提到】
: 两个人那个...noip 2000 就考过了...经典 dp
P*******b
发帖数: 1001
43
lz这些题都做出来了吗?很厉害啊。
第一道题试着写了写,感觉半个小时想考虑全面并写出来代码很难啊

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

s******k
发帖数: 3716
44
bless。
道所谓的难题这么做(DP):
首先,假设每个节点的金子都是非负数。那么,两个人走的路线必然不相交,否则可以
修改一个人的路线使得总金子数不减少。
现在,两个人同时走,那么在第一步只有一个选择(一个向上一个向右),第二步要在
三个位置取两个,第三步是四个位置取两个。只要知道在该位置的最大钱数就可以继续
计算:
cost(i1,j1,i2,j2) = max(cost(i1,j1-1,i2,j2-1),cost(i1-1,j1,i2,j2-1),cost(i1,
j1-1,i2-1,j2),cos(i1-1,j1,i2-1,j2))+money(i1,j1)+money(i2,j2).
这里i1+j1=i2+j2。最后把cost(m,n,m,n)算出来就好了。

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
45
对的
多谢 :)

【在 P*******b 的大作中提到】
: bless!
: 第一题intersection的函数应该长什么样?
: TreeNode* intersection(TreeNode* root1, TreeNode* root2)
: 返回新的树,这样对吗?
:
: 的。

p*****2
发帖数: 21240
46

想了想。感觉还好。我准备写一下。

【在 P*******b 的大作中提到】
: lz这些题都做出来了吗?很厉害啊。
: 第一道题试着写了写,感觉半个小时想考虑全面并写出来代码很难啊
:
: 的。

f*****e
发帖数: 2992
47
差不多:
http://mitbbs.com/article1/JobHunting/32322997_3_0.html

i1,

【在 s******k 的大作中提到】
: bless。
: 道所谓的难题这么做(DP):
: 首先,假设每个节点的金子都是非负数。那么,两个人走的路线必然不相交,否则可以
: 修改一个人的路线使得总金子数不减少。
: 现在,两个人同时走,那么在第一步只有一个选择(一个向上一个向右),第二步要在
: 三个位置取两个,第三步是四个位置取两个。只要知道在该位置的最大钱数就可以继续
: 计算:
: cost(i1,j1,i2,j2) = max(cost(i1,j1-1,i2,j2-1),cost(i1-1,j1,i2,j2-1),cost(i1,
: j1-1,i2-1,j2),cos(i1-1,j1,i2-1,j2))+money(i1,j1)+money(i2,j2).
: 这里i1+j1=i2+j2。最后把cost(m,n,m,n)算出来就好了。

j*****y
发帖数: 1071
48
不是 :)

【在 B*******1 的大作中提到】
: 是烙印出的?
:
: ★ 发自iPhone App: ChineseWeb 7.8

j*****y
发帖数: 1071
49
多谢 :)

【在 w****a 的大作中提到】
: Bless!楼主答的应该都没啥问题吧。
: prefix tree让你code没?
: 快速找范围内min值你怎么答的?

p*****2
发帖数: 21240
50
第一题练了练。没有测试。
class QTreeNode (var color:Int){
val children=new Array[QTreeNode](4)
}
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}

def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.children(i)=intersection(left.children
(i), right.children(i))
newNode
}
else if(left.color==0 || right.color==0) return new QTreeNode(0)
else if(left.color==1) return clone(right)
else return clone(left)
}
相关主题
长年潜水,回馈FLG面经问个题,用递归方法
地图上分割成不同区域这个设计题的核心是什么来着?一道linked list编程题
请问一道面试题ms面试题
进入JobHunting版参与讨论
j*****y
发帖数: 1071
51
我当时要是能想出你这个反例就好了 :)

【在 a***o 的大作中提到】
: 证明出来了
: 一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
: 交点,然后绕道,根据方向,和是相加的
: 楼主说的greedy是错的
: 比如这种:
: 40 40 0
: 50 50 50
: 0 40 40
: 左下角的是起点,右上角的是终点

p*****2
发帖数: 21240
52

这个搞一个binary tree行吗?
root是(0, n-1) + min in (0,n-1)
然后从min两边分成两棵子树。
查找的时候logn复杂度

【在 j*****y 的大作中提到】
: prefix tree没让 code,
: 快速找 min, 给了两个方法,第一个没有第二个好.
: given A[1,...,n]
: 方法1 : compute B[1,...,n]
: where B[i] = min {A[j], 1 <=j <= i}
: 这个方法效率不好。
: 方法 2: compute B[1,...,n]
: where B[i] = j such that for any k, i <= k <= j
: , we have A[k] >= A[i] and A[j + 1] < A[i]
: 方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法

o***d
发帖数: 313
53
先bless再看

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
54
多谢 :)

【在 o***d 的大作中提到】
: 先bless再看
:
: 的。

f*****e
发帖数: 2992
55
可以对所有元素建Balanced-BST。
不过应该把位置作为key建平衡二叉树,而且每个节点还应该记录他左子树和右子树的
最小值。

【在 p*****2 的大作中提到】
:
: 这个搞一个binary tree行吗?
: root是(0, n-1) + min in (0,n-1)
: 然后从min两边分成两棵子树。
: 查找的时候logn复杂度

p*****2
发帖数: 21240
56

随便搞了一个。不是balanced
class Node(arr:Array[Int], start:Int, end:Int){
val minid=arr.indexOf(arr.slice(start,end+1).min,start)
val left=if(start val right=if(end>minid) new Node(arr,minid+1,end) else null

def query(s:Int, e:Int):Int={
if(e if(s>minid) return right.query(s,e)
arr(minid)
}
}

【在 f*****e 的大作中提到】
: 可以对所有元素建Balanced-BST。
: 不过应该把位置作为key建平衡二叉树,而且每个节点还应该记录他左子树和右子树的
: 最小值。

f*****e
发帖数: 2992
57
第二个人出的第1题就是第四个人出的第2题的提示。

【在 p*****2 的大作中提到】
:
: 随便搞了一个。不是balanced
: class Node(arr:Array[Int], start:Int, end:Int){
: val minid=arr.indexOf(arr.slice(start,end+1).min,start)
: val left=if(start: val right=if(end>minid) new Node(arr,minid+1,end) else null
:
: def query(s:Int, e:Int):Int={
: if(e: if(s>minid) return right.query(s,e)

p*****2
发帖数: 21240
58

第四题不是不是sorted的吗

【在 f*****e 的大作中提到】
: 第二个人出的第1题就是第四个人出的第2题的提示。
f*****e
发帖数: 2992
59
位置是sorted的。呵呵。

【在 p*****2 的大作中提到】
:
: 第四题不是不是sorted的吗

j*****y
发帖数: 1071
60
第四题是任意的array

【在 p*****2 的大作中提到】
:
: 第四题不是不是sorted的吗

相关主题
这题谁知道答案?问道google面试题
Amazon的LRU设计题Construct Binary Tree from Inorder and Postorder Traversal
【哪里有C++比较好的LinkedList实现?】FB 面经
进入JobHunting版参与讨论
f*****e
发帖数: 2992
61
算法就是找到一个node, 位置为k,使得 start < k < end
然后找start在树中的位置,并同时记录k之后所有经过节点 右 子树的最小值min1。
然后找end在树中的位置,并同时记录k之后所有经过节点 左 子树的最小值min2。
然后最终结果就是min(min1, min2)

【在 f*****e 的大作中提到】
: 位置是sorted的。呵呵。
p*****2
发帖数: 21240
62

对。这样可以。建balanced BST。coding要麻烦一些了。

【在 f*****e 的大作中提到】
: 位置是sorted的。呵呵。
f*****e
发帖数: 2992
63
一个节点上的钱只能用一次。

【在 o***d 的大作中提到】
: 先bless再看
:
: 的。

f*****e
发帖数: 2992
64
你的简历肯定很impressive,要不然google会这么狠!:-)

【在 j*****y 的大作中提到】
: 第四题是任意的array
o***d
发帖数: 313
65
第4题,似乎以前见过?说是把用户以前的搜索的数据存在本地,然后做trie?我是说,他问
怎么加快速度,似乎是调本地的以前的数据和bookmarks?
4.2???
怎么做?难道再做个数据结构,把数组先sort一遍,对应好原来的数组????
总之,确实够难啊....

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
66
我就觉得和你的差距不是那么一点点阿 :)
你太厉害了,那道 dp的题目我这几天一直在想,还是没想出来,
我就对自己说,坦然了,当时没想出来确实就是没想出来.

【在 f*****e 的大作中提到】
: 你的简历肯定很impressive,要不然google会这么狠!:-)
p*****2
发帖数: 21240
67

嗯。新题挺多的。LZ的面经挺珍贵的。祝LZ好运。

【在 f*****e 的大作中提到】
: 你的简历肯定很impressive,要不然google会这么狠!:-)
j*****y
发帖数: 1071
68
多谢二爷 :)

【在 p*****2 的大作中提到】
:
: 嗯。新题挺多的。LZ的面经挺珍贵的。祝LZ好运。

p*****2
发帖数: 21240
69

我感觉那道DP的思路就是先想greedy,这个特别自然。然后发现greedy是错的,就自然
想到DP了。因为DP的根本还是brute force。你想到greedy了,但是当时可能紧张没有
想到greedy是错的,面试官也在这个方向引导了。

【在 j*****y 的大作中提到】
: 我就觉得和你的差距不是那么一点点阿 :)
: 你太厉害了,那道 dp的题目我这几天一直在想,还是没想出来,
: 我就对自己说,坦然了,当时没想出来确实就是没想出来.

j*****y
发帖数: 1071
70
还是思路没有二爷这么敏捷阿 :)

【在 p*****2 的大作中提到】
:
: 我感觉那道DP的思路就是先想greedy,这个特别自然。然后发现greedy是错的,就自然
: 想到DP了。因为DP的根本还是brute force。你想到greedy了,但是当时可能紧张没有
: 想到greedy是错的,面试官也在这个方向引导了。

相关主题
FB 面经G家最新电面
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。怎样求common divisor 最快
请教个G题目却看妻子愁何在,漫卷诗书喜欲狂
进入JobHunting版参与讨论
j*****y
发帖数: 1071
71
多谢二爷启发.

【在 p*****2 的大作中提到】
:
: 我感觉那道DP的思路就是先想greedy,这个特别自然。然后发现greedy是错的,就自然
: 想到DP了。因为DP的根本还是brute force。你想到greedy了,但是当时可能紧张没有
: 想到greedy是错的,面试官也在这个方向引导了。

l***b
发帖数: 125
72
quadtree...这个似乎很少考,两年前我去也被问到这个,不会还是同一个面试官吧:)

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
73
面我的是个老美

:)

【在 l***b 的大作中提到】
: quadtree...这个似乎很少考,两年前我去也被问到这个,不会还是同一个面试官吧:)
:
: 的。

p*****2
发帖数: 21240
74

我要是面试的时候也不一定能想出来呢。面试一紧张还真难说了。哎。感觉你这次面试
比一般的onsite难度高出一个级别。不过可能是好事。

【在 j*****y 的大作中提到】
: 还是思路没有二爷这么敏捷阿 :)
j*****y
发帖数: 1071
75
google一般是面5个人的吧,我这个只见四个人,感觉有点郁闷

【在 p*****2 的大作中提到】
:
: 我要是面试的时候也不一定能想出来呢。面试一紧张还真难说了。哎。感觉你这次面试
: 比一般的onsite难度高出一个级别。不过可能是好事。

j*****y
发帖数: 1071
76
多谢 :)

【在 p*****2 的大作中提到】
:
: 我要是面试的时候也不一定能想出来呢。面试一紧张还真难说了。哎。感觉你这次面试
: 比一般的onsite难度高出一个级别。不过可能是好事。

l***b
发帖数: 125
77
好像是个老美,不过时间久了,记不确切啦。感觉你答得都还不错,bless:)

【在 j*****y 的大作中提到】
: 面我的是个老美
:
: :)

p*****2
发帖数: 21240
78

:)
你上次考的是什么题?前两天有个T的面试官说quadtree解。还不清楚应该怎么解。

【在 l***b 的大作中提到】
: quadtree...这个似乎很少考,两年前我去也被问到这个,不会还是同一个面试官吧:)
:
: 的。

j*****y
发帖数: 1071
79
多谢 :)

【在 l***b 的大作中提到】
: 好像是个老美,不过时间久了,记不确切啦。感觉你答得都还不错,bless:)
m******s
发帖数: 165
80
咦,和我面的味道有点像。。。非主流难题啊。。。bless

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

相关主题
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb地图上分割成不同区域这个设计题的核心是什么来着?
这题到底是啥意思请问一道面试题
长年潜水,回馈FLG面经问个题,用递归方法
进入JobHunting版参与讨论
j*****y
发帖数: 1071
81
多谢 :)

【在 m******s 的大作中提到】
: 咦,和我面的味道有点像。。。非主流难题啊。。。bless
:
: 的。

p*****2
发帖数: 21240
82

感觉4个人挺正常的呀。

【在 j*****y 的大作中提到】
: google一般是面5个人的吧,我这个只见四个人,感觉有点郁闷
p*****2
发帖数: 21240
83

你的面经在哪里呢?

【在 m******s 的大作中提到】
: 咦,和我面的味道有点像。。。非主流难题啊。。。bless
:
: 的。

m******s
发帖数: 165
84
少了轮thesis discussion,估计跟你非科班有关。。。
不过不知道是不是把你算成fresh orz

【在 j*****y 的大作中提到】
: google一般是面5个人的吧,我这个只见四个人,感觉有点郁闷
l***b
发帖数: 125
85
另外,没全做出来应该也没什么。感觉面试官有时更看重你的思路和沟通之类。我当时
有一个题也没想出最优解,只是和面试官讨论了一堆次优解和可能的时空tradeoff。后
来听hr说所有feedback都很positive,所以不用苛求完美

【在 j*****y 的大作中提到】
: 多谢 :)
j*****y
发帖数: 1071
86
好厉害。
他们还真的是把我当成了 new grad

【在 m******s 的大作中提到】
: 少了轮thesis discussion,估计跟你非科班有关。。。
: 不过不知道是不是把你算成fresh orz

j*****y
发帖数: 1071
87
多谢 :)

【在 l***b 的大作中提到】
: 另外,没全做出来应该也没什么。感觉面试官有时更看重你的思路和沟通之类。我当时
: 有一个题也没想出最优解,只是和面试官讨论了一堆次优解和可能的时空tradeoff。后
: 来听hr说所有feedback都很positive,所以不用苛求完美

p*****2
发帖数: 21240
88

你是骑驴找马呀?

【在 j*****y 的大作中提到】
: 好厉害。
: 他们还真的是把我当成了 new grad

f*****e
发帖数: 2992
89
似乎是金融转码农。

【在 p*****2 的大作中提到】
:
: 你是骑驴找马呀?

j*****y
发帖数: 1071
90
前不久 lay off了,专心找马 :)

【在 p*****2 的大作中提到】
:
: 你是骑驴找马呀?

相关主题
一道linked list编程题Amazon的LRU设计题
ms面试题【哪里有C++比较好的LinkedList实现?】
这题谁知道答案?问道google面试题
进入JobHunting版参与讨论
j*****y
发帖数: 1071
91
码农转码农 :)

【在 f*****e 的大作中提到】
: 似乎是金融转码农。
a***o
发帖数: 1182
92
我觉得能拿到offer~ bless!

【在 j*****y 的大作中提到】
: 我当时要是能想出你这个反例就好了 :)
j*****y
发帖数: 1071
93
多谢 :)

【在 a***o 的大作中提到】
: 我觉得能拿到offer~ bless!
o***d
发帖数: 313
94
恩,仔细看了看大家的讨论,确实够难啊!!!op果然牛人

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
95
:)

【在 o***d 的大作中提到】
: 恩,仔细看了看大家的讨论,确实够难啊!!!op果然牛人
:
: 的。

p*****2
发帖数: 21240
96

那很牛呀。

【在 j*****y 的大作中提到】
: 码农转码农 :)
j*****y
发帖数: 1071
97
二爷给个牛字,让人有点飘起来的感觉阿 :)
多谢 :)

【在 p*****2 的大作中提到】
:
: 那很牛呀。

m******s
发帖数: 165
98
真要虐出翔了。。。
1:
边同时遍历两个树边建一个新的,最后有可能要再遍历一次,比如:
I1 =
01
10
I2 =
10
01
则I1 intersect I2 =
00
00
即I1 intersect I2 = 0
2A:
O(n),由于array可以随机存取所以很好写。。。
2B:
好像前面有说,根据两个人的位置dp,greedy不太对
3A:
c++ stl lower_bound
3B:
应该不用上template吧orz,意思意思行了
4A:
trie (prefix tree),根据用户输入习惯或者是流行搜索词进行缓存
4B:
range minimum query,做法很多,在线算法评判的标准有这么几个:
空间复杂度 预处理时间复杂度 每次查询时间复杂度
可以搜索一下各种算法的不同
另外还可以扩展到多线程/多台机器

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

p*****2
发帖数: 21240
99

为什么有可能再遍历一次?

【在 m******s 的大作中提到】
: 真要虐出翔了。。。
: 1:
: 边同时遍历两个树边建一个新的,最后有可能要再遍历一次,比如:
: I1 =
: 01
: 10
: I2 =
: 10
: 01
: 则I1 intersect I2 =

m******s
发帖数: 165
100
4个pixel全白,根据quadtree定义,应该merge成一个大的
后序遍历一次完事。。。

【在 p*****2 的大作中提到】
:
: 为什么有可能再遍历一次?

相关主题
Construct Binary Tree from Inorder and Postorder Traversal请教个G题目
FB 面经G家最新电面
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。怎样求common divisor 最快
进入JobHunting版参与讨论
p*****2
发帖数: 21240
101

这样呀。那还真是。我那个程序没有考虑到这个。

【在 m******s 的大作中提到】
: 4个pixel全白,根据quadtree定义,应该merge成一个大的
: 后序遍历一次完事。。。

p*****2
发帖数: 21240
102

加了一句,检查这个条件。你觉得够了吗?
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}

def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.children(i)=intersection(left.children
(i), right.children(i))
if(newNode.children.count(_.color==0)==4) new QTreeNode(0) else
newNode
}
else if(left.color==0 || right.color==0) return new QTreeNode(0)
else if(left.color==1) return clone(right)
else return clone(left)
}

【在 m******s 的大作中提到】
: 4个pixel全白,根据quadtree定义,应该merge成一个大的
: 后序遍历一次完事。。。

m******s
发帖数: 165
103
恩,感觉上是这个意思。。。

【在 p*****2 的大作中提到】
:
: 加了一句,检查这个条件。你觉得够了吗?
: def clone(root:QTreeNode):QTreeNode={
: if(root==null) return null
: val newNode=new QTreeNode(root.color)
: for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
: newNode
: }
:
: def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={

x***y
发帖数: 633
104
Just write to mark for personal reference purpose
>>>>>>>>>>
一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值
>>>>>>>>>>
(1) Find one single optimal path P which contains m+n point
(2) For each point (i,j), (k,h) in P, denoting P((i,j)->(k,h)) as the path
connecting 2 points in P, there is one property
* For all the possible paths between (i,j) and (k,h), the P((i,j)->(k,h)) is
optimal.
(3) For this problem, the solution may be 2 possible cases(the 2 paths
should not collide at any point)
<1> P + optimal path for either the upper part or lowe part split by the
optimal path (this one is easy)
<2> It's obvious that the final solutions P1 and P2 must each collide with P
on some parts(otherwise, case 1 will be always better than this). Given
property *, the final 2 paths should be like this: WLOG, P1 will collide
with P on the beginning part, and P2 will collide with P on the endin part,
and these 2 colliding parts don't necessarily cover the whole P.
So, the answer will be for each point (i,j) in P, in the upper part and
lower part split by P, find the optimal path from (m,0)->(i,j) and (i,j)->(0
,n); And then find out the pair (i1,j1), (i2,j2)in P that give the optimal
of
P((m,0)->(i1,j1))+Pupper((i1,j1)->(0,n))+Plower((m,0)->(i2,j2))+P(i2,j2)->(0
,n))
or
Pupper((m,0)->(i2,j2))+P((i2,j2)->(0,n))+P((m,0)->(i1,j1))+Plower((i1,j1)->(
0,n))
assuming (i1,j1) is before (i2,j2) in P.
Total time will be O(mn)+O(m2)+O(n2)
h****n
发帖数: 1093
105
确实挺难的,不过难不一定代表你就挂了,你难别的candidate也一样觉得难,主要看
你面试的想法和思路吧
bless

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

c**s
发帖数: 159
106
两个人的我做过 要同时记录两个人的位置,同时走才行。

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

P*******b
发帖数: 1001
107
lz问你的经验,项目和research了吗?

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

c***s
发帖数: 192
108

structure
感觉recursive的方法是NP-hard的。
如果是这样的话,还不如brute-force的:
就是先找出一个人所有的路径,然后另外一个人用DP。

【在 j*****y 的大作中提到】
: 我也想过先用 recursive 的 方法 show一下 idea, 但是这个 recursive的 structure
: 还是不好弄阿

j*****y
发帖数: 1071
109
多谢 :)

【在 h****n 的大作中提到】
: 确实挺难的,不过难不一定代表你就挂了,你难别的candidate也一样觉得难,主要看
: 你面试的想法和思路吧
: bless
:
: 的。

j*****y
发帖数: 1071
110
好厉害阿 :)

【在 c**s 的大作中提到】
: 两个人的我做过 要同时记录两个人的位置,同时走才行。
:
: 的。

相关主题
怎样求common divisor 最快这题到底是啥意思
却看妻子愁何在,漫卷诗书喜欲狂长年潜水,回馈FLG面经
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb地图上分割成不同区域这个设计题的核心是什么来着?
进入JobHunting版参与讨论
j*****y
发帖数: 1071
111
没怎么问, 也就是随便聊几句

【在 P*******b 的大作中提到】
: lz问你的经验,项目和research了吗?
:
: 的。

j*****y
发帖数: 1071
112
不错,你这个 idea 是 work 的

【在 c***s 的大作中提到】
:
: structure
: 感觉recursive的方法是NP-hard的。
: 如果是这样的话,还不如brute-force的:
: 就是先找出一个人所有的路径,然后另外一个人用DP。

P*******b
发帖数: 1001
113
好像也没有大问system design的问题,基本就全是算法设计。对吧

【在 j*****y 的大作中提到】
: 没怎么问, 也就是随便聊几句
j*****y
发帖数: 1071
114
差不多吧,第四个人差不多和 system design有点沾边

【在 P*******b 的大作中提到】
: 好像也没有大问system design的问题,基本就全是算法设计。对吧
B*******1
发帖数: 2454
115
你这个真的是general hire吗? 怎么看着这么象一个跟算法关系很紧密得职位阿。
反正比我的难多多了,我要是onite遇到这些肯定当场悲剧。
还有,面你的人是小年轻还是工作很多年的googler阿?

【在 j*****y 的大作中提到】
: 差不多吧,第四个人差不多和 system design有点沾边
j*****y
发帖数: 1071
116
面我的人都比较年轻,年纪不算大

【在 B*******1 的大作中提到】
: 你这个真的是general hire吗? 怎么看着这么象一个跟算法关系很紧密得职位阿。
: 反正比我的难多多了,我要是onite遇到这些肯定当场悲剧。
: 还有,面你的人是小年轻还是工作很多年的googler阿?

o***d
发帖数: 313
117
她是做数学的,可以理解吧

【在 B*******1 的大作中提到】
: 你这个真的是general hire吗? 怎么看着这么象一个跟算法关系很紧密得职位阿。
: 反正比我的难多多了,我要是onite遇到这些肯定当场悲剧。
: 还有,面你的人是小年轻还是工作很多年的googler阿?

j*****y
发帖数: 1071
118
数学的做算法应该比科班出身的弱吧? :)

【在 o***d 的大作中提到】
: 她是做数学的,可以理解吧
o***d
发帖数: 313
119
不清楚别人怎么想,如果我有同事是数学出身,我本能反应就是他应该算法很强,就算不
强,应该一说就明白吧.

【在 j*****y 的大作中提到】
: 数学的做算法应该比科班出身的弱吧? :)
B*******1
发帖数: 2454
120
感觉这就是原因,似乎这些年轻人可能进google不久,而且之前算法练多了,所以都面
比较难的,
我当时面的几乎都是lead,senior,都比我年纪大,google里面最少都干了5-6年,所
以很多很多system design question。 记得面的第一个就是40多50的老头。

【在 j*****y 的大作中提到】
: 面我的人都比较年轻,年纪不算大
相关主题
请问一道面试题ms面试题
问个题,用递归方法这题谁知道答案?
一道linked list编程题Amazon的LRU设计题
进入JobHunting版参与讨论
j*****y
发帖数: 1071
121
多谢 :)

【在 o***d 的大作中提到】
: 不清楚别人怎么想,如果我有同事是数学出身,我本能反应就是他应该算法很强,就算不
: 强,应该一说就明白吧.

j*****y
发帖数: 1071
122
羡慕嫉妒恨阿 :)

【在 B*******1 的大作中提到】
: 感觉这就是原因,似乎这些年轻人可能进google不久,而且之前算法练多了,所以都面
: 比较难的,
: 我当时面的几乎都是lead,senior,都比我年纪大,google里面最少都干了5-6年,所
: 以很多很多system design question。 记得面的第一个就是40多50的老头。

w********p
发帖数: 948
123
这题第一反应是DP. 所以要是用greedy, 面试官肯定不同意。
第二反应是两个同时走,想了下觉的有点难。牵扯到每一步谁先走后走。
在想想不对,其实谁走,谁先走后走没关系。就是走两条路,不重合的两条路,然后把
最多的钱拿走。
我觉的,用DP走两趟就好了。
第一次DP走过后,要把那个点mark掉(比如负数),
也就是说,每个人走的时候向上或者向右,同时有mark的地方不可以走。
第一次之前,没有被mark的点。
第一次DP之后,被选着的点都被mark上。
第二次DP的时候,遇到mak下次请绕道。
不知道这个思路是不是合理。

一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值
一看这个就傻了. 两个人的,太难了。 面试官让我先算一个人的算法,
这个
easy.
然后他就问两个人怎么搞,我当时首先想到的是,会不会是 greedy, 先算
第一个人的,然后把第一个人走过的路径上的每个点上的钱变成0,再算第
二个
人的。我当时试图证明这个 greedy是正确的,但也证明不出来。
面试官说你能举出一个反例证明你的 greedy 不 work也行,我当时就试了试
1 2 3
4 5 6
7 8 9

【在 j*****y 的大作中提到】
: 羡慕嫉妒恨阿 :)
w********p
发帖数: 948
124
两个人同时走比较讨厌,因为每一步,谁先谁后,都得考虑。。。
不过对结果是没有帮助。

【在 c**s 的大作中提到】
: 两个人的我做过 要同时记录两个人的位置,同时走才行。
:
: 的。

P*******b
发帖数: 1001
125
想不到lz是数学phd还是F,厉害啊,我觉得你的google肯定拿下来了,我开始排包子了。

【在 o***d 的大作中提到】
: 她是做数学的,可以理解吧
w********p
发帖数: 948
126
数学系多出大牛啊。认识的数学系转CS的没有例外的都是牛人。就是我吭哧吭哧弄很久
的,牛人一下下,就搞定了。

【在 j*****y 的大作中提到】
: 数学的做算法应该比科班出身的弱吧? :)
f*****e
发帖数: 2992
127
这道题DP有点特别,一般是一行一行,这题是一斜列(45度),一斜列的求到达每一
个斜列中任意两个位置(可以相等)的极大值。只有前一个斜列的算好了,才可以算
下一个斜列的值。

【在 w********p 的大作中提到】
: 这题第一反应是DP. 所以要是用greedy, 面试官肯定不同意。
: 第二反应是两个同时走,想了下觉的有点难。牵扯到每一步谁先走后走。
: 在想想不对,其实谁走,谁先走后走没关系。就是走两条路,不重合的两条路,然后把
: 最多的钱拿走。
: 我觉的,用DP走两趟就好了。
: 第一次DP走过后,要把那个点mark掉(比如负数),
: 也就是说,每个人走的时候向上或者向右,同时有mark的地方不可以走。
: 第一次之前,没有被mark的点。
: 第一次DP之后,被选着的点都被mark上。
: 第二次DP的时候,遇到mak下次请绕道。

w********p
发帖数: 948
128
好像想到思路有点问题。
找到一个反例。 如果第一条恰好是内似对角线,按照我的思路,第二条就无解了(堵
死了)。
重新想。

【在 w********p 的大作中提到】
: 这题第一反应是DP. 所以要是用greedy, 面试官肯定不同意。
: 第二反应是两个同时走,想了下觉的有点难。牵扯到每一步谁先走后走。
: 在想想不对,其实谁走,谁先走后走没关系。就是走两条路,不重合的两条路,然后把
: 最多的钱拿走。
: 我觉的,用DP走两趟就好了。
: 第一次DP走过后,要把那个点mark掉(比如负数),
: 也就是说,每个人走的时候向上或者向右,同时有mark的地方不可以走。
: 第一次之前,没有被mark的点。
: 第一次DP之后,被选着的点都被mark上。
: 第二次DP的时候,遇到mak下次请绕道。

x***i
发帖数: 585
129
mark
o***d
发帖数: 313
130
大牛,问个弱问题,这题初始化怎么做?
似乎不容易啊?
难道用dp初始化dp[,,,,]边界?比如 dp[0,2,1,2]这种初始值怎么算出来?

【在 f*****e 的大作中提到】
: 这道题DP有点特别,一般是一行一行,这题是一斜列(45度),一斜列的求到达每一
: 个斜列中任意两个位置(可以相等)的极大值。只有前一个斜列的算好了,才可以算
: 下一个斜列的值。

相关主题
【哪里有C++比较好的LinkedList实现?】FB 面经
问道google面试题linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。
Construct Binary Tree from Inorder and Postorder Traversal请教个G题目
进入JobHunting版参与讨论
f*****e
发帖数: 2992
131
初始化就是,第一斜列只有一个元素A[0][0],只有一个组合,就是它和它自身。
所以dp2[0][0][0][0] = A[0][0]
第二斜列有两个元素(0,1),(1,0),所以有3对组合dp2(0,1,0,1),dp2(0,1,1,0),
dp2(1,0,1,0),这3对组合都可以用dp2[0][0][0][0]算。
dp2(0,1,0,1) = dp2(0,0,0,0) + A[0,1];
dp2(0,1,1,0) = dp2(0,0,0,0) + A[0,1] + A[1,0];
dp2(1,0,1,0) = dp2(0,0,0,0) + A[1,0];
如果45度斜列有n个元素,上面的计算就要算C_n^2 + n = n(n+1)/2次。

【在 o***d 的大作中提到】
: 大牛,问个弱问题,这题初始化怎么做?
: 似乎不容易啊?
: 难道用dp初始化dp[,,,,]边界?比如 dp[0,2,1,2]这种初始值怎么算出来?

f*****e
发帖数: 2992
132
(0,2,2,1)不在45度对角线上,所以不用算。只算45度对角线上的。
一层一层推进,就可以到达右上端点(m,n)

【在 f*****e 的大作中提到】
: 初始化就是,第一斜列只有一个元素A[0][0],只有一个组合,就是它和它自身。
: 所以dp2[0][0][0][0] = A[0][0]
: 第二斜列有两个元素(0,1),(1,0),所以有3对组合dp2(0,1,0,1),dp2(0,1,1,0),
: dp2(1,0,1,0),这3对组合都可以用dp2[0][0][0][0]算。
: dp2(0,1,0,1) = dp2(0,0,0,0) + A[0,1];
: dp2(0,1,1,0) = dp2(0,0,0,0) + A[0,1] + A[1,0];
: dp2(1,0,1,0) = dp2(0,0,0,0) + A[1,0];
: 如果45度斜列有n个元素,上面的计算就要算C_n^2 + n = n(n+1)/2次。

o***d
发帖数: 313
133
好吧,我用你的那个对角线的方法试一下,我刚才在始二爷的那种n^4的方法

【在 f*****e 的大作中提到】
: (0,2,2,1)不在45度对角线上,所以不用算。只算45度对角线上的。
: 一层一层推进,就可以到达右上端点(m,n)

j*****y
发帖数: 1071
134
多谢 :)

了。

【在 P*******b 的大作中提到】
: 想不到lz是数学phd还是F,厉害啊,我觉得你的google肯定拿下来了,我开始排包子了。
j*****y
发帖数: 1071
135
多谢 :)

【在 w********p 的大作中提到】
: 数学系多出大牛啊。认识的数学系转CS的没有例外的都是牛人。就是我吭哧吭哧弄很久
: 的,牛人一下下,就搞定了。

x********y
发帖数: 14
136
bless 楼主.
第二题应该用dp。
如果一个人在位置(i,j)时向上走,就说这个位置是这个人的“折点”。
然后这个问题每个state是(i,j,k),i是当前row,(i,j) 是第一个人的折点,
(i,
k) 是第二个人折点.
递推关系是 state(i,j,k) = max {state(i+1, j1, k1), where j1 <= j and k1
<= k}
sample code:
const int M = 4;
const int N = 4;
int a[M][N] = {
{1, 2, 3, 4},
{1, 0, 3, 0},
{1, 20, 3, 0},
{10, 10, 3, 0}};
int dp_two_max_gold() {
int state[M][N][N];
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
state[i][j][k] = 0;
// First the bottom line.
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
int max_val = max(j, k);
int sum = 0;
for (int m = 0; m <= max_val; ++m) {
sum += a[M - 1][m];
}
state[M - 1][j][k] = sum;
}
}
for (int i = M - 2; i >= 1; --i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
// From (j1, k1) to (j, k).
for (int j1 = 0; j1 <= j; ++j1) {
for (int k1 = 0; k1 <= k; ++k1) {
int max_gold = 0;
for (int m = min(j1, k1); m <= max(j1, k1); ++m) {
if ((m >= j1 && m <= j) || (m >= k1 && m <= k)) {
max_gold += a[i][m];
}
}
if (state[i][j][k] < state[i + 1][j1][k1] + max_gold) {
state[i][j][k] = state[i + 1][j1][k1] + max_gold;
}
}
}
}
}
}
int res = 0;
// NOw compute final result from states in row 1.
for (int j = 0;j < N; ++j) {
for (int k = 0; k < N; ++k) {
int min_val = min(j, k);
int sum = state[1][j][k]; // Row 1 states.
for (int m = min_val; m < N; ++m) {
sum += a[0][m];
}
if (sum > res) {
res = sum;
}
}
}
return res;
}
int main() {
cout << dp_two_max_gold() << endl;
return 0;
}
f*****e
发帖数: 2992
137
你自己的例子都通不过。

k1

【在 x********y 的大作中提到】
: bless 楼主.
: 第二题应该用dp。
: 如果一个人在位置(i,j)时向上走,就说这个位置是这个人的“折点”。
: 然后这个问题每个state是(i,j,k),i是当前row,(i,j) 是第一个人的折点,
: (i,
: k) 是第二个人折点.
: 递推关系是 state(i,j,k) = max {state(i+1, j1, k1), where j1 <= j and k1
: <= k}
: sample code:
: const int M = 4;

H****s
发帖数: 247
138
strong bless!
看了这些题,我怎么感觉都找不着北啊。做了leetcode再看这些题怎么感觉还是当场傻
眼啊。一种想轻生的感觉油然而生啊。
楼主已经很强了!

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
139
多谢 :)

【在 H****s 的大作中提到】
: strong bless!
: 看了这些题,我怎么感觉都找不着北啊。做了leetcode再看这些题怎么感觉还是当场傻
: 眼啊。一种想轻生的感觉油然而生啊。
: 楼主已经很强了!
:
: 的。

h**********y
发帖数: 1293
140
4维dp应该可以,
不过注意两人位置重合时候只加那个位置点数一次。

【在 p*****2 的大作中提到】
:
: 加了一句,检查这个条件。你觉得够了吗?
: def clone(root:QTreeNode):QTreeNode={
: if(root==null) return null
: val newNode=new QTreeNode(root.color)
: for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
: newNode
: }
:
: def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={

相关主题
请教个G题目却看妻子愁何在,漫卷诗书喜欲狂
G家最新电面interview question: Given a list of points in 2D and a single reference point, find k nearest neighb
怎样求common divisor 最快这题到底是啥意思
进入JobHunting版参与讨论
p*****2
发帖数: 21240
141

看我后边的帖子。

【在 h**********y 的大作中提到】
: 4维dp应该可以,
: 不过注意两人位置重合时候只加那个位置点数一次。

o***d
发帖数: 313
142
二爷对这个题的初始化有什么好的办法么?
白天我折腾半天也没找到好办法,fatalme大牛说按对角线作.
如果用你的n^4呢?
问题:看我下面的例子,怎么初始化dp[,,,,]才能满足最后的结果?
比如,简化问题为 从左上角向右下角跑,然后用aoyao 23楼的例子
matrix
4 4 0
5 5 5
0 4 4
那么结果应该是
dp:
4 8 8
9 18 23
9 22 31
我算dp的值第一行第二个值(8)和第三个值(8)总是不对
dp[1,1,1,2]
dp[1,1,1,3]
dp[1,1,1,2]
=max(dp[0,1,0,2],dp[0,1,1,1],dp[1,0,0,2],dp[1,0,1,1])+matrix[0,0]+matrix[0,1]
=max(...)+4+4
=max(...)+8
//so, here, max(...) should be 0. How?
=8???
dp[1,1,1,3]
=max(dp[0,1,0,3],dp[0,1,1,2],dp[1,0,0,3],dp[1,0,1,2])+matrix[0,0]+matrix[0,2]
=max(...)+4+0
=max(...)+4
//so, here, max(...) should be 4, How?
=8????

【在 p*****2 的大作中提到】
:
: 看我后边的帖子。

o***d
发帖数: 313
143
坦白说,fatalme大牛的初始化我没有try过,他举的例子自然没问题,那是第一
和第二个斜列,如果用在那个算法上,我再试一下
我再看看好了,不成就算了
我还找到了这个
http://www.cppblog.com/Climber-pI/archive/2010/10/02/128346.asp
这是noip2000的,解法跟你的一样,似乎他还测试通过了.....
不管怎么说,多谢了.
这次做题,我对dp又多了点理解,justtry同学真是给了个好题
睡觉去了,为了份工作真不容易啊大家

【在 p*****2 的大作中提到】
:
: 看我后边的帖子。

p*****2
发帖数: 21240
144

是我刚才的程序有个bug。你看看这个对不对。
object test6 extends App {
val mat=Array(Array(4,4,0), Array(5,5,5), Array(0, 4, 4))
val m=3
val n=3
val dp=Array.ofDim[Int](m,n,m,n)

for(i<-0 until m; j<-0 until n; x<-0 until m; y<-0 until n if i+j==x+y){
if(i>0 && x>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i-1)(j)(x-
1)(y))
if(i>0 && y>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i-1)(j)(x)
(y-1))
if(j>0 && x>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i)(j-1)(x-
1)(y))
if(j>0 && y>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i)(j-1)(x)
(y-1))

dp(i)(j)(x)(y)+= (if(i==x && j==y) mat(i)(j) else mat(i)(j)+mat(x)(y
))
}

println(dp(m-1)(n-1)(m-1)(n-1))
}

【在 o***d 的大作中提到】
: 坦白说,fatalme大牛的初始化我没有try过,他举的例子自然没问题,那是第一
: 和第二个斜列,如果用在那个算法上,我再试一下
: 我再看看好了,不成就算了
: 我还找到了这个
: http://www.cppblog.com/Climber-pI/archive/2010/10/02/128346.asp
: 这是noip2000的,解法跟你的一样,似乎他还测试通过了.....
: 不管怎么说,多谢了.
: 这次做题,我对dp又多了点理解,justtry同学真是给了个好题
: 睡觉去了,为了份工作真不容易啊大家

H****s
发帖数: 247
145
赞这个研究精神,没想到4维dp也可以这么简洁。本来一看到思维就发怵,看来以后即
使是N维也要硬着头皮上了。 二爷厉害,一下就指出得四维,我即使看得出也没胆做四
维的。
这题我做定了。

【在 o***d 的大作中提到】
: 坦白说,fatalme大牛的初始化我没有try过,他举的例子自然没问题,那是第一
: 和第二个斜列,如果用在那个算法上,我再试一下
: 我再看看好了,不成就算了
: 我还找到了这个
: http://www.cppblog.com/Climber-pI/archive/2010/10/02/128346.asp
: 这是noip2000的,解法跟你的一样,似乎他还测试通过了.....
: 不管怎么说,多谢了.
: 这次做题,我对dp又多了点理解,justtry同学真是给了个好题
: 睡觉去了,为了份工作真不容易啊大家

o***d
发帖数: 313
146
二爷威武!
work了,看了你的code我才明白问题到底出在哪儿........
我测了上面的那个case和另一个简单的case
1 2 3
4 0 6
7 8 9

){
x-
x)

【在 p*****2 的大作中提到】
:
: 是我刚才的程序有个bug。你看看这个对不对。
: object test6 extends App {
: val mat=Array(Array(4,4,0), Array(5,5,5), Array(0, 4, 4))
: val m=3
: val n=3
: val dp=Array.ofDim[Int](m,n,m,n)
:
: for(i<-0 until m; j<-0 until n; x<-0 until m; y<-0 until n if i+j==x+y){
: if(i>0 && x>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i-1)(j)(x-

s*****n
发帖数: 5488
147
楼主什么背景,这题都很难啊。
1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
所有的的点来一遍就可以得到intersection
2. 双向搜是biidrectional dijistra吧。
4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
否则那么多怎么选。然后算概率还要调整。尼玛,不看书老夫早基本忘了叫什么了。没
有NLP背景这题太坑爹了。

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
148
多谢 :)
不是cs科班的 :)

【在 s*****n 的大作中提到】
: 楼主什么背景,这题都很难啊。
: 1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
: 所有的的点来一遍就可以得到intersection
: 2. 双向搜是biidrectional dijistra吧。
: 4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
: 否则那么多怎么选。然后算概率还要调整。尼玛,不看书老夫早基本忘了叫什么了。没
: 有NLP背景这题太坑爹了。
:
: 的。

o***d
发帖数: 313
149
方法2似乎不是个常规方法阿,能问问,是你figure out的方法2,还是他上来就告诉你方
法2,然后问你怎么实现么?

【在 j*****y 的大作中提到】
: prefix tree没让 code,
: 快速找 min, 给了两个方法,第一个没有第二个好.
: given A[1,...,n]
: 方法1 : compute B[1,...,n]
: where B[i] = min {A[j], 1 <=j <= i}
: 这个方法效率不好。
: 方法 2: compute B[1,...,n]
: where B[i] = j such that for any k, i <= k <= j
: , we have A[k] >= A[i] and A[j + 1] < A[i]
: 方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法

j*****y
发帖数: 1071
150
我当时 figure out 出来的 :)

【在 o***d 的大作中提到】
: 方法2似乎不是个常规方法阿,能问问,是你figure out的方法2,还是他上来就告诉你方
: 法2,然后问你怎么实现么?

相关主题
长年潜水,回馈FLG面经问个题,用递归方法
地图上分割成不同区域这个设计题的核心是什么来着?一道linked list编程题
请问一道面试题ms面试题
进入JobHunting版参与讨论
o***d
发帖数: 313
151
果然很厉害,呵呵,这个方法不常规,但也不错,复杂度似乎也不高,尤其是空间复杂度,很
tricky

【在 j*****y 的大作中提到】
: 我当时 figure out 出来的 :)
j*****y
发帖数: 1071
152
多谢 :)

【在 o***d 的大作中提到】
: 果然很厉害,呵呵,这个方法不常规,但也不错,复杂度似乎也不高,尤其是空间复杂度,很
: tricky

w********p
发帖数: 948
153
我偷懒,回头再写这题。
p*****2
发帖数: 21240
c********t
发帖数: 5706
155
来晚了,看到你的面经,我面瘫了!
big big bless!
问个大家没问的,如何实现hashtable, 请问你是用 list chaining还是open address
做的?

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
156
多谢 :)
我用的是 chaining

address

【在 c********t 的大作中提到】
: 来晚了,看到你的面经,我面瘫了!
: big big bless!
: 问个大家没问的,如何实现hashtable, 请问你是用 list chaining还是open address
: 做的?
:
: 的。

c***s
发帖数: 192
157
你这个算法的复杂度是多少啊?
最差情况下你还得扫描B[p...q]啊。

【在 j*****y 的大作中提到】
: prefix tree没让 code,
: 快速找 min, 给了两个方法,第一个没有第二个好.
: given A[1,...,n]
: 方法1 : compute B[1,...,n]
: where B[i] = min {A[j], 1 <=j <= i}
: 这个方法效率不好。
: 方法 2: compute B[1,...,n]
: where B[i] = j such that for any k, i <= k <= j
: , we have A[k] >= A[i] and A[j + 1] < A[i]
: 方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法

j*****y
发帖数: 1071
158
最差情况下是线性的,比如 A 是 decreasing的

【在 c***s 的大作中提到】
: 你这个算法的复杂度是多少啊?
: 最差情况下你还得扫描B[p...q]啊。

c***s
发帖数: 192
159
可是这道题有log(n)的算法啊。
就是建一个二叉树来保存每一个区域的最小值。

【在 j*****y 的大作中提到】
: 最差情况下是线性的,比如 A 是 decreasing的
j*****y
发帖数: 1071
160
这个我还没想,板上有人给出了这个思路 :)

【在 c***s 的大作中提到】
: 可是这道题有log(n)的算法啊。
: 就是建一个二叉树来保存每一个区域的最小值。

相关主题
这题谁知道答案?问道google面试题
Amazon的LRU设计题Construct Binary Tree from Inorder and Postorder Traversal
【哪里有C++比较好的LinkedList实现?】FB 面经
进入JobHunting版参与讨论
c********t
发帖数: 5706
161
二爷, 你博客上的codes是不是只有 左下角和右上角都为0的时候才正确?
大家测测 int[][] matrix = { { 12, 2, 10, 1 }, { 4, 9, 8, 11 }, { 3, 6, 7, 5
} };
是什么结果?
应该是66,可我为什么得出64呢?

【在 p*****2 的大作中提到】
: 粗略的想了一下。感觉是个4维DP
: dp[i][j][x][y] 是A走到(i,j), B走到(x)(y)能够拿到的最大钱数
: dp[i][j][x][y]=max(dp[i+1][j][x+1][y], dp[i+1][j][x][y-1] 一共四种情况
: + if(i==x && j==y) x(i)(j) else x(i)(j)+x(x)(y)
: 最后返回dp(0)(n-1)(0)(n-1)

c********t
发帖数: 5706
162
大侠帮忙看看有什么bug? 多谢!
public static int twoMaxFromLBtoRT(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int n = matrix[0].length;
int m = matrix.length;
int[][][][] dp = new int[m][n][m][n];
dp[m - 1][0][m - 1][0] = matrix[m - 1][0];
for (int j = m - 2; j >= 0; j--) {
dp[j][0][j][0] = matrix[j][0] + dp[j + 1][0][j + 1][0];
}
for (int i = 1; i < n; i++) {
dp[m - 1][i][m - 1][i] = matrix[m - 1][i]
+ dp[m - 1][i - 1][m - 1][i - 1];
}
for (int j = m - 2; j >= 0; j--) {
for (int i = 1; i < n; i++) {
dp[j][0][m - 1][i] = dp[j][0][j][0] + dp[m - 1][i][m - 1][i]
- matrix[m - 1][0];
dp[m - 1][i][j][0] = dp[j][0][m - 1][i];
}
}
for (int j = m - 2; j >= 0; j--) {
for (int i = 1; i < n; i++) {
for (int q = m - 2; q >= 0; q--) {
for (int p = 1; p < n; p++) {
dp[j][i][q][p] = Math.max(Math.max(
dp[j + 1][i][q + 1][p],
dp[j + 1][i][q][p - 1]), Math.max(
dp[j][i - 1][q + 1][p],
dp[j][i - 1][q][p - 1]));
if (j == q && i == p) {
dp[j][i][q][p]+=matrix[j][i];
}else{
dp[j][i][q][p]+=matrix[j][i] + matrix[q][p];
}
}
}
}
}
return dp[0][n - 1][0][n - 1];
}

5

【在 c********t 的大作中提到】
: 二爷, 你博客上的codes是不是只有 左下角和右上角都为0的时候才正确?
: 大家测测 int[][] matrix = { { 12, 2, 10, 1 }, { 4, 9, 8, 11 }, { 3, 6, 7, 5
: } };
: 是什么结果?
: 应该是66,可我为什么得出64呢?

f*****e
发帖数: 2992
163
你这个复杂度多少?

【在 c********t 的大作中提到】
: 大侠帮忙看看有什么bug? 多谢!
: public static int twoMaxFromLBtoRT(int[][] matrix) {
: if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
: return 0;
: int n = matrix[0].length;
: int m = matrix.length;
: int[][][][] dp = new int[m][n][m][n];
: dp[m - 1][0][m - 1][0] = matrix[m - 1][0];
: for (int j = m - 2; j >= 0; j--) {
: dp[j][0][j][0] = matrix[j][0] + dp[j + 1][0][j + 1][0];

c********t
发帖数: 5706
164
嗯,惭愧, 想先写个 n^4,但是都过不了我自己的test case.

【在 f*****e 的大作中提到】
: 你这个复杂度多少?
a*****4
发帖数: 342
165
想起一个朋友几年前的去G家的经历。 准备了一个月,Onsite 2次,最后没要。过了一
年HR电话再安排一次onsite,朋友回答伤心了,不去了。第二天HR又来电话,说你可以
直接上班了。
j*****y
发帖数: 1071
166
有意思 :)

【在 a*****4 的大作中提到】
: 想起一个朋友几年前的去G家的经历。 准备了一个月,Onsite 2次,最后没要。过了一
: 年HR电话再安排一次onsite,朋友回答伤心了,不去了。第二天HR又来电话,说你可以
: 直接上班了。

c********t
发帖数: 5706
167
仿照别人的,把初始化都去掉反而对了,奇怪。大牛有空就帮看一眼哪里有错吧。

【在 c********t 的大作中提到】
: 大侠帮忙看看有什么bug? 多谢!
: public static int twoMaxFromLBtoRT(int[][] matrix) {
: if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
: return 0;
: int n = matrix[0].length;
: int m = matrix.length;
: int[][][][] dp = new int[m][n][m][n];
: dp[m - 1][0][m - 1][0] = matrix[m - 1][0];
: for (int j = m - 2; j >= 0; j--) {
: dp[j][0][j][0] = matrix[j][0] + dp[j + 1][0][j + 1][0];

e***s
发帖数: 799
168
这种事也有?
BTW,谢谢楼主

【在 a*****4 的大作中提到】
: 想起一个朋友几年前的去G家的经历。 准备了一个月,Onsite 2次,最后没要。过了一
: 年HR电话再安排一次onsite,朋友回答伤心了,不去了。第二天HR又来电话,说你可以
: 直接上班了。

S**********r
发帖数: 284
169
问题
一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值.
为了叙述方便,改成从左上(0,0) 走到 右下 (m-1, n-1)
分析
三维 DP ,有点烦琐,我也没有验证过,自己感觉是对。这个问题的重点就是,每走一
步都会破原来的状态。 通过分析,可以知道,最优解中,两个人走的线路,不可能有
任何的重合。 证明方法是,只要有重合,总能通过修改一条线路,去掉重合而达到更
优的解。 也就是说,要得到最优解的话,如果某个位置的金币被人拿走了,这个位
置,另一个人就不能再去走。 还可以观察到,在任何一层 i, 这两个人所处的位
置 j 和 k, j < k 总成立.
A 是 m x n 的matrix,假设所有数都非负数
C 是 m x m x n 的 3d matrix, C[i][j][k] 表示, 两个人处于A[i][j] 和 A[
i][k] 的位置时, 能拿到最多的金币数。
C[i][j][k] 状态,基于前面的分析(如果某个位置的金币被拿走,就不能再走),
只能由下面三种情况转换过来,
第一是从 C[i-1][j][k] 变换过来, 也就是说, 两个人同是往下走一层。
第二是 C[i][j-1][k], 这个意思是,第一个人从位置 j-1 走到 j, 但是 第二
个人保持不动. 这么移动可能的条件是, j-1>= 0,
第三是 C[i][j][k-1], 这个意思是,第一个不动, 第二个人从 k-1 走到 k。
这个移动可能的条件是 k-1 > j . 如果这个条件不成立的话, 第一个人要走到因为
确保每个合理的走动,都要拿到金币。
(其实还有一种情况, 两人同是往右边走动一格,但是这个可以分解成 第二 和第三
种情况,所以就不用考虑了。)
pseudo code:
C[i][j][k] = INT_MIN;
C[0][0][k] = sum(A[0][0] .... A[0][k]) // 第一行的初始化,有点特殊,
C[i][j][k] = max(C[i][j][k], C[i][j-1][k-1] + A[i][j] + A[i][k]);
if (j-1>=0) C[i][j][k] = max(C[i][j][k], C[i][j-1][k] + A[i][j]);
if (k-1>j) C[i][j][k] = max(C[i][j][k], C[i][j][k-1] + A[i][k]);
H****s
发帖数: 247
170
应该是 66, 这是我的代码
int maxMoney(vector> & mat)
{
int rowCnt = mat.size(), colCnt = mat[0].size();
vector> table(rowCnt + 1, vector(colCnt + 1, 0));
vector>>> cache(rowCnt + 1, vector vector>>(colCnt + 1, table));
for(int i = rowCnt - 1; i >= 0; --i){
for(int j = 1; j <= colCnt; ++j){
for(int k = rowCnt - 1; k >= 0; --k){
for(int l = 1; l <= colCnt; ++l){
cache[i][j][k][l] = max(cache[i + 1][j][k + 1][l], cache
[i+1][j][k][l - 1]);
cache[i][j][k][l] = max(cache[i][j][k][l], cache[i][j -
1][k + 1][l]);
cache[i][j][k][l] = max(cache[i][j][k][l], cache[i][j -
1][k][l - 1]);
cache[i][j][k][l] += (mat[i][j-1] + mat[k][l-1]);
if(i==k && j==l) cache[i][j][k][l] -= mat[i][j-1];
}
}
}
}
return cache[0][colCnt][0][colCnt];
}

5

【在 c********t 的大作中提到】
: 二爷, 你博客上的codes是不是只有 左下角和右上角都为0的时候才正确?
: 大家测测 int[][] matrix = { { 12, 2, 10, 1 }, { 4, 9, 8, 11 }, { 3, 6, 7, 5
: } };
: 是什么结果?
: 应该是66,可我为什么得出64呢?

相关主题
FB 面经G家最新电面
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。怎样求common divisor 最快
请教个G题目却看妻子愁何在,漫卷诗书喜欲狂
进入JobHunting版参与讨论
j*****y
发帖数: 1071
171
求 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] 的最小
值.



h*******e
发帖数: 1377
172
2个人那个双向广搜啊。
j*****y
发帖数: 1071
173
怎么做阿?

【在 h*******e 的大作中提到】
: 2个人那个双向广搜啊。
j******2
发帖数: 362
174
先赞再看!
j******2
发帖数: 362
175
并狠狠地bless
j*****y
发帖数: 1071
176
多谢 :)

【在 j******2 的大作中提到】
: 并狠狠地bless
f*******t
发帖数: 7549
177
好难的题,bless
j*****y
发帖数: 1071
178
多谢 :)

【在 f*******t 的大作中提到】
: 好难的题,bless
p*****2
发帖数: 21240
179

是不是不应该变成0,应该变成-1,也就是2不能再走了?

【在 j*****y 的大作中提到】
: 怎么做阿?
B*******1
发帖数: 2454
180
我也觉得。给我就跪了。

★ 发自iPhone App: ChineseWeb 7.8

【在 f*******t 的大作中提到】
: 好难的题,bless
相关主题
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb地图上分割成不同区域这个设计题的核心是什么来着?
这题到底是啥意思请问一道面试题
长年潜水,回馈FLG面经问个题,用递归方法
进入JobHunting版参与讨论
p*****2
发帖数: 21240
181

这个不行。不能一个先走。要两个一起走才可以。

【在 p*****2 的大作中提到】
:
: 是不是不应该变成0,应该变成-1,也就是2不能再走了?

p*****2
发帖数: 21240
182
想到了。不能一个先走。
两个一起走,因为每一个可以走两个方向,那么两个人一起走就有4种可能。选择4种里
边的最大钱数的那个就可以了。
w****a
发帖数: 710
183
楼主什么背景?这个题难度比普通的G家面经大啊。
p*****2
发帖数: 21240
184

感觉不能一个先走。

【在 a***o 的大作中提到】
: 我觉得能拿到offer~ bless!
a***o
发帖数: 1182
185
好像是,不能往下走

【在 p*****2 的大作中提到】
:
: 感觉不能一个先走。

p*****2
发帖数: 21240
186

可能也不一定。再想想。

【在 p*****2 的大作中提到】
: 想到了。不能一个先走。
: 两个一起走,因为每一个可以走两个方向,那么两个人一起走就有4种可能。选择4种里
: 边的最大钱数的那个就可以了。

j*****y
发帖数: 1071
187
我也想过先用 recursive 的 方法 show一下 idea, 但是这个 recursive的 structure
还是不好弄阿

【在 p*****2 的大作中提到】
: 想到了。不能一个先走。
: 两个一起走,因为每一个可以走两个方向,那么两个人一起走就有4种可能。选择4种里
: 边的最大钱数的那个就可以了。

j*****y
发帖数: 1071
188
问题的关键不是先走,后走或者同时走
怎么的顺序走都可以,关键是要求出两个人拿到的钱
的和的最大数目

【在 p*****2 的大作中提到】
:
: 可能也不一定。再想想。

j*****y
发帖数: 1071
189
那道 dp的题目感觉是个新题。没见过.

【在 w****a 的大作中提到】
: 楼主什么背景?这个题难度比普通的G家面经大啊。
j*****y
发帖数: 1071
190
背景很弱, phd + 1 年。而且还不是科班cs

【在 w****a 的大作中提到】
: 楼主什么背景?这个题难度比普通的G家面经大啊。
相关主题
一道linked list编程题Amazon的LRU设计题
ms面试题【哪里有C++比较好的LinkedList实现?】
这题谁知道答案?问道google面试题
进入JobHunting版参与讨论
B*******1
发帖数: 2454
191
是烙印出的?

★ 发自iPhone App: ChineseWeb 7.8

【在 j*****y 的大作中提到】
: 背景很弱, phd + 1 年。而且还不是科班cs
w****a
发帖数: 710
192
Bless!楼主答的应该都没啥问题吧。
prefix tree让你code没?
快速找范围内min值你怎么答的?
a***o
发帖数: 1182
193
证明出来了
一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
交点,然后绕道,根据方向,和是相加的
楼主说的greedy是错的
比如这种:
40 40 0
50 50 50
0 40 40
左下角的是起点,右上角的是终点

【在 p*****2 的大作中提到】
:
: 可能也不一定。再想想。

p******9
发帖数: 47
194
按对角线进行动态规划,两个人都需要n + m - 1步才能走到终到,每一步两个人都在
一条斜对角线上,所以可以进行动态规划,分为n + m - 1步,每一步有n^2状态,n^3
可解。
p*****2
发帖数: 21240
195
粗略的想了一下。感觉是个4维DP
dp[i][j][x][y] 是A走到(i,j), B走到(x)(y)能够拿到的最大钱数
dp[i][j][x][y]=max(dp[i+1][j][x+1][y], dp[i+1][j][x][y-1] 一共四种情况
+ if(i==x && j==y) x(i)(j) else x(i)(j)+x(x)(y)
最后返回dp(0)(n-1)(0)(n-1)
p******9
发帖数: 47
p*****2
发帖数: 21240
197

感觉可以走相同的点。至少如果那个点的钱数是0

【在 a***o 的大作中提到】
: 证明出来了
: 一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
: 交点,然后绕道,根据方向,和是相加的
: 楼主说的greedy是错的
: 比如这种:
: 40 40 0
: 50 50 50
: 0 40 40
: 左下角的是起点,右上角的是终点

f*****e
发帖数: 2992
198
握手!差不多想法。有些细节不同。
最后一题:minimum
就是记录local minimum的位置。然后对local minimum的位置建
balanced binary search tree。
直接binary search 位置也行。

【在 p*****2 的大作中提到】
: 粗略的想了一下。感觉是个4维DP
: dp[i][j][x][y] 是A走到(i,j), B走到(x)(y)能够拿到的最大钱数
: dp[i][j][x][y]=max(dp[i+1][j][x+1][y], dp[i+1][j][x][y-1] 一共四种情况
: + if(i==x && j==y) x(i)(j) else x(i)(j)+x(x)(y)
: 最后返回dp(0)(n-1)(0)(n-1)

p*****2
发帖数: 21240
199

交叉点的钱数也许是0,所以走相同的点无所谓

【在 a***o 的大作中提到】
: 证明出来了
: 一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
: 交点,然后绕道,根据方向,和是相加的
: 楼主说的greedy是错的
: 比如这种:
: 40 40 0
: 50 50 50
: 0 40 40
: 左下角的是起点,右上角的是终点

j*****y
发帖数: 1071
200
prefix tree没让 code,
快速找 min, 给了两个方法,第一个没有第二个好.
given A[1,...,n]
方法1 : compute B[1,...,n]
where B[i] = min {A[j], 1 <=j <= i}
这个方法效率不好。
方法 2: compute B[1,...,n]
where B[i] = j such that for any k, i <= k <= j
, we have A[k] >= A[i] and A[j + 1] < A[i]
方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法
二的 search min
int minimum(int start, int index)
的时候,出了些 边界上的 error

【在 w****a 的大作中提到】
: Bless!楼主答的应该都没啥问题吧。
: prefix tree让你code没?
: 快速找范围内min值你怎么答的?

相关主题
Construct Binary Tree from Inorder and Postorder Traversal请教个G题目
FB 面经G家最新电面
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。怎样求common divisor 最快
进入JobHunting版参与讨论
p*****2
发帖数: 21240
201

嗯。感觉greedy不行,还是得用DP,考虑所有情况。

【在 f*****e 的大作中提到】
: 握手!差不多想法。有些细节不同。
: 最后一题:minimum
: 就是记录local minimum的位置。然后对local minimum的位置建
: balanced binary search tree。
: 直接binary search 位置也行。

a***o
发帖数: 1182
202
如果绕道的那个点不是0的话有所谓呀

【在 p*****2 的大作中提到】
:
: 嗯。感觉greedy不行,还是得用DP,考虑所有情况。

f*****e
发帖数: 2992
203
right!

【在 p*****2 的大作中提到】
:
: 嗯。感觉greedy不行,还是得用DP,考虑所有情况。

s****0
发帖数: 117
204
在两条路相交的时候要特殊处理一下就行了,对不对?
p*****2
发帖数: 21240
205

我的意思是解法可以不考虑这种情况。考虑的话反而变复杂了。DP把所有情况都考虑了
,管你是不是走了相同的点。

【在 a***o 的大作中提到】
: 如果绕道的那个点不是0的话有所谓呀
a***o
发帖数: 1182
206
O(n^4) ...

【在 p*****2 的大作中提到】
:
: 我的意思是解法可以不考虑这种情况。考虑的话反而变复杂了。DP把所有情况都考虑了
: ,管你是不是走了相同的点。

p******9
发帖数: 47
207
按对角线一步一步走 可以优化到O(n^3)时间,O(n^2)空间
p*****2
发帖数: 21240
208

上边有个n^3的DP,你看看,我还没仔细看。

【在 a***o 的大作中提到】
: O(n^4) ...
f*****e
发帖数: 2992
209
storm8的 online test 的升级版,3个循环搞定。
for(int j = 0; j < m; j++) // row from bottom to top
for(int i = 0; i < n; i++) // column from left to right
for(int k = 0; k <=j; k++) // calculate diagnal '\' elements
dp2[i][j][i+k][j-k] = max{of the 4 combinations};
// k = 0 is what we want, other values of k are prepared for later
calculation of the 4 combinations (left, left), (left, down), (down, left),
(down, down)
O(n*(1+...+m))=O(nm^2)=O(MN*min(M,N)), m = min(M, N)
-------(i,j)>---->>---->(n,m) <= new row is calculated from left to right
| | \ \ \ \ \ \ \
| | \ \ \ \ \ \ \
| | \ \ \ \ \ \
----(i,j-k)----(i+k,j-k) where k is from 0 to j
| | | \ \ \ \
| | | \ \ \
| | | \ \
----------------------------

【在 p*****2 的大作中提到】
:
: 上边有个n^3的DP,你看看,我还没仔细看。

b*********h
发帖数: 103
210
两个人那个...noip 2000 就考过了...经典 dp
相关主题
怎样求common divisor 最快这题到底是啥意思
却看妻子愁何在,漫卷诗书喜欲狂长年潜水,回馈FLG面经
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb地图上分割成不同区域这个设计题的核心是什么来着?
进入JobHunting版参与讨论
P*******b
发帖数: 1001
211
bless!
第一题intersection的函数应该长什么样?
TreeNode* intersection(TreeNode* root1, TreeNode* root2)
返回新的树,这样对吗?

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

s****0
发帖数: 117
212
zkss

【在 b*********h 的大作中提到】
: 两个人那个...noip 2000 就考过了...经典 dp
P*******b
发帖数: 1001
213
lz这些题都做出来了吗?很厉害啊。
第一道题试着写了写,感觉半个小时想考虑全面并写出来代码很难啊

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

s******k
发帖数: 3716
214
bless。
道所谓的难题这么做(DP):
首先,假设每个节点的金子都是非负数。那么,两个人走的路线必然不相交,否则可以
修改一个人的路线使得总金子数不减少。
现在,两个人同时走,那么在第一步只有一个选择(一个向上一个向右),第二步要在
三个位置取两个,第三步是四个位置取两个。只要知道在该位置的最大钱数就可以继续
计算:
cost(i1,j1,i2,j2) = max(cost(i1,j1-1,i2,j2-1),cost(i1-1,j1,i2,j2-1),cost(i1,
j1-1,i2-1,j2),cos(i1-1,j1,i2-1,j2))+money(i1,j1)+money(i2,j2).
这里i1+j1=i2+j2。最后把cost(m,n,m,n)算出来就好了。

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
215
对的
多谢 :)

【在 P*******b 的大作中提到】
: bless!
: 第一题intersection的函数应该长什么样?
: TreeNode* intersection(TreeNode* root1, TreeNode* root2)
: 返回新的树,这样对吗?
:
: 的。

p*****2
发帖数: 21240
216

想了想。感觉还好。我准备写一下。

【在 P*******b 的大作中提到】
: lz这些题都做出来了吗?很厉害啊。
: 第一道题试着写了写,感觉半个小时想考虑全面并写出来代码很难啊
:
: 的。

f*****e
发帖数: 2992
217
差不多:
http://mitbbs.com/article1/JobHunting/32322997_3_0.html

i1,

【在 s******k 的大作中提到】
: bless。
: 道所谓的难题这么做(DP):
: 首先,假设每个节点的金子都是非负数。那么,两个人走的路线必然不相交,否则可以
: 修改一个人的路线使得总金子数不减少。
: 现在,两个人同时走,那么在第一步只有一个选择(一个向上一个向右),第二步要在
: 三个位置取两个,第三步是四个位置取两个。只要知道在该位置的最大钱数就可以继续
: 计算:
: cost(i1,j1,i2,j2) = max(cost(i1,j1-1,i2,j2-1),cost(i1-1,j1,i2,j2-1),cost(i1,
: j1-1,i2-1,j2),cos(i1-1,j1,i2-1,j2))+money(i1,j1)+money(i2,j2).
: 这里i1+j1=i2+j2。最后把cost(m,n,m,n)算出来就好了。

j*****y
发帖数: 1071
218
不是 :)

【在 B*******1 的大作中提到】
: 是烙印出的?
:
: ★ 发自iPhone App: ChineseWeb 7.8

j*****y
发帖数: 1071
219
多谢 :)

【在 w****a 的大作中提到】
: Bless!楼主答的应该都没啥问题吧。
: prefix tree让你code没?
: 快速找范围内min值你怎么答的?

p*****2
发帖数: 21240
220
第一题练了练。没有测试。
class QTreeNode (var color:Int){
val children=new Array[QTreeNode](4)
}
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}

def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.children(i)=intersection(left.children
(i), right.children(i))
newNode
}
else if(left.color==0 || right.color==0) return new QTreeNode(0)
else if(left.color==1) return clone(right)
else return clone(left)
}
相关主题
请问一道面试题ms面试题
问个题,用递归方法这题谁知道答案?
一道linked list编程题Amazon的LRU设计题
进入JobHunting版参与讨论
j*****y
发帖数: 1071
221
我当时要是能想出你这个反例就好了 :)

【在 a***o 的大作中提到】
: 证明出来了
: 一定不能走相同的节点(除了起点,终点以外),因为如果有相同节点,取第一个
: 交点,然后绕道,根据方向,和是相加的
: 楼主说的greedy是错的
: 比如这种:
: 40 40 0
: 50 50 50
: 0 40 40
: 左下角的是起点,右上角的是终点

p*****2
发帖数: 21240
222

这个搞一个binary tree行吗?
root是(0, n-1) + min in (0,n-1)
然后从min两边分成两棵子树。
查找的时候logn复杂度

【在 j*****y 的大作中提到】
: prefix tree没让 code,
: 快速找 min, 给了两个方法,第一个没有第二个好.
: given A[1,...,n]
: 方法1 : compute B[1,...,n]
: where B[i] = min {A[j], 1 <=j <= i}
: 这个方法效率不好。
: 方法 2: compute B[1,...,n]
: where B[i] = j such that for any k, i <= k <= j
: , we have A[k] >= A[i] and A[j + 1] < A[i]
: 方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法

o***d
发帖数: 313
223
先bless再看

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
224
多谢 :)

【在 o***d 的大作中提到】
: 先bless再看
:
: 的。

f*****e
发帖数: 2992
225
可以对所有元素建Balanced-BST。
不过应该把位置作为key建平衡二叉树,而且每个节点还应该记录他左子树和右子树的
最小值。

【在 p*****2 的大作中提到】
:
: 这个搞一个binary tree行吗?
: root是(0, n-1) + min in (0,n-1)
: 然后从min两边分成两棵子树。
: 查找的时候logn复杂度

p*****2
发帖数: 21240
226

随便搞了一个。不是balanced
class Node(arr:Array[Int], start:Int, end:Int){
val minid=arr.indexOf(arr.slice(start,end+1).min,start)
val left=if(start val right=if(end>minid) new Node(arr,minid+1,end) else null

def query(s:Int, e:Int):Int={
if(e if(s>minid) return right.query(s,e)
arr(minid)
}
}

【在 f*****e 的大作中提到】
: 可以对所有元素建Balanced-BST。
: 不过应该把位置作为key建平衡二叉树,而且每个节点还应该记录他左子树和右子树的
: 最小值。

f*****e
发帖数: 2992
227
第二个人出的第1题就是第四个人出的第2题的提示。

【在 p*****2 的大作中提到】
:
: 随便搞了一个。不是balanced
: class Node(arr:Array[Int], start:Int, end:Int){
: val minid=arr.indexOf(arr.slice(start,end+1).min,start)
: val left=if(start: val right=if(end>minid) new Node(arr,minid+1,end) else null
:
: def query(s:Int, e:Int):Int={
: if(e: if(s>minid) return right.query(s,e)

p*****2
发帖数: 21240
228

第四题不是不是sorted的吗

【在 f*****e 的大作中提到】
: 第二个人出的第1题就是第四个人出的第2题的提示。
f*****e
发帖数: 2992
229
位置是sorted的。呵呵。

【在 p*****2 的大作中提到】
:
: 第四题不是不是sorted的吗

j*****y
发帖数: 1071
230
第四题是任意的array

【在 p*****2 的大作中提到】
:
: 第四题不是不是sorted的吗

相关主题
【哪里有C++比较好的LinkedList实现?】FB 面经
问道google面试题linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。
Construct Binary Tree from Inorder and Postorder Traversal请教个G题目
进入JobHunting版参与讨论
f*****e
发帖数: 2992
231
算法就是找到一个node, 位置为k,使得 start < k < end
然后找start在树中的位置,并同时记录k之后所有经过节点 右 子树的最小值min1。
然后找end在树中的位置,并同时记录k之后所有经过节点 左 子树的最小值min2。
然后最终结果就是min(min1, min2)

【在 f*****e 的大作中提到】
: 位置是sorted的。呵呵。
p*****2
发帖数: 21240
232

对。这样可以。建balanced BST。coding要麻烦一些了。

【在 f*****e 的大作中提到】
: 位置是sorted的。呵呵。
f*****e
发帖数: 2992
233
一个节点上的钱只能用一次。

【在 o***d 的大作中提到】
: 先bless再看
:
: 的。

f*****e
发帖数: 2992
234
你的简历肯定很impressive,要不然google会这么狠!:-)

【在 j*****y 的大作中提到】
: 第四题是任意的array
o***d
发帖数: 313
235
第4题,似乎以前见过?说是把用户以前的搜索的数据存在本地,然后做trie?我是说,他问
怎么加快速度,似乎是调本地的以前的数据和bookmarks?
4.2???
怎么做?难道再做个数据结构,把数组先sort一遍,对应好原来的数组????
总之,确实够难啊....

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
236
我就觉得和你的差距不是那么一点点阿 :)
你太厉害了,那道 dp的题目我这几天一直在想,还是没想出来,
我就对自己说,坦然了,当时没想出来确实就是没想出来.

【在 f*****e 的大作中提到】
: 你的简历肯定很impressive,要不然google会这么狠!:-)
p*****2
发帖数: 21240
237

嗯。新题挺多的。LZ的面经挺珍贵的。祝LZ好运。

【在 f*****e 的大作中提到】
: 你的简历肯定很impressive,要不然google会这么狠!:-)
j*****y
发帖数: 1071
238
多谢二爷 :)

【在 p*****2 的大作中提到】
:
: 嗯。新题挺多的。LZ的面经挺珍贵的。祝LZ好运。

p*****2
发帖数: 21240
239

我感觉那道DP的思路就是先想greedy,这个特别自然。然后发现greedy是错的,就自然
想到DP了。因为DP的根本还是brute force。你想到greedy了,但是当时可能紧张没有
想到greedy是错的,面试官也在这个方向引导了。

【在 j*****y 的大作中提到】
: 我就觉得和你的差距不是那么一点点阿 :)
: 你太厉害了,那道 dp的题目我这几天一直在想,还是没想出来,
: 我就对自己说,坦然了,当时没想出来确实就是没想出来.

j*****y
发帖数: 1071
240
还是思路没有二爷这么敏捷阿 :)

【在 p*****2 的大作中提到】
:
: 我感觉那道DP的思路就是先想greedy,这个特别自然。然后发现greedy是错的,就自然
: 想到DP了。因为DP的根本还是brute force。你想到greedy了,但是当时可能紧张没有
: 想到greedy是错的,面试官也在这个方向引导了。

相关主题
请教个G题目却看妻子愁何在,漫卷诗书喜欲狂
G家最新电面interview question: Given a list of points in 2D and a single reference point, find k nearest neighb
怎样求common divisor 最快这题到底是啥意思
进入JobHunting版参与讨论
j*****y
发帖数: 1071
241
多谢二爷启发.

【在 p*****2 的大作中提到】
:
: 我感觉那道DP的思路就是先想greedy,这个特别自然。然后发现greedy是错的,就自然
: 想到DP了。因为DP的根本还是brute force。你想到greedy了,但是当时可能紧张没有
: 想到greedy是错的,面试官也在这个方向引导了。

l***b
发帖数: 125
242
quadtree...这个似乎很少考,两年前我去也被问到这个,不会还是同一个面试官吧:)

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
243
面我的是个老美

:)

【在 l***b 的大作中提到】
: quadtree...这个似乎很少考,两年前我去也被问到这个,不会还是同一个面试官吧:)
:
: 的。

p*****2
发帖数: 21240
244

我要是面试的时候也不一定能想出来呢。面试一紧张还真难说了。哎。感觉你这次面试
比一般的onsite难度高出一个级别。不过可能是好事。

【在 j*****y 的大作中提到】
: 还是思路没有二爷这么敏捷阿 :)
j*****y
发帖数: 1071
245
google一般是面5个人的吧,我这个只见四个人,感觉有点郁闷

【在 p*****2 的大作中提到】
:
: 我要是面试的时候也不一定能想出来呢。面试一紧张还真难说了。哎。感觉你这次面试
: 比一般的onsite难度高出一个级别。不过可能是好事。

j*****y
发帖数: 1071
246
多谢 :)

【在 p*****2 的大作中提到】
:
: 我要是面试的时候也不一定能想出来呢。面试一紧张还真难说了。哎。感觉你这次面试
: 比一般的onsite难度高出一个级别。不过可能是好事。

l***b
发帖数: 125
247
好像是个老美,不过时间久了,记不确切啦。感觉你答得都还不错,bless:)

【在 j*****y 的大作中提到】
: 面我的是个老美
:
: :)

p*****2
发帖数: 21240
248

:)
你上次考的是什么题?前两天有个T的面试官说quadtree解。还不清楚应该怎么解。

【在 l***b 的大作中提到】
: quadtree...这个似乎很少考,两年前我去也被问到这个,不会还是同一个面试官吧:)
:
: 的。

j*****y
发帖数: 1071
249
多谢 :)

【在 l***b 的大作中提到】
: 好像是个老美,不过时间久了,记不确切啦。感觉你答得都还不错,bless:)
j*****y
发帖数: 1071
250
多谢 :)

【在 m******s 的大作中提到】
: 咦,和我面的味道有点像。。。非主流难题啊。。。bless
:
: 的。

相关主题
长年潜水,回馈FLG面经问个题,用递归方法
地图上分割成不同区域这个设计题的核心是什么来着?一道linked list编程题
请问一道面试题ms面试题
进入JobHunting版参与讨论
p*****2
发帖数: 21240
251

感觉4个人挺正常的呀。

【在 j*****y 的大作中提到】
: google一般是面5个人的吧,我这个只见四个人,感觉有点郁闷
p*****2
发帖数: 21240
252

你的面经在哪里呢?

【在 m******s 的大作中提到】
: 咦,和我面的味道有点像。。。非主流难题啊。。。bless
:
: 的。

l***b
发帖数: 125
253
另外,没全做出来应该也没什么。感觉面试官有时更看重你的思路和沟通之类。我当时
有一个题也没想出最优解,只是和面试官讨论了一堆次优解和可能的时空tradeoff。后
来听hr说所有feedback都很positive,所以不用苛求完美

【在 j*****y 的大作中提到】
: 多谢 :)
j*****y
发帖数: 1071
254
好厉害。
他们还真的是把我当成了 new grad

【在 m******s 的大作中提到】
: 少了轮thesis discussion,估计跟你非科班有关。。。
: 不过不知道是不是把你算成fresh orz

j*****y
发帖数: 1071
255
多谢 :)

【在 l***b 的大作中提到】
: 另外,没全做出来应该也没什么。感觉面试官有时更看重你的思路和沟通之类。我当时
: 有一个题也没想出最优解,只是和面试官讨论了一堆次优解和可能的时空tradeoff。后
: 来听hr说所有feedback都很positive,所以不用苛求完美

p*****2
发帖数: 21240
256

你是骑驴找马呀?

【在 j*****y 的大作中提到】
: 好厉害。
: 他们还真的是把我当成了 new grad

f*****e
发帖数: 2992
257
似乎是金融转码农。

【在 p*****2 的大作中提到】
:
: 你是骑驴找马呀?

j*****y
发帖数: 1071
258
前不久 lay off了,专心找马 :)

【在 p*****2 的大作中提到】
:
: 你是骑驴找马呀?

j*****y
发帖数: 1071
259
码农转码农 :)

【在 f*****e 的大作中提到】
: 似乎是金融转码农。
a***o
发帖数: 1182
260
我觉得能拿到offer~ bless!

【在 j*****y 的大作中提到】
: 我当时要是能想出你这个反例就好了 :)
相关主题
这题谁知道答案?问道google面试题
Amazon的LRU设计题Construct Binary Tree from Inorder and Postorder Traversal
【哪里有C++比较好的LinkedList实现?】FB 面经
进入JobHunting版参与讨论
j*****y
发帖数: 1071
261
多谢 :)

【在 a***o 的大作中提到】
: 我觉得能拿到offer~ bless!
o***d
发帖数: 313
262
恩,仔细看了看大家的讨论,确实够难啊!!!op果然牛人

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
263
:)

【在 o***d 的大作中提到】
: 恩,仔细看了看大家的讨论,确实够难啊!!!op果然牛人
:
: 的。

p*****2
发帖数: 21240
264

那很牛呀。

【在 j*****y 的大作中提到】
: 码农转码农 :)
j*****y
发帖数: 1071
265
二爷给个牛字,让人有点飘起来的感觉阿 :)
多谢 :)

【在 p*****2 的大作中提到】
:
: 那很牛呀。

p*****2
发帖数: 21240
266

为什么有可能再遍历一次?

【在 m******s 的大作中提到】
: 真要虐出翔了。。。
: 1:
: 边同时遍历两个树边建一个新的,最后有可能要再遍历一次,比如:
: I1 =
: 01
: 10
: I2 =
: 10
: 01
: 则I1 intersect I2 =

p*****2
发帖数: 21240
267

这样呀。那还真是。我那个程序没有考虑到这个。

【在 m******s 的大作中提到】
: 4个pixel全白,根据quadtree定义,应该merge成一个大的
: 后序遍历一次完事。。。

p*****2
发帖数: 21240
268

加了一句,检查这个条件。你觉得够了吗?
def clone(root:QTreeNode):QTreeNode={
if(root==null) return null
val newNode=new QTreeNode(root.color)
for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
newNode
}

def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={
if(left.color==2 && right.color==2){
val newNode=new QTreeNode(2)
for(i<-0 until 4) newNode.children(i)=intersection(left.children
(i), right.children(i))
if(newNode.children.count(_.color==0)==4) new QTreeNode(0) else
newNode
}
else if(left.color==0 || right.color==0) return new QTreeNode(0)
else if(left.color==1) return clone(right)
else return clone(left)
}

【在 m******s 的大作中提到】
: 4个pixel全白,根据quadtree定义,应该merge成一个大的
: 后序遍历一次完事。。。

x***y
发帖数: 633
269
Just write to mark for personal reference purpose
>>>>>>>>>>
一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值
>>>>>>>>>>
(1) Find one single optimal path P which contains m+n point
(2) For each point (i,j), (k,h) in P, denoting P((i,j)->(k,h)) as the path
connecting 2 points in P, there is one property
* For all the possible paths between (i,j) and (k,h), the P((i,j)->(k,h)) is
optimal.
(3) For this problem, the solution may be 2 possible cases(the 2 paths
should not collide at any point)
<1> P + optimal path for either the upper part or lowe part split by the
optimal path (this one is easy)
<2> It's obvious that the final solutions P1 and P2 must each collide with P
on some parts(otherwise, case 1 will be always better than this). Given
property *, the final 2 paths should be like this: WLOG, P1 will collide
with P on the beginning part, and P2 will collide with P on the endin part,
and these 2 colliding parts don't necessarily cover the whole P.
So, the answer will be for each point (i,j) in P, in the upper part and
lower part split by P, find the optimal path from (m,0)->(i,j) and (i,j)->(0
,n); And then find out the pair (i1,j1), (i2,j2)in P that give the optimal
of
P((m,0)->(i1,j1))+Pupper((i1,j1)->(0,n))+Plower((m,0)->(i2,j2))+P(i2,j2)->(0
,n))
or
Pupper((m,0)->(i2,j2))+P((i2,j2)->(0,n))+P((m,0)->(i1,j1))+Plower((i1,j1)->(
0,n))
assuming (i1,j1) is before (i2,j2) in P.
Total time will be O(mn)+O(m2)+O(n2)
h****n
发帖数: 1093
270
确实挺难的,不过难不一定代表你就挂了,你难别的candidate也一样觉得难,主要看
你面试的想法和思路吧
bless

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

相关主题
FB 面经G家最新电面
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。怎样求common divisor 最快
请教个G题目却看妻子愁何在,漫卷诗书喜欲狂
进入JobHunting版参与讨论
c**s
发帖数: 159
271
两个人的我做过 要同时记录两个人的位置,同时走才行。

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

P*******b
发帖数: 1001
272
lz问你的经验,项目和research了吗?

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

c***s
发帖数: 192
273

structure
感觉recursive的方法是NP-hard的。
如果是这样的话,还不如brute-force的:
就是先找出一个人所有的路径,然后另外一个人用DP。

【在 j*****y 的大作中提到】
: 我也想过先用 recursive 的 方法 show一下 idea, 但是这个 recursive的 structure
: 还是不好弄阿

j*****y
发帖数: 1071
274
多谢 :)

【在 h****n 的大作中提到】
: 确实挺难的,不过难不一定代表你就挂了,你难别的candidate也一样觉得难,主要看
: 你面试的想法和思路吧
: bless
:
: 的。

j*****y
发帖数: 1071
275
好厉害阿 :)

【在 c**s 的大作中提到】
: 两个人的我做过 要同时记录两个人的位置,同时走才行。
:
: 的。

j*****y
发帖数: 1071
276
没怎么问, 也就是随便聊几句

【在 P*******b 的大作中提到】
: lz问你的经验,项目和research了吗?
:
: 的。

j*****y
发帖数: 1071
277
不错,你这个 idea 是 work 的

【在 c***s 的大作中提到】
:
: structure
: 感觉recursive的方法是NP-hard的。
: 如果是这样的话,还不如brute-force的:
: 就是先找出一个人所有的路径,然后另外一个人用DP。

P*******b
发帖数: 1001
278
好像也没有大问system design的问题,基本就全是算法设计。对吧

【在 j*****y 的大作中提到】
: 没怎么问, 也就是随便聊几句
j*****y
发帖数: 1071
279
差不多吧,第四个人差不多和 system design有点沾边

【在 P*******b 的大作中提到】
: 好像也没有大问system design的问题,基本就全是算法设计。对吧
B*******1
发帖数: 2454
280
你这个真的是general hire吗? 怎么看着这么象一个跟算法关系很紧密得职位阿。
反正比我的难多多了,我要是onite遇到这些肯定当场悲剧。
还有,面你的人是小年轻还是工作很多年的googler阿?

【在 j*****y 的大作中提到】
: 差不多吧,第四个人差不多和 system design有点沾边
相关主题
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb地图上分割成不同区域这个设计题的核心是什么来着?
这题到底是啥意思请问一道面试题
长年潜水,回馈FLG面经问个题,用递归方法
进入JobHunting版参与讨论
j*****y
发帖数: 1071
281
面我的人都比较年轻,年纪不算大

【在 B*******1 的大作中提到】
: 你这个真的是general hire吗? 怎么看着这么象一个跟算法关系很紧密得职位阿。
: 反正比我的难多多了,我要是onite遇到这些肯定当场悲剧。
: 还有,面你的人是小年轻还是工作很多年的googler阿?

o***d
发帖数: 313
282
她是做数学的,可以理解吧

【在 B*******1 的大作中提到】
: 你这个真的是general hire吗? 怎么看着这么象一个跟算法关系很紧密得职位阿。
: 反正比我的难多多了,我要是onite遇到这些肯定当场悲剧。
: 还有,面你的人是小年轻还是工作很多年的googler阿?

j*****y
发帖数: 1071
283
数学的做算法应该比科班出身的弱吧? :)

【在 o***d 的大作中提到】
: 她是做数学的,可以理解吧
o***d
发帖数: 313
284
不清楚别人怎么想,如果我有同事是数学出身,我本能反应就是他应该算法很强,就算不
强,应该一说就明白吧.

【在 j*****y 的大作中提到】
: 数学的做算法应该比科班出身的弱吧? :)
B*******1
发帖数: 2454
285
感觉这就是原因,似乎这些年轻人可能进google不久,而且之前算法练多了,所以都面
比较难的,
我当时面的几乎都是lead,senior,都比我年纪大,google里面最少都干了5-6年,所
以很多很多system design question。 记得面的第一个就是40多50的老头。

【在 j*****y 的大作中提到】
: 面我的人都比较年轻,年纪不算大
j*****y
发帖数: 1071
286
多谢 :)

【在 o***d 的大作中提到】
: 不清楚别人怎么想,如果我有同事是数学出身,我本能反应就是他应该算法很强,就算不
: 强,应该一说就明白吧.

j*****y
发帖数: 1071
287
羡慕嫉妒恨阿 :)

【在 B*******1 的大作中提到】
: 感觉这就是原因,似乎这些年轻人可能进google不久,而且之前算法练多了,所以都面
: 比较难的,
: 我当时面的几乎都是lead,senior,都比我年纪大,google里面最少都干了5-6年,所
: 以很多很多system design question。 记得面的第一个就是40多50的老头。

w********p
发帖数: 948
288
这题第一反应是DP. 所以要是用greedy, 面试官肯定不同意。
第二反应是两个同时走,想了下觉的有点难。牵扯到每一步谁先走后走。
在想想不对,其实谁走,谁先走后走没关系。就是走两条路,不重合的两条路,然后把
最多的钱拿走。
我觉的,用DP走两趟就好了。
第一次DP走过后,要把那个点mark掉(比如负数),
也就是说,每个人走的时候向上或者向右,同时有mark的地方不可以走。
第一次之前,没有被mark的点。
第一次DP之后,被选着的点都被mark上。
第二次DP的时候,遇到mak下次请绕道。
不知道这个思路是不是合理。

一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值
一看这个就傻了. 两个人的,太难了。 面试官让我先算一个人的算法,
这个
easy.
然后他就问两个人怎么搞,我当时首先想到的是,会不会是 greedy, 先算
第一个人的,然后把第一个人走过的路径上的每个点上的钱变成0,再算第
二个
人的。我当时试图证明这个 greedy是正确的,但也证明不出来。
面试官说你能举出一个反例证明你的 greedy 不 work也行,我当时就试了试
1 2 3
4 5 6
7 8 9

【在 j*****y 的大作中提到】
: 羡慕嫉妒恨阿 :)
w********p
发帖数: 948
289
两个人同时走比较讨厌,因为每一步,谁先谁后,都得考虑。。。
不过对结果是没有帮助。

【在 c**s 的大作中提到】
: 两个人的我做过 要同时记录两个人的位置,同时走才行。
:
: 的。

P*******b
发帖数: 1001
290
想不到lz是数学phd还是F,厉害啊,我觉得你的google肯定拿下来了,我开始排包子了。

【在 o***d 的大作中提到】
: 她是做数学的,可以理解吧
相关主题
一道linked list编程题Amazon的LRU设计题
ms面试题【哪里有C++比较好的LinkedList实现?】
这题谁知道答案?问道google面试题
进入JobHunting版参与讨论
w********p
发帖数: 948
291
数学系多出大牛啊。认识的数学系转CS的没有例外的都是牛人。就是我吭哧吭哧弄很久
的,牛人一下下,就搞定了。

【在 j*****y 的大作中提到】
: 数学的做算法应该比科班出身的弱吧? :)
f*****e
发帖数: 2992
292
这道题DP有点特别,一般是一行一行,这题是一斜列(45度),一斜列的求到达每一
个斜列中任意两个位置(可以相等)的极大值。只有前一个斜列的算好了,才可以算
下一个斜列的值。

【在 w********p 的大作中提到】
: 这题第一反应是DP. 所以要是用greedy, 面试官肯定不同意。
: 第二反应是两个同时走,想了下觉的有点难。牵扯到每一步谁先走后走。
: 在想想不对,其实谁走,谁先走后走没关系。就是走两条路,不重合的两条路,然后把
: 最多的钱拿走。
: 我觉的,用DP走两趟就好了。
: 第一次DP走过后,要把那个点mark掉(比如负数),
: 也就是说,每个人走的时候向上或者向右,同时有mark的地方不可以走。
: 第一次之前,没有被mark的点。
: 第一次DP之后,被选着的点都被mark上。
: 第二次DP的时候,遇到mak下次请绕道。

w********p
发帖数: 948
293
好像想到思路有点问题。
找到一个反例。 如果第一条恰好是内似对角线,按照我的思路,第二条就无解了(堵
死了)。
重新想。

【在 w********p 的大作中提到】
: 这题第一反应是DP. 所以要是用greedy, 面试官肯定不同意。
: 第二反应是两个同时走,想了下觉的有点难。牵扯到每一步谁先走后走。
: 在想想不对,其实谁走,谁先走后走没关系。就是走两条路,不重合的两条路,然后把
: 最多的钱拿走。
: 我觉的,用DP走两趟就好了。
: 第一次DP走过后,要把那个点mark掉(比如负数),
: 也就是说,每个人走的时候向上或者向右,同时有mark的地方不可以走。
: 第一次之前,没有被mark的点。
: 第一次DP之后,被选着的点都被mark上。
: 第二次DP的时候,遇到mak下次请绕道。

x***i
发帖数: 585
294
mark
o***d
发帖数: 313
295
大牛,问个弱问题,这题初始化怎么做?
似乎不容易啊?
难道用dp初始化dp[,,,,]边界?比如 dp[0,2,1,2]这种初始值怎么算出来?

【在 f*****e 的大作中提到】
: 这道题DP有点特别,一般是一行一行,这题是一斜列(45度),一斜列的求到达每一
: 个斜列中任意两个位置(可以相等)的极大值。只有前一个斜列的算好了,才可以算
: 下一个斜列的值。

f*****e
发帖数: 2992
296
初始化就是,第一斜列只有一个元素A[0][0],只有一个组合,就是它和它自身。
所以dp2[0][0][0][0] = A[0][0]
第二斜列有两个元素(0,1),(1,0),所以有3对组合dp2(0,1,0,1),dp2(0,1,1,0),
dp2(1,0,1,0),这3对组合都可以用dp2[0][0][0][0]算。
dp2(0,1,0,1) = dp2(0,0,0,0) + A[0,1];
dp2(0,1,1,0) = dp2(0,0,0,0) + A[0,1] + A[1,0];
dp2(1,0,1,0) = dp2(0,0,0,0) + A[1,0];
如果45度斜列有n个元素,上面的计算就要算C_n^2 + n = n(n+1)/2次。

【在 o***d 的大作中提到】
: 大牛,问个弱问题,这题初始化怎么做?
: 似乎不容易啊?
: 难道用dp初始化dp[,,,,]边界?比如 dp[0,2,1,2]这种初始值怎么算出来?

f*****e
发帖数: 2992
297
(0,2,2,1)不在45度对角线上,所以不用算。只算45度对角线上的。
一层一层推进,就可以到达右上端点(m,n)

【在 f*****e 的大作中提到】
: 初始化就是,第一斜列只有一个元素A[0][0],只有一个组合,就是它和它自身。
: 所以dp2[0][0][0][0] = A[0][0]
: 第二斜列有两个元素(0,1),(1,0),所以有3对组合dp2(0,1,0,1),dp2(0,1,1,0),
: dp2(1,0,1,0),这3对组合都可以用dp2[0][0][0][0]算。
: dp2(0,1,0,1) = dp2(0,0,0,0) + A[0,1];
: dp2(0,1,1,0) = dp2(0,0,0,0) + A[0,1] + A[1,0];
: dp2(1,0,1,0) = dp2(0,0,0,0) + A[1,0];
: 如果45度斜列有n个元素,上面的计算就要算C_n^2 + n = n(n+1)/2次。

o***d
发帖数: 313
298
好吧,我用你的那个对角线的方法试一下,我刚才在始二爷的那种n^4的方法

【在 f*****e 的大作中提到】
: (0,2,2,1)不在45度对角线上,所以不用算。只算45度对角线上的。
: 一层一层推进,就可以到达右上端点(m,n)

j*****y
发帖数: 1071
299
多谢 :)

了。

【在 P*******b 的大作中提到】
: 想不到lz是数学phd还是F,厉害啊,我觉得你的google肯定拿下来了,我开始排包子了。
j*****y
发帖数: 1071
300
多谢 :)

【在 w********p 的大作中提到】
: 数学系多出大牛啊。认识的数学系转CS的没有例外的都是牛人。就是我吭哧吭哧弄很久
: 的,牛人一下下,就搞定了。

相关主题
Construct Binary Tree from Inorder and Postorder Traversal请教个G题目
FB 面经G家最新电面
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。怎样求common divisor 最快
进入JobHunting版参与讨论
x********y
发帖数: 14
301
bless 楼主.
第二题应该用dp。
如果一个人在位置(i,j)时向上走,就说这个位置是这个人的“折点”。
然后这个问题每个state是(i,j,k),i是当前row,(i,j) 是第一个人的折点,
(i,
k) 是第二个人折点.
递推关系是 state(i,j,k) = max {state(i+1, j1, k1), where j1 <= j and k1
<= k}
sample code:
const int M = 4;
const int N = 4;
int a[M][N] = {
{1, 2, 3, 4},
{1, 0, 3, 0},
{1, 20, 3, 0},
{10, 10, 3, 0}};
int dp_two_max_gold() {
int state[M][N][N];
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
state[i][j][k] = 0;
// First the bottom line.
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
int max_val = max(j, k);
int sum = 0;
for (int m = 0; m <= max_val; ++m) {
sum += a[M - 1][m];
}
state[M - 1][j][k] = sum;
}
}
for (int i = M - 2; i >= 1; --i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
// From (j1, k1) to (j, k).
for (int j1 = 0; j1 <= j; ++j1) {
for (int k1 = 0; k1 <= k; ++k1) {
int max_gold = 0;
for (int m = min(j1, k1); m <= max(j1, k1); ++m) {
if ((m >= j1 && m <= j) || (m >= k1 && m <= k)) {
max_gold += a[i][m];
}
}
if (state[i][j][k] < state[i + 1][j1][k1] + max_gold) {
state[i][j][k] = state[i + 1][j1][k1] + max_gold;
}
}
}
}
}
}
int res = 0;
// NOw compute final result from states in row 1.
for (int j = 0;j < N; ++j) {
for (int k = 0; k < N; ++k) {
int min_val = min(j, k);
int sum = state[1][j][k]; // Row 1 states.
for (int m = min_val; m < N; ++m) {
sum += a[0][m];
}
if (sum > res) {
res = sum;
}
}
}
return res;
}
int main() {
cout << dp_two_max_gold() << endl;
return 0;
}
f*****e
发帖数: 2992
302
你自己的例子都通不过。

k1

【在 x********y 的大作中提到】
: bless 楼主.
: 第二题应该用dp。
: 如果一个人在位置(i,j)时向上走,就说这个位置是这个人的“折点”。
: 然后这个问题每个state是(i,j,k),i是当前row,(i,j) 是第一个人的折点,
: (i,
: k) 是第二个人折点.
: 递推关系是 state(i,j,k) = max {state(i+1, j1, k1), where j1 <= j and k1
: <= k}
: sample code:
: const int M = 4;

H****s
发帖数: 247
303
strong bless!
看了这些题,我怎么感觉都找不着北啊。做了leetcode再看这些题怎么感觉还是当场傻
眼啊。一种想轻生的感觉油然而生啊。
楼主已经很强了!

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
304
多谢 :)

【在 H****s 的大作中提到】
: strong bless!
: 看了这些题,我怎么感觉都找不着北啊。做了leetcode再看这些题怎么感觉还是当场傻
: 眼啊。一种想轻生的感觉油然而生啊。
: 楼主已经很强了!
:
: 的。

h**********y
发帖数: 1293
305
4维dp应该可以,
不过注意两人位置重合时候只加那个位置点数一次。

【在 p*****2 的大作中提到】
:
: 加了一句,检查这个条件。你觉得够了吗?
: def clone(root:QTreeNode):QTreeNode={
: if(root==null) return null
: val newNode=new QTreeNode(root.color)
: for(i<-0 until 4) newNode.children(i)=clone(root.children(i))
: newNode
: }
:
: def intersection(left:QTreeNode, right:QTreeNode):QTreeNode={

p*****2
发帖数: 21240
306

看我后边的帖子。

【在 h**********y 的大作中提到】
: 4维dp应该可以,
: 不过注意两人位置重合时候只加那个位置点数一次。

o***d
发帖数: 313
307
二爷对这个题的初始化有什么好的办法么?
白天我折腾半天也没找到好办法,fatalme大牛说按对角线作.
如果用你的n^4呢?
问题:看我下面的例子,怎么初始化dp[,,,,]才能满足最后的结果?
比如,简化问题为 从左上角向右下角跑,然后用aoyao 23楼的例子
matrix
4 4 0
5 5 5
0 4 4
那么结果应该是
dp:
4 8 8
9 18 23
9 22 31
我算dp的值第一行第二个值(8)和第三个值(8)总是不对
dp[1,1,1,2]
dp[1,1,1,3]
dp[1,1,1,2]
=max(dp[0,1,0,2],dp[0,1,1,1],dp[1,0,0,2],dp[1,0,1,1])+matrix[0,0]+matrix[0,1]
=max(...)+4+4
=max(...)+8
//so, here, max(...) should be 0. How?
=8???
dp[1,1,1,3]
=max(dp[0,1,0,3],dp[0,1,1,2],dp[1,0,0,3],dp[1,0,1,2])+matrix[0,0]+matrix[0,2]
=max(...)+4+0
=max(...)+4
//so, here, max(...) should be 4, How?
=8????

【在 p*****2 的大作中提到】
:
: 看我后边的帖子。

o***d
发帖数: 313
308
坦白说,fatalme大牛的初始化我没有try过,他举的例子自然没问题,那是第一
和第二个斜列,如果用在那个算法上,我再试一下
我再看看好了,不成就算了
我还找到了这个
http://www.cppblog.com/Climber-pI/archive/2010/10/02/128346.asp
这是noip2000的,解法跟你的一样,似乎他还测试通过了.....
不管怎么说,多谢了.
这次做题,我对dp又多了点理解,justtry同学真是给了个好题
睡觉去了,为了份工作真不容易啊大家

【在 p*****2 的大作中提到】
:
: 看我后边的帖子。

p*****2
发帖数: 21240
309

是我刚才的程序有个bug。你看看这个对不对。
object test6 extends App {
val mat=Array(Array(4,4,0), Array(5,5,5), Array(0, 4, 4))
val m=3
val n=3
val dp=Array.ofDim[Int](m,n,m,n)

for(i<-0 until m; j<-0 until n; x<-0 until m; y<-0 until n if i+j==x+y){
if(i>0 && x>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i-1)(j)(x-
1)(y))
if(i>0 && y>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i-1)(j)(x)
(y-1))
if(j>0 && x>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i)(j-1)(x-
1)(y))
if(j>0 && y>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i)(j-1)(x)
(y-1))

dp(i)(j)(x)(y)+= (if(i==x && j==y) mat(i)(j) else mat(i)(j)+mat(x)(y
))
}

println(dp(m-1)(n-1)(m-1)(n-1))
}

【在 o***d 的大作中提到】
: 坦白说,fatalme大牛的初始化我没有try过,他举的例子自然没问题,那是第一
: 和第二个斜列,如果用在那个算法上,我再试一下
: 我再看看好了,不成就算了
: 我还找到了这个
: http://www.cppblog.com/Climber-pI/archive/2010/10/02/128346.asp
: 这是noip2000的,解法跟你的一样,似乎他还测试通过了.....
: 不管怎么说,多谢了.
: 这次做题,我对dp又多了点理解,justtry同学真是给了个好题
: 睡觉去了,为了份工作真不容易啊大家

H****s
发帖数: 247
310
赞这个研究精神,没想到4维dp也可以这么简洁。本来一看到思维就发怵,看来以后即
使是N维也要硬着头皮上了。 二爷厉害,一下就指出得四维,我即使看得出也没胆做四
维的。
这题我做定了。

【在 o***d 的大作中提到】
: 坦白说,fatalme大牛的初始化我没有try过,他举的例子自然没问题,那是第一
: 和第二个斜列,如果用在那个算法上,我再试一下
: 我再看看好了,不成就算了
: 我还找到了这个
: http://www.cppblog.com/Climber-pI/archive/2010/10/02/128346.asp
: 这是noip2000的,解法跟你的一样,似乎他还测试通过了.....
: 不管怎么说,多谢了.
: 这次做题,我对dp又多了点理解,justtry同学真是给了个好题
: 睡觉去了,为了份工作真不容易啊大家

相关主题
怎样求common divisor 最快这题到底是啥意思
却看妻子愁何在,漫卷诗书喜欲狂长年潜水,回馈FLG面经
interview question: Given a list of points in 2D and a single reference point, find k nearest neighb地图上分割成不同区域这个设计题的核心是什么来着?
进入JobHunting版参与讨论
o***d
发帖数: 313
311
二爷威武!
work了,看了你的code我才明白问题到底出在哪儿........
我测了上面的那个case和另一个简单的case
1 2 3
4 0 6
7 8 9

){
x-
x)

【在 p*****2 的大作中提到】
:
: 是我刚才的程序有个bug。你看看这个对不对。
: object test6 extends App {
: val mat=Array(Array(4,4,0), Array(5,5,5), Array(0, 4, 4))
: val m=3
: val n=3
: val dp=Array.ofDim[Int](m,n,m,n)
:
: for(i<-0 until m; j<-0 until n; x<-0 until m; y<-0 until n if i+j==x+y){
: if(i>0 && x>0) dp(i)(j)(x)(y)=math.max(dp(i)(j)(x)(y), dp(i-1)(j)(x-

s*****n
发帖数: 5488
312
楼主什么背景,这题都很难啊。
1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
所有的的点来一遍就可以得到intersection
2. 双向搜是biidrectional dijistra吧。
4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
否则那么多怎么选。然后算概率还要调整。尼玛,不看书老夫早基本忘了叫什么了。没
有NLP背景这题太坑爹了。

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

j*****y
发帖数: 1071
313
多谢 :)
不是cs科班的 :)

【在 s*****n 的大作中提到】
: 楼主什么背景,这题都很难啊。
: 1. quadtree其实就是geohash.可以用zorder排序的。所以第一题应该是map reduce.
: 所有的的点来一遍就可以得到intersection
: 2. 双向搜是biidrectional dijistra吧。
: 4.最后那个其实是n-gram markov chain.里面水挺深的。简单prefix tree是不行的。
: 否则那么多怎么选。然后算概率还要调整。尼玛,不看书老夫早基本忘了叫什么了。没
: 有NLP背景这题太坑爹了。
:
: 的。

o***d
发帖数: 313
314
方法2似乎不是个常规方法阿,能问问,是你figure out的方法2,还是他上来就告诉你方
法2,然后问你怎么实现么?

【在 j*****y 的大作中提到】
: prefix tree没让 code,
: 快速找 min, 给了两个方法,第一个没有第二个好.
: given A[1,...,n]
: 方法1 : compute B[1,...,n]
: where B[i] = min {A[j], 1 <=j <= i}
: 这个方法效率不好。
: 方法 2: compute B[1,...,n]
: where B[i] = j such that for any k, i <= k <= j
: , we have A[k] >= A[i] and A[j + 1] < A[i]
: 方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法

j*****y
发帖数: 1071
315
我当时 figure out 出来的 :)

【在 o***d 的大作中提到】
: 方法2似乎不是个常规方法阿,能问问,是你figure out的方法2,还是他上来就告诉你方
: 法2,然后问你怎么实现么?

o***d
发帖数: 313
316
果然很厉害,呵呵,这个方法不常规,但也不错,复杂度似乎也不高,尤其是空间复杂度,很
tricky

【在 j*****y 的大作中提到】
: 我当时 figure out 出来的 :)
j*****y
发帖数: 1071
317
多谢 :)

【在 o***d 的大作中提到】
: 果然很厉害,呵呵,这个方法不常规,但也不错,复杂度似乎也不高,尤其是空间复杂度,很
: tricky

w********p
发帖数: 948
318
我偷懒,回头再写这题。
p*****2
发帖数: 21240
c********t
发帖数: 5706
320
来晚了,看到你的面经,我面瘫了!
big big bless!
问个大家没问的,如何实现hashtable, 请问你是用 list chaining还是open address
做的?

的。

【在 j*****y 的大作中提到】
: 求 bless :)
: 面了四个人.
: 第一个人: 关于 quadtree 的
: 比如一个二维的 image, 里面的 pixel是 白或者黑, 若果所有的pixel是黑
: 那么这个 image就是黑(B)的,如果所有的pixel 是白(W)的,那么这个 image就是白的。
: 否则的话,需要把这个 image等分成四份,如下图
: __________ __________
: | | 等分成四份就变成 | | |
: | | |____|___|
: | | | | |

相关主题
请问一道面试题ms面试题
问个题,用递归方法这题谁知道答案?
一道linked list编程题Amazon的LRU设计题
进入JobHunting版参与讨论
j*****y
发帖数: 1071
321
多谢 :)
我用的是 chaining

address

【在 c********t 的大作中提到】
: 来晚了,看到你的面经,我面瘫了!
: big big bless!
: 问个大家没问的,如何实现hashtable, 请问你是用 list chaining还是open address
: 做的?
:
: 的。

c***s
发帖数: 192
322
你这个算法的复杂度是多少啊?
最差情况下你还得扫描B[p...q]啊。

【在 j*****y 的大作中提到】
: prefix tree没让 code,
: 快速找 min, 给了两个方法,第一个没有第二个好.
: given A[1,...,n]
: 方法1 : compute B[1,...,n]
: where B[i] = min {A[j], 1 <=j <= i}
: 这个方法效率不好。
: 方法 2: compute B[1,...,n]
: where B[i] = j such that for any k, i <= k <= j
: , we have A[k] >= A[i] and A[j + 1] < A[i]
: 方法2效率上要高,也是面试官需要的,不过它让我写 code基于方法

j*****y
发帖数: 1071
323
最差情况下是线性的,比如 A 是 decreasing的

【在 c***s 的大作中提到】
: 你这个算法的复杂度是多少啊?
: 最差情况下你还得扫描B[p...q]啊。

c***s
发帖数: 192
324
可是这道题有log(n)的算法啊。
就是建一个二叉树来保存每一个区域的最小值。

【在 j*****y 的大作中提到】
: 最差情况下是线性的,比如 A 是 decreasing的
j*****y
发帖数: 1071
325
这个我还没想,板上有人给出了这个思路 :)

【在 c***s 的大作中提到】
: 可是这道题有log(n)的算法啊。
: 就是建一个二叉树来保存每一个区域的最小值。

c********t
发帖数: 5706
326
二爷, 你博客上的codes是不是只有 左下角和右上角都为0的时候才正确?
大家测测 int[][] matrix = { { 12, 2, 10, 1 }, { 4, 9, 8, 11 }, { 3, 6, 7, 5
} };
是什么结果?
应该是66,可我为什么得出64呢?

【在 p*****2 的大作中提到】
: 粗略的想了一下。感觉是个4维DP
: dp[i][j][x][y] 是A走到(i,j), B走到(x)(y)能够拿到的最大钱数
: dp[i][j][x][y]=max(dp[i+1][j][x+1][y], dp[i+1][j][x][y-1] 一共四种情况
: + if(i==x && j==y) x(i)(j) else x(i)(j)+x(x)(y)
: 最后返回dp(0)(n-1)(0)(n-1)

c********t
发帖数: 5706
327
大侠帮忙看看有什么bug? 多谢!
public static int twoMaxFromLBtoRT(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int n = matrix[0].length;
int m = matrix.length;
int[][][][] dp = new int[m][n][m][n];
dp[m - 1][0][m - 1][0] = matrix[m - 1][0];
for (int j = m - 2; j >= 0; j--) {
dp[j][0][j][0] = matrix[j][0] + dp[j + 1][0][j + 1][0];
}
for (int i = 1; i < n; i++) {
dp[m - 1][i][m - 1][i] = matrix[m - 1][i]
+ dp[m - 1][i - 1][m - 1][i - 1];
}
for (int j = m - 2; j >= 0; j--) {
for (int i = 1; i < n; i++) {
dp[j][0][m - 1][i] = dp[j][0][j][0] + dp[m - 1][i][m - 1][i]
- matrix[m - 1][0];
dp[m - 1][i][j][0] = dp[j][0][m - 1][i];
}
}
for (int j = m - 2; j >= 0; j--) {
for (int i = 1; i < n; i++) {
for (int q = m - 2; q >= 0; q--) {
for (int p = 1; p < n; p++) {
dp[j][i][q][p] = Math.max(Math.max(
dp[j + 1][i][q + 1][p],
dp[j + 1][i][q][p - 1]), Math.max(
dp[j][i - 1][q + 1][p],
dp[j][i - 1][q][p - 1]));
if (j == q && i == p) {
dp[j][i][q][p]+=matrix[j][i];
}else{
dp[j][i][q][p]+=matrix[j][i] + matrix[q][p];
}
}
}
}
}
return dp[0][n - 1][0][n - 1];
}

5

【在 c********t 的大作中提到】
: 二爷, 你博客上的codes是不是只有 左下角和右上角都为0的时候才正确?
: 大家测测 int[][] matrix = { { 12, 2, 10, 1 }, { 4, 9, 8, 11 }, { 3, 6, 7, 5
: } };
: 是什么结果?
: 应该是66,可我为什么得出64呢?

f*****e
发帖数: 2992
328
你这个复杂度多少?

【在 c********t 的大作中提到】
: 大侠帮忙看看有什么bug? 多谢!
: public static int twoMaxFromLBtoRT(int[][] matrix) {
: if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
: return 0;
: int n = matrix[0].length;
: int m = matrix.length;
: int[][][][] dp = new int[m][n][m][n];
: dp[m - 1][0][m - 1][0] = matrix[m - 1][0];
: for (int j = m - 2; j >= 0; j--) {
: dp[j][0][j][0] = matrix[j][0] + dp[j + 1][0][j + 1][0];

c********t
发帖数: 5706
329
嗯,惭愧, 想先写个 n^4,但是都过不了我自己的test case.

【在 f*****e 的大作中提到】
: 你这个复杂度多少?
a*****4
发帖数: 342
330
想起一个朋友几年前的去G家的经历。 准备了一个月,Onsite 2次,最后没要。过了一
年HR电话再安排一次onsite,朋友回答伤心了,不去了。第二天HR又来电话,说你可以
直接上班了。
相关主题
【哪里有C++比较好的LinkedList实现?】FB 面经
问道google面试题linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。
Construct Binary Tree from Inorder and Postorder Traversal请教个G题目
进入JobHunting版参与讨论
j*****y
发帖数: 1071
331
有意思 :)

【在 a*****4 的大作中提到】
: 想起一个朋友几年前的去G家的经历。 准备了一个月,Onsite 2次,最后没要。过了一
: 年HR电话再安排一次onsite,朋友回答伤心了,不去了。第二天HR又来电话,说你可以
: 直接上班了。

c********t
发帖数: 5706
332
仿照别人的,把初始化都去掉反而对了,奇怪。大牛有空就帮看一眼哪里有错吧。

【在 c********t 的大作中提到】
: 大侠帮忙看看有什么bug? 多谢!
: public static int twoMaxFromLBtoRT(int[][] matrix) {
: if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
: return 0;
: int n = matrix[0].length;
: int m = matrix.length;
: int[][][][] dp = new int[m][n][m][n];
: dp[m - 1][0][m - 1][0] = matrix[m - 1][0];
: for (int j = m - 2; j >= 0; j--) {
: dp[j][0][j][0] = matrix[j][0] + dp[j + 1][0][j + 1][0];

e***s
发帖数: 799
333
这种事也有?
BTW,谢谢楼主

【在 a*****4 的大作中提到】
: 想起一个朋友几年前的去G家的经历。 准备了一个月,Onsite 2次,最后没要。过了一
: 年HR电话再安排一次onsite,朋友回答伤心了,不去了。第二天HR又来电话,说你可以
: 直接上班了。

S**********r
发帖数: 284
334
问题
一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
(m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
的钱的和的最大值.
为了叙述方便,改成从左上(0,0) 走到 右下 (m-1, n-1)
分析
三维 DP ,有点烦琐,我也没有验证过,自己感觉是对。这个问题的重点就是,每走一
步都会破原来的状态。 通过分析,可以知道,最优解中,两个人走的线路,不可能有
任何的重合。 证明方法是,只要有重合,总能通过修改一条线路,去掉重合而达到更
优的解。 也就是说,要得到最优解的话,如果某个位置的金币被人拿走了,这个位
置,另一个人就不能再去走。 还可以观察到,在任何一层 i, 这两个人所处的位
置 j 和 k, j < k 总成立.
A 是 m x n 的matrix,假设所有数都非负数
C 是 m x m x n 的 3d matrix, C[i][j][k] 表示, 两个人处于A[i][j] 和 A[
i][k] 的位置时, 能拿到最多的金币数。
C[i][j][k] 状态,基于前面的分析(如果某个位置的金币被拿走,就不能再走),
只能由下面三种情况转换过来,
第一是从 C[i-1][j][k] 变换过来, 也就是说, 两个人同是往下走一层。
第二是 C[i][j-1][k], 这个意思是,第一个人从位置 j-1 走到 j, 但是 第二
个人保持不动. 这么移动可能的条件是, j-1>= 0,
第三是 C[i][j][k-1], 这个意思是,第一个不动, 第二个人从 k-1 走到 k。
这个移动可能的条件是 k-1 > j . 如果这个条件不成立的话, 第一个人要走到因为
确保每个合理的走动,都要拿到金币。
(其实还有一种情况, 两人同是往右边走动一格,但是这个可以分解成 第二 和第三
种情况,所以就不用考虑了。)
pseudo code:
C[i][j][k] = INT_MIN;
C[0][0][k] = sum(A[0][0] .... A[0][k]) // 第一行的初始化,有点特殊,
C[i][j][k] = max(C[i][j][k], C[i][j-1][k-1] + A[i][j] + A[i][k]);
if (j-1>=0) C[i][j][k] = max(C[i][j][k], C[i][j-1][k] + A[i][j]);
if (k-1>j) C[i][j][k] = max(C[i][j][k], C[i][j][k-1] + A[i][k]);
H****s
发帖数: 247
335
应该是 66, 这是我的代码
int maxMoney(vector> & mat)
{
int rowCnt = mat.size(), colCnt = mat[0].size();
vector> table(rowCnt + 1, vector(colCnt + 1, 0));
vector>>> cache(rowCnt + 1, vector vector>>(colCnt + 1, table));
for(int i = rowCnt - 1; i >= 0; --i){
for(int j = 1; j <= colCnt; ++j){
for(int k = rowCnt - 1; k >= 0; --k){
for(int l = 1; l <= colCnt; ++l){
cache[i][j][k][l] = max(cache[i + 1][j][k + 1][l], cache
[i+1][j][k][l - 1]);
cache[i][j][k][l] = max(cache[i][j][k][l], cache[i][j -
1][k + 1][l]);
cache[i][j][k][l] = max(cache[i][j][k][l], cache[i][j -
1][k][l - 1]);
cache[i][j][k][l] += (mat[i][j-1] + mat[k][l-1]);
if(i==k && j==l) cache[i][j][k][l] -= mat[i][j-1];
}
}
}
}
return cache[0][colCnt][0][colCnt];
}

5

【在 c********t 的大作中提到】
: 二爷, 你博客上的codes是不是只有 左下角和右上角都为0的时候才正确?
: 大家测测 int[][] matrix = { { 12, 2, 10, 1 }, { 4, 9, 8, 11 }, { 3, 6, 7, 5
: } };
: 是什么结果?
: 应该是66,可我为什么得出64呢?

a********n
发帖数: 1287
336
这难度,,,
明摆着要让人挂的。
e*******i
发帖数: 56
337
what is target hit/miss of binary search?
大牛科普一下
m****i
发帖数: 650
338
mark
t****a
发帖数: 1212
339
aglee, 感觉是4维dp,要考虑两人重叠的情况。

【在 S**********r 的大作中提到】
: 问题
: 一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
: (m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
: 现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
: 的钱的和的最大值.
: 为了叙述方便,改成从左上(0,0) 走到 右下 (m-1, n-1)
: 分析
: 三维 DP ,有点烦琐,我也没有验证过,自己感觉是对。这个问题的重点就是,每走一
: 步都会破原来的状态。 通过分析,可以知道,最优解中,两个人走的线路,不可能有
: 任何的重合。 证明方法是,只要有重合,总能通过修改一条线路,去掉重合而达到更

u*******g
发帖数: 1808
340
隔行如隔山!
第二个人的题目对我来说太easy,想了不到两分钟就有答案了,后面看到也有人想到了
dp。
其他的题目打死我也打不上来。
相关主题
请教个G题目却看妻子愁何在,漫卷诗书喜欲狂
G家最新电面interview question: Given a list of points in 2D and a single reference point, find k nearest neighb
怎样求common divisor 最快这题到底是啥意思
进入JobHunting版参与讨论
w***y
发帖数: 49
341
谢谢楼主分享!
f**********e
发帖数: 288
342
BLESS,
a********n
发帖数: 1287
343
这难度,,,
明摆着要让人挂的。
e*******i
发帖数: 56
344
what is target hit/miss of binary search?
大牛科普一下
m****i
发帖数: 650
345
mark
t****a
发帖数: 1212
346
aglee, 感觉是4维dp,要考虑两人重叠的情况。

【在 S**********r 的大作中提到】
: 问题
: 一个 m x n 二维区域,每个点上有一定数量的钱,考虑路径 : 从坐下角
: (m-1, 0)出发,终点是 右上角(0, n-1), 在每个点只能向右或者向上走,
: 现在有两个人,从起点出发,走到终点,问怎么样求出这两个人能拿到
: 的钱的和的最大值.
: 为了叙述方便,改成从左上(0,0) 走到 右下 (m-1, n-1)
: 分析
: 三维 DP ,有点烦琐,我也没有验证过,自己感觉是对。这个问题的重点就是,每走一
: 步都会破原来的状态。 通过分析,可以知道,最优解中,两个人走的线路,不可能有
: 任何的重合。 证明方法是,只要有重合,总能通过修改一条线路,去掉重合而达到更

u*******g
发帖数: 1808
347
隔行如隔山!
第二个人的题目对我来说太easy,想了不到两分钟就有答案了,后面看到也有人想到了
dp。
其他的题目打死我也打不上来。
w***y
发帖数: 49
348
谢谢楼主分享!
f**********e
发帖数: 288
349
BLESS,
y*****3
发帖数: 451
350
求问最后一个题怎么做啊?


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

【在 j*****y 的大作中提到】
: 有意思 :)
相关主题
长年潜水,回馈FLG面经问个题,用递归方法
地图上分割成不同区域这个设计题的核心是什么来着?一道linked list编程题
请问一道面试题ms面试题
进入JobHunting版参与讨论
c********e
发帖数: 186
351
bless
k*****m
发帖数: 14
352
最后一题是不是可以用segment Tree,假设二分,每个节点保存index range和在这个
区间的最小值。然后子节点就是二分父节点的range,分别保存在这个range内的最小值
,一次类推。
这样就是log(N)的复杂度得到最小值。
不知道有没有更好的解法。
求第二题的解法呀。
g********e
发帖数: 1142
353

我感觉是之前的index大小,似乎可以达到constant time的同时index space 小于N^2.

【在 k*****m 的大作中提到】
: 最后一题是不是可以用segment Tree,假设二分,每个节点保存index range和在这个
: 区间的最小值。然后子节点就是二分父节点的range,分别保存在这个range内的最小值
: ,一次类推。
: 这样就是log(N)的复杂度得到最小值。
: 不知道有没有更好的解法。
: 求第二题的解法呀。

k*****m
发帖数: 14
354
能具体说说么 ?

2.

【在 g********e 的大作中提到】
:
: 我感觉是之前的index大小,似乎可以达到constant time的同时index space 小于N^2.

g********e
发帖数: 1142
355

也许是logN的query
building个index,如下:
选择一个chunk size,比如是256. 然后把原来数组scan 一边,每256个选个最小值保
存。然后每256*2个如是再来一边;然后256*2*2, 256*2^3....
and so on, 都记录各个shard上的最小值,exponential。共有nlogn个纪录。
query的时候,根据A和B的值,得到对应的chunk,再得到需要read哪些shard (logN个
)。在这些shard的最小中选择最小,返回。

【在 k*****m 的大作中提到】
: 能具体说说么 ?
:
: 2.

y*****3
发帖数: 451
356
求问最后一个题怎么做啊?


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

【在 j*****y 的大作中提到】
: 有意思 :)
c********e
发帖数: 186
357
bless
k*****m
发帖数: 14
358
最后一题是不是可以用segment Tree,假设二分,每个节点保存index range和在这个
区间的最小值。然后子节点就是二分父节点的range,分别保存在这个range内的最小值
,一次类推。
这样就是log(N)的复杂度得到最小值。
不知道有没有更好的解法。
求第二题的解法呀。
g********e
发帖数: 1142
359

我感觉是之前的index大小,似乎可以达到constant time的同时index space 小于N^2.

【在 k*****m 的大作中提到】
: 最后一题是不是可以用segment Tree,假设二分,每个节点保存index range和在这个
: 区间的最小值。然后子节点就是二分父节点的range,分别保存在这个range内的最小值
: ,一次类推。
: 这样就是log(N)的复杂度得到最小值。
: 不知道有没有更好的解法。
: 求第二题的解法呀。

k*****m
发帖数: 14
360
能具体说说么 ?

2.

【在 g********e 的大作中提到】
:
: 我感觉是之前的index大小,似乎可以达到constant time的同时index space 小于N^2.

相关主题
这题谁知道答案?问道google面试题
Amazon的LRU设计题Construct Binary Tree from Inorder and Postorder Traversal
【哪里有C++比较好的LinkedList实现?】FB 面经
进入JobHunting版参与讨论
g********e
发帖数: 1142
361

也许是logN的query
building个index,如下:
选择一个chunk size,比如是256. 然后把原来数组scan 一边,每256个选个最小值保
存。然后每256*2个如是再来一边;然后256*2*2, 256*2^3....
and so on, 都记录各个shard上的最小值,exponential。共有nlogn个纪录。
query的时候,根据A和B的值,得到对应的chunk,再得到需要read哪些shard (logN个
)。在这些shard的最小中选择最小,返回。

【在 k*****m 的大作中提到】
: 能具体说说么 ?
:
: 2.

r*******g
发帖数: 1335
362
挖坟,最后一题什么意思?怎么破?
l***n
发帖数: 29
363
前面回复了Segment Tree啦。
http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-q

【在 r*******g 的大作中提到】
: 挖坟,最后一题什么意思?怎么破?
x*******9
发帖数: 138
364
矩阵走两次那题是最大费用流。。。
我会建模,但是不会写。。。
a*****a
发帖数: 46
365
怎么设计?

【在 x*******9 的大作中提到】
: 矩阵走两次那题是最大费用流。。。
: 我会建模,但是不会写。。。

1 (共1页)
进入JobHunting版参与讨论
相关主题
这题谁知道答案?G家最新电面
Amazon的LRU设计题怎样求common divisor 最快
【哪里有C++比较好的LinkedList实现?】却看妻子愁何在,漫卷诗书喜欲狂
问道google面试题interview question: Given a list of points in 2D and a single reference point, find k nearest neighb
Construct Binary Tree from Inorder and Postorder Traversal这题到底是啥意思
FB 面经长年潜水,回馈FLG面经
linkedin 电面面经!另求内推!!两道题都答出来了,还是跪了。 请大牛分析原因。地图上分割成不同区域这个设计题的核心是什么来着?
请教个G题目请问一道面试题
相关话题的讨论汇总
话题: dp话题: int话题: qtreenode话题: matrix话题: max