Redian新闻
>
据说D7k,k-5,A580用的都是同一快感光芯片?
avatar
据说D7k,k-5,A580用的都是同一快感光芯片?# PhotoGear - 摄影器材
z*h
1
大家常去的网站或论坛除了未名还有?
我先说吧
搜狐
水木
文学城
youtube
avatar
b*s
2
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
两天后被拒了,求大牛指出我的代码错哪了


avatar
h*a
3
是这样吗?如果是的话,那是不是拍的raw照片都一样,jpg机内加工不同?
avatar
O*O
4
劳动人民喜闻乐见的毒窝

【在 z******h 的大作中提到】
: 大家常去的网站或论坛除了未名还有?
: 我先说吧
: 搜狐
: 水木
: 文学城
: youtube

avatar
u*o
5
面的是whitepage吗? 做过一模一样的coding challenge的题。。。用的是greedy的解
,也被据了。。不知是不是DP更好?
avatar
r*l
6
火星回来的?

【在 h*****a 的大作中提到】
: 是这样吗?如果是的话,那是不是拍的raw照片都一样,jpg机内加工不同?
avatar
S*l
7
popyard, sina

【在 z******h 的大作中提到】
: 大家常去的网站或论坛除了未名还有?
: 我先说吧
: 搜狐
: 水木
: 文学城
: youtube

avatar
b*s
8

是的 就是whitepage 我觉得greedy已经是最好的了啊 空间O(1),时间O(n)
死的不甘心啊

【在 u*****o 的大作中提到】
: 面的是whitepage吗? 做过一模一样的coding challenge的题。。。用的是greedy的解
: ,也被据了。。不知是不是DP更好?

avatar
q*z
9
ADC不一样,D7000 k5都是加了外置14bit ADC, a580是用sensor内置的
12 bit ADC,a580的raw应该差一些.

【在 h*****a 的大作中提到】
: 是这样吗?如果是的话,那是不是拍的raw照片都一样,jpg机内加工不同?
avatar
h*1
10
google, baidu
avatar
u*o
11
没错,我还写了很详尽的complexity analysis, 说明它比DP superior。。
你是UW career fair递的简历吗? 我当时就是做了那个checker board的题,然后收到
这个code challenge, 没想到这个要求这么高。。。

【在 b*********s 的大作中提到】
:
: 是的 就是whitepage 我觉得greedy已经是最好的了啊 空间O(1),时间O(n)
: 死的不甘心啊

avatar
h*a
12
如您所说的这个情况,对ISO也会有影响吗?

【在 q*z 的大作中提到】
: ADC不一样,D7000 k5都是加了外置14bit ADC, a580是用sensor内置的
: 12 bit ADC,a580的raw应该差一些.

avatar
p*a
13
tudou

【在 z******h 的大作中提到】
: 大家常去的网站或论坛除了未名还有?
: 我先说吧
: 搜狐
: 水木
: 文学城
: youtube

avatar
b*s
14

不是 我是在LinkedIn上给他们的hr发了一封inMail
hr第二天给我发了封邮件问我愿不愿意做coding challenge,我回了他之后就一个星期
都没再联系我,后来我又发了一封邮件去催他才把题目发过来,交了之后两天就被拒了

【在 u*****o 的大作中提到】
: 没错,我还写了很详尽的complexity analysis, 说明它比DP superior。。
: 你是UW career fair递的简历吗? 我当时就是做了那个checker board的题,然后收到
: 这个code challenge, 没想到这个要求这么高。。。

avatar
z*h
15
这是哪个?

【在 O*O 的大作中提到】
: 劳动人民喜闻乐见的毒窝
avatar
u*o
16
这家很好吗? 我根本没听说过呀。。
career fair才认识他家,别人都送劣质笔,他家送的是手套,我现在还带着呢。。。
感觉对coding challenge要求还蛮高的。。

【在 b*********s 的大作中提到】
:
: 不是 我是在LinkedIn上给他们的hr发了一封inMail
: hr第二天给我发了封邮件问我愿不愿意做coding challenge,我回了他之后就一个星期
: 都没再联系我,后来我又发了一封邮件去催他才把题目发过来,交了之后两天就被拒了

avatar
b*s
17

实情是我太挫了哈哈 在linkedin上面骚扰了很多hr 目前只有他们一家鸟我

【在 u*****o 的大作中提到】
: 这家很好吗? 我根本没听说过呀。。
: career fair才认识他家,别人都送劣质笔,他家送的是手套,我现在还带着呢。。。
: 感觉对coding challenge要求还蛮高的。。

avatar
J*3
18
。。。哈哈

【在 u*****o 的大作中提到】
: 这家很好吗? 我根本没听说过呀。。
: career fair才认识他家,别人都送劣质笔,他家送的是手套,我现在还带着呢。。。
: 感觉对coding challenge要求还蛮高的。。

avatar
z*e
19
现在看到这种题第一感觉就是dp……
avatar
c*2
20
我前天也做了这道题...
然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...
avatar
w*t
21
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,昨晚
: 看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...

avatar
l*n
22
你理解的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.

avatar
b*s
23

能说一下你的解法是什么吗?我现在就只是想知道到底我的解法错在哪里了

【在 c*******2 的大作中提到】
: 我前天也做了这道题...
: 然后昨天起来回想自己的思路, 发现了一个bug, 硬着头皮给HR发邮件说明了bug,昨晚
: 看到这个帖子后感觉他们不会理我了, 结果今天收到邮件说想多聊聊...

avatar
b*s
24
不好意思 有点不太懂你的例子 能详细点说说吗

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.

avatar
c*2
25
也是greedy的

能说一下你的解法是什么吗?我现在就只是想知道到底我的解法错在哪里了

【在 b*********s 的大作中提到】
: 不好意思 有点不太懂你的例子 能详细点说说吗
:
: I

avatar
l*o
26
不仔细看帖就吃亏呀!我也做了这家,在大家之后。交了之后发现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

avatar
b*s
27
我不太懂他那个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

avatar
C*w
28
greedy不对吧,这题正解是dp啊,O(N)时间解决不了的吧
avatar
l*o
29
我觉得你是对的,真是o(n)。
如果非要吹毛求疵的话,是不是一旦跳出去,就不用继续loop,直接返回结果

★ 发自iPhone App: ChineseWeb 7.8

【在 b*********s 的大作中提到】
: 我不太懂他那个test的意思
: 用3 100 1 1 1 1 1 0 作input的话我写的那个greedy出来结果是0, 1, out

avatar
b*s
30

求大牛解释 或给反例

【在 C******w 的大作中提到】
: greedy不对吧,这题正解是dp啊,O(N)时间解决不了的吧
avatar
C*w
31
首先,是若菜不是大牛;
其次,仔细看了下题目还有你的解法,您这个O(N)算法是对的。

【在 b*********s 的大作中提到】
:
: 求大牛解释 或给反例

avatar
p*o
32
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

avatar
b*s
33

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)

avatar
p*o
34
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

avatar
b*s
35

"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 = []

avatar
w*e
36
这道题目就是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

avatar
z*n
37
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

avatar
b*s
38
我的程序输出 0, 2, out

【在 z***n 的大作中提到】
: lz这个贪心算法不对,给个例子(下标从0开始)。大家验证一下
: 2 3 100 1 1 1
: 自己推算,lz的程序会输出 0 1 2 out

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。