A电面题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

A电面题

A电面题# JobHunting - 待字闺中

l*n2013-01-30 08:01

1 楼

寒暄，介绍下project。
1. 合并interval (leetcode)
2. 给一个部分排好序的序列。保证每个elem在k范围内能找到自己正确的位置。比如
说a[i]它在完全排序的序列中应处的位置j，满足 abs(i-j) <= k的。怎样把序列完全
排序？
implement sort(a, k)，代价？

d*e2013-01-30 08:01

2 楼

这个是 nearly sorted problem，用堆可以做。O(NlgK) run time, O(K) space.

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

: 寒暄，介绍下project。
: 1. 合并interval (leetcode)
: 2. 给一个部分排好序的序列。保证每个elem在k范围内能找到自己正确的位置。比如
: 说a[i]它在完全排序的序列中应处的位置j，满足 abs(i-j) <= k的。怎样把序列完全
: 排序？
: implement sort(a, k)，代价？

H*s2013-01-30 08:01

3 楼

这题不用堆也行吧，就是每 2K 个一组排序，一共分成N/K 组,总的时间 O(N/K * 2K
log(2K)) = O(NlgK)

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

:
: 这个是 nearly sorted problem，用堆可以做。O(NlgK) run time, O(K) space.

l*b2013-01-30 08:01

4 楼

嗯,CLRS上一个习题. 开始我也是这样想的. 这两个算法差不多吧, heap里每个元素一
进一出,基本上每个元素处理两遍. 这个办法也大约是每个元素处理两遍.

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

: 这题不用堆也行吧，就是每 2K 个一组排序，一共分成N/K 组,总的时间 O(N/K * 2K
: log(2K)) = O(NlgK)

H*s2013-01-30 08:01

5 楼

你还记得这是个习题啊，不错！我是彻底忘了在哪见过了。

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

: 嗯,CLRS上一个习题. 开始我也是这样想的. 这两个算法差不多吧, heap里每个元素一
: 进一出,基本上每个元素处理两遍. 这个办法也大约是每个元素处理两遍.

d*x2013-01-30 08:01

6 楼

多半是order statistics，或者是augmented datastructures

素一

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

: 你还记得这是个习题啊，不错！我是彻底忘了在哪见过了。

f*m2013-01-30 08:01

7 楼

这样划分：
A[0]~A[k-1]一组，A[k]~A[2k-1]一组？

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

: 这题不用堆也行吧，就是每 2K 个一组排序，一共分成N/K 组,总的时间 O(N/K * 2K
: log(2K)) = O(NlgK)

d*g2013-01-30 08:01

8 楼

两个题都要写程序？45分钟很吃力啊。。。还要边说边写~

H*s2013-01-30 08:01

9 楼

A[0]~A[2k-1], A[k]~A[3k-1], ...

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

: 这样划分：
: A[0]~A[k-1]一组，A[k]~A[2k-1]一组？

p*22013-01-30 08:01

10 楼

这样搞的话还需要实现一个快排吗？

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

: A[0]~A[2k-1], A[k]~A[3k-1], ...

b*m2013-01-30 08:01

11 楼

现在再去面试一定挂。感觉这些题都不会做。

l*a2013-01-30 08:01

12 楼

这个是另类A店面
绝大多数 A店面比这个简单的多

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

: 现在再去面试一定挂。感觉这些题都不会做。

b*m2013-01-30 08:01

13 楼

Onsite来这么一道也吃不消呀。

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

: 这个是另类A店面
: 绝大多数 A店面比这个简单的多

l*b2013-01-30 08:01

14 楼

上个月还在读... 现在也放在手边,呵呵,后面半本还没念...
奇怪,可能记错了, 找了一圈没找到...
http://ocw.mit.edu/courses/electrical-engineering-and-computer-
应该不在书上, 上面的problem 2-2

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

: 你还记得这是个习题啊，不错！我是彻底忘了在哪见过了。

l*a2013-01-30 08:01

15 楼

那就看运气了

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

:
: Onsite来这么一道也吃不消呀。

H*s2013-01-30 08:01

16 楼

恩，是需要的

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

:
: 这样搞的话还需要实现一个快排吗？

H*s2013-01-30 08:01

17 楼

赞你这研究精神, 被你找到出处了

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

: 上个月还在读... 现在也放在手边,呵呵,后面半本还没念...
: 奇怪,可能记错了, 找了一圈没找到...
: http://ocw.mit.edu/courses/electrical-engineering-and-computer-
: 应该不在书上, 上面的problem 2-2

p*22013-01-30 08:01

18 楼

所以写起来也比较麻烦。

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

: 恩，是需要的

l*n2013-01-30 08:01

19 楼

H*s2013-01-30 08:01

20 楼

这题不用堆也行吧，就是每 2K 个一组排序，一共分成N/K 组,总的时间 O(N/K * 2K
log(2K)) = O(NlgK)

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

:
: 这个是 nearly sorted problem，用堆可以做。O(NlgK) run time, O(K) space.

l*b2013-01-30 08:01

21 楼

: 这题不用堆也行吧，就是每 2K 个一组排序，一共分成N/K 组,总的时间 O(N/K * 2K
: log(2K)) = O(NlgK)

H*s2013-01-30 08:01

22 楼

你还记得这是个习题啊，不错！我是彻底忘了在哪见过了。

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

d*x2013-01-30 08:01

23 楼

多半是order statistics，或者是augmented datastructures

素一

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

: 你还记得这是个习题啊，不错！我是彻底忘了在哪见过了。

f*m2013-01-30 08:01

24 楼

这样划分：
A[0]~A[k-1]一组，A[k]~A[2k-1]一组？

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

: 这题不用堆也行吧，就是每 2K 个一组排序，一共分成N/K 组,总的时间 O(N/K * 2K
: log(2K)) = O(NlgK)

d*g2013-01-30 08:01

25 楼

两个题都要写程序？45分钟很吃力啊。。。还要边说边写~

H*s2013-01-30 08:01

26 楼

A[0]~A[2k-1], A[k]~A[3k-1], ...

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

: 这样划分：
: A[0]~A[k-1]一组，A[k]~A[2k-1]一组？

p*22013-01-30 08:01

27 楼

这样搞的话还需要实现一个快排吗？

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

: A[0]~A[2k-1], A[k]~A[3k-1], ...

b*m2013-01-30 08:01

28 楼

现在再去面试一定挂。感觉这些题都不会做。

l*a2013-01-30 08:01

29 楼

这个是另类A店面
绝大多数 A店面比这个简单的多

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

: 现在再去面试一定挂。感觉这些题都不会做。

b*m2013-01-30 08:01

30 楼

Onsite来这么一道也吃不消呀。

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

: 这个是另类A店面
: 绝大多数 A店面比这个简单的多

l*b2013-01-30 08:01

31 楼

: 你还记得这是个习题啊，不错！我是彻底忘了在哪见过了。

l*a2013-01-30 08:01

32 楼

那就看运气了

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

:
: Onsite来这么一道也吃不消呀。

H*s2013-01-30 08:01

33 楼

恩，是需要的

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

:
: 这样搞的话还需要实现一个快排吗？

H*s2013-01-30 08:01

34 楼

赞你这研究精神, 被你找到出处了

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

p*22013-01-30 08:01

35 楼

所以写起来也比较麻烦。

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

: 恩，是需要的

b*g2013-01-30 08:01

36 楼

Page 207, very similar to Problem 8-5
We can prove that a[i] <= a[i + 2k + 1]
Thus this problem can be transformed to the problem of merging 2k + 1 sorted
lists:
a[0], a[2k + 1], ...
a[1], a[2k + 2], ...
...
a[2k], a[4k + 1], ...
https://www.dropbox.com/s/ctl3r4b4o4i5w0u/Introduction%20to%20Algorithms%20%
283nd%20Edition%29.pdf

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

: 你还记得这是个习题啊，不错！我是彻底忘了在哪见过了。

n*52013-01-30 08:01

37 楼

http://stackoverflow.com/questions/2726785/interview-q-sorting-

n*w2013-01-30 08:01

38 楼

要是不用实现sort本身，面试这样写应该最简单啊。
sortK(arr, k):
start = 0
n = len(arr)
while start < n-k:
sort(arr, start, min(n, start+2*k)-1) #sort start到start+2k-1 in
place
start += k

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

: 这题不用堆也行吧，就是每 2K 个一组排序，一共分成N/K 组,总的时间 O(N/K * 2K
: log(2K)) = O(NlgK)