问一道刚面试完的algorithm 的题，面试官非要最优解，我想不出来啊 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道刚面试完的algorithm 的题，面试官非要最优解，我想不出来啊

问一道刚面试完的algorithm 的题，面试官非要最优解，我想不出来啊# JobHunting - 待字闺中

l*i2015-12-23 08:12

1 楼

Q：Give a array of integers, remove all the duplicate.
我首先说sort array，然后比较当前和next，如果一样，就in place override当前，
最后array 就shrink到没有duplicate的了。面试官说sort too expensive.
接着，我说用map，如果insert过了，就 remove，他说hash expensive。
接着，我说用set，当insert int 到set 里有conflict stl会catch到，然后in place
override duplicate，面试官说set 还是用的hash，expensive，有可能collision，
hash不一定O（1）time complexity.
好像面试官一定要求不能extra time cost, space没有明确限制。
请问板上大神怎么破？
接下来，他又说，假如给你的array里面都是string呢？又怎么解？

N*D2015-12-23 08:12

2 楼

用trie便宜点？

e*22015-12-23 08:12

3 楼

应该和range有关。

place

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

: Q：Give a array of integers, remove all the duplicate.
: 我首先说sort array，然后比较当前和next，如果一样，就in place override当前，
: 最后array 就shrink到没有duplicate的了。面试官说sort too expensive.
: 接着，我说用map，如果insert过了，就 remove，他说hash expensive。
: 接着，我说用set，当insert int 到set 里有conflict stl会catch到，然后in place
: override duplicate，面试官说set 还是用的hash，expensive，有可能collision，
: hash不一定O（1）time complexity.
: 好像面试官一定要求不能extra time cost, space没有明确限制。
: 请问板上大神怎么破？
: 接下来，他又说，假如给你的array里面都是string呢？又怎么解？

d*b2015-12-23 08:12

4 楼

问问整数的范围，然后直接打表

f*h2015-12-23 08:12

5 楼

很模糊的问题啊，我也是这么想的，先问一下整数的范围，如果有一个最大值，然后看
能否用counting sort来解决？如果memory有限，也可以考虑用bit vector来解决（1
bit表示1 integer).

U*A2015-12-23 08:12

6 楼

难道用bitmap？

f*e2015-12-23 08:12

7 楼

是给 1 2 1 输出是2吗,还是输出是 1 2

place

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

n*g2015-12-23 08:12

8 楼

LRU cache?

T*u2015-12-23 08:12

9 楼

list?

b*g2015-12-23 08:12

10 楼

hash table 吧！
(1) check the hash table to see if the current element is exist, if true,
remove, else keep and insert this to hash table.
(2) move to the next element, do (1) until end

r*g2015-12-23 08:12

11 楼

mark

a*h2015-12-23 08:12

12 楼

同意，好像是tree吧

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

: 用trie便宜点？

j*x2015-12-23 08:12

13 楼

这面试官没好好准备题目
临时瞎问
相信我
因为我经常瞎问

l*82015-12-23 08:12

14 楼

hash的话O(n)time，我不知道什么样的算法可以不用看遍n个数，就把重复的删掉，除
非这个数列有特别的性质。如果看遍的话就是O(n)
至于说hash有冲突的情况，这个比较极端，一般都认为hash是O(1)的。
总不至于说要heap吧，那个是O(nlogn), 和sorting一样，不知道是不是比sorting会快
一点，比hash的好处是不会冲突就是了。heap sorting也是一种sorting。
哪个公司呀？

place

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

l*82015-12-23 08:12

15 楼

string的话，直接hash应该比trie快才对。trie　可以用来查找开头部分重合的
string。

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

: 用trie便宜点？

f*s2015-12-23 08:12

16 楼

hash的average running time是O(n)。只需要维持n格的hash table，expected
collision机会是1/n，expected table looking time是constant的，那样查找删除每
一个数的expected time是constant的。最终expected running time就是数组的长度

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

: hash的话O(n)time，我不知道什么样的算法可以不用看遍n个数，就把重复的删掉，除
: 非这个数列有特别的性质。如果看遍的话就是O(n)
: 至于说hash有冲突的情况，这个比较极端，一般都认为hash是O(1)的。
: 总不至于说要heap吧，那个是O(nlogn), 和sorting一样，不知道是不是比sorting会快
: 一点，比hash的好处是不会冲突就是了。heap sorting也是一种sorting。
: 哪个公司呀？
:
: place

f*s2015-12-23 08:12

17 楼

l*i2015-12-23 08:12

18 楼

谢谢你的回复，面试官一直说hash有collision，不一定是O（1）的lookup. 是非flg的
一个软件公司，现在还不太方便透露，等最后上完整面经的时候再说吧，希望理解。

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

: string的话，直接hash应该比trie快才对。trie　可以用来查找开头部分重合的
: string。

l*i2015-12-23 08:12

19 楼

how?

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

: 同意，好像是tree吧

l*i2015-12-23 08:12

20 楼

恩，感觉你说的是对的。我当时应该就这样跟他说。

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

: hash的average running time是O(n)。只需要维持n格的hash table，expected
: collision机会是1/n，expected table looking time是constant的，那样查找删除每
: 一个数的expected time是constant的。最终expected running time就是数组的长度

a*r2015-12-23 08:12

21 楼

这个问题的关键是要有足够的clarification. 根据具体的问题再考虑用哪种方法。比
如如果都是一定范围的整数，那么counting就够了。对于复杂的情况，你可以用hash或
者tree，但要说清楚为什么要用。

t*r2015-12-23 08:12

22 楼

single pass找RANGE也不影响RUNTIME，反正最低要O(N)

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

: 很模糊的问题啊，我也是这么想的，先问一下整数的范围，如果有一个最大值，然后看
: 能否用counting sort来解决？如果memory有限，也可以考虑用bit vector来解决（1
: bit表示1 integer).

w*g2015-12-23 08:12

23 楼

if it allow extra space, then you can get it done with O(n).
Here is how:
basically, scan each character from the beginning, if it is not duplicate,
then move pointer to next one. if it is duplicate, then just ignore it until
you get next one and put it at the end of non-duplicate array.

s*72015-12-23 08:12

24 楼

你回答的够好了。
别想了，纯粹浪费生命。
问你的人，吃错药了。

E*y2015-12-23 08:12

25 楼

多年前好像被问过,记得也是这也不行那也不够好, 最后我说用INTEGER的值作MEMORY地
址去标记,好像没再纠结了.

m*y2015-12-23 08:12

26 楼

对头，这个明显就是面试官最近刚用过trie，趁着记忆犹新来显摆一下。
最后那个用字符串的提示，最明显不过了，因为要是不用排序，只是查找的话，字符串
天然就该用trie。当场你要是竭力辩护，比如为hash辩护，如果都说对了，那他也嚼的
你只知其一，不知其二；如果错了任何地方，你死定了。
现在你赶紧写thank-you note，强调一下trie对你其它几个答案的优势，这事儿有戏，
比你答上来还有戏。大多数面试官都是喜欢比自己慢一点的，慢太多他又嫌你拖累。只
有老板才不介意你技术比他强，但老板又不用亲自靠你编程：）

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

: 这面试官没好好准备题目
: 临时瞎问
: 相信我
: 因为我经常瞎问

d*e2015-12-23 08:12

27 楼

面试官是想O(1)的check duplicate
建议找出max 和 min，然后生成一个存boolean数组，size是max-min+1
遍历过array，在新数组中找到每个数对应的index(num-min)，如果是false就改成true
，保留这个num，如果是true就remove这个数。当然可以把array先转为list，然后直接
调用remove()就好。

w*n2015-12-23 08:12

28 楼

正解。
但是写thank you note来弥补恐怕太晚了。

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

: 对头，这个明显就是面试官最近刚用过trie，趁着记忆犹新来显摆一下。
: 最后那个用字符串的提示，最明显不过了，因为要是不用排序，只是查找的话，字符串
: 天然就该用trie。当场你要是竭力辩护，比如为hash辩护，如果都说对了，那他也嚼的
: 你只知其一，不知其二；如果错了任何地方，你死定了。
: 现在你赶紧写thank-you note，强调一下trie对你其它几个答案的优势，这事儿有戏，
: 比你答上来还有戏。大多数面试官都是喜欢比自己慢一点的，慢太多他又嫌你拖累。只
: 有老板才不介意你技术比他强，但老板又不用亲自靠你编程：）

y*e2015-12-23 08:12

29 楼

Hashtable查询开支：
- 最好是O(1)
- 最差是O(N)
- 平均是O(1)
对于这个问题，要把输入的数字过一遍，所以用hashtable是最好的。
那个面试官说hash有collision，你应该回复他说这个是最差的情况，但是平均下来
hash查询的复杂度是O(1)。打个比方，qsort最差是O(N^2)，这并不阻碍qsort成为最好
的排序算法之一。

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

: 谢谢你的回复，面试官一直说hash有collision，不一定是O（1）的lookup. 是非flg的
: 一个软件公司，现在还不太方便透露，等最后上完整面经的时候再说吧，希望理解。