b*********s
发帖数: 115 | 1 array hooper
给一个array，每个元素都是大于等于0的数字，每个数字代表可以向右跳的最大步数。
从第一个元素出发，要跳出数组。跟leetcode的jump gameII差不多，区别在于
1. 这里要求跳出数组，leetcode是要求跳到最后一个元素
2. 如果能跳出数组，给出其中一组最少步数的跳法，如不能跳出，输出failure。
leetcode是只要求给出答案能不能跳到最后
examples:
input: 1, 1 output: 0, 1, out
input: 2, 1, 3, 1, 1 output: 0, 2, out
input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
input: 1, 2, 1, 0, 2 output: failure
我的代码是
def hopper(a):
a.append(0)
path = []
cur = 0
maxCenter = 0
maxRange = 0
for i, n in enumerate(a):
if i > cur:
if i > maxRange:
print "failure"
return
else:
path.append(maxCenter)
cur = maxRange
if i + n > maxRange:
maxCenter = i
maxRange = max(maxRange, i + n)
path.append('out')
print ', '.join(map(str, path))
return
两天后被拒了，求大牛指出我的代码错哪了
| u*****o
发帖数: 1224 | 2 面的是whitepage吗？ 做过一模一样的coding challenge的题。。。用的是greedy的解
，也被据了。。不知是不是DP更好？ | b*********s
发帖数: 115 | 3
是的 就是whitepage 我觉得greedy已经是最好的了啊 空间O(1)，时间O(n)
死的不甘心啊
【在 u*****o 的大作中提到】
: 面的是whitepage吗？ 做过一模一样的coding challenge的题。。。用的是greedy的解
: ，也被据了。。不知是不是DP更好？
| u*****o
发帖数: 1224 | 4 没错，我还写了很详尽的complexity analysis， 说明它比DP superior。。
你是UW career fair递的简历吗？ 我当时就是做了那个checker board的题，然后收到
这个code challenge, 没想到这个要求这么高。。。
【在 b*********s 的大作中提到】
:
: 是的 就是whitepage 我觉得greedy已经是最好的了啊 空间O(1)，时间O(n)
: 死的不甘心啊
| b*********s
发帖数: 115 | 5
不是 我是在LinkedIn上给他们的hr发了一封inMail
hr第二天给我发了封邮件问我愿不愿意做coding challenge，我回了他之后就一个星期
都没再联系我，后来我又发了一封邮件去催他才把题目发过来，交了之后两天就被拒了
【在 u*****o 的大作中提到】
: 没错，我还写了很详尽的complexity analysis， 说明它比DP superior。。
: 你是UW career fair递的简历吗？ 我当时就是做了那个checker board的题，然后收到
: 这个code challenge, 没想到这个要求这么高。。。
| u*****o
发帖数: 1224 | 6 这家很好吗？ 我根本没听说过呀。。
career fair才认识他家，别人都送劣质笔，他家送的是手套，我现在还带着呢。。。
感觉对coding challenge要求还蛮高的。。
【在 b*********s 的大作中提到】
:
: 不是 我是在LinkedIn上给他们的hr发了一封inMail
: hr第二天给我发了封邮件问我愿不愿意做coding challenge，我回了他之后就一个星期
: 都没再联系我，后来我又发了一封邮件去催他才把题目发过来，交了之后两天就被拒了
| b*********s
发帖数: 115 | 7
实情是我太挫了哈哈 在linkedin上面骚扰了很多hr 目前只有他们一家鸟我
【在 u*****o 的大作中提到】
: 这家很好吗？ 我根本没听说过呀。。
: career fair才认识他家，别人都送劣质笔，他家送的是手套，我现在还带着呢。。。
: 感觉对coding challenge要求还蛮高的。。
| J****3
发帖数: 427 | 8 。。。哈哈
【在 u*****o 的大作中提到】
: 这家很好吗？ 我根本没听说过呀。。
: career fair才认识他家，别人都送劣质笔，他家送的是手套，我现在还带着呢。。。
: 感觉对coding challenge要求还蛮高的。。
| z****e
发帖数: 54598 | | c*******2
发帖数: 60 | 10 我前天也做了这道题...
然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊... | | | w**t
发帖数: 893 | 11 greedy for sure does not work.
eg. step 0 -- 1, 3
step 1 -- 100
step 3 -- 1
first to 1 is better than to 3
this is a dp with memorization. should be space o(n), time o(n2), the best I
can come up.
【在 c*******2 的大作中提到】
: 我前天也做了这道题...
: 然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
: 看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...
| l*n
发帖数: 529 | 12 你理解的greedy有问题，不是每次直接跑最远。
http://stackoverflow.com/questions/9041853/interview-puzzle-jum
I
【在 w**t 的大作中提到】
: greedy for sure does not work.
: eg. step 0 -- 1, 3
: step 1 -- 100
: step 3 -- 1
: first to 1 is better than to 3
: this is a dp with memorization. should be space o(n), time o(n2), the best I
: can come up.
| b*********s
发帖数: 115 | 13
能说一下你的解法是什么吗？我现在就只是想知道到底我的解法错在哪里了
【在 c*******2 的大作中提到】
: 我前天也做了这道题...
: 然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
: 看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...
| b*********s
发帖数: 115 | 14 不好意思 有点不太懂你的例子 能详细点说说吗
I
【在 w**t 的大作中提到】
: greedy for sure does not work.
: eg. step 0 -- 1, 3
: step 1 -- 100
: step 3 -- 1
: first to 1 is better than to 3
: this is a dp with memorization. should be space o(n), time o(n2), the best I
: can come up.
| c*******2
发帖数: 60 | 15 也是greedy的
能说一下你的解法是什么吗？我现在就只是想知道到底我的解法错在哪里了
【在 b*********s 的大作中提到】
: 不好意思 有点不太懂你的例子 能详细点说说吗
:
: I
| l**********o
发帖数: 260 | 16 不仔细看帖就吃亏呀！我也做了这家，在大家之后。交了之后发现bug。。。。
这题能O(n) 时间？不可能吧。。。
bfs 或者 dp 都有解，我用了dp, 完了之后才想到bfs, bfs应该更有效率。
我不太熟Python， wzxt 给的例子你test一下试试看。
array 是 3 100 1 1 1 1 1 0 或者你试试这个 case
★ 发自iPhone App: ChineseWeb 7.8
【在 b*********s 的大作中提到】
: 不好意思 有点不太懂你的例子 能详细点说说吗
:
: I
| b*********s
发帖数: 115 | 17 我不太懂他那个test的意思
用3 100 1 1 1 1 1 0 作input的话我写的那个greedy出来结果是0, 1, out
【在 l**********o 的大作中提到】
: 不仔细看帖就吃亏呀！我也做了这家，在大家之后。交了之后发现bug。。。。
: 这题能O(n) 时间？不可能吧。。。
: bfs 或者 dp 都有解，我用了dp, 完了之后才想到bfs, bfs应该更有效率。
: 我不太熟Python， wzxt 给的例子你test一下试试看。
: array 是 3 100 1 1 1 1 1 0 或者你试试这个 case
:
: ★ 发自iPhone App: ChineseWeb 7.8
| C******w
发帖数: 23 | 18 greedy不对吧，这题正解是dp啊，O（N）时间解决不了的吧 | l**********o
发帖数: 260 | 19 我觉得你是对的，真是o(n)。
如果非要吹毛求疵的话，是不是一旦跳出去，就不用继续loop，直接返回结果
★ 发自iPhone App: ChineseWeb 7.8
【在 b*********s 的大作中提到】
: 我不太懂他那个test的意思
: 用3 100 1 1 1 1 1 0 作input的话我写的那个greedy出来结果是0, 1, out
| b*********s
发帖数: 115 | 20
求大牛解释 或给反例
【在 C******w 的大作中提到】
: greedy不对吧，这题正解是dp啊，O（N）时间解决不了的吧
| | | C******w
发帖数: 23 | 21 首先，是若菜不是大牛；
其次，仔细看了下题目还有你的解法，您这个O(N)算法是对的。
【在 b*********s 的大作中提到】
:
: 求大牛解释 或给反例
| p****o
发帖数: 46 | 22 I think your condition for "failure" is wrong:
if i > cur:
if i > maxRange:
print "failure"
return
e.g., the case that it stops right at the end (i.e., case maxRange == n-1, n
is the size of input array a):
[2,3,1,1,0], which you should output "failure".
the right condition for success should be "maxRange > n-1", strictly greater
. (i.e., "<=" for failure)
based on your code, you can decide fail or success after the loop is
finished, e.g., if (maxRange > len(a)-1) out; else fail
【在 b*********s 的大作中提到】
: array hooper
: 给一个array，每个元素都是大于等于0的数字，每个数字代表可以向右跳的最大步数。
: 从第一个元素出发，要跳出数组。跟leetcode的jump gameII差不多，区别在于
: 1. 这里要求跳出数组，leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组，给出其中一组最少步数的跳法，如不能跳出，输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
| b*********s
发帖数: 115 | 23
n
greater
输入是2， 3， 1， 1， 0的时候我的程序没有错，结果是failure
我在最开始的时候往数组最后面加了个0
【在 p****o 的大作中提到】
: I think your condition for "failure" is wrong:
: if i > cur:
: if i > maxRange:
: print "failure"
: return
: e.g., the case that it stops right at the end (i.e., case maxRange == n-1, n
: is the size of input array a):
: [2,3,1,1,0], which you should output "failure".
: the right condition for success should be "maxRange > n-1", strictly greater
: . (i.e., "<=" for failure)
| p****o
发帖数: 46 | 24 ok, I only had a glimpse on a.append(0), and quickly skip it... :-), have
not written python for quite some time.
then I think it is correct. but personally, I feel it is tricky to append "0
" at the end of input, and also the input has to change. Another
controversial case is the empty input, you will output "out".
Well, maybe the reviewer did not see that "append", or did not think too
much. or there is still something wrong we have not checked out.
Your code is not far from not modifying input, as follows.
def hopper(a):
path = []
cur = 0
maxCenter = 0
maxRange = 0
for i, n in enumerate(a):
if i > cur:
path.append(maxCenter)
cur = maxRange
if i + n > maxRange:
maxCenter = i
maxRange = i + n
if (maxRange <= len(a)):
print "failure"
return
path.append('out')
print ', '.join(map(str, path))
return
【在 b*********s 的大作中提到】
:
: n
: greater
: 输入是2， 3， 1， 1， 0的时候我的程序没有错，结果是failure
: 我在最开始的时候往数组最后面加了个0
| b*********s
发帖数: 115 | 25
"0
You're right. Thanks!
【在 p****o 的大作中提到】
: ok, I only had a glimpse on a.append(0), and quickly skip it... :-), have
: not written python for quite some time.
: then I think it is correct. but personally, I feel it is tricky to append "0
: " at the end of input, and also the input has to change. Another
: controversial case is the empty input, you will output "out".
: Well, maybe the reviewer did not see that "append", or did not think too
: much. or there is still something wrong we have not checked out.
: Your code is not far from not modifying input, as follows.
: def hopper(a):
: path = []
| w*******e
发帖数: 395 | 26 这道题目就是leetcode的jump game II，没有任何区别
【在 b*********s 的大作中提到】
: array hooper
: 给一个array，每个元素都是大于等于0的数字，每个数字代表可以向右跳的最大步数。
: 从第一个元素出发，要跳出数组。跟leetcode的jump gameII差不多，区别在于
: 1. 这里要求跳出数组，leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组，给出其中一组最少步数的跳法，如不能跳出，输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
| z***n
发帖数: 11 | 27 lz这个贪心算法不对，给个例子（下标从0开始）。大家验证一下
2 3 100 1 1 1
自己推算，lz的程序会输出 0 1 2 out
【在 b*********s 的大作中提到】
: array hooper
: 给一个array，每个元素都是大于等于0的数字，每个数字代表可以向右跳的最大步数。
: 从第一个元素出发，要跳出数组。跟leetcode的jump gameII差不多，区别在于
: 1. 这里要求跳出数组，leetcode是要求跳到最后一个元素
: 2. 如果能跳出数组，给出其中一组最少步数的跳法，如不能跳出，输出failure。
: leetcode是只要求给出答案能不能跳到最后
: examples:
: input: 1, 1 output: 0, 1, out
: input: 2, 1, 3, 1, 1 output: 0, 2, out
: input: 5, 6, 0, 4, 2, 4, 1, 0, 0, 4 output: 0, 5, 9, out
| b*********s
发帖数: 115 | 28 我的程序输出 0, 2, out
【在 z***n 的大作中提到】
: lz这个贪心算法不对，给个例子（下标从0开始）。大家验证一下
: 2 3 100 1 1 1
: 自己推算，lz的程序会输出 0 1 2 out
|
|
