8 |+ N) q: ~. E: s

编程题：1 ~- k* U1 L. \, G9 K

9 X’ N# w% b* w; m, K’ j: n8 n

1. 求一个二叉树的高度，如果只有root结点，高度为0

! j* L& L* W# [) I& g) {/ _7 E' I1 o- h2 |+ |) v/ k9 X: x

2. 将稀疏疏组中的非零元素提取出来，用链表表示

- Z" c3 ~& l4 s

. I5 u' k2 W# @3. 两个n维数组，已排序，为升序。设计算法求2n的数中

. j' u5 v& t- |4 D, e8 S, @* k- g# h第n大的数。要求分析时间和空间复杂度。不用给出代码

====================================================================

这是部分google面试题目,希望后来者好运.

1 O2 H- S' \4 D/ [( k+ a2 d1.求直方图的最大内接矩形,假设每个细条的宽度为1.这个题很hot,两个人来问.我没想出什么好的算法. # u) t) w4 V8 Z7 F; _. `

$ @) h' _1 E: z8 u2.NxN行列有序的矩阵查找一个数.以前有人遇到过.O(N)的时间复杂度 ' E3 e4 ~" m" w2 C4 J4 @

) e; a. g. 3 n+ s

3.给定一篇文章,求包含所有单词的最短摘要.O(N)的时间复杂度

4 l: g3 s# z" O7 K2 n! N8 M, f3 T# A) a7 ]( z5 E5 Z

4.将MxN的矩阵转秩,要求O(1)的空间复杂度.参考群论中cyclic group,group generator * O( I9 Y& l9 Y2 P8 z” u

& ], a0 U% ^% B1 J2 c* b5.开放式问题,怎么避免重复抓取网页 9 Q& t4 U) ]* v& ]& E” O$ R5 X0 I

‘ C+ w3 _0 |+ |6.开放式问题,有些网站每天只允许有限次访问,怎么抓取网页使得索引尽量全面和新鲜

. X1 a( @/ Z: ^! |8 W0 X7 ]’ J6 K2 ~’ d% x” N’ h- p8 H) K

7.写一个singleton pattern的例子 # w i [1 j9 s. h3 |( J: @5 m8 f

5 |$ x) X, A1 B. {& A

8.vector vs. arraylist, growth strategy & complexity

% u8 j: V/ v’ W! L: m’ F1 X9 H( Q6 {& k

9.在C++文件中只declare class A, 但不以任何方式define class A, 是做什么用

- p” @/ j G, V* O; \ C6 Q2 b& V5 z9 B0 a/ [

10.virtual function # v5 i: q& T! \8 r4 r; a

” }4 _# `$ L4 W: l4 f8 x& E- A

11.讨论html vs. xhtml vs. xml : x9 ^# { Y; z- @# Q z# d+ Y

G2 M* F5 T% C% o* t6

12.描述在浏览器中敲入一个网址后所发生的事情.dns,cache等* y’ K7 ^1