软软的出路。 - 未名空间MITBBS历史存档

p*t2013-01-25 08:01

1 楼

要知道农村永远都是靠着山靠着水建造的，农村的生活也大多数都是自给自足的，所
以很多人会下河洗衣服摸鱼，下山砍柴找野果。那么你是否见过山里有这样的“葡萄”
呢，过去到山上见到了这样的“葡萄”树藤绝对是见到就砍，可现在大家都只摘了葡萄
用来酿酒呢！
这样的山里“葡萄”很多人会称之为是彩色葡萄，因为他不是自家里面种植的，反而是
野生出来的，结果在没成熟的时候会有各种颜色的变化，很多时候在山里“葡萄”没熟
的时候有蓝色白色粉色，可成熟了之后就是紫色红色甚至是黑色的呢。是不是觉得这真
的是大自然的奇妙变化？
我还记得以前到山里看到了“葡萄”就会和小伙伴们一起都摘下来，别说什么颜色了，
反正摘下来就吃，有的酸有的甜有的熟了有的没有但没人在乎，那时候的想法就是有葡
萄吃就是好的了。可我那时候就怕的也就是大人上山发现，因为大人已发现就会看下他
，听大人说这葡萄藤有药用价值可以卖钱呢。
不过这次我回家却发现就算是山上大家发现了这样的“葡萄”也没有人会砍倒它反而是
跟小孩子一起摘葡萄，原来不知道从谁开始试着用这个山里的“葡萄”酿酒，酿出来的
酒没有一个人不喜欢，老少皆宜，所以这山里的“葡萄”的树藤就这么被保留了下来。

c*72013-01-25 08:01

2 楼

1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
， time O(n), space O(n)。求time O(n), constant space的解。。。

2.Given P machines, each containing an array of N elements, find the medium
of the array resulted by concatenating all the arrays on the machines. You
cannot move data across machines.

n*32013-01-25 08:01

3 楼

好不容易申请到了绿卡，现在有一个很好的工作机会需要离开美国。
我的移民律师告诉我这样我就会失去绿卡，因为我不能保证在美国每年待180天以上。
想请问下是否有朋友知道如何解决这个问题！
包子答谢

T*a2013-01-25 08:01

4 楼

就是学习nvidia的老黄。丫果断地杀了欧洲厂商，集中精力干亚洲厂商。软软买了dell
，杀了hp，全线转战亚洲。尼玛，不发达都难。

c*p2013-01-25 08:01

5 楼

第1题前面版上讨论过了
先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
再扫第二遍，对于每个Ai，
如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
如果Ai<1 或者Ai>max直接忽略。
最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1

integers
medium

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

: 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
: 2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
: ， time O(n), space O(n)。求time O(n), constant space的解。。。
:
: 2.Given P machines, each containing an array of N elements, find the medium
: of the array resulted by concatenating all the arrays on the machines. You
: cannot move data across machines.

u*s2013-01-25 08:01

6 楼

如果是公司外派，公司会帮助处理的。你在海外的时间仍旧算你在美国国内时间，好像
每年要回来一趟，一点不影响将来的公民申请（如果愿意的话）。

T*a2013-01-25 08:01

7 楼

尼玛这样一来，软工们都得遣返天朝了。

c*p2013-01-25 08:01

8 楼

大体思路如此，可能有问题没有考虑到。

1

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

: 第1题前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium

z*m2013-01-25 08:01

9 楼

http://blog.wenxuecity.com/blogview.php?date=200709&postID=3149

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

: 好不容易申请到了绿卡，现在有一个很好的工作机会需要离开美国。
: 我的移民律师告诉我这样我就会失去绿卡，因为我不能保证在美国每年待180天以上。
: 想请问下是否有朋友知道如何解决这个问题！
: 包子答谢

g*t2013-01-25 08:01

10 楼

把msn关了，你还指望软软能干什么？
除了改名字， ms这几年什么都没干，

D*g2013-01-25 08:01

11 楼

第二题
１．每台机器sort array, NlgN
2. Maintain一个size为P的min-heap，heap的每个元素是1中每个array当前最小元素
的值和array的id (1 -- p )，以及指向对应array首部的pointer，heap里的元素是按
照array当前最小元素排列的。
3. 对heap的根，increment 对应array的pointer.然后update heap。重复直道找到Ｎ*
P/2个元素为止。

integers
medium

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

: 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
: 2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
: ， time O(n), space O(n)。求time O(n), constant space的解。。。
:
: 2.Given P machines, each containing an array of N elements, find the medium
: of the array resulted by concatenating all the arrays on the machines. You
: cannot move data across machines.

n*32013-01-25 08:01

12 楼

谢谢各位了！
其实担心的不是公民，我们是打算待3-4年回美国的，小孩那时也要上学了，就是怕绿
卡被取消了。

a*a2013-01-25 08:01

13 楼

感觉第二题思路跟external sort思路大同小异。

integers
medium

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

: 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
: 2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
: ， time O(n), space O(n)。求time O(n), constant space的解。。。
:
: 2.Given P machines, each containing an array of N elements, find the medium
: of the array resulted by concatenating all the arrays on the machines. You
: cannot move data across machines.

a*a2013-01-25 08:01

14 楼

这个方法也不一定省space？
temp array长度大概也跟O(n)差不多了，如果基本都是正数

1

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

: 第1题前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium

s*n2013-01-25 08:01

15 楼

不用记min, negative之类的东西。直接扫描把1放到位置1(A[0])，2放到位置2，<=0不
处理。
for (int i=0; iwhile (A[i]>0 && A[i]！=i+1 && A[i]<=A.length) {
int tmp = A[A[i]-1] ;
A[A[i]-1] = A[i];
A[i] = tmp;
}
}
for (int i=0; iif (A[i]!=i+1) {
printf("%d\n", i+1);
break;
}
}

1

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

: 第1题前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium

s*n2013-01-25 08:01

16 楼

第二题，就是搞2个Heap来实现。
Heap1：MaxHeap, Heap2：MinHeap，保持Heap1.size==Heap2.size或者Heap1.size==
Heap2.size+1
void addNum(int num) {
if (Heap1.size==Heap2.size+1) {
if (num<=Heap1.maxValue()) {
int heap1MaxValue = Heap1.pop();
Heap2.add(heap1MaxValue);
Heap1.add(num);
} else Heap2.add(num);
} else {
if (num>=Heap2.MinValue()) {
int heap2MinValue = Heap2.pop();
Heap1.add(heap2MinValue);
Heap2.add(num);
} else Heap1.add(num);
}
}
多个机器的问题：从每个机器读一个block过来，效率比较好

c*p2013-01-25 08:01

17 楼

inplace

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

: 这个方法也不一定省space？
: temp array长度大概也跟O(n)差不多了，如果基本都是正数
:
: 1

c*p2013-01-25 08:01

18 楼

min算是小优化。。n_positve起到相当于a.length、防止越界的作用。
更深的小优化还有：先令max = n_positive，每发现一个大于max的数，都忽略之并令m
ax--，
只是这样做可能会漏数，所以就没在原帖里写。【在 swanswan (swan) 的大作中提到

a*g2013-01-25 08:01

19 楼

为什么需要第一遍？

1

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

: 第1题前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium

s*n2013-01-25 08:01

20 楼

一次扫描就够了，小于等于0或者大于a.length的数字直接无视，[1,a.length]之间的
数字搬位置就行了。然后从头找第一个A[i]!=i+1

令m

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

: min算是小优化。。n_positve起到相当于a.length、防止越界的作用。
: 更深的小优化还有：先令max = n_positive，每发现一个大于max的数，都忽略之并令m
: ax--，
: 只是这样做可能会漏数，所以就没在原帖里写。【在 swanswan (swan) 的大作中提到

p*n2013-01-25 08:01

21 楼

这个还要考虑A数组中可能含相同的数吧

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

: 不用记min, negative之类的东西。直接扫描把1放到位置1(A[0])，2放到位置2，<=0不
: 处理。
: for (int i=0; i: while (A[i]>0 && A[i]！=i+1 && A[i]<=A.length) {
: int tmp = A[A[i]-1] ;
: A[A[i]-1] = A[i];
: A[i] = tmp;
: }
: }
: for (int i=0; i

s*o2013-01-25 08:01

22 楼

try A = {1, 1}
it will end up with an infinite loop
You need to change the condition to:
while (A[i]>0 && A[A[i]-1]!=A[i] && A[i]<=A.length)

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

: 不用记min, negative之类的东西。直接扫描把1放到位置1(A[0])，2放到位置2，<=0不
: 处理。
: for (int i=0; i: while (A[i]>0 && A[i]！=i+1 && A[i]<=A.length) {
: int tmp = A[A[i]-1] ;
: A[A[i]-1] = A[i];
: A[i] = tmp;
: }
: }
: for (int i=0; i

s*r2013-01-25 08:01

23 楼

这个时间复杂度是多少？ O（n）？
但是每个while循环可能执行很多次啊

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

: try A = {1, 1}
: it will end up with an infinite loop
: You need to change the condition to:
: while (A[i]>0 && A[A[i]-1]!=A[i] && A[i]<=A.length)