由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - 刚面的，发一个google新题
相关主题
● careercup书上那个maintain median value的题● Amazon面筋
● 请教关于build heap BIG-O的问题● Facebook Interview Questions
● 发个evernote的code challenge● 请教MinHeap用STL实现
● twittier的onsite挂了，来问个常见题● leetcode 上的k way merge
● 问道indeed面试算法题● 弱弱的问个C++用priority_queue定义min heap的问题
● 上午偷闲把TopKFrequentWords写出来了● 面试用C++, heap 怎么办？
● 问三道题● L家coding question一问
● k sorted array merge大家现场写一个heap？● how to code this question of LinkedIn
相关话题的讨论汇总
话题: point话题: int话题: height话题: nx话题: visited
进入JobHunting版参与讨论
1 (共1页)
h**********y
发帖数: 1293
1
攒人品，求祝福！
别的题都蛮常见的。就这个没见过。
二维版本water trap问题。。
当场解决了。呵呵。。
f*******t
发帖数: 7549
2
电面就问这么难的？
a***o
发帖数: 1182
3
求解法，这个想过，不会做啊

【在 h**********y 的大作中提到】
: 攒人品，求祝福！
: 别的题都蛮常见的。就这个没见过。
: 二维版本water trap问题。。
: 当场解决了。呵呵。。
r*********n
发帖数: 4553
4
这个题？
Rain Water Trap (2D Version)
http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
j*****s
发帖数: 189
5
怎么做？
c********t
发帖数: 5706
6
很强大! 你是brute force解法吗？复杂度多少？

【在 h**********y 的大作中提到】
: 攒人品，求祝福！
: 别的题都蛮常见的。就这个没见过。
: 二维版本water trap问题。。
: 当场解决了。呵呵。。
p*****2
发帖数: 21240
7

大牛写个code出来看看？

【在 c********t 的大作中提到】
: 很强大! 你是brute force解法吗？复杂度多少？
l*******b
发帖数: 2586
8
brutal force也不会做呀...

【在 c********t 的大作中提到】
: 很强大! 你是brute force解法吗？复杂度多少？
l*******b
发帖数: 2586
9
想了个这个办法, 不知道好实现不?
建立一个高度的priority queue
把边界一圈push进去
当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
返回总积水量
h**********y
发帖数: 1293
10
从最外圈往里push。找当前圈内部的邻居。keep track 当前圈最矮的那个，邻居比这
个矮就算diff，accumulate到总水量，比这个高就代替原来圈上那个元素。。O(n)
其实和一维很类似。。

【在 c********t 的大作中提到】
: 很强大! 你是brute force解法吗？复杂度多少？
相关主题
● 上午偷闲把TopKFrequentWords写出来了● Amazon面筋
● 问三道题● Facebook Interview Questions
● k sorted array merge大家现场写一个heap？● 请教MinHeap用STL实现
进入JobHunting版参与讨论
p*****2
发帖数: 21240
11

onsite吧？代码好写吗？

【在 h**********y 的大作中提到】
: 从最外圈往里push。找当前圈内部的邻居。keep track 当前圈最矮的那个，邻居比这
: 个矮就算diff，accumulate到总水量，比这个高就代替原来圈上那个元素。。O(n)
: 其实和一维很类似。。
c******3
发帖数: 60
12
这个复杂度太高。用LZ的迭代法是不错的选择

【在 l*******b 的大作中提到】
: 想了个这个办法, 不知道好实现不?
: 建立一个高度的priority queue
: 把边界一圈push进去
: 当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
: 比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
: 返回总积水量
p*****2
发帖数: 21240
13
LZ答的不错，看到offer是必拿了。
l*******b
发帖数: 2586
14
迭代感觉有点问题呀,
5 5 5 5
5 3 5 2
5 5 5 5
5 5 5 5

【在 c******3 的大作中提到】
: 这个复杂度太高。用LZ的迭代法是不错的选择
f******n
发帖数: 279
15
mark以后做
p*****2
发帖数: 21240
16

这个有什么问题呀？

【在 l*******b 的大作中提到】
: 迭代感觉有点问题呀,
: 5 5 5 5
: 5 3 5 2
: 5 5 5 5
: 5 5 5 5
M******7
发帖数: 30
17
m
l*******b
发帖数: 2586
18
先看外面一圈最小的是2, 再看里面一圈, 发现3 的时候就不会增加water了. 所以一圈
一圈iterate肯定不灵吧

【在 p*****2 的大作中提到】
:
: 这个有什么问题呀？
h**********y
发帖数: 1293
19
圈形状是动态变化的。不是正方形。。。。

【在 l*******b 的大作中提到】
: 先看外面一圈最小的是2, 再看里面一圈, 发现3 的时候就不会增加water了. 所以一圈
: 一圈iterate肯定不灵吧
h**********y
发帖数: 1293
20
本地有他们office
直接去office面第一轮的。。

【在 p*****2 的大作中提到】
:
: 这个有什么问题呀？
相关主题
● leetcode 上的k way merge● L家coding question一问
● 弱弱的问个C++用priority_queue定义min heap的问题● how to code this question of LinkedIn
● 面试用C++, heap 怎么办？● 到底什么是priority queue啊？
进入JobHunting版参与讨论
l*******b
发帖数: 2586
21
嗯,边界应该是变化的都不一定是连续的, 所以两个办法复杂度是一样的吧

【在 h**********y 的大作中提到】
: 圈形状是动态变化的。不是正方形。。。。
c********t
发帖数: 5706
22
brute force解法很幼稚，lz很强大。
http://codingways.blogspot.com/2012/06/rain-water-trap-problem-
google一面现在太狠了，onsite还不只要多难啊！我算早死早托生了。

【在 p*****2 的大作中提到】
:
: 这个有什么问题呀？
j*****y
发帖数: 1071
23
感觉光 leetcode 还不够阿， poj, zoj 得上了

【在 c********t 的大作中提到】
: brute force解法很幼稚，lz很强大。
: http://codingways.blogspot.com/2012/06/rain-water-trap-problem-
: google一面现在太狠了，onsite还不只要多难啊！我算早死早托生了。
p*****2
发帖数: 21240
24

有这个趋势。大牛准备搞吗？可以一起搞。

【在 j*****y 的大作中提到】
: 感觉光 leetcode 还不够阿， poj, zoj 得上了
j*****y
发帖数: 1071
25
我是要搞了，二爷也要搞吗？

【在 p*****2 的大作中提到】
:
: 有这个趋势。大牛准备搞吗？可以一起搞。
c********t
发帖数: 5706
26
如果中间到一个元素i,j, 这时候它有三个没访问的邻居，这时候应该用哪一个来替代
圈上那个元素？
这个圈元素数目是不是固定的4*（n-1)?

【在 h**********y 的大作中提到】
: 从最外圈往里push。找当前圈内部的邻居。keep track 当前圈最矮的那个，邻居比这
: 个矮就算diff，accumulate到总水量，比这个高就代替原来圈上那个元素。。O(n)
: 其实和一维很类似。。
l*******b
发帖数: 2586
27
应该是3个都push进去, 如果高度比现在这个低, 那么它的高度用现在这个的高度代替
5 5 5 3 5 5 5
5 1 1 2 4 1 5
5 1 1 1 5 1 5
5 5 5 5 5 5 5
开始是
5 5 5 3 5 5 5
5 5
5 5
5 5 5 5 5 5 5
下一步, 同时积水3-1 + 3-2
5 5 5 * 5 5 5
5 3 3 4 5
5 5
5 5 5 5 5 5 5
接下来, 又得到积水4*(3-1)
5 5 5 * 5 5 5
5 3 * 3 4 5
5 3 3 3 5
5 5 5 5 5 5 5
再下来
5 5 5 * 5 5 5
5 * * * 4 5
5 * * * 5 5
5 5 5 5 5 5 5
再下来
5 5 5 * 5 5 5
5 * * * * 4 5
5 * * * 5 4 5
5 5 5 5 5 5 5
最后都是 * 都被取过了

【在 c********t 的大作中提到】
: 如果中间到一个元素i,j, 这时候它有三个没访问的邻居，这时候应该用哪一个来替代
: 圈上那个元素？
: 这个圈元素数目是不是固定的4*（n-1)?
c********t
发帖数: 5706
28
嗯，同意，只有一个问题，我觉得对每一个点，应该只算上下左右4个，比如你的例子
，第一次3只应该对2起作用。然后像lz说的，比3小的算差值，比3大的push进去。

【在 l*******b 的大作中提到】
: 应该是3个都push进去, 如果高度比现在这个低, 那么它的高度用现在这个的高度代替
: 5 5 5 3 5 5 5
: 5 1 1 2 4 1 5
: 5 1 1 1 5 1 5
: 5 5 5 5 5 5 5
: 开始是
: 5 5 5 3 5 5 5
: 5 5
: 5 5
: 5 5 5 5 5 5 5
l*******b
发帖数: 2586
29
en, should have 4 neighbours instead of 8.
another thought: using a dfs for height less or equal to current height
might make the code a bit faster.

【在 c********t 的大作中提到】
: 嗯，同意，只有一个问题，我觉得对每一个点，应该只算上下左右4个，比如你的例子
: ，第一次3只应该对2起作用。然后像lz说的，比3小的算差值，比3大的push进去。
c********t
发帖数: 5706
30
dfs recursion写不下去了，比如从3开始，不知道何时应该终止.
睡了。明天改写iteration.coding和bfs一样繁琐了。
lz真是牛中牛啊！

【在 l*******b 的大作中提到】
: en, should have 4 neighbours instead of 8.
: another thought: using a dfs for height less or equal to current height
: might make the code a bit faster.
相关主题
● 又想起一道google题目● 请教关于build heap BIG-O的问题
● 怎么计算一个网站过去5min的访问量？● 发个evernote的code challenge
● careercup书上那个maintain median value的题● twittier的onsite挂了，来问个常见题
进入JobHunting版参与讨论
l*******b
发帖数: 2586
31
en, lz DaNiu
dfs recursion should return when the value of current pos is larger than
searching value. It will push current pos into the priority queue, then
return.

【在 c********t 的大作中提到】
: dfs recursion写不下去了，比如从3开始，不知道何时应该终止.
: 睡了。明天改写iteration.coding和bfs一样繁琐了。
: lz真是牛中牛啊！
c********t
发帖数: 5706
32
循环是因为2-＞1-＞2-＞1 visited 矩阵用的有问,明天改。 minheap may not be a
good choice, since u may want remove element very often.

★ 发自iPhone App: ChineseWeb 7.8

【在 l*******b 的大作中提到】
: en, lz DaNiu
: dfs recursion should return when the value of current pos is larger than
: searching value. It will push current pos into the priority queue, then
: return.
p*****2
发帖数: 21240
33

你先搞一下发发心得好吗？我以前稍微搞过一下。感觉还是有点难呀。

【在 j*****y 的大作中提到】
: 我是要搞了，二爷也要搞吗？
h***i
发帖数: 1970
34
楼主大牛呀。

【在 h**********y 的大作中提到】
: 攒人品，求祝福！
: 别的题都蛮常见的。就这个没见过。
: 二维版本water trap问题。。
: 当场解决了。呵呵。。
i******r
发帖数: 793
35
出这种题目，干脆直接从ACM校队里面招人算了
这不是什么好的趋势
j*****y
发帖数: 1071
36
我也觉得 google现在出题目有点问题，直接搞竞赛题了

【在 i******r 的大作中提到】
: 出这种题目，干脆直接从ACM校队里面招人算了
: 这不是什么好的趋势
i******r
发帖数: 793
37
不是说竞赛题不能出
但是这种题目，没做过的有几个能知道算法，何况写程序
再说算法也只是一个基本功，还有很多其他方面的能力呢
这种面试的趋势有点偏了

【在 j*****y 的大作中提到】
: 我也觉得 google现在出题目有点问题，直接搞竞赛题了
j*****y
发帖数: 1071
38
没办法阿，是公司挑人，不是人挑公司。

【在 i******r 的大作中提到】
: 不是说竞赛题不能出
: 但是这种题目，没做过的有几个能知道算法，何况写程序
: 再说算法也只是一个基本功，还有很多其他方面的能力呢
: 这种面试的趋势有点偏了
c********t
发帖数: 5706
39
终于搞定，不是visited问题。而是循环里忘了把min variable重新赋值，导致一直用
以前的最小点，所以死循环。昨天熬夜实在是晕菜了。

【在 c********t 的大作中提到】
: 循环是因为2-＞1-＞2-＞1 visited 矩阵用的有问,明天改。 minheap may not be a
: good choice, since u may want remove element very often.
:
: ★ 发自iPhone App: ChineseWeb 7.8
l*******b
发帖数: 2586
40
嗯最后用的什么做priority queue

【在 c********t 的大作中提到】
: 终于搞定，不是visited问题。而是循环里忘了把min variable重新赋值，导致一直用
: 以前的最小点，所以死循环。昨天熬夜实在是晕菜了。
相关主题
● twittier的onsite挂了，来问个常见题● 问三道题
● 问道indeed面试算法题● k sorted array merge大家现场写一个heap？
● 上午偷闲把TopKFrequentWords写出来了● Amazon面筋
进入JobHunting版参与讨论
c********t
发帖数: 5706
41
用的hashmap,每次要找一遍min, 比如你那个例子，要找一次3，再找一次4。好像没有
啥办法。

【在 l*******b 的大作中提到】
: 嗯最后用的什么做priority queue
a***o
发帖数: 1182
42
大拿贴个code学习一下,多谢

【在 c********t 的大作中提到】
: 终于搞定，不是visited问题。而是循环里忘了把min variable重新赋值，导致一直用
: 以前的最小点，所以死循环。昨天熬夜实在是晕菜了。
p*****2
发帖数: 21240
43

才看到你这个。我也是这个思路。感觉复杂度不高呀。准备今天练练。

【在 l*******b 的大作中提到】
: 想了个这个办法, 不知道好实现不?
: 建立一个高度的priority queue
: 把边界一圈push进去
: 当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
: 比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
: 返回总积水量
h**********y
发帖数: 1293
44
攒人品，求祝福！
别的题都蛮常见的。就这个没见过。
二维版本water trap问题。。
当场解决了。呵呵。。
f*******t
发帖数: 7549
45
电面就问这么难的？
a***o
发帖数: 1182
46
求解法，这个想过，不会做啊

【在 h**********y 的大作中提到】
: 攒人品，求祝福！
: 别的题都蛮常见的。就这个没见过。
: 二维版本water trap问题。。
: 当场解决了。呵呵。。
r*********n
发帖数: 4553
47
这个题？
Rain Water Trap (2D Version)
http://leetcode.com/groups/twitter-interview/forum/topic/rain-w
j*****s
发帖数: 189
48
怎么做？
c********t
发帖数: 5706
49
很强大! 你是brute force解法吗？复杂度多少？

【在 h**********y 的大作中提到】
: 攒人品，求祝福！
: 别的题都蛮常见的。就这个没见过。
: 二维版本water trap问题。。
: 当场解决了。呵呵。。
p*****2
发帖数: 21240
50

大牛写个code出来看看？

【在 c********t 的大作中提到】
: 很强大! 你是brute force解法吗？复杂度多少？
相关主题
● Facebook Interview Questions● 弱弱的问个C++用priority_queue定义min heap的问题
● 请教MinHeap用STL实现● 面试用C++, heap 怎么办？
● leetcode 上的k way merge● L家coding question一问
进入JobHunting版参与讨论
l*******b
发帖数: 2586
51
brutal force也不会做呀...

【在 c********t 的大作中提到】
: 很强大! 你是brute force解法吗？复杂度多少？
l*******b
发帖数: 2586
52
想了个这个办法, 不知道好实现不?
建立一个高度的priority queue
把边界一圈push进去
当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
返回总积水量
h**********y
发帖数: 1293
53
从最外圈往里push。找当前圈内部的邻居。keep track 当前圈最矮的那个，邻居比这
个矮就算diff，accumulate到总水量，比这个高就代替原来圈上那个元素。。O(n)
其实和一维很类似。。

【在 c********t 的大作中提到】
: 很强大! 你是brute force解法吗？复杂度多少？
p*****2
发帖数: 21240
54

onsite吧？代码好写吗？

【在 h**********y 的大作中提到】
: 从最外圈往里push。找当前圈内部的邻居。keep track 当前圈最矮的那个，邻居比这
: 个矮就算diff，accumulate到总水量，比这个高就代替原来圈上那个元素。。O(n)
: 其实和一维很类似。。
c******3
发帖数: 60
55
这个复杂度太高。用LZ的迭代法是不错的选择

【在 l*******b 的大作中提到】
: 想了个这个办法, 不知道好实现不?
: 建立一个高度的priority queue
: 把边界一圈push进去
: 当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
: 比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
: 返回总积水量
p*****2
发帖数: 21240
56
LZ答的不错，看到offer是必拿了。
l*******b
发帖数: 2586
57
迭代感觉有点问题呀,
5 5 5 5
5 3 5 2
5 5 5 5
5 5 5 5

【在 c******3 的大作中提到】
: 这个复杂度太高。用LZ的迭代法是不错的选择
f******n
发帖数: 279
58
mark以后做
p*****2
发帖数: 21240
59

这个有什么问题呀？

【在 l*******b 的大作中提到】
: 迭代感觉有点问题呀,
: 5 5 5 5
: 5 3 5 2
: 5 5 5 5
: 5 5 5 5
M******7
发帖数: 30
60
m
相关主题
● how to code this question of LinkedIn● 怎么计算一个网站过去5min的访问量？
● 到底什么是priority queue啊？● careercup书上那个maintain median value的题
● 又想起一道google题目● 请教关于build heap BIG-O的问题
进入JobHunting版参与讨论
l*******b
发帖数: 2586
61
先看外面一圈最小的是2, 再看里面一圈, 发现3 的时候就不会增加water了. 所以一圈
一圈iterate肯定不灵吧

【在 p*****2 的大作中提到】
:
: 这个有什么问题呀？
h**********y
发帖数: 1293
62
圈形状是动态变化的。不是正方形。。。。

【在 l*******b 的大作中提到】
: 先看外面一圈最小的是2, 再看里面一圈, 发现3 的时候就不会增加water了. 所以一圈
: 一圈iterate肯定不灵吧
h**********y
发帖数: 1293
63
本地有他们office
直接去office面第一轮的。。

【在 p*****2 的大作中提到】
:
: 这个有什么问题呀？
l*******b
发帖数: 2586
64
嗯,边界应该是变化的都不一定是连续的, 所以两个办法复杂度是一样的吧

【在 h**********y 的大作中提到】
: 圈形状是动态变化的。不是正方形。。。。
c********t
发帖数: 5706
65
brute force解法很幼稚，lz很强大。
http://codingways.blogspot.com/2012/06/rain-water-trap-problem-
google一面现在太狠了，onsite还不只要多难啊！我算早死早托生了。

【在 p*****2 的大作中提到】
:
: 这个有什么问题呀？
j*****y
发帖数: 1071
66
感觉光 leetcode 还不够阿， poj, zoj 得上了

【在 c********t 的大作中提到】
: brute force解法很幼稚，lz很强大。
: http://codingways.blogspot.com/2012/06/rain-water-trap-problem-
: google一面现在太狠了，onsite还不只要多难啊！我算早死早托生了。
p*****2
发帖数: 21240
67

有这个趋势。大牛准备搞吗？可以一起搞。

【在 j*****y 的大作中提到】
: 感觉光 leetcode 还不够阿， poj, zoj 得上了
j*****y
发帖数: 1071
68
我是要搞了，二爷也要搞吗？

【在 p*****2 的大作中提到】
:
: 有这个趋势。大牛准备搞吗？可以一起搞。
c********t
发帖数: 5706
69
如果中间到一个元素i,j, 这时候它有三个没访问的邻居，这时候应该用哪一个来替代
圈上那个元素？
这个圈元素数目是不是固定的4*（n-1)?

【在 h**********y 的大作中提到】
: 从最外圈往里push。找当前圈内部的邻居。keep track 当前圈最矮的那个，邻居比这
: 个矮就算diff，accumulate到总水量，比这个高就代替原来圈上那个元素。。O(n)
: 其实和一维很类似。。
l*******b
发帖数: 2586
70
应该是3个都push进去, 如果高度比现在这个低, 那么它的高度用现在这个的高度代替
5 5 5 3 5 5 5
5 1 1 2 4 1 5
5 1 1 1 5 1 5
5 5 5 5 5 5 5
开始是
5 5 5 3 5 5 5
5 5
5 5
5 5 5 5 5 5 5
下一步, 同时积水3-1 + 3-2
5 5 5 * 5 5 5
5 3 3 4 5
5 5
5 5 5 5 5 5 5
接下来, 又得到积水4*(3-1)
5 5 5 * 5 5 5
5 3 * 3 4 5
5 3 3 3 5
5 5 5 5 5 5 5
再下来
5 5 5 * 5 5 5
5 * * * 4 5
5 * * * 5 5
5 5 5 5 5 5 5
再下来
5 5 5 * 5 5 5
5 * * * * 4 5
5 * * * 5 4 5
5 5 5 5 5 5 5
最后都是 * 都被取过了

【在 c********t 的大作中提到】
: 如果中间到一个元素i,j, 这时候它有三个没访问的邻居，这时候应该用哪一个来替代
: 圈上那个元素？
: 这个圈元素数目是不是固定的4*（n-1)?
相关主题
● 请教关于build heap BIG-O的问题● 问道indeed面试算法题
● 发个evernote的code challenge● 上午偷闲把TopKFrequentWords写出来了
● twittier的onsite挂了，来问个常见题● 问三道题
进入JobHunting版参与讨论
c********t
发帖数: 5706
71
嗯，同意，只有一个问题，我觉得对每一个点，应该只算上下左右4个，比如你的例子
，第一次3只应该对2起作用。然后像lz说的，比3小的算差值，比3大的push进去。

【在 l*******b 的大作中提到】
: 应该是3个都push进去, 如果高度比现在这个低, 那么它的高度用现在这个的高度代替
: 5 5 5 3 5 5 5
: 5 1 1 2 4 1 5
: 5 1 1 1 5 1 5
: 5 5 5 5 5 5 5
: 开始是
: 5 5 5 3 5 5 5
: 5 5
: 5 5
: 5 5 5 5 5 5 5
l*******b
发帖数: 2586
72
en, should have 4 neighbours instead of 8.
another thought: using a dfs for height less or equal to current height
might make the code a bit faster.

【在 c********t 的大作中提到】
: 嗯，同意，只有一个问题，我觉得对每一个点，应该只算上下左右4个，比如你的例子
: ，第一次3只应该对2起作用。然后像lz说的，比3小的算差值，比3大的push进去。
c********t
发帖数: 5706
73
dfs recursion写不下去了，比如从3开始，不知道何时应该终止.
睡了。明天改写iteration.coding和bfs一样繁琐了。
lz真是牛中牛啊！

【在 l*******b 的大作中提到】
: en, should have 4 neighbours instead of 8.
: another thought: using a dfs for height less or equal to current height
: might make the code a bit faster.
l*******b
发帖数: 2586
74
en, lz DaNiu
dfs recursion should return when the value of current pos is larger than
searching value. It will push current pos into the priority queue, then
return.

【在 c********t 的大作中提到】
: dfs recursion写不下去了，比如从3开始，不知道何时应该终止.
: 睡了。明天改写iteration.coding和bfs一样繁琐了。
: lz真是牛中牛啊！
c********t
发帖数: 5706
75
循环是因为2-＞1-＞2-＞1 visited 矩阵用的有问,明天改。 minheap may not be a
good choice, since u may want remove element very often.

★ 发自iPhone App: ChineseWeb 7.8

【在 l*******b 的大作中提到】
: en, lz DaNiu
: dfs recursion should return when the value of current pos is larger than
: searching value. It will push current pos into the priority queue, then
: return.
p*****2
发帖数: 21240
76

你先搞一下发发心得好吗？我以前稍微搞过一下。感觉还是有点难呀。

【在 j*****y 的大作中提到】
: 我是要搞了，二爷也要搞吗？
h***i
发帖数: 1970
77
楼主大牛呀。

【在 h**********y 的大作中提到】
: 攒人品，求祝福！
: 别的题都蛮常见的。就这个没见过。
: 二维版本water trap问题。。
: 当场解决了。呵呵。。
i******r
发帖数: 793
78
出这种题目，干脆直接从ACM校队里面招人算了
这不是什么好的趋势
j*****y
发帖数: 1071
79
我也觉得 google现在出题目有点问题，直接搞竞赛题了

【在 i******r 的大作中提到】
: 出这种题目，干脆直接从ACM校队里面招人算了
: 这不是什么好的趋势
i******r
发帖数: 793
80
不是说竞赛题不能出
但是这种题目，没做过的有几个能知道算法，何况写程序
再说算法也只是一个基本功，还有很多其他方面的能力呢
这种面试的趋势有点偏了

【在 j*****y 的大作中提到】
: 我也觉得 google现在出题目有点问题，直接搞竞赛题了
相关主题
● k sorted array merge大家现场写一个heap？● 请教MinHeap用STL实现
● Amazon面筋● leetcode 上的k way merge
● Facebook Interview Questions● 弱弱的问个C++用priority_queue定义min heap的问题
进入JobHunting版参与讨论
j*****y
发帖数: 1071
81
没办法阿，是公司挑人，不是人挑公司。

【在 i******r 的大作中提到】
: 不是说竞赛题不能出
: 但是这种题目，没做过的有几个能知道算法，何况写程序
: 再说算法也只是一个基本功，还有很多其他方面的能力呢
: 这种面试的趋势有点偏了
c********t
发帖数: 5706
82
终于搞定，不是visited问题。而是循环里忘了把min variable重新赋值，导致一直用
以前的最小点，所以死循环。昨天熬夜实在是晕菜了。

【在 c********t 的大作中提到】
: 循环是因为2-＞1-＞2-＞1 visited 矩阵用的有问,明天改。 minheap may not be a
: good choice, since u may want remove element very often.
:
: ★ 发自iPhone App: ChineseWeb 7.8
l*******b
发帖数: 2586
83
嗯最后用的什么做priority queue

【在 c********t 的大作中提到】
: 终于搞定，不是visited问题。而是循环里忘了把min variable重新赋值，导致一直用
: 以前的最小点，所以死循环。昨天熬夜实在是晕菜了。
c********t
发帖数: 5706
84
用的hashmap,每次要找一遍min, 比如你那个例子，要找一次3，再找一次4。好像没有
啥办法。

【在 l*******b 的大作中提到】
: 嗯最后用的什么做priority queue
a***o
发帖数: 1182
85
大拿贴个code学习一下,多谢

【在 c********t 的大作中提到】
: 终于搞定，不是visited问题。而是循环里忘了把min variable重新赋值，导致一直用
: 以前的最小点，所以死循环。昨天熬夜实在是晕菜了。
p*****2
发帖数: 21240
86

才看到你这个。我也是这个思路。感觉复杂度不高呀。准备今天练练。

【在 l*******b 的大作中提到】
: 想了个这个办法, 不知道好实现不?
: 建立一个高度的priority queue
: 把边界一圈push进去
: 当该queue非空时, 弹出最低的那个, 把该点未搜索过的领域push到queue里. 如果领域
: 比弹出的这个元素高度低, 那么就把差距加到总的可以积水的量里面
: 返回总积水量
f*******t
发帖数: 7549
87
写了一下，牛算法实现和理解起来挺简单的
import java.util.PriorityQueue;
public class RainWater2D {
private final int[][] directions = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1}
};

private int width, height;

private class Point implements Comparable {
public int x, y, h;
public Point(int y, int x, int h) {
this.y = y;
this.x = x;
this.h = h;
}
@Override
public int compareTo(Point p) {
return h > p.h ? 1 : -1;
}
}

private boolean isValid(int y, int x) {
if (y < 0 || x < 0 || y >= height || x >= width)
return false;
return true;
}

public int preserveWater(int[][] A) {
if (A == null || A.length < 3 || A[0].length < 3)
return 0;
height = A.length;
width = A[0].length;
boolean[][] visited = new boolean[height][width];
int water = 0;
PriorityQueue heap = new PriorityQueue();
for (int i = 0; i < width; i++) {
heap.add(new Point(0, i, A[0][i]));
visited[0][i] = true;
heap.add(new Point(height - 1, i, A[height - 1][i]));
visited[height - 1][i] = true;
}
for (int i = 1; i < height - 1; i++) {
heap.add(new Point(i, 0, A[i][0]));
visited[i][0] = true;
heap.add(new Point(i, width - 1, A[i][width - 1]));
visited[i][width - 1] = true;
}
while (!heap.isEmpty()) {
Point p = heap.poll();
for (int i = 0; i < 4; i++) {
int ny = p.y + directions[i][0];
int nx = p.x + directions[i][1];
if (isValid(ny, nx) && !visited[ny][nx]) {
if (A[ny][nx] < p.h) {
water = p.h - A[ny][nx] + water;
heap.add(new Point(ny, nx, p.h));
} else
heap.add(new Point(ny, nx, A[ny][nx]));
visited[ny][nx] = true;
}
}
}

return water;
}

public static void main(String[] args) {
int[][] A = {
{5, 5, 5, 5},
{5, 3, 2, 5},
{5, 4, 4, 5},
{5, 1, 5, 5}
};
RainWater2D r = new RainWater2D();
System.out.println(r.preserveWater(A));
}
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
● how to code this question of LinkedIn● 问道indeed面试算法题
● 到底什么是priority queue啊？● 上午偷闲把TopKFrequentWords写出来了
● 又想起一道google题目● 问三道题
● 怎么计算一个网站过去5min的访问量？● k sorted array merge大家现场写一个heap？
● careercup书上那个maintain median value的题● Amazon面筋
● 请教关于build heap BIG-O的问题● Facebook Interview Questions
● 发个evernote的code challenge● 请教MinHeap用STL实现
● twittier的onsite挂了，来问个常见题● leetcode 上的k way merge
相关话题的讨论汇总
话题: point话题: int话题: height话题: nx话题: visited

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑