T problem - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

T problem

T problem# JobHunting - 待字闺中

G*a2013-03-06 08:03

1 楼

日前有圈内人透露，王菲与李亚鹏离婚了！王菲好友那英的姐姐那辛也回应，「王菲的
事，我真的不能多插嘴。真的实在很抱歉。」而身为王菲好姐妹的那英怎麽问都不说，
也有知情人爆料，「只能说盛传王菲李亚鹏感情出问题了。」
其实关于王菲和李亚鹏的新闻去年一直没有断过，先是年初的时候传王菲复出歌坛在即
，接著又传王菲怀孕了，而且其经纪人陈家瑛也证实了王菲怀孕的消息，期间不少媒体
爆料说王菲不断的拜神祈福为孩子，而接下来又传王菲流产了，一连串的传闻不绝于耳。
报导指出，从王菲和李亚鹏不断的传闻，以及无休止的猜测，两人的婚姻看起来这的是
风雨飘摇，现在知情人的爆料说王菲李亚鹏「婚变」，更加是山雨欲来风满楼。但无论
怎麽说李亚鹏和王菲婚变都仅是传闻，但是从传闻也能看出王菲和李亚鹏的婚姻有著太
多的困扰和难题。

b*e2013-03-06 08:03

2 楼

array of N integers, 0 < x < N,
find the first repeated element in the array.
do it in linear time and constant space.
I got the answer but guess failed ...
typically how many problems are expected to resolve in one phone interview?

a*e2013-03-06 08:03

3 楼

不是很早就说王非的婆媳关系堪忧么

耳。

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

: 日前有圈内人透露，王菲与李亚鹏离婚了！王菲好友那英的姐姐那辛也回应，「王菲的
: 事，我真的不能多插嘴。真的实在很抱歉。」而身为王菲好姐妹的那英怎麽问都不说，
: 也有知情人爆料，「只能说盛传王菲李亚鹏感情出问题了。」
: 其实关于王菲和李亚鹏的新闻去年一直没有断过，先是年初的时候传王菲复出歌坛在即
: ，接著又传王菲怀孕了，而且其经纪人陈家瑛也证实了王菲怀孕的消息，期间不少媒体
: 爆料说王菲不断的拜神祈福为孩子，而接下来又传王菲流产了，一连串的传闻不绝于耳。
: 报导指出，从王菲和李亚鹏不断的传闻，以及无休止的猜测，两人的婚姻看起来这的是
: 风雨飘摇，现在知情人的爆料说王菲李亚鹏「婚变」，更加是山雨欲来风满楼。但无论
: 怎麽说李亚鹏和王菲婚变都仅是传闻，但是从传闻也能看出王菲和李亚鹏的婚姻有著太
: 多的困扰和难题。

z*g2013-03-06 08:03

4 楼

我觉得可以首先建一个int array[N],初始化为0，
然后从所给的N integers array given[i]的第一个开始扫描,i = 0:N-1，如果array[
given[i]]=0,那么就设array[given[i]]=1,如果array[given[i]]已经是1了说明之前出
现过了，所以就结束程序，given[i]就是第一个重复的数。

?

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

: array of N integers, 0 < x < N,
: find the first repeated element in the array.
: do it in linear time and constant space.
: I got the answer but guess failed ...
: typically how many problems are expected to resolve in one phone interview?

f*e2013-03-06 08:03

5 楼

前面讨论过了，看这个thread
http://mitbbs.com/article1/JobHunting/32341161_3_0.html

?

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

l*i2013-03-06 08:03

6 楼

what was your answer?

?

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

l*i2013-03-06 08:03

7 楼

题目不一样吧。first repeated element怎么定义？

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

: 前面讨论过了，看这个thread
: http://mitbbs.com/article1/JobHunting/32341161_3_0.html
:
: ?

e*s2013-03-06 08:03

8 楼

Swap吧。
loop array
if(A[i] != i + 1){
if(A[A[i - 1]] == A[i]) return A[i];
swap(A[i], A[A[i - 1]]);
}

b*e2013-03-06 08:03

9 楼

example: { 3, 2, 4, 1 3} 3 is the fist repeated.
// const space
for (int i = 0; i < N; i++) {
int x = a[i];
if ( x> 0 ) {
if ( a[x] < 0 ) { // means the xith item has been changed before.
that means X has shown up already
cout << x << endl;
break;
}
else { // means the xth item has not bee changed yet. let us change
the xth item to negative. Also this mean X does not show up yet
a[x] = a[x]- N;
}
}
else { // this x has been changed
//get the orig value first
int orig = x + N;
if ( a[orig] <= 0 ) { // this a[orig] has been hitted before
cout<< orig << endl;
break;
}
else {
a[orig] = a[orig] - N;
}
}
}

f*e2013-03-06 08:03

10 楼

A[i]=-(index of i first appears)*2，顶多扫两遍。

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

: 题目不一样吧。first repeated element怎么定义？

b*e2013-03-06 08:03

11 楼

not constant space.

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

: 我觉得可以首先建一个int array[N],初始化为0，
: 然后从所给的N integers array given[i]的第一个开始扫描,i = 0:N-1，如果array[
: given[i]]=0,那么就设array[given[i]]=1,如果array[given[i]]已经是1了说明之前出
: 现过了，所以就结束程序，given[i]就是第一个重复的数。
:
: ?

d*e2013-03-06 08:03

12 楼

int find_dup(int A[], int n) {
for (int i = 0; i < n; i++) {
while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
if (A[i] != i+1) return A[i];
}
}

?

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

b*e2013-03-06 08:03

13 楼

I may miss your point.... how does this work on
34112?
can we find 1?
>>>>
int find_dup(int A[], int n) {
for (int i = 0; i < n; i++) {
while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
if (A[i] != i+1) return A[i];
}
}

?

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

b*e2013-03-06 08:03

14 楼

could you give more details?
I did not get it yet. could you use an example to describe your idea?

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

: Swap吧。
: loop array
: if(A[i] != i + 1){
: if(A[A[i - 1]] == A[i]) return A[i];
: swap(A[i], A[A[i - 1]]);
: }

j*y2013-03-06 08:03

15 楼

感觉不对
比如
1 2 2 1
你这个找出来的是 2

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

: int find_dup(int A[], int n) {
: for (int i = 0; i < n; i++) {
: while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
: if (A[i] != i+1) return A[i];
: }
: }
:
: ?

h*t2013-03-06 08:03

16 楼

就应该是2啊， 2 repeat的比1 repeat的早

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

: 感觉不对
: 比如
: 1 2 2 1
: 你这个找出来的是 2

j*y2013-03-06 08:03

17 楼

这么理解吗，感觉应该是 1阿
请楼主来澄清一下

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

: 就应该是2啊， 2 repeat的比1 repeat的早

j*y2013-03-06 08:03

18 楼

感觉还是不对，你看看
4 2 2 4 1
这个用他的code跑出来是 4, 按照你的看法，应该是 2

就应该是2啊， 2 repeat的比1 repeat的早

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

: 就应该是2啊， 2 repeat的比1 repeat的早

c*r2013-03-06 08:03

19 楼

位操作不就可以了么？

j*y2013-03-06 08:03

20 楼

你这个扫两遍，第一遍的时候是不是已经把原来的array 修改了？第二遍还怎么搞？

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

: A[i]=-(index of i first appears)*2，顶多扫两遍。

j*y2013-03-06 08:03

21 楼

这个感觉难度不太一样吧?

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

: 前面讨论过了，看这个thread
: http://mitbbs.com/article1/JobHunting/32341161_3_0.html
:
: ?

j*y2013-03-06 08:03

22 楼

xor ? 感觉不太一样吧 ?

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

: 位操作不就可以了么？

b*e2013-03-06 08:03

23 楼

should be 2.
Does my agorithm give 4?
btw, could you give more details about the swap algorithm? I did not get it.

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

: 感觉还是不对，你看看
: 4 2 2 4 1
: 这个用他的code跑出来是 4, 按照你的看法，应该是 2
:
: 就应该是2啊， 2 repeat的比1 repeat的早

b*e2013-03-06 08:03

24 楼

Some modificaiton on my code. don't need to use x-N to track whether a X is
hit. Simply use -X is okay.
-------------
are you talking about my algorithm?
It gives 2 for 1221.
(1) go to a[0], 1 -> will change a[1] to 2-4 = -2. the array becomes 1, -2,
2, 1
(2) go to a[1], -2, calculate the original = 4-2 = 2. check a[orig] = a[2] =
2 > 0, so change a[2] to 2-4
= -2. now the array becomes 1, -2, -2, 1. Note here a[2] is changed because
of a[1] originally == 2.
(3) go to a[2], -2, calculate the orignal = 4-2 =2. check a[orig] = [2] = -2
< 0 which indicates it is changed by a[**] = orig = 2 where ** is before 2
(here ** is 1). So 2 is found as the first repeated one.
Below is the code.
// const space
for (int i = 0; i < N; i++) {
int x = a[i];
if ( x> 0 ) {
if ( a[x] < 0 ) { // means the xith item has been changed before.
that means X has shown up already
cout << x << endl;
break;
}
else { // means the xth item has not bee changed yet. let us change
the xth item to negative. Also this mean X does not show up yet
a[x] = -a[x];
}
}
else { // this x has been changed
//get the orig value first
int orig = -x;
if ( a[orig] <= 0 ) { // this a[orig] has been hitted before
cout<< orig << endl;
break;
}
else {
a[orig] = -a[orig];
}
}
}

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

: 感觉还是不对，你看看
: 4 2 2 4 1
: 这个用他的code跑出来是 4, 按照你的看法，应该是 2
:
: 就应该是2啊， 2 repeat的比1 repeat的早

j*y2013-03-06 08:03

25 楼

不是，刚才是说 didiaoge的
正在研究你的 :)

2,
4
because
-2
2

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

: Some modificaiton on my code. don't need to use x-N to track whether a X is
: hit. Simply use -X is okay.
: -------------
: are you talking about my algorithm?
: It gives 2 for 1221.
: (1) go to a[0], 1 -> will change a[1] to 2-4 = -2. the array becomes 1, -2,
: 2, 1
: (2) go to a[1], -2, calculate the original = 4-2 = 2. check a[orig] = a[2] =
: 2 > 0, so change a[2] to 2-4
: = -2. now the array becomes 1, -2, -2, 1. Note here a[2] is changed because

b*e2013-03-06 08:03

26 楼

how this work for 24332?
Did I miss anything?
Seems,
i = 0, a[0] = 2 != a[2-1] = 4, so swap a[0] && a[2-1] = a[1]. so the array
is
now 42332.
check if (a[0] = 4 != 0+1 = 1) so return a[0] = 4.
Yet the answer should be 3.
Do I miss anything?

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

: int find_dup(int A[], int n) {
: for (int i = 0; i < n; i++) {
: while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
: if (A[i] != i+1) return A[i];
: }
: }
:
: ?

r*n2013-03-06 08:03

27 楼

这个题一般的version是 there are N+1 integers ranging from 0 to N-1, find the
repeated integer。显然有且只有一个重复的。用swap归位，如果 arr[arr[i]] ==
arr[i]，就返回arr[i]。
这个问题问the first repeated integer，所以用一个变量存repeated integer seen
so far，每次遇到新的就和这个比较一下。

j*y2013-03-06 08:03

28 楼

关键是怎么比较，因为那个应该是第一个 repeat number的数或许交换到后面去了

the
seen

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

: 这个题一般的version是 there are N+1 integers ranging from 0 to N-1, find the
: repeated integer。显然有且只有一个重复的。用swap归位，如果 arr[arr[i]] ==
: arr[i]，就返回arr[i]。
: 这个问题问the first repeated integer，所以用一个变量存repeated integer seen
: so far，每次遇到新的就和这个比较一下。

r*n2013-03-06 08:03

29 楼

没有关系啊，因为是归位，
比如第一次遇到
arr[i] = 3， arr[arr[i]] = 3，那么repeated number seen so far就是3
如果后面来一个
arr[j] = 10, arr[arr[j]] = 10, 那么10和3比较，还是存3

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

: 关键是怎么比较，因为那个应该是第一个 repeat number的数或许交换到后面去了
:
: the
: seen

j*y2013-03-06 08:03

30 楼

能写一个 code 吗 ? thanks.

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

: 没有关系啊，因为是归位，
: 比如第一次遇到
: arr[i] = 3， arr[arr[i]] = 3，那么repeated number seen so far就是3
: 如果后面来一个
: arr[j] = 10, arr[arr[j]] = 10, 那么10和3比较，还是存3

j*y2013-03-06 08:03

31 楼

你的算法应该是对的，不过挺难想到的，厉害

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

: example: { 3, 2, 4, 1 3} 3 is the fist repeated.
: // const space
: for (int i = 0; i < N; i++) {
: int x = a[i];
: if ( x> 0 ) {
: if ( a[x] < 0 ) { // means the xith item has been changed before.
: that means X has shown up already
: cout << x << endl;
: break;
: }

r*n2013-03-06 08:03

32 楼

int tmp = numeric_limits::max();
for(int i = 0; iwhile(arr[i] != arr[arr[i]])
swap(arr[i],arr[arr[i]]);
if(arr[i] == i) continue;
if(arr[i] < tmp ) tmp = arr[i];
}
试了一下
1 2 2 1 输出 1
4 2 2 4 1 输出 2

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

: 能写一个 code 吗 ? thanks.

b*e2013-03-06 08:03

33 楼

for 1221 the first repeated one is 2, not 1.

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

: int tmp = numeric_limits::max();
: for(int i = 0; i: while(arr[i] != arr[arr[i]])
: swap(arr[i],arr[arr[i]]);
: if(arr[i] == i) continue;
: if(arr[i] < tmp ) tmp = arr[i];
: }
: 试了一下
: 1 2 2 1 输出 1
: 4 2 2 4 1 输出 2

r*n2013-03-06 08:03

34 楼

恩，我理解错了，没那么简单

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

: for 1221 the first repeated one is 2, not 1.