我的面试高频题 - 未名空间MITBBS历史存档

d*w2012-03-01 08:03

1 楼

coding:
- JOIN: nested join, hash join, sort-merge join
- Number: Fibonacci, prime，随机取文件某一行
- String: strstr, wordcount
- Tree: height, lca, balance tree
- Heap: 查找最大的k个数
- DP: 最大连续子串和
- array: find a key in rotated array, 去除重复字符
- linkedlist: 是否有环，插入结点，删除重复结点
- 递归回溯：变化很多，这方面需要大量练习
知识性：
多线程，mutex/semaphore
java GC
C++ virtual, smart pointer
regex使用
数据库：知道btree, 索引
search engine: 倒排表,拉链，稀疏索引，空间向量模型，tf*idf,
large scale data: hash, consistent hash, bloom filter, bitmap, 外排序，
partition
分布式：CAP理论，gossip，Paxos, GFS设计思想
network: socket, tcp3次握手, asyschnoized io, epoll, select, 惊群
设计型：
queue/stack实现
LRU
trie　tree
设计游戏
四则运算求值
我感觉把我上面说的练熟，还是很大可能性遇到的，虽然不是很全面，但我觉得不应该
把太多时间花在难题上，充实知识体系，符合职位要求更重要。

p*22012-03-01 08:03

2 楼

LZ真慷慨呀。贡献这么多面经。

R*i2012-03-01 08:03

3 楼

赞！谢谢楼主了！

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

d*w2012-03-01 08:03

4 楼

呵呵，我面的是很多，光onsite就１０多个了，还是觉得运气很重要，基本上要遇到印
度人我就挂了。

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

: LZ真慷慨呀。贡献这么多面经。

d*y2012-03-01 08:03

5 楼

膜拜牛人，好人好报。昨天电话面试估计挂了。第一次面试。嗨！

d*w2012-03-01 08:03

6 楼

coding:
- JOIN: nested join, hash join, sort-merge join
- Number: Fibonacci, prime，随机取文件某一行
- String: strstr, wordcount
- Tree: height, lca, balance tree
- Heap: 查找最大的k个数
- DP: 最大连续子串和
- array: find a key in rotated array, 去除重复字符
- linkedlist: 是否有环，插入结点，删除重复结点
- 递归回溯：变化很多，这方面需要大量练习
知识性：
多线程，mutex/semaphore
java GC
C++ virtual, smart pointer
regex使用
数据库：知道btree, 索引
search engine: 倒排表,拉链，稀疏索引，空间向量模型，tf*idf,
large scale data: hash, consistent hash, bloom filter, bitmap, 外排序，
partition
分布式：CAP理论，gossip，Paxos, GFS设计思想
network: socket, tcp3次握手, asyschnoized io, epoll, select, 惊群
设计型：
queue/stack实现
LRU
trie　tree
设计游戏
四则运算求值
我感觉把我上面说的练熟，还是很大可能性遇到的，虽然不是很全面，但我觉得不应该
把太多时间花在难题上，充实知识体系，符合职位要求更重要。

c*p2012-03-01 08:03

7 楼

mark

j*a2012-03-01 08:03

8 楼

同mark

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

: mark

v*e2012-03-01 08:03

9 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

t*n2012-03-01 08:03

10 楼

mark

N*d2012-03-01 08:03

11 楼

mark

f*32012-03-01 08:03

12 楼

mark

l*82012-03-01 08:03

13 楼

mark

★ 发自iPhone App: ChineseWeb 8.6

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

: mark

b*g2012-03-01 08:03

14 楼

mark

j*u2012-03-01 08:03

15 楼

mark

E*Z2012-03-01 08:03

16 楼

mark

f*n2012-03-01 08:03

17 楼

mark

k*32012-03-01 08:03

18 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

w*52012-03-01 08:03

19 楼

mark

s*y2012-03-01 08:03

20 楼

Thanks for sharing.

j*32012-03-01 08:03

21 楼

mark

z*92012-03-01 08:03

22 楼

mark

o*n2012-03-01 08:03

23 楼

mark

v*n2012-03-01 08:03

24 楼

mark!

l*92012-03-01 08:03

25 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

W*y2012-03-01 08:03

26 楼

mark

t*n2012-03-01 08:03

27 楼

mark

y*g2012-03-01 08:03

28 楼

太难了，，我遇到你肯定跪了

c*t2012-03-01 08:03

29 楼

l*r2012-03-01 08:03

30 楼

Mark

a*m2012-03-01 08:03

31 楼

多谢大牛，请教一下Paxos有什么可以透彻理解的材料么？原paper巨难一直不明白到底
怎么回事。

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

m*w2012-03-01 08:03

32 楼

mark. thanks

j*32012-03-01 08:03

33 楼

2012年

e*92012-03-01 08:03

34 楼

mark 谢谢

l*92012-03-01 08:03

35 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

s*x2012-03-01 08:03

36 楼

Zan

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

: 2012年

m*g2012-03-01 08:03

37 楼

mark谢谢分享。

b*92012-03-01 08:03

38 楼

mark

q*12012-03-01 08:03

39 楼

MARK

b*f2012-03-01 08:03

40 楼

Mark

q*l2012-03-01 08:03

41 楼

怒马

u*o2012-03-01 08:03

42 楼

mark

w*t2012-03-01 08:03

43 楼

cut!

t*r2012-03-01 08:03

44 楼

Thanks

★ 发自iPhone App: ChineseWeb 8.7

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

s*62012-03-01 08:03

45 楼

感谢前辈分享！！

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

s*y2012-03-01 08:03

46 楼

mark

J*o2012-03-01 08:03

47 楼

Mark

h*12012-03-01 08:03

48 楼

thanks for share

l*92012-03-01 08:03

49 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

g*l2012-03-01 08:03

50 楼

Write code to implement "join"?

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

b*72012-03-01 08:03

51 楼

Congrat! you mentioned "算法导论那本书看了3遍," which book is this, please?

e*i2012-03-01 08:03

52 楼

mark....

c*62012-03-01 08:03

53 楼

mark

p*92012-03-01 08:03

54 楼

mark 好人一生平安

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

c*p2012-03-01 08:03

55 楼

mark

j*a2012-03-01 08:03

56 楼

同mark

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

: mark

v*e2012-03-01 08:03

57 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

t*n2012-03-01 08:03

58 楼

mark

N*d2012-03-01 08:03

59 楼

mark

f*32012-03-01 08:03

60 楼

mark

l*82012-03-01 08:03

61 楼

mark

★ 发自iPhone App: ChineseWeb 8.6

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

: mark

b*g2012-03-01 08:03

62 楼

mark

j*u2012-03-01 08:03

63 楼

mark

E*Z2012-03-01 08:03

64 楼

mark

f*n2012-03-01 08:03

65 楼

mark

k*32012-03-01 08:03

66 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

w*52012-03-01 08:03

67 楼

mark

s*y2012-03-01 08:03

68 楼

Thanks for sharing.

j*32012-03-01 08:03

69 楼

mark

z*92012-03-01 08:03

70 楼

mark

o*n2012-03-01 08:03

71 楼

mark

v*n2012-03-01 08:03

72 楼

mark!

l*92012-03-01 08:03

73 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

W*y2012-03-01 08:03

74 楼

mark

t*n2012-03-01 08:03

75 楼

mark

y*g2012-03-01 08:03

76 楼

太难了，，我遇到你肯定跪了

c*t2012-03-01 08:03

77 楼

l*r2012-03-01 08:03

78 楼

Mark

a*m2012-03-01 08:03

79 楼

多谢大牛，请教一下Paxos有什么可以透彻理解的材料么？原paper巨难一直不明白到底
怎么回事。

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

m*w2012-03-01 08:03

80 楼

mark. thanks

j*32012-03-01 08:03

81 楼

2012年

e*92012-03-01 08:03

82 楼

mark 谢谢

l*92012-03-01 08:03

83 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

s*x2012-03-01 08:03

84 楼

Zan

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

: 2012年

m*g2012-03-01 08:03

85 楼

mark谢谢分享。

b*92012-03-01 08:03

86 楼

mark

q*12012-03-01 08:03

87 楼

MARK

b*f2012-03-01 08:03

88 楼

Mark

q*l2012-03-01 08:03

89 楼

怒马

u*o2012-03-01 08:03

90 楼

mark

w*t2012-03-01 08:03

91 楼

cut!

t*r2012-03-01 08:03

92 楼

Thanks

★ 发自iPhone App: ChineseWeb 8.7

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

s*62012-03-01 08:03

93 楼

感谢前辈分享！！

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

s*y2012-03-01 08:03

94 楼

mark

J*o2012-03-01 08:03

95 楼

Mark

h*12012-03-01 08:03

96 楼

thanks for share

l*92012-03-01 08:03

97 楼

mark

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

g*l2012-03-01 08:03

98 楼

Write code to implement "join"?

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

b*72012-03-01 08:03

99 楼

Congrat! you mentioned "算法导论那本书看了3遍," which book is this, please?

e*i2012-03-01 08:03

100 楼

mark....

c*62012-03-01 08:03

101 楼

mark

p*92012-03-01 08:03

102 楼

mark 好人一生平安

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习

P*s2012-03-01 08:03

103 楼

谢谢楼主分享。

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

: coding:
: - JOIN: nested join, hash join, sort-merge join
: - Number: Fibonacci, prime，随机取文件某一行
: - String: strstr, wordcount
: - Tree: height, lca, balance tree
: - Heap: 查找最大的k个数
: - DP: 最大连续子串和
: - array: find a key in rotated array, 去除重复字符
: - linkedlist: 是否有环，插入结点，删除重复结点
: - 递归回溯：变化很多，这方面需要大量练习