j**l
发帖数: 2911 | 1 假如题目都事先没看过。
估计面试时候也经常会问到一般站友，中级站友和高级站友是主力，长老级作为bar
raiser, 开国大老用来刁难人。
新手上路级：
比如O(n)时间找数组最大元素
一般站友级：
比如链表反转，限制用一层循环找单词个数
中级站友级：
比如二叉树的前序中序非递归遍历
前序中序序列重构二叉树并coding
高级站友级：
O(1)空间反转句子中的每个单词
log(n)时间找两个排序数组的median
O(1)时间GetMin的栈
循环数组的二分查找
二叉树的后序非递归
各种DP题
长老级：
复制含有random指针的链表
开国大老：
发在paper上的算法，比如寻找0-1矩阵最大的的全1子矩阵 |
y**i
发帖数: 1112 | |
d**e
发帖数: 6098 | 3 长老级那题知道，因为看过，但前面还有很多暂时还不知道……唉
看来还是新手上路
【在 j**l 的大作中提到】
: 假如题目都事先没看过。
: 估计面试时候也经常会问到一般站友，中级站友和高级站友是主力，长老级作为bar
: raiser, 开国大老用来刁难人。
: 新手上路级：
: 比如O(n)时间找数组最大元素
: 一般站友级：
: 比如链表反转，限制用一层循环找单词个数
: 中级站友级：
: 比如二叉树的前序中序非递归遍历
: 前序中序序列重构二叉树并coding
|
w*****1
发帖数: 245 | 4 前序中序序列重构二叉树并coding.
这意思是以数组形式给出pre-order, in-order, 用它们来create the tree?
这个挺难的, code起来比reverse words要难啊 |
w*****1
发帖数: 245 | 5 log(n)时间找两个排序数组的median.
这题能具体说下吗 |
r****o
发帖数: 1950 | 6 binary search啊，好像jntl发过两个等长排序数组找median的算法。
【在 w*****1 的大作中提到】
: log(n)时间找两个排序数组的median.
: 这题能具体说下吗
|
j**l
发帖数: 2911 | 7 确实，思路简单清晰，草图也很好画，就是代码写起来繁琐啊繁琐。
繁琐的代码要多在白板上练习练习再练习。
【在 w*****1 的大作中提到】
: 前序中序序列重构二叉树并coding.
: 这意思是以数组形式给出pre-order, in-order, 用它们来create the tree?
: 这个挺难的, code起来比reverse words要难啊
|
j**l
发帖数: 2911 | 8 http://geeksforgeeks.org/?p=2105
【在 w*****1 的大作中提到】
: log(n)时间找两个排序数组的median.
: 这题能具体说下吗
|
l***i
发帖数: 1309 | 9 长老级的那题据说是中国大陆信息学奥赛选手的基础DP题，原题在USACO上有。这个结
果30年前都不见得能发paper。当然面世的时候要10分钟想出来也不容易。 |
j**l
发帖数: 2911 | 10 开国大老级吧。
另外，像Floyd的龟兔赛跑算法检链表的环，以及Kadane的经典Maximum Sum，事后看起
来都很简单，比这题要好理解的多，代码也很短。就看你是不是第一个想到的人。
【在 l***i 的大作中提到】
: 长老级的那题据说是中国大陆信息学奥赛选手的基础DP题，原题在USACO上有。这个结
: 果30年前都不见得能发paper。当然面世的时候要10分钟想出来也不容易。
|
|
|
y**i
发帖数: 1112 | 11 怎么感觉只要元素没有重复，只有前序序列就可以重构二叉树了，只有中序序列无论如
何也不能重构二叉树的。
只有前序序列，第一个元素肯定是根，从第二个元素开始循环，对于每个待插入元素，
如果小于之前的元素，就插入到之前元素的左孩子处；待插入元素如果大于之前的元素
，并且任一祖先不是其父结点的左孩子的时候，就插入到之前元素的右孩子处，如果有
一个（最近一个）祖先是其父结点的左孩子，就比较待插入元素和那个父结点的值，如
果小于，同样插入到之前元素的右孩子处，如果大于，就插入到那个父结点的右孩子处。
【在 w*****1 的大作中提到】
: 前序中序序列重构二叉树并coding.
: 这意思是以数组形式给出pre-order, in-order, 用它们来create the tree?
: 这个挺难的, code起来比reverse words要难啊
|
j**l
发帖数: 2911 | 12 嘉定没有重复元素。这里是指普通的二叉树，不是BST，而且要唯一的重建
另外已知的的事实是
知道前序和中序可以唯一重建
知道中序和后序也可以唯一重建
知道前序和后序不能唯一重建
另外如果左右孩子为空指针时也输出话，一个前序，一个中序，或者一个后序也能唯一
重建。
处。
【在 y**i 的大作中提到】
: 怎么感觉只要元素没有重复，只有前序序列就可以重构二叉树了，只有中序序列无论如
: 何也不能重构二叉树的。
: 只有前序序列，第一个元素肯定是根，从第二个元素开始循环，对于每个待插入元素，
: 如果小于之前的元素，就插入到之前元素的左孩子处；待插入元素如果大于之前的元素
: ，并且任一祖先不是其父结点的左孩子的时候，就插入到之前元素的右孩子处，如果有
: 一个（最近一个）祖先是其父结点的左孩子，就比较待插入元素和那个父结点的值，如
: 果小于，同样插入到之前元素的右孩子处，如果大于，就插入到那个父结点的右孩子处。
|
y**i
发帖数: 1112 | 13 原来指的是普通的二叉树，没注意到。
【在 j**l 的大作中提到】
: 嘉定没有重复元素。这里是指普通的二叉树，不是BST，而且要唯一的重建
: 另外已知的的事实是
: 知道前序和中序可以唯一重建
: 知道中序和后序也可以唯一重建
: 知道前序和后序不能唯一重建
: 另外如果左右孩子为空指针时也输出话，一个前序，一个中序，或者一个后序也能唯一
: 重建。
:
: 处。
|
y**i
发帖数: 1112 | 14 我又想了一下，其实对于普通的二叉树，算法还是一样的，只不过需要依赖中序来实现
BST的“小于到左边，大于到右边”的属性了，这个算法就是确定唯一的重建的（不唯
一的重建有很多种，根本就不需要想算法了）。
同样，在前序序列，第一个元素肯定是根，从第二个元素开始循环，对于每个待插入元
素A[i]，如果小于之前的元素A[i-1]（对应普通的二叉树，相当于待插入元素在中序序
列里在之前的元素的左边），就插入到之前元素的左孩子处；待插入元素如果大于之前
的元素（类似的，对应普通的二叉树，相当于待插入元素在中序序列里在之前的元素的
右边），并且任一祖先不是其父结点的左孩子的时候，就插入到之前元素的右孩子处，
如果有一个（最近一个）祖先是其父结点的左孩子，就比较待插入元素和那个父结点的
值（同样，对应普通的二叉树，相当于比较待插入元素和那个父结点在中序序列里的位
置），如果小于（思想同上），同样插入到之前元素的右孩子处，如果大于（思想同上
），就插入到那个父结点的右孩子处。
总而言之，中序序列就是二叉树的顺序，是BST的有序序列，也是普通二叉树的一个顺
序参考，甚至可以看做是一个改写后的比较函数（相当
【在 j**l 的大作中提到】
: 嘉定没有重复元素。这里是指普通的二叉树，不是BST，而且要唯一的重建
: 另外已知的的事实是
: 知道前序和中序可以唯一重建
: 知道中序和后序也可以唯一重建
: 知道前序和后序不能唯一重建
: 另外如果左右孩子为空指针时也输出话，一个前序，一个中序，或者一个后序也能唯一
: 重建。
:
: 处。
|
c********t
发帖数: 1756 | 15 这个分类好，以后我们可以分级讨论。
不知hash table 相关的题算哪一类；
还有suffix tree相关问题? |
j**l
发帖数: 2911 | 16 如果题目看过弄懂了，开国大老的题做起来也就和新手上路一样了。
关键是锻炼自己的思维，举一反三。这样在做从没见过的长老级以上的题目时候很有用。
Hash表算中高级站友，就怕问到解决冲突，再Hash的一些细节。
Suffix和trie，弄懂原理也快，就是怕让你实际写个完整代码，据说在面试短短时间是
不够的。
【在 c********t 的大作中提到】
: 这个分类好，以后我们可以分级讨论。
: 不知hash table 相关的题算哪一类；
: 还有suffix tree相关问题?
|
