A phone interview problem about algorithm - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

A phone interview problem about algorithm

A phone interview problem about algorithm# JobHunting - 待字闺中

V*i2011-11-05 07:11

1 楼

I cannot figure it out till now. Looking for help.
Given an array of integers with duplication, write a function to determine
whether this array is a sequence. A sequence is defined as every integer
between min and max is present. For example, {2, 3, 2, 5, 7, 7, 6, 4, 2} is
a sequence. But {2, 3, 5, 3} is not.
Write a program with O(n) time complexity, and O(1) space. The array CAN BE
DESTROYED.

f*t2011-11-05 07:11

2 楼

有可能吗。。

x*o2011-11-05 07:11

3 楼

这个可以有。。。关键词， data can be DESTROYED...
那原来那个数组就可以用来存，相当于你有O(N)的space了。
扫描数组两便就好了。

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

: 有可能吗。。

n*w2011-11-05 07:11

4 楼

basic idea is to sort the array in O(n)
first, find minimal and maximal value, say min, max
if it is a sequence, after sorting, a[i] should store min+i, for i from 0 to
max-min
the code to sort in O(n),
for(i = 0 to n-1)
while(a[a[i]-min]!=a[i]){
swap(a, a[i]-min, i); //swap the element at the index (a[i]-min) and i
}

is
BE

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

: I cannot figure it out till now. Looking for help.
: Given an array of integers with duplication, write a function to determine
: whether this array is a sequence. A sequence is defined as every integer
: between min and max is present. For example, {2, 3, 2, 5, 7, 7, 6, 4, 2} is
: a sequence. But {2, 3, 5, 3} is not.
: Write a program with O(n) time complexity, and O(1) space. The array CAN BE
: DESTROYED.

z*n2011-11-05 07:11

5 楼

有duplication，a[i] 不一定 store min+i

to
and i

【在 n*******w 的大作中提到】

: basic idea is to sort the array in O(n)
: first, find minimal and maximal value, say min, max
: if it is a sequence, after sorting, a[i] should store min+i, for i from 0 to
: max-min
: the code to sort in O(n),
: for(i = 0 to n-1)
: while(a[a[i]-min]!=a[i]){
: swap(a, a[i]-min, i); //swap the element at the index (a[i]-min) and i
: }
:

V*i2011-11-05 07:11

6 楼

I use nooneknow's idea to write a program, it seems to be correct after many
testing, but I have not convinced myself yet using a clear logic. Anybody
can help?
bool if_sequence(int* a, int N) {
int min = a[0];
int max = a[0];
for (int i=1; iif (a[i] < min) min = a[i];
else if (a[i] > max) max = a[i];
}
if (max-min+1 > N) return false;
// p is the pointer for the garbage area
int p = max-min+1;
for (int i=0; iwhile (a[i] != min+i) {
if (a[i] != a[a[i]-min]) swap(a[i], a[a[i]-min]);
else if (p >= N) return false;
else swap(a[i], a[p++]);
}
}
return true;
}

【在 z*****n 的大作中提到】

: 有duplication，a[i] 不一定 store min+i
:
: to
: and i

q*x2011-11-05 07:11

7 楼

没看懂。到底什么是sequence？为何第一个是，第二个不是？

is
BE

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

n*w2011-11-05 07:11

8 楼

本质上就是把a[i]放到它该待着的地方，如果那个地方已经store这个数了。不用swap
，直接i++处理下一个。
证明很容易，每次swap至少保证把一个元素放到该去的地方，最多n个不同的元素。最
多swap n次。
不过你这code好像会死循环。逻辑也不清晰。好像跟我说的有点反着的意思。
我觉得先sort完，再检查min到max中间每个元素是不是都存在，逻辑会比较清晰。

many

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

: I use nooneknow's idea to write a program, it seems to be correct after many
: testing, but I have not convinced myself yet using a clear logic. Anybody
: can help?
: bool if_sequence(int* a, int N) {
: int min = a[0];
: int max = a[0];
: for (int i=1; i: if (a[i] < min) min = a[i];
: else if (a[i] > max) max = a[i];
: }

r*n2011-11-05 07:11

9 楼

我也没看懂, 有没有人给翻译下

【在 q****x 的大作中提到】

: 没看懂。到底什么是sequence？为何第一个是，第二个不是？
:
: is
: BE

V*i2011-11-05 07:11

10 楼

抱歉，说的不是很清楚。这题是问一个数组，是不是最大值和最小值之间的每一个整数
都存在。比方说第一个数组，最小最大是2,7，数组中3,4,5,6都有，所以他是一个序列
。第二个数组中，缺4,所以不是序列。

l*n2011-11-05 07:11

11 楼

Assume that the number range is smaller than half of possible range of the
data type, saying int. Then use the original array as hashtable to memorize
whether a number is in the arrey or not.
Modify Viterbi code below (not for easy typing, the idea behind is quite
different):
bool IsSequence(int* a, int N) {
int min = 0, max = 0;
for (int i=0; iif (a[i] < min) min = a[i];
else if (a[i] > max) max = a[i];
}
if (max-min+1 > N) return false;
for (int i=0; ifor (int i=0; i{
a[a[i]] = a[a[i]] * -1;
}

for(int i=0; i<=max-min; i++)
{
if(a[i] >= 0)return false;
}

return true;
}
Code not tested, just to show the idea.

many

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

s*e2011-11-05 07:11

12 楼

no swap method,
first scan to get min and max
in second scan, each element minus min, then get an index array, 0,1,2,4,3,3
in 3rd scan, b = abs(a[i]);
if(a[b] >0) a[b] *= -1;
in 4th scan to find out if the all first max element are < 0;
2nd scan and 3rd scan can be merged.

e*s2011-11-05 07:11

13 楼

赞CODE.这个a[a[i]] *= -1;太巧了！

the
memorize
quite

【在 l*****n 的大作中提到】

: Assume that the number range is smaller than half of possible range of the
: data type, saying int. Then use the original array as hashtable to memorize
: whether a number is in the arrey or not.
: Modify Viterbi code below (not for easy typing, the idea behind is quite
: different):
: bool IsSequence(int* a, int N) {
: int min = 0, max = 0;
: for (int i=0; i: if (a[i] < min) min = a[i];
: else if (a[i] > max) max = a[i];

d*n2011-11-05 07:11

14 楼

My implementation of sdvaline' idea:
boolean isSquence(int[] a, int N) {
int min = a[0];
int max = a[0];

// first scan
for (int i = 0; i < N; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}

// return if there are not enough elements to form a sequence
if (max - min + 1 > N) {
return false;
}

// second scan
for (int i = 0; i < N; i++) {
a[i] -= min;
}

// third scan
for (int i = 0; i < N; i++) {
int index = Math.abs(a[i]);
a[index] = (a[index] < 0)? a[index] : -1 * a[index];
}

// fourth scan
for (int i = 0; i < max - min + 1; i++) {
if (a[i] > 0) {
return false;
}
}

return true;
}

d*l2011-11-05 07:11

15 楼

你这个和楼上那个思路并不一样，初看有点怪，看明白之后觉得应该是对的，而且还挺
巧的。比楼上的其它方法更直接。很难想象你自己没弄明白能写出来。。

many

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

q*x2011-11-05 07:11

16 楼

O(N) time O(1) space应该能搞定。

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

: 抱歉，说的不是很清楚。这题是问一个数组，是不是最大值和最小值之间的每一个整数
: 都存在。比方说第一个数组，最小最大是2,7，数组中3,4,5,6都有，所以他是一个序列
: 。第二个数组中，缺4,所以不是序列。

c*e2011-11-05 07:11

17 楼

关键是借助-1把数字做个标记下来，有的脑筋急转弯。

,3

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

: no swap method,
: first scan to get min and max
: in second scan, each element minus min, then get an index array, 0,1,2,4,3,3
: in 3rd scan, b = abs(a[i]);
: if(a[b] >0) a[b] *= -1;
: in 4th scan to find out if the all first max element are < 0;
: 2nd scan and 3rd scan can be merged.

n*w2011-11-05 07:11

18 楼

那个思路的确够曲折的。看了半天发现的确work。
sdvaline 的code有个bug。第4个scan判断的时候应该是要把0当做valid，这个没问题。
但是0是valid的话，会出现问题。如果数组里存在多个min。
反例比如[0 0 2]，答案是false，但是跑出来的结果是true。
0要特殊对待。

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

: 你这个和楼上那个思路并不一样，初看有点怪，看明白之后觉得应该是对的，而且还挺
: 巧的。比楼上的其它方法更直接。很难想象你自己没弄明白能写出来。。
:
: many

s*e2011-11-05 07:11

19 楼

Yes. you are right. that is a bug. I managed to use two scans.
since array can be destroyed, so we can modify the value to make a flag, say
the original value is x, flaged value is x + (max-min+1).
// first scan skiped to get min and max
// second scan;
count = 0;
for(int i=0;i< n;i++)
{
//restore to original value
if(a[i] > max)
{
value = a[i] - max;
}
else
{
value = a[i];
}
//index
index = value - min;
if(a[index] < = max)
{
count ++;
a[index] += (max -min +1);
}
}
return count == max -min +1;

题。

【在 n*******w 的大作中提到】

: 那个思路的确够曲折的。看了半天发现的确work。
: sdvaline 的code有个bug。第4个scan判断的时候应该是要把0当做valid，这个没问题。
: 但是0是valid的话，会出现问题。如果数组里存在多个min。
: 反例比如[0 0 2]，答案是false，但是跑出来的结果是true。
: 0要特殊对待。

a*t2011-11-05 07:11

20 楼

这个不错。
就有一点：
下面这一行是不是要改成 value = a[i] - (max - min + 1),
还是我理解错了？
//restore to original value
if(a[i] > max)
{
value = a[i] - max; }

say

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

: Yes. you are right. that is a bug. I managed to use two scans.
: since array can be destroyed, so we can modify the value to make a flag, say
: the original value is x, flaged value is x + (max-min+1).
: // first scan skiped to get min and max
: // second scan;
: count = 0;
: for(int i=0;i< n;i++)
: {
: //restore to original value
: if(a[i] > max)

v*12011-11-05 07:11

21 楼

没看明白，大虾给解释解释？

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

h*l2011-11-05 07:11

22 楼

zan，终于有个明白的解释了

,3

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

d*l2011-11-05 07:11

23 楼

不敢。我说说我的想法：一般的思路先找min和max肯定没问题，接下来的做法通常就是
对i从0-n-1，不断把a[i]换到a[a[i]-min]去，直到a[i]=a[a[i]-min]。然后再从头检
查一遍前max-min+1个元素是不是满足a[i]=i+min就行。
但他的那个方法是i只从0循环到max-min，并且检测到a[i]=a[a[i]-min]并不停止，而
是把后面的换过来继续做交换。如果观察他的程序，可以看出p只有在出现了duplicate
之后才可能++。p初始是max-min+1，说明我们至少需要max-min+1个不同元素来构成
sequence，每出现一个duplicate，p++。如果p=N就说明我们需要N个元素才可能构成序
列，这个时候如果再碰到duplicate就说明无法取到max-min+1个不同元素了，因为
duplicates的数量超过了可以接受的最大值。

【在 v****1 的大作中提到】

: 没看明白，大虾给解释解释？

v*12011-11-05 07:11

24 楼

多谢，我理解是把序列的前max-min+1项变成a[i]=i+min,不过怎么想到通过交换a[i]和
a[a[i]-min]这种方式的?

duplicate

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

: 不敢。我说说我的想法：一般的思路先找min和max肯定没问题，接下来的做法通常就是
: 对i从0-n-1，不断把a[i]换到a[a[i]-min]去，直到a[i]=a[a[i]-min]。然后再从头检
: 查一遍前max-min+1个元素是不是满足a[i]=i+min就行。
: 但他的那个方法是i只从0循环到max-min，并且检测到a[i]=a[a[i]-min]并不停止，而
: 是把后面的换过来继续做交换。如果观察他的程序，可以看出p只有在出现了duplicate
: 之后才可能++。p初始是max-min+1，说明我们至少需要max-min+1个不同元素来构成
: sequence，每出现一个duplicate，p++。如果p=N就说明我们需要N个元素才可能构成序
: 列，这个时候如果再碰到duplicate就说明无法取到max-min+1个不同元素了，因为
: duplicates的数量超过了可以接受的最大值。

d*l2011-11-05 07:11

25 楼

把a[i]换到a[a[i]-min]其实就是在把a[j]变成j+min的过程，j=a[i]-min。

【在 v****1 的大作中提到】

: 多谢，我理解是把序列的前max-min+1项变成a[i]=i+min,不过怎么想到通过交换a[i]和
: a[a[i]-min]这种方式的?
:
: duplicate

s*k2011-11-05 07:11

26 楼

这个是不对的，试试{ 3, 3, 2, 1, 0, 5, 1, 2 }
可以用一个tail记录最后一个index，然后不停地把当前的数字放到应该放的位置上，
如果应该放的位置已经有数字了，就和tail交换，然后tail--。
当当前的数字应该在的位置超过tail时，return false。
当循环到tail的时候，循环结束。
然后最后检查0->tail的位置是不是一个序列。

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

: My implementation of sdvaline' idea:
: boolean isSquence(int[] a, int N) {
: int min = a[0];
: int max = a[0];
:
: // first scan
: for (int i = 0; i < N; i++) {
: if (a[i] < min) {
: min = a[i];
: }

v*12011-11-05 07:11

27 楼

十分感谢。现在是把a[i]换到a[a[i]-min]去，如果反过来把a[i]-min换到a[i]呢？这
样最后一遍扫描也不用了.

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

: 把a[i]换到a[a[i]-min]其实就是在把a[j]变成j+min的过程，j=a[i]-min。

d*n2011-11-05 07:11

28 楼

// this one is similar to v1 but in third scan, it count the # of uniq
elements
boolean isSquence_v2(int[] a, int N) {
int min = a[0];
int max = a[0];

// first scan
for (int i = 0; i < N; i++) {
if (a[i] < min) {
min = a[i];
}
else if (a[i] > max) {
max = a[i];
}
}

// return if there are not enough elements to form a sequence
if (max - min + 1 > N) {
return false;
}

// second scan
for (int i = 0; i < N; i++) {
a[i] = a[i] - min + 1; // make the least value to be 1 instead
of 0 to avoid ambiguous later.
}

int count = 0;
// third scan
for (int i = 0; i < N; i++) {
int index = Math.abs(a[i]) - 1; // -1 because we added 1 earlier.
if (a[index] > 0) { ++count; a[index] *= -1;}
}
return count == max - min + 1;
}

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

: 这个是不对的，试试{ 3, 3, 2, 1, 0, 5, 1, 2 }
: 可以用一个tail记录最后一个index，然后不停地把当前的数字放到应该放的位置上，
: 如果应该放的位置已经有数字了，就和tail交换，然后tail--。
: 当当前的数字应该在的位置超过tail时，return false。
: 当循环到tail的时候，循环结束。
: 然后最后检查0->tail的位置是不是一个序列。

n*w2011-11-05 07:11

29 楼

a[i]-min换到a[i]的逻辑稍复杂一些。
面试一紧张不一定玩得转，个人觉得。

【在 v****1 的大作中提到】

: 十分感谢。现在是把a[i]换到a[a[i]-min]去，如果反过来把a[i]-min换到a[i]呢？这
: 样最后一遍扫描也不用了.

r*g2011-11-05 07:11

30 楼

你一边说没看懂一边写出这么好的解法，牛
这个关键似乎是：p之后的数字无所谓，只要前面1到max-min+1的位置都找到了就好。

many

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

r*g2011-11-05 07:11

31 楼

p*22011-11-05 07:11

32 楼

2, 3, 2, 5, 7, 7, 6, 4, 2
先扫一遍得到最小最大值
min=2
max=7
在扫一遍把每个数减去最小值
0，1，0，3，5，5，4，2，0
在扫一遍，把每个数放到这个数的index上，比如，0，放到index 0。如果有duplicate
不管。
0, 1, 2, 3, 4, 5, 2， 0
这样，前边max-min+1个数应该出现，0-max-min+1才对。否则，就return false.