G家面经 - 未名空间MITBBS历史存档

b*o2012-08-23 07:08

1 楼

又Fail了，已经是连续两年了
1 An array with n elements which is K most sorted. 就是每个element的初始位置
和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
than O(n*lgn)
2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
paint 上需要的颜色
3 又一个排序好的不知道长度的数组，在其中search 一个给定值
4 1..n 这些数有两个missing,find out which two are missing.

p*e2012-08-23 07:08

2 楼

试着答一下：
1） nlgK: sort first k elements first, then determine elements one after
another
2) ???
3) lgn, pretty easy
4) O(n), use bit array, space can be O(n)/32

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

d*e2012-08-23 07:08

3 楼

请问这是onsite还是电面？
我电面只够时间问code一个问题。。。然后悲剧地要第二次电面，本来说只有一轮的

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

w*x2012-08-23 07:08

4 楼

1. k size min heap
2. 老题了, 好像不需要辅助矩阵, 递归就可以了
3. 1, 2, 4, 8, 16 ...找到下界, 然后二分
4. 解方程, 我做就增加两个变量tmp1 tmp2然后归位后再扫描一遍
OnSite?????

d*e2012-08-23 07:08

5 楼

3)长度不知的是如何lg N?
我觉得是不是应该是0开始，按长度递增地去搜？
如果比A[2^i]小，就在A[2^(i-1)]和A[2^i]区间再二分搜

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

: 试着答一下：
: 1） nlgK: sort first k elements first, then determine elements one after
: another
: 2) ???
: 3) lgn, pretty easy
: 4) O(n), use bit array, space can be O(n)/32

b*d2012-08-23 07:08

6 楼

~~~~~
this one could be done smarter:
x + y = n(n+1) /2 - sum(a1...ak)
x^2 + y^2 = sum(1^2, 2^2, 3^2, ..., n^2) - sum(a1^2， a2^2, ..., ak^2)
solve these simple equation for x and y.

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

: 试着答一下：
: 1） nlgK: sort first k elements first, then determine elements one after
: another
: 2) ???
: 3) lgn, pretty easy
: 4) O(n), use bit array, space can be O(n)/32

a*o2012-08-23 07:08

7 楼

第二题到底啥意思？好像很多人问

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

d*s2012-08-23 07:08

8 楼

good one

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

:
: ~~~~~
: this one could be done smarter:
: x + y = n(n+1) /2 - sum(a1...ak)
: x^2 + y^2 = sum(1^2, 2^2, 3^2, ..., n^2) - sum(a1^2， a2^2, ..., ak^2)
: solve these simple equation for x and y.

l*a2012-08-23 07:08

9 楼

ding
seldom can we see a mianjing recently

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

s*92012-08-23 07:08

10 楼

第一题没太明白，能再解释一下么？

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

: 1. k size min heap
: 2. 老题了, 好像不需要辅助矩阵, 递归就可以了
: 3. 1, 2, 4, 8, 16 ...找到下界, 然后二分
: 4. 解方程, 我做就增加两个变量tmp1 tmp2然后归位后再扫描一遍
: OnSite?????

l*42012-08-23 07:08

11 楼

第二题是150上原题，递归就行了

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

o*u2012-08-23 07:08

12 楼

乘法时间复杂度略高
可以改成如下：
x+y = n(n+1)/2-sum(a1....ak)
x^y = 1^2^3....^n^a1^a2^a3.....^ak

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

:
: ~~~~~
: this one could be done smarter:
: x + y = n(n+1) /2 - sum(a1...ak)
: x^2 + y^2 = sum(1^2, 2^2, 3^2, ..., n^2) - sum(a1^2， a2^2, ..., ak^2)
: solve these simple equation for x and y.

k*x2012-08-23 07:08

13 楼

这个如果n比较大的话，很容易溢出的吧？

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

: 乘法时间复杂度略高
: 可以改成如下：
: x+y = n(n+1)/2-sum(a1....ak)
: x^y = 1^2^3....^n^a1^a2^a3.....^ak

s*n2012-08-23 07:08

14 楼

1. Use a min heap. First insert number a0, a1… ak into the heap. We know
that the min number (the root of the heap) must be placed in position b0. So
we remove it from the heap and place it at b0. Next, we insert number ak+1
into the heap. Again, we can see that the current min number must be placed
in position b1.
So, the time complexity is O(n lgk).

s*n2012-08-23 07:08

15 楼

2.Flood fill
http://en.wikipedia.org/wiki/Flood_fill

h*62012-08-23 07:08

16 楼

弱问下，第三题里，search的时候当n超过数组长度时，处理exception的代码怎么写比
较好？

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

p*e2012-08-23 07:08

17 楼

没看明白， sum(a1^2， a2^2, ..., ak^2)的复杂度是O(n)，而且涉及乘法
sum(a1...ak)也是O(n)
直接iterate这个array, 用n bit array记住位置，再iterate一次，就知道哪两个数
missing了

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

:
: ~~~~~
: this one could be done smarter:
: x + y = n(n+1) /2 - sum(a1...ak)
: x^2 + y^2 = sum(1^2, 2^2, 3^2, ..., n^2) - sum(a1^2， a2^2, ..., ak^2)
: solve these simple equation for x and y.

a*e2012-08-23 07:08

18 楼

我操。。。人整人。。。整死人
我老了。

i*e2012-08-23 07:08

19 楼

第一题难道不是insertion sort 吗？每个最多移动K个位置！ o（n*k) , k 为常数！

l*i2012-08-23 07:08

20 楼

problem 1 appears as an exercise in Dasgupta, Vazirani and Papadimitrious'
textbook 'algorithms' a very small book with free pdf online.

l*i2012-08-23 07:08

21 楼

From what I heard, sometimes it is not how well you perform, but the
relative ranking you got among candidates. For super strong candidates this
makes no difference, but for most people luck can play a role.

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

g*n2012-08-23 07:08

22 楼

第一题没理解意思。如果是1-10,倒序排好的话（10-1），k=5什么的，是不是就做不
到？

z*e2012-08-23 07:08

23 楼

我觉得需要一个exception处理，从上一个合理的index开始做线性搜索

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

: 弱问下，第三题里，search的时候当n超过数组长度时，处理exception的代码怎么写比
: 较好？

N*n2012-08-23 07:08

24 楼

倒序排好K怎么等于5的？

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

: 第一题没理解意思。如果是1-10,倒序排好的话（10-1），k=5什么的，是不是就做不
: 到？

N*n2012-08-23 07:08

25 楼

冒泡排序都是O(NK)，堆排序是O(NlogK)

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

: 第一题难道不是insertion sort 吗？每个最多移动K个位置！ o（n*k) , k 为常数！

N*n2012-08-23 07:08

26 楼

如果没有那么多内存呢？

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

: 没看明白， sum(a1^2， a2^2, ..., ak^2)的复杂度是O(n)，而且涉及乘法
: sum(a1...ak)也是O(n)
: 直接iterate这个array, 用n bit array记住位置，再iterate一次，就知道哪两个数
: missing了

N*n2012-08-23 07:08

27 楼

这种算法题还要处理这种exception？

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

: 弱问下，第三题里，search的时候当n超过数组长度时，处理exception的代码怎么写比
: 较好？

N*n2012-08-23 07:08

28 楼

这个不需要考虑溢出的，溢出了结果也是对的，只要低位是对的就行了，除非你说n>
INT_MAX/2，那估计就很难做了，这些数内存也存不下吧

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

: 这个如果n比较大的话，很容易溢出的吧？

g*e2012-08-23 07:08

29 楼

XOR, O(n) time O(1) space. Similar way to find two repating numbers.
final public static void find2missingInt(int[] array) {
int xor = 0;
for(int i=0; ixor ^= array[i];

//start from 1 to n, watch the upper limit
for (int i=1; i<=array.length+2; i++)
xor ^= i;

/* Get the rightmost set bit in set_bit_no */
int rightMostBit = xor & -xor;

int x = 0, y = 0;

/* Now divide elements in two sets by comparing rightmost
set
bit of xor with bit at same position in each element. */
for(int i=0; iif ((array[i] & rightMostBit)>0)
x ^= array[i];
else
y ^= array[i];
}

for (int i=1; i<=array.length+2; i++) {
if ((i & rightMostBit)>0)
x ^= i;
else
y ^= i;
}

System.out.println("Missing number: " + x + " " + y);
}

个数

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

: 如果没有那么多内存呢？

g*e2012-08-23 07:08

30 楼

另外如果能扩展数组，在最后补两个空位，然后set a[i] = a[a[i] -1]，最后扫描一
遍哪两个位置空的就是。这个方法能解决任意数字missing的情况，就是修改了数组不
能恢复了
另外一个修改（可恢复）数组方法是set array[abs(array[i])-1] = -array[abs(
array[i])-1].
这种缺几个多几个数的题都是差不多的解法，那么三四种随便弄一种就吃遍天了。

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

: XOR, O(n) time O(1) space. Similar way to find two repating numbers.
: final public static void find2missingInt(int[] array) {
: int xor = 0;
: for(int i=0; i: xor ^= array[i];
:
: //start from 1 to n, watch the upper limit
: for (int i=1; i<=array.length+2; i++)
: xor ^= i;
:

j*22012-08-23 07:08

31 楼

这个不对吧. For example, k=2, 124536. You will not see 3 after you remove 1
and 2 in the heap.
the size of heap should be 2k+1. The n-th largest number can occur b/w A[n-k
,n+k], whose size is 2k+1.

So
1
placed

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

: 1. Use a min heap. First insert number a0, a1… ak into the heap. We know
: that the min number (the root of the heap) must be placed in position b0. So
: we remove it from the heap and place it at b0. Next, we insert number ak+1
: into the heap. Again, we can see that the current min number must be placed
: in position b1.
: So, the time complexity is O(n lgk).

r*e2012-08-23 07:08

32 楼

bless LZ，再接再厉，6个月以后再试

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

: 又Fail了，已经是连续两年了
: 1 An array with n elements which is K most sorted. 就是每个element的初始位置
: 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster
: than O(n*lgn)
: 2 Paint 一块画板上的区域。从一个点出发，直到所有相邻的和出发点一样颜色的点都
: paint 上需要的颜色
: 3 又一个排序好的不知道长度的数组，在其中search 一个给定值
: 4 1..n 这些数有两个missing,find out which two are missing.

s*02012-08-23 07:08

33 楼

那位大神看看对不对？

1
-k

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

: 这个不对吧. For example, k=2, 124536. You will not see 3 after you remove 1
: and 2 in the heap.
: the size of heap should be 2k+1. The n-th largest number can occur b/w A[n-k
: ,n+k], whose size is 2k+1.
:
: So
: 1
: placed