MMD, 死在了longest contiguous increasing sub-array上了. - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

MMD, 死在了longest contiguous increasing sub-array上了.

MMD, 死在了longest contiguous increasing sub-array上了.# JobHunting - 待字闺中

j*g2010-10-29 07:10

1 楼

面官一出此题，俺窃喜，大笔一挥，O(n) one scan解法跃然纸上：
loop
if a[i] >= a[i + 1]
len = 1
else
len++

if len > max then max = len
etc.etc.
面官说有没有更快的。。。disaster自此开始...//省略5000字。。。直到面官把能提
醒的都提醒了才发现其中奥妙.

P*b2010-10-29 07:10

2 楼

你的代码找的是decreasing的，不过想不出还能比linear更好的方法

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

: 面官一出此题，俺窃喜，大笔一挥，O(n) one scan解法跃然纸上：
: loop
: if a[i] >= a[i + 1]
: len = 1
: else
: len++
:
: if len > max then max = len
: etc.etc.
: 面官说有没有更快的。。。disaster自此开始...//省略5000字。。。直到面官把能提

r*o2010-10-29 07:10

3 楼

if multiple repetitive elements, use binary search first?

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

: 你的代码找的是decreasing的，不过想不出还能比linear更好的方法

l*a2010-10-29 07:10

4 楼

if a[i] >= a[i + 1]
后一个不比前一个小，就重新开始
是递增吧

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

: 你的代码找的是decreasing的，不过想不出还能比linear更好的方法

j*g2010-10-29 07:10

5 楼

what? of course my code is looking for increasing sequence.
if a[i] >= a[i+1], reset len back to 1.

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

: 你的代码找的是decreasing的，不过想不出还能比linear更好的方法

j*g2010-10-29 07:10

6 楼

nope. the array elements are random, not sorted, binary search doesn't fit
here.

【在 r****o 的大作中提到】

: if multiple repetitive elements, use binary search first?

r*o2010-10-29 07:10

7 楼

you are right. Then what is the faster algorithm?

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

: nope. the array elements are random, not sorted, binary search doesn't fit
: here.

j*g2010-10-29 07:10

8 楼

让俺好好伤心伤心，让大牛们先想着，明天公布答案，if still not solved...

r*o2010-10-29 07:10

9 楼

if the # of rest elements is smaller than or equal to len, and a[i]>=a[i+1]
then exit?

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

d*e2010-10-29 07:10

10 楼

将 if len > max 那个放第一个if里面,reset len = 1 之前
if len > max then max = len end if
len = 1
减少比较次数，还是O(n)，但系数小

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

j*g2010-10-29 07:10

11 楼

slightly better, not good enough..

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

: 将 if len > max 那个放第一个if里面,reset len = 1 之前
: if len > max then max = len end if
: len = 1
: 减少比较次数，还是O(n)，但系数小

j*g2010-10-29 07:10

12 楼

有点意思，但你的optimization只在array的尾巴上，isn't it a bit too little too
late?

]

【在 r****o 的大作中提到】

: if the # of rest elements is smaller than or equal to len, and a[i]>=a[i+1]
: then exit?

d*e2010-10-29 07:10

13 楼

我忍……你会令我今晚无眠 -_-!

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

: slightly better, not good enough..

i*e2010-10-29 07:10

14 楼

O(N)的复杂度是肯定的了。。。
我只能想到的就是在后段减少一些比较次数。
因为后段剩下的元素少于或者等于 max，就不用继续比较了，反正不可能超于max。
还有没有更好的方法呢？
max = 1
loop from i = 0 .. n-max-1
if a[i] >= a[i + 1]
len = 1
else
len++

if len > max then max = len
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

c*22010-10-29 07:10

15 楼

http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem

j*g2010-10-29 07:10

16 楼

yours is essentially what roufoo said:
发信人: roufoo (五经勤向窗前读), 信区: JobHunting
标题: Re: MMD, 死在了longest contiguous increasing sub-array上了.
发信站: BBS 未名空间站 (Fri Oct 29 01:57:19 2010, 美东)
if the # of rest elements is smaller than or equal to len, and a[i]>=a[i+1
]
then exit?
this only improves slightly near the end of the array. if the array is very
long, then the improvement is so small that is negligible.

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

: O(N)的复杂度是肯定的了。。。
: 我只能想到的就是在后段减少一些比较次数。
: 因为后段剩下的元素少于或者等于 max，就不用继续比较了，反正不可能超于max。
: 还有没有更好的方法呢？
: max = 1
: loop from i = 0 .. n-max-1
: if a[i] >= a[i + 1]
: len = 1
: else
: len++

j*g2010-10-29 07:10

17 楼

dude, read the problem again :)

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

: http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem

i*e2010-10-29 07:10

18 楼

damn...
didn't see it.
gotta do better than this i guess :)
thanks to you, i can't sleep tonight as well!
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

+1
very

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

: yours is essentially what roufoo said:
: 发信人: roufoo (五经勤向窗前读), 信区: JobHunting
: 标题: Re: MMD, 死在了longest contiguous increasing sub-array上了.
: 发信站: BBS 未名空间站 (Fri Oct 29 01:57:19 2010, 美东)
: if the # of rest elements is smaller than or equal to len, and a[i]>=a[i+1
: ]
: then exit?
: this only improves slightly near the end of the array. if the array is very
: long, then the improvement is so small that is negligible.

d*e2010-10-29 07:10

19 楼

我觉得方法大概是差不多，但不应该focus在后段，中间应该也可以这么干。
比如进入if时，len=10，那么直接比较a[i+9]和a[i+10]
1) if a[i+9] >= a[i+10] //如果是这个情况，那么就少比较10个了。
i = i + 10
再继续比较a[i+9]和a[i+10]
2) if a[i+9] < a[i+10]
那么往左回来比较
不知是不是这样，但暂时没想到怎么写个简洁的code

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

i*e2010-10-29 07:10

20 楼

这里假设全部都是 integer，floating point numbers 就不行。
不知道这个假设合不合理呢？
思路是既然是 integer，假设当前的 max 是 3，那就直接比较　a[i] 和 a[i+3]的相差。如果相差小于3，那之间的元素都可以直接略过。如果相差大于或等于3的话，那就要一个一个比较之间的元素，然后如果之间的元素都是递增的，那就继续比较到 a[i] >= a[i+1]为止。
max = 1
loop from i = 0 .. n-max-1
if (a[i + max] - a[i] < max)
i = i + max
else
j = i
len = 1
while j <= n-max-1
if (a[j+1] <= a[j])
i = i + max
break
else
len++
if len > max then max = len
j++
end while
end else
end loop
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

r*o2010-10-29 07:10

21 楼

Will the repetitive elements will also be counted as continuously increasing?
then your algorithm needs to consider them.

相差。如果相差小于3，那之间的元素都可以直接略过。如果相差大于或等于3的话，那
就要一个一个比较之间的元素，然后如果之间的元素都是递增的，那就继续比较到 a[i
] >= a[i+1]为止。

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

: 这里假设全部都是 integer，floating point numbers 就不行。
: 不知道这个假设合不合理呢？
: 思路是既然是 integer，假设当前的 max 是 3，那就直接比较　a[i] 和 a[i+3]的相差。如果相差小于3，那之间的元素都可以直接略过。如果相差大于或等于3的话，那就要一个一个比较之间的元素，然后如果之间的元素都是递增的，那就继续比较到 a[i] >= a[i+1]为止。
: max = 1
: loop from i = 0 .. n-max-1
: if (a[i + max] - a[i] < max)
: i = i + max
: else
: j = i
: len = 1

i*e2010-10-29 07:10

22 楼

阿　晕～
刚才没看到你已经提出了解答。
我觉得你的思路是正确的。
我刚post的代码只能应用于 integers，你的方法而没有这样的限制。
可以安心去睡了吧你
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 我觉得方法大概是差不多，但不应该focus在后段，中间应该也可以这么干。
: 比如进入if时，len=10，那么直接比较a[i+9]和a[i+10]
: 1) if a[i+9] >= a[i+10] //如果是这个情况，那么就少比较10个了。
: i = i + 10
: 再继续比较a[i+9]和a[i+10]
: 2) if a[i+9] < a[i+10]
: 那么往左回来比较
: 不知是不是这样，但暂时没想到怎么写个简洁的code

i*e2010-10-29 07:10

23 楼

No the repetitive elements will not be counted as continuously increasing.
Could you give a counter-example?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

increasing?
[i

【在 r****o 的大作中提到】

: Will the repetitive elements will also be counted as continuously increasing?
: then your algorithm needs to consider them.
:
: 相差。如果相差小于3，那之间的元素都可以直接略过。如果相差大于或等于3的话，那
: 就要一个一个比较之间的元素，然后如果之间的元素都是递增的，那就继续比较到 a[i
: ] >= a[i+1]为止。

r*o2010-10-29 07:10

24 楼

No counter-example.
If the repetitive elements are not counted as continuously incr, then your
solution is correct.

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

: No the repetitive elements will not be counted as continuously increasing.
: Could you give a counter-example?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: increasing?
: [i

d*e2010-10-29 07:10

25 楼

嗯，睡得很安心，早上睡到自然醒了....
哈哈

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

: 阿　晕～
: 刚才没看到你已经提出了解答。
: 我觉得你的思路是正确的。
: 我刚post的代码只能应用于 integers，你的方法而没有这样的限制。
: 可以安心去睡了吧你
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

c*22010-10-29 07:10

26 楼

You are right, man. The difference is whether "contiguous".
Thanks for pointing that out.

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

: dude, read the problem again :)

i*e2010-10-29 07:10

27 楼

Nevermind.
My solution is incorrect.
I think done's solution is the correct one.
Is there better optimization?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

相差。如果相差小于3，那之间的元素都可以直接略过。如果相差大于或等于3的话，那
就要一个一个比较之间的元素，然后如果之间的元素都是递增的，那就继续比较到 a[i
] >= a[i+1]为止。

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

c*22010-10-29 07:10

28 楼

Performance of done's solution: (for array size of 10)
======================================================
Input Array:
-45 -85 -1 -37 -21 -11 -5 52 -57 46
comparisons=33
longest_inc_sub:
length=5
startIdx=3
Sub-array:
-37 -21 -11 -5 52
Input Array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
comparisons=12
longest_inc_sub:
length=10
startIdx=0
Sub-array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
Input Array:
52 46 -1 -5 -11 -21 -37 -45 -57 -85
comparisons=9
longest_inc_sub:
length=1
startIdx=0
Sub-array:
52

c*22010-10-29 07:10

29 楼

Using brute-force
========================
Input Array:
-45 -85 -1 -37 -21 -11 -5 52 -57 46
comparisons=21
longest_inc_sub_bf:
length=5
startIdx=3
Sub-array:
-37 -21 -11 -5 52
Input Array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
comparisons=10
longest_inc_sub_bf:
length=10
startIdx=0
Sub-array:
-85 -57 -45 -37 -21 -11 -5 -1 46 52
Input Array:
52 46 -1 -5 -11 -21 -37 -45 -57 -85
comparisons=10
longest_inc_sub_bf:
length=1
startIdx=0
Sub-array:
52

c*22010-10-29 07:10

30 楼

/* longest contiguous increasing sub-array : brute-force */
int longest_inc_sub_bf(int array[], int size, int *start)
{
int max,len,i;
int from,max_from;
int comparisons=0;

max=len=1;
max_from=from=0;
i=0;

while(1){
i=from;
while((i=array[i])){
i++;
len++;
comparisons++;
}
comparisons++;

if(len>max) {
max_from=from;
max=len;
if(max>size){
max=size;
break;
}
}

if(i>=size-1) break;

from++;
len=1;
}

printf("comparisons=%d\n",comparisons);

*start=max_from;
return max;
}

c*22010-10-29 07:10

31 楼

/* longest contiguous increasing sub-array : improvement */
int longest_inc_sub(int array[], int size, int *start)
{
int max,len,i;
int from,to,max_from;
int comparisons=0;

max=len=1;
max_from=from=to=0;
i=0;

while(1){
/* advance to next block */
to = from+len;

if(to>=size) break;

/* looking backward */
i=to;
while((i>from)&&(array[i]>=array[i-1])){
i--;
len++;
comparisons++;
}
comparisons++;

/* whole block is good */
if(i==from){
i=to;
/* looking forward */
while((i=array[i])){
i++;
len++;
comparisons++;
}
comparisons++;

if(len>max) {
max_from=from;
max=len;
if(max>size){
max=size;
break;
}
}
if(i==size) break;
}
else{
from++;
len=1;
}
}

printf("comparisons=%d\n",comparisons);

*start=max_from;
return max;
}

c*22010-10-29 07:10

32 楼

I don't see any improvement. Did I miss something?

c*82010-10-29 07:10

33 楼

how about just focus on the position, where is not increasing order?

d*e2010-10-29 07:10

34 楼

你的例子不够长，所以没什么区别。
但你试试这个，最长的部分相对数组长度比较小的情况下：
int a[] = {0, 1, 2, 3, 4, 3, 5, 4, 3, 2, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 0};
我的测试是一个comparison 10，一个是 26

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

: I don't see any improvement. Did I miss something?

i*e2010-10-29 07:10

35 楼

The reason you are not getting the lower comparisons is because in your code:
else{
from++;
len=1;
}
after the if (i==from) block.
Are you sure you want to increase the search position by one forward?
Here's an example:
... 1 2 4 3 5 ...
i=5 6 7 8 9
Let's say your current maximum is 4. And now your index i starts at 5. You
compare element no. 8 and 9, and since 3 is less than 5, you continue
comparing element no. 7 and 8. Since 4 is not less than 3, you decided that
you can stop comparing. Now, should you increment your search index by one
to index no. 6? I guess not. You should increment your search index to
element no. 8, right where you first found the first element that is bigger
or equal than its right element.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: /* longest contiguous increasing sub-array : improvement */
: int longest_inc_sub(int array[], int size, int *start)
: {
: int max,len,i;
: int from,to,max_from;
: int comparisons=0;
:
: max=len=1;
: max_from=from=to=0;
: i=0;

i*e2010-10-29 07:10

36 楼

BTW, I found a potential bug in your code.
This line:
while((i=array[i])){
What if i==size-1?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

i*e2010-10-29 07:10

37 楼

Here's a counter-example:
... 1 3 1 2 ...
i=5 6 7 8
Let's say my current max is 3. Therefore I compare element no. 5 and no. 8.
The difference is only 1, therefore i skip all elements from index 5 to 8.
This is incorrect, as we should start the next search from element no. 7.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

[i

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

: Nevermind.
: My solution is incorrect.
: I think done's solution is the correct one.
: Is there better optimization?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: 相差。如果相差小于3，那之间的元素都可以直接略过。如果相差大于或等于3的话，那
: 就要一个一个比较之间的元素，然后如果之间的元素都是递增的，那就继续比较到 a[i
: ] >= a[i+1]为止。

i*e2010-10-29 07:10

38 楼

Here's my implementation base on done's solution.
int findMaxIncreasing(int arr[], int n) {
if (n == 0) return 0;
int max = 1;
for (int i = 0; i < n-max;) {
int j = i+max-1;
while (j >= i && (arr[j] < arr[j+1]))
j--;
if (j == i-1) { // all prev values are increasing order
bool increase = true;
j = i+max;
while (increase && j < n-1) {
if (arr[j] < arr[j+1])
j++;
else
increase = false;
}
int len = j-i+1;
if (len > max) max = len;
i = j+1;
} else {
i = j+1;
}
}
return max;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

d*e2010-10-29 07:10

39 楼

赞～看得真仔细

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

: BTW, I found a potential bug in your code.
: This line:
: while((i=array[i])){
: What if i==size-1?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

c*22010-10-29 07:10

40 楼

Right. This is the key thing: from=i instead of from++

code:

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

: The reason you are not getting the lower comparisons is because in your code:
: else{
: from++;
: len=1;
: }
: after the if (i==from) block.
: Are you sure you want to increase the search position by one forward?
: Here's an example:
: ... 1 2 4 3 5 ...
: i=5 6 7 8 9

c*22010-10-29 07:10

41 楼

good finding. thanks.

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

: BTW, I found a potential bug in your code.
: This line:
: while((i=array[i])){
: What if i==size-1?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

c*22010-10-29 07:10

42 楼

much better after change of from=i;

j*g2010-10-29 07:10

43 楼

done/ihasleetcode你们是不是专业interviewee啊？？//佩服！
从来没贴过图，不知道贴对了没。done的想法是对的：
step 1: suppose we've already done the scan for step 1, and how we have the
max length MAX at point a.
step 2: no need to compare one by one, just jump to MAX position b, and do
an adjacent comparison. If >=, then we know there won't be anything before
could satisfy "increasing" as well as beat MAX. So in this case, keep
jumping MAX ahead.
step 3: suppose we're at MAX place b, and adjacent comparision is we have a potential candidate, so scan left-ward. if our left-wards scan hit
a >= at position c, then we do the MAX jump again.
step 4: now suppose our new MAX jump (to position d) is good (left-wards again, a little note is that we don't need to scan all the way
back to the jump point c, all we need to do is to scan back to point b,
becaus [c, b] has already been scanned and it's increasing.
还没有写code, 就是algo description, 不好意思。

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

: much better after change of from=i;

j*g2010-10-29 07:10

44 楼

就知道没贴队...再贴

the
!
hit

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

: done/ihasleetcode你们是不是专业interviewee啊？？//佩服！
: 从来没贴过图，不知道贴对了没。done的想法是对的：
: step 1: suppose we've already done the scan for step 1, and how we have the
: max length MAX at point a.
: step 2: no need to compare one by one, just jump to MAX position b, and do
: an adjacent comparison. If >=, then we know there won't be anything before
: could satisfy "increasing" as well as beat MAX. So in this case, keep
: jumping MAX ahead.
: step 3: suppose we're at MAX place b, and adjacent comparision is : we have a potential candidate, so scan left-ward. if our left-wards scan hit

P*72010-10-29 07:10

45 楼

挺难的，估计面试官也不指望有人当场做出来吧。

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

: 就知道没贴队...再贴
:
: the
: !
: hit

j*g2010-10-29 07:10

46 楼

还是挺搞笑的。我问面官how'd you get this problem.他说，以前他interview一个
fresh grad, 问那个简单的部分(linear continuous scan)，结果那个grad很不屑，
说那个太弱了，你要问就要问这个(faster than linear scan in randomly
distrubted series),结果那个interview session两个人换了个位子。所以他印象深刻
，从此用此题来虐待别人。。

【在 P*******7 的大作中提到】

: 挺难的，估计面试官也不指望有人当场做出来吧。

P*72010-10-29 07:10

47 楼

那就不用担心了，面官当年也不会嘛

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

: 还是挺搞笑的。我问面官how'd you get this problem.他说，以前他interview一个
: fresh grad, 问那个简单的部分(linear continuous scan)，结果那个grad很不屑，
: 说那个太弱了，你要问就要问这个(faster than linear scan in randomly
: distrubted series),结果那个interview session两个人换了个位子。所以他印象深刻
: ，从此用此题来虐待别人。。

P*l2010-10-29 07:10

48 楼

done利用已知的最大长度来跳过不必要的比较,觉得应该是最优的解法了。
但是代码上还可以改进：
int maxLength(int[] arr) {
if (arr.length < 2)
return arr.length;
// at least, the length contiguous incremental sequence
is 1.
int maxLen = 1;
// checking using the known maximum length
for (int i = maxLen; i < arr.length; i += maxLen) {
// i-maxLen is the starting position of the
sequence, so,
// invariant: arr[i-maxLen-1] >= arr[i-maxLen]
if (arr[i - 1] >= arr[i]) {
continue;
}
// potentially, the sequence starting from i-
maxLen can be longer.
／／这里，应该从左向右重新找最大的长度。
int subMax = 1;
for (int j = i - maxLen + 1; j < arr.length;
j++) {
if (arr[j - 1] >= arr[j]) {
break;
}
subMax++;
}
if (subMax > maxLen) {
// found one, adjust both i and the
maximum length
i = i - maxLen + subMax; // tricky step，
调整一下，继续按最大长度跳
maxLen = subMax;
}
}
return maxLen;
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
http://code.google.com/p/sureinterview/source/browse/src/solution/misc/C
ontiguousIncreasingSubarray.java#15
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
再贴上测试数据：
// {maxLen},{sequence}
{ 1 }, { 1 },// 1
{ 2 }, { 1, 0, 1, 0, 1, 0 },// 2
{ 3 }, { 1, 2, 3, 0, 1, 0, 1, 0 },// 3
{ 4 }, { 1, 0, 1, 0, 1, 2, 3, 0 },// 4
{ 4 }, { 1, 0, 1, 0, 1, 2, 3 },// 4
{ 4 }, { 1, 0, 1, 2, 3, 0, 1, 0 },// 4
};
for (int i = 0; i < arrs.length; i += 2) {
Assert.assertEquals(arrs[i][0], maxLength(arrs[i
+ 1]));
}

have the
and do
before
great!
scan hit

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

P*l2010-10-29 07:10

49 楼

Using code here