此时此刻，我想到小少爷了 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

此时此刻，我想到小少爷了

此时此刻，我想到小少爷了# Living

c*a2013-10-30 07:10

1 楼

上周写了liveramp的OA题，分享给大家：）
之前也看了大家的许多面经，回馈一下。
两道题比较第二道比较新。
1) Given an array A, find the index p, in which A[0] + A[1] +...+ A[p-1] = A
[p+1] + A[p+2] +.. + A[n-1]. Time complex O(n)
2) Given an array A, find the longest subarray which biggest element minus
smallest element not less than 1.

i*e2013-10-30 07:10

2 楼

那么心地好的一位ID就这样默默地远离我们，不知道他现在去哪个版，

e*22013-10-30 07:10

3 楼

第二题要么无解，要么整个array？

A

【在 c******a 的大作中提到】

: 上周写了liveramp的OA题，分享给大家：）
: 之前也看了大家的许多面经，回馈一下。
: 两道题比较第二道比较新。
: 1) Given an array A, find the index p, in which A[0] + A[1] +...+ A[p-1] = A
: [p+1] + A[p+2] +.. + A[n-1]. Time complex O(n)
: 2) Given an array A, find the longest subarray which biggest element minus
: smallest element not less than 1.

p*g2013-10-30 07:10

4 楼

我也想念小少爷

c*a2013-10-30 07:10

5 楼

数组的顺序不能变，例如：A = [ 3, 5, 7,7,6], 最长的应该是[7, 7, 6]

【在 e********2 的大作中提到】

: 第二题要么无解，要么整个array？
:
: A

p*g2013-10-30 07:10

6 楼

小少爷修网不来了

g*i2013-10-30 07:10

7 楼

这个是no more than 1吧，用sliding window做。

C*e2013-10-30 07:10

8 楼

当年走的是他？

j*32013-10-30 07:10

9 楼

他家的oa限时么？要求多久以内做完？

s*s2013-10-30 07:10

10 楼

是不是我们都该休网了。。。

b*e2013-10-30 07:10

11 楼

这个用sliding window的确可以做到线性，但是很难。

【在 g********i 的大作中提到】

: 这个是no more than 1吧，用sliding window做。

m*s2013-10-30 07:10

12 楼

付给costco100个包子给你答案。

【在 i***e 的大作中提到】

: 那么心地好的一位ID就这样默默地远离我们，不知道他现在去哪个版，

f*y2013-10-30 07:10

13 楼

大概这样做:
use an array len[ ] to keep track of the longest subarray ending at A[i]
use {min, minIndex } and {max, maxIndex} to keep track of current min/max
and their indices.
if A[i] > max + 1, then update max and clear min; set len[i] = 1
if A[i] < min -1, then update min and clear max; set len[i] = 1
if A[i] is between min and max, then set len[i] = len[i-1] + 1
if A[i] == max + 1 && minIndex < maxIndex, then min = max; max = A[i],
len[i] = len[i-1] + (maxIndex - minIndex)
if A[i] == min -1 && minIndex > maxIndex, then max = min; min = A[i], len[i
] = len[i-1] + (minIndex - maxIndex)
第一遍走完，len[ ] 就设好了；第二遍遍历 len[ ] 找最大值

【在 b***e 的大作中提到】

: 这个用sliding window的确可以做到线性，但是很难。

p*g2013-10-30 07:10

14 楼

是啊
版主居然还删我的帖子，我至今还是耿耿于怀

【在 C******e 的大作中提到】

: 当年走的是他？

b*e2013-10-30 07:10

15 楼

Are you assuming each number is an integer?
Anyways, the general approach requires sliding window max/min algorithm,
which is non-trivial. I think this problem is too hard for an interview
question.

[i

【在 f********y 的大作中提到】

: 大概这样做:
: use an array len[ ] to keep track of the longest subarray ending at A[i]
: use {min, minIndex } and {max, maxIndex} to keep track of current min/max
: and their indices.
: if A[i] > max + 1, then update max and clear min; set len[i] = 1
: if A[i] < min -1, then update min and clear max; set len[i] = 1
: if A[i] is between min and max, then set len[i] = len[i-1] + 1
: if A[i] == max + 1 && minIndex < maxIndex, then min = max; max = A[i],
: len[i] = len[i-1] + (maxIndex - minIndex)
: if A[i] == min -1 && minIndex > maxIndex, then max = min; min = A[i], len[i

i*e2013-10-30 07:10

16 楼

亲人啊，您可终于来了。。

【在 m********s 的大作中提到】

: 付给costco100个包子给你答案。

G*s2013-10-30 07:10

17 楼

这会儿才真相大白。。。。他并木有灌得很离谱

【在 p**********g 的大作中提到】

: 是啊
: 版主居然还删我的帖子，我至今还是耿耿于怀

b*b2013-10-30 07:10

18 楼

我知道小少爷现在过得不错，吃香的，喝辣的！

【在 i***e 的大作中提到】

: 那么心地好的一位ID就这样默默地远离我们，不知道他现在去哪个版，

p*g2013-10-30 07:10

19 楼

难道他不想我们吗？

【在 b***b 的大作中提到】

: 我知道小少爷现在过得不错，吃香的，喝辣的！

d*02013-10-30 07:10

20 楼

原来小白胖嫁给他拉？

【在 b***b 的大作中提到】

: 我知道小少爷现在过得不错，吃香的，喝辣的！

b*b2013-10-30 07:10

21 楼

这个可以想。

【在 p**********g 的大作中提到】

: 难道他不想我们吗？

G*e2013-10-30 07:10

22 楼

请把“们”去掉。。。。。。。

【在 p**********g 的大作中提到】

: 难道他不想我们吗？

i*e2013-10-30 07:10

23 楼

希望他开开心心。
要是有机会，白胖妹妹也可邀请小少爷去钓鱼，他人很好的。

【在 b***b 的大作中提到】

: 我知道小少爷现在过得不错，吃香的，喝辣的！

M*u2013-10-30 07:10

24 楼

哈哈哈，你不懂丁版的良苦用心。他是想在你心里留下一滴眼泪啊！

【在 p**********g 的大作中提到】

: 是啊
: 版主居然还删我的帖子，我至今还是耿耿于怀

M*u2013-10-30 07:10

25 楼

在一起，在一起.......

【在 i***e 的大作中提到】

:
: 希望他开开心心。
: 要是有机会，白胖妹妹也可邀请小少爷去钓鱼，他人很好的。

G*e2013-10-30 07:10

26 楼

nm。。。。
。。。。
介糯米文学奖是厉害。。。。。

【在 M****u 的大作中提到】

: 哈哈哈，你不懂丁版的良苦用心。他是想在你心里留下一滴眼泪啊！

p*g2013-10-30 07:10

27 楼

他怎么可以摧残一个这么善良，憨厚的wsn

【在 M****u 的大作中提到】

: 哈哈哈，你不懂丁版的良苦用心。他是想在你心里留下一滴眼泪啊！

M*u2013-10-30 07:10

28 楼

这样你就永远忘不了他了

【在 p**********g 的大作中提到】

: 他怎么可以摧残一个这么善良，憨厚的wsn

G*e2013-10-30 07:10

29 楼

lmaorotf。。。。。。。。。。。。。。
。。。。。。。
。哈哈哈哈哈哈哈

【在 p**********g 的大作中提到】

: 他怎么可以摧残一个这么善良，憨厚的wsn

M*u2013-10-30 07:10

30 楼

全靠肉鸽栽培

【在 G*****e 的大作中提到】

: nm。。。。
: 。。。。
: 介糯米文学奖是厉害。。。。。

i*e2013-10-30 07:10

31 楼

哎呀，不好意思

【在 M****u 的大作中提到】

: 在一起，在一起.......

G*e2013-10-30 07:10

32 楼

月哥牙洞这么大了？。。。
。。。。
这回音

【在 M****u 的大作中提到】

: 在一起，在一起.......

b*b2013-10-30 07:10

33 楼

大侠跟少爷钓过鱼？
羡慕。

【在 i***e 的大作中提到】

:
: 哎呀，不好意思

i*e2013-10-30 07:10

34 楼

呵呵，如果将来有机会。
小少爷曾经和我说过波士顿的家。

【在 b***b 的大作中提到】

: 大侠跟少爷钓过鱼？
: 羡慕。

G*e2013-10-30 07:10

35 楼

厚厚。。。。说的是威力吧。。。。。。。。？

【在 b***b 的大作中提到】

: 大侠跟少爷钓过鱼？
: 羡慕。

p*g2013-10-30 07:10

36 楼

我也不在这里了，又是五花肉，又是穿VS的版主
民不聊生啊........

【在 G*****e 的大作中提到】

: 厚厚。。。。说的是威力吧。。。。。。。。？

G*e2013-10-30 07:10

37 楼

皮熊风格大便。。。。。。。。。虽然不常驻，但是经常上来打两棒棰就跑。。。。。。

【在 p**********g 的大作中提到】

: 我也不在这里了，又是五花肉，又是穿VS的版主
: 民不聊生啊........

b*b2013-10-30 07:10

38 楼

我是福尔摩斯，综合分析出来的。

【在 d**********0 的大作中提到】

: 原来小白胖嫁给他拉？

s*t2013-10-30 07:10

39 楼

是不是y打头的一个id?

【在 i***e 的大作中提到】

: 那么心地好的一位ID就这样默默地远离我们，不知道他现在去哪个版，

i*e2013-10-30 07:10

40 楼

是的，
一直想为小少爷做件事。

【在 s*********t 的大作中提到】

: 是不是y打头的一个id?

s*t2013-10-30 07:10

41 楼

他有一阵子在上海版冒泡，后来也大来了

【在 i***e 的大作中提到】

:
: 是的，
: 一直想为小少爷做件事。

p*g2013-10-30 07:10

42 楼

什么？
我等到现在才问，你一定憋坏了吧

【在 G*****e 的大作中提到】

: lmaorotf。。。。。。。。。。。。。。
: 。。。。。。。
: 。哈哈哈哈哈哈哈

i*e2013-10-30 07:10

43 楼

这儿还有上海版?

【在 s*********t 的大作中提到】

: 他有一阵子在上海版冒泡，后来也大来了

G*e2013-10-30 07:10

44 楼

一滴眼泪。。。。。。。我已经知道答案。。。。。wuhahaha。。。

【在 p**********g 的大作中提到】

: 什么？
: 我等到现在才问，你一定憋坏了吧

p*g2013-10-30 07:10

45 楼

我还不知道啊？

【在 G*****e 的大作中提到】

: 一滴眼泪。。。。。。。我已经知道答案。。。。。wuhahaha。。。