又一道面试题，我是不是想多了？ - 未名空间MITBBS历史存档

又一道面试题，我是不是想多了？# Programming - 葵花宝典

h*o2007-09-12 07:09

1 楼

Question: Given the following prototype:
int compact(int * p, int size);
Write a function that will take a sorted array, possibly with duplicates,
and compact the array, returning the new length of the array. That is, if p
points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function
returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 6
returned.
我觉得要分情况如果min(p)和max(p)差距小，就用设标注位的方法。
如果min(p)和max(p)差距大，size小，就用hash的方法。对吗？
用hash怎么做那？

t*t2007-09-12 07:09

2 楼

你说得很对，你想太多了。

p
function
6

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

: Question: Given the following prototype:
: int compact(int * p, int size);
: Write a function that will take a sorted array, possibly with duplicates,
: and compact the array, returning the new length of the array. That is, if p
: points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function
: returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 6
: returned.
: 我觉得要分情况如果min(p)和max(p)差距小，就用设标注位的方法。
: 如果min(p)和max(p)差距大，size小，就用hash的方法。对吗？
: 用hash怎么做那？

s*u2007-09-12 07:09

3 楼

都排好序拉，一个个抽出来就好拉，为什么hash啊

p
function
6

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

: Question: Given the following prototype:
: int compact(int * p, int size);
: Write a function that will take a sorted array, possibly with duplicates,
: and compact the array, returning the new length of the array. That is, if p
: points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function
: returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 6
: returned.
: 我觉得要分情况如果min(p)和max(p)差距小，就用设标注位的方法。
: 如果min(p)和max(p)差距大，size小，就用hash的方法。对吗？
: 用hash怎么做那？

F*n2007-09-12 07:09

4 楼

问一下,如果array size不知道该怎么做?

s*u2007-09-12 07:09

5 楼

没法做

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

: 问一下,如果array size不知道该怎么做?

F*n2007-09-12 07:09

6 楼

上次微软面试偶的时候问到这题了, 我问他size是否知道,他说no
结果我没做出来.
不过我觉得他也不是很懂
发信人: skatou (skatou), 信区: Programming
标题: Re: 又一道面试题，我是不是想多了？
发信站: BBS 未名空间站 (Wed Sep 12 10:21:00 2007), 转信
没法做

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

: 问一下,如果array size不知道该怎么做?

a*f2007-09-12 07:09

7 楼

估计面试官以为你在问resulting array的size，所以他说不知道。

h*o2007-09-12 07:09

8 楼

那时不是还要把*p的最后几位没用的销掉，还是就让他去？

p
function
6

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

: Question: Given the following prototype:
: int compact(int * p, int size);
: Write a function that will take a sorted array, possibly with duplicates,
: and compact the array, returning the new length of the array. That is, if p
: points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function
: returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 6
: returned.
: 我觉得要分情况如果min(p)和max(p)差距小，就用设标注位的方法。
: 如果min(p)和max(p)差距大，size小，就用hash的方法。对吗？
: 用hash怎么做那？

b*n2007-09-12 07:09

9 楼

sizeof(p)/sizeof(*p)不就是int array的size吗

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

: 没法做

k*f2007-09-12 07:09

10 楼

@@@
看你的p是怎么定义了

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

: sizeof(p)/sizeof(*p)不就是int array的size吗

b*n2007-09-12 07:09

11 楼

呵呵

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

: @@@
: 看你的p是怎么定义了

s*u2007-09-12 07:09

12 楼

作为参数传进去的sizeof(p)是指针size

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

: sizeof(p)/sizeof(*p)不就是int array的size吗

L*r2007-09-12 07:09

13 楼

msize

N*n2007-09-12 07:09

14 楼

俩指针，一个永远向前，另一个只有第一个指针遇到不同值时才向前并纪录。
一趟遍历不就完了。

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

: Question: Given the following prototype:
: int compact(int * p, int size);
: Write a function that will take a sorted array, possibly with duplicates,
: and compact the array, returning the new length of the array. That is, if p
: points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function
: returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 6
: returned.
: 我觉得要分情况如果min(p)和max(p)差距小，就用设标注位的方法。
: 如果min(p)和max(p)差距大，size小，就用hash的方法。对吗？
: 用hash怎么做那？