几道面试题:memory, sort, 等 - 未名空间MITBBS历史存档

几道面试题:memory, sort, 等# Programming - 葵花宝典

h*o2007-10-05 07:10

1 楼

1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
是这个array size 较小.请问怎么sort?
2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
跟上.有人会作这题吗?或从那儿可以找到答案?
3. 如何判断是bigendian, little endian,
int i = 1;
if(*(char*)&i) return little;
else return big;
我一开始写成if((char)i) return little;他说我应用指针. 请问为何非用指针那?我
回来发现不用也对阿.

d*d2007-10-05 07:10

2 楼

2是mem pool的管理。
用一个linklist来放可用地址和可用长度。每次malloc的时候，从linklist里面取走需
要的
地址，free的时候，放回linklist就好。只要linklist还不为空，就还有可用的。
碎片的管理，让我想想

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

: 1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
: 是这个array size 较小.请问怎么sort?
: 2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
: 的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
: 较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
: 实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
: 跟上.有人会作这题吗?或从那儿可以找到答案?
: 3. 如何判断是bigendian, little endian,
: int i = 1;
: if(*(char*)&i) return little;

k*f2007-10-05 07:10

3 楼

1。radix sort
3. 当然要指针了。直接转换是不行的

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

: 1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
: 是这个array size 较小.请问怎么sort?
: 2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
: 的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
: 较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
: 实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
: 跟上.有人会作这题吗?或从那儿可以找到答案?
: 3. 如何判断是bigendian, little endian,
: int i = 1;
: if(*(char*)&i) return little;

d*d2007-10-05 07:10

4 楼

对

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

: 1。radix sort
: 3. 当然要指针了。直接转换是不行的

x*g2007-10-05 07:10

5 楼

1. size较小还O(n)个头呀。
3. 不用指针怎么可能对？

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

: 1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
: 是这个array size 较小.请问怎么sort?
: 2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
: 的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
: 较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
: 实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
: 跟上.有人会作这题吗?或从那儿可以找到答案?
: 3. 如何判断是bigendian, little endian,
: int i = 1;
: if(*(char*)&i) return little;

t*d2007-10-05 07:10

6 楼

本科生的os的project, 修改内存管理的算法，Minix。用一个链表记住每个未用片断
的大小及开始地址，malloc时根据算法选一个位置，然后更新相关的节点；free的时候
要做merge。那个加结束符太麻烦了，直接分配2^k的倍数。从哪里开始scan，你可以
另外再记录一个起点用用于下一次分配。不知道说清楚没有，需要我可以贴点source
code.

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

: 1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
: 是这个array size 较小.请问怎么sort?
: 2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
: 的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
: 较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
: 实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
: 跟上.有人会作这题吗?或从那儿可以找到答案?
: 3. 如何判断是bigendian, little endian,
: int i = 1;
: if(*(char*)&i) return little;

g*n2007-10-05 07:10

7 楼

union {
int x;
char c[sizeof(int)];
} u;
u.x=1;
if (u.c[0] != 0) {
big endian;
} else {
little endian;
}

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

: 1. size较小还O(n)个头呀。
: 3. 不用指针怎么可能对？

h*o2007-10-05 07:10

8 楼

谢谢各位。我原来不是学cs的,所以基础较差.
1. 那个加结束符太麻烦了，直接分配2^k的倍数。从哪里开始scan，你可以
2. 为什么非要指针那?我不用指针也得到正确答案了.不就是typecast 吗? 把int变成
char 那int中有两个Byte 就丢了, 不是挺对的吗.

j*e2007-10-05 07:10

9 楼

成
When you typecast int to char, the least significant byte is used for the
char regardless of the Endian.

a*l2007-10-05 07:10

10 楼

I think 1 is totally BS. The theoratical minimum of sorting is O(nlogn), so
there is no O(n) sorting algorithm at all, unless you are not trully sorting
a "random" array,i.e., there is something unique about the array. And, O()
notation only matters when you have large data set.

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

: 1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
: 是这个array size 较小.请问怎么sort?
: 2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
: 的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
: 较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
: 实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
: 跟上.有人会作这题吗?或从那儿可以找到答案?
: 3. 如何判断是bigendian, little endian,
: int i = 1;
: if(*(char*)&i) return little;

c*t2007-10-05 07:10

11 楼

Go read radix sort on wikipedia. O(nlogn) is the theoretical minimum
when only considering comparison operators. Radix sort works on integers
because of use of additional properties of integers.

so
sorting
()

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

: I think 1 is totally BS. The theoratical minimum of sorting is O(nlogn), so
: there is no O(n) sorting algorithm at all, unless you are not trully sorting
: a "random" array,i.e., there is something unique about the array. And, O()
: notation only matters when you have large data set.

s*u2007-10-05 07:10

12 楼

radix sort is not O(n) even for integers, TONGXUE.
some condition have to be met.

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

: Go read radix sort on wikipedia. O(nlogn) is the theoretical minimum
: when only considering comparison operators. Radix sort works on integers
: because of use of additional properties of integers.
:
: so
: sorting
: ()

X*r2007-10-05 07:10

13 楼

As long as the integers are in a predefined range, i.e. limited in their
length,
which is true for most practical cases, radix sort is O(n)

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

: radix sort is not O(n) even for integers, TONGXUE.
: some condition have to be met.

s*u2007-10-05 07:10

14 楼

ya, as long as
which is true for most practical cases, 2^100 is big enough, quicksort is O(
100n)=O(n)

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

: As long as the integers are in a predefined range, i.e. limited in their
: length,
: which is true for most practical cases, radix sort is O(n)

c*t2007-10-05 07:10

15 楼

100n is not even remotely close for large set of numbers. Worst
case for quick-sort is O(n^2). I thought you want to get technical :)

O(

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

: ya, as long as
: which is true for most practical cases, 2^100 is big enough, quicksort is O(
: 100n)=O(n)

s*u2007-10-05 07:10

16 楼

我敢保证quicksort可以做到O(nlogn)，只是不考虑coding的痛苦程度

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

: 100n is not even remotely close for large set of numbers. Worst
: case for quick-sort is O(n^2). I thought you want to get technical :)
:
: O(

s*u2007-10-05 07:10

17 楼

而且其实也不是很痛苦

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

: 我敢保证quicksort可以做到O(nlogn)，只是不考虑coding的痛苦程度

c*t2007-10-05 07:10

18 楼

可以做到算是 best case 还是 worse case 还是 average case ？
I can write an O (n) algorithm for any problems in the best
case ^_^

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

: 我敢保证quicksort可以做到O(nlogn)，只是不考虑coding的痛苦程度

s*u2007-10-05 07:10

19 楼

worst
其实就是根据nth_element可以O(n)

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

: 可以做到算是 best case 还是 worse case 还是 average case ？
: I can write an O (n) algorithm for any problems in the best
: case ^_^

c*t2007-10-05 07:10

20 楼

回去复习一下 quicksort 的定义吧。你可以弄个 O (nlogn）不错，但是
那不一定是 quicksort 。不要指着 merge sort 或者 merge sort 的变种
说是 quicksort 。

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

: worst
: 其实就是根据nth_element可以O(n)

s*u2007-10-05 07:10

21 楼

-_-

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

: 回去复习一下 quicksort 的定义吧。你可以弄个 O (nlogn）不错，但是
: 那不一定是 quicksort 。不要指着 merge sort 或者 merge sort 的变种
: 说是 quicksort 。

s*u2007-10-05 07:10

22 楼

算了，不跟你说了 -.-

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

: 回去复习一下 quicksort 的定义吧。你可以弄个 O (nlogn）不错，但是
: 那不一定是 quicksort 。不要指着 merge sort 或者 merge sort 的变种
: 说是 quicksort 。

P*f2007-10-05 07:10

23 楼

nth_element 一般实现是hoare select,average O(n).
这个和sort还不一样，partial_sort比这个就慢了
如果你是指worst case linear selection,其常系数也是相当的大。
radix O(n)没有问题，其实就是不是in place而已。
quick sort一般的角度来讲,average nlogn, worst n^2 也是没错的。
尽管你可以做些randomize,median of three之类的优化。

worst
其实就是根据nth_element可以O(n)

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

: worst
: 其实就是根据nth_element可以O(n)

s*u2007-10-05 07:10

24 楼

nth_element不是average O(n)，是worst O(n)

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

: nth_element 一般实现是hoare select,average O(n).
: 这个和sort还不一样，partial_sort比这个就慢了
: 如果你是指worst case linear selection,其常系数也是相当的大。
: radix O(n)没有问题，其实就是不是in place而已。
: quick sort一般的角度来讲,average nlogn, worst n^2 也是没错的。
: 尽管你可以做些randomize,median of three之类的优化。
:
: worst
: 其实就是根据nth_element可以O(n)

P*f2007-10-05 07:10

25 楼

哪个实现的文挡这样说的？sgi? vc++?

nth_element不是average O(n)，是worst O(n)

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

: nth_element不是average O(n)，是worst O(n)

s*u2007-10-05 07:10

26 楼

所以我就是说可以啊，没事谁那样写啊，一个sort就完了 -_-

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

: nth_element 一般实现是hoare select,average O(n).
: 这个和sort还不一样，partial_sort比这个就慢了
: 如果你是指worst case linear selection,其常系数也是相当的大。
: radix O(n)没有问题，其实就是不是in place而已。
: quick sort一般的角度来讲,average nlogn, worst n^2 也是没错的。
: 尽管你可以做些randomize,median of three之类的优化。
:
: worst
: 其实就是根据nth_element可以O(n)

s*u2007-10-05 07:10

27 楼

我说的 -_-
n + n/2 + n/4 + ... + n/(2^log(n)) = O(2n)

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

: 哪个实现的文挡这样说的？sgi? vc++?
:
: nth_element不是average O(n)，是worst O(n)

P*f2007-10-05 07:10

28 楼

你说的不算:)不要想当然

我说的 -_-
n + n/2 + n/4 + ... + n/(2^log(n)) = O(2n)

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

: 我说的 -_-
: n + n/2 + n/4 + ... + n/(2^log(n)) = O(2n)

s*u2007-10-05 07:10

29 楼

怎么看都是2n啊，不过到处都说是平均 -_-

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

: 你说的不算:)不要想当然
:
: 我说的 -_-
: n + n/2 + n/4 + ... + n/(2^log(n)) = O(2n)

q*c2007-10-05 07:10

30 楼

Bucket sort, for sure. he he

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

: 1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
: 是这个array size 较小.请问怎么sort?
: 2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
: 的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
: 较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
: 实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
: 跟上.有人会作这题吗?或从那儿可以找到答案?
: 3. 如何判断是bigendian, little endian,
: int i = 1;
: if(*(char*)&i) return little;

s*u2007-10-05 07:10

31 楼

寒，我错了，原来有个方向可以等于，可能分不balance...

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

: 怎么看都是2n啊，不过到处都说是平均 -_-

a*l2007-10-05 07:10

32 楼

right, what if the numbers are floats? still use radix sort? so there is
some "uniqueness" of the data, right?

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

: Go read radix sort on wikipedia. O(nlogn) is the theoretical minimum
: when only considering comparison operators. Radix sort works on integers
: because of use of additional properties of integers.
:
: so
: sorting
: ()

s*u2007-10-05 07:10

33 楼

终于找到了，introduction to algorithm 9.3，虽然bt了点，但是nth_element还是可
以O(n)
所以quicksort就可以O(nlogn)，也不知道前面讲sorting的就咬定worst是n方

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

: 寒，我错了，原来有个方向可以等于，可能分不balance...

P*f2007-10-05 07:10

34 楼

这就是我说的worst cast linear selection, 但nth_element算法所有实现没有用这个的
1. 方法复杂不值得 2. 常数系数很大.
所以我说一般说quick sort worst case (n^2) 是可以的

终于找到了，introduction to algorithm 9.3，虽然bt了点，但是nth_element还是可
以O(n)
所以quicksort就可以O(nlogn)，也不知道前面讲sorting的就咬定worst是n方

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

: 终于找到了，introduction to algorithm 9.3，虽然bt了点，但是nth_element还是可
: 以O(n)
: 所以quicksort就可以O(nlogn)，也不知道前面讲sorting的就咬定worst是n方

s*u2007-10-05 07:10

35 楼

反正还是存在，ms很多都是这样的，虽然灭有人会用

个的

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

: 这就是我说的worst cast linear selection, 但nth_element算法所有实现没有用这个的
: 1. 方法复杂不值得 2. 常数系数很大.
: 所以我说一般说quick sort worst case (n^2) 是可以的
:
: 终于找到了，introduction to algorithm 9.3，虽然bt了点，但是nth_element还是可
: 以O(n)
: 所以quicksort就可以O(nlogn)，也不知道前面讲sorting的就咬定worst是n方

t*t2007-10-05 07:10

36 楼

你这就接近于胡搅蛮缠了
通常的说法, quicksort 平均O(nlogn),最差O(n^2), radix是O(n), hash也是O(n)
如果要谈细节,都可以找出毛病来
quicksort worse case O(nlogn)?可以啊,加一个大常数你干不干
radix, 样本空间很大怎么办
hash, 找不到好的函数怎么办

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

: 终于找到了，introduction to algorithm 9.3，虽然bt了点，但是nth_element还是可
: 以O(n)
: 所以quicksort就可以O(nlogn)，也不知道前面讲sorting的就咬定worst是n方

s*u2007-10-05 07:10

37 楼

是啊，其实每次被问起这些，我都很别扭，总感觉在自己骗自己
突然觉得人生怎么这么空虚无趣呢，唉

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

: 你这就接近于胡搅蛮缠了
: 通常的说法, quicksort 平均O(nlogn),最差O(n^2), radix是O(n), hash也是O(n)
: 如果要谈细节,都可以找出毛病来
: quicksort worse case O(nlogn)?可以啊,加一个大常数你干不干
: radix, 样本空间很大怎么办
: hash, 找不到好的函数怎么办

c*x2007-10-05 07:10

38 楼

1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
是这个array size 较小.请问怎么sort?
buble sort, o(n) - o(n2)
2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
跟上.有人会作这题吗?或从那儿可以找到答案?
you need to build a table to maintain all the pointer and the size
of block.
3. 如何判断是bigendian, little endian,
int i = 1;
if(*(char*)&i) ret

z*y2007-10-05 07:10

39 楼

stty is used to read and modify the devices's driver program for user!

z*y2007-10-05 07:10

40 楼

stty is used to read and modify the devices' driver program's settings for
user!

y*e2007-10-05 07:10

41 楼

1 用 counting sort 吧

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

: 1.给一个array with random numbers, how to efficiently sort it with O(n)? 说
: 是这个array size 较小.请问怎么sort?
: 2.给定一个64kB buffer及其头指针, 要在里面实现类似malloc(size), free(ptr)之类
: 的function., 而且只有连续未用空间>size, 才能 malloc(size).他说用linklist实现
: 较好.还说malloc完要加一个结束符,这样 free时能知道赋值时有无溢出.他还问我如何
: 实现这个linklist使得不用每次malloc 前都去从头scan有无空位. 他说的挺快的,我没
: 跟上.有人会作这题吗?或从那儿可以找到答案?
: 3. 如何判断是bigendian, little endian,
: int i = 1;
: if(*(char*)&i) return little;

f*y2007-10-05 07:10

42 楼

wrong.
u.c[0] != 0 should return little endian.

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

: union {
: int x;
: char c[sizeof(int)];
: } u;
: u.x=1;
: if (u.c[0] != 0) {
: big endian;
: } else {
: little endian;
: }

P*e2007-10-05 07:10

43 楼

其实本质上就是radix sort, by least significant bit
0 1 2 3 4 5 6 7 8 9
same as ten bucket

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

:
: Bucket sort, for sure. he he