Redian新闻
>
讨论下面试题的难度分布?
avatar
讨论下面试题的难度分布?# JobHunting - 待字闺中
j*l
1
假如题目都事先没看过。
估计面试时候也经常会问到一般站友,中级站友和高级站友是主力,长老级作为bar
raiser, 开国大老用来刁难人。
新手上路级:
比如O(n)时间找数组最大元素
一般站友级:
比如链表反转,限制用一层循环找单词个数
中级站友级:
比如二叉树的前序中序非递归遍历
前序中序序列重构二叉树并coding
高级站友级:
O(1)空间反转句子中的每个单词
log(n)时间找两个排序数组的median
O(1)时间GetMin的栈
循环数组的二分查找
二叉树的后序非递归
各种DP题
长老级:
复制含有random指针的链表
开国大老:
发在paper上的算法,比如寻找0-1矩阵最大的的全1子矩阵
avatar
y*i
2
顶这个
avatar
d*e
3
长老级那题知道,因为看过,但前面还有很多暂时还不知道……唉
看来还是新手上路

【在 j**l 的大作中提到】
: 假如题目都事先没看过。
: 估计面试时候也经常会问到一般站友,中级站友和高级站友是主力,长老级作为bar
: raiser, 开国大老用来刁难人。
: 新手上路级:
: 比如O(n)时间找数组最大元素
: 一般站友级:
: 比如链表反转,限制用一层循环找单词个数
: 中级站友级:
: 比如二叉树的前序中序非递归遍历
: 前序中序序列重构二叉树并coding

avatar
w*1
4
前序中序序列重构二叉树并coding.
这意思是以数组形式给出pre-order, in-order, 用它们来create the tree?
这个挺难的, code起来比reverse words要难啊
avatar
w*1
5
log(n)时间找两个排序数组的median.
这题能具体说下吗
avatar
r*o
6
binary search啊,好像jntl发过两个等长排序数组找median的算法。

【在 w*****1 的大作中提到】
: log(n)时间找两个排序数组的median.
: 这题能具体说下吗

avatar
j*l
7
确实,思路简单清晰,草图也很好画,就是代码写起来繁琐啊繁琐。
繁琐的代码要多在白板上练习练习再练习。

【在 w*****1 的大作中提到】
: 前序中序序列重构二叉树并coding.
: 这意思是以数组形式给出pre-order, in-order, 用它们来create the tree?
: 这个挺难的, code起来比reverse words要难啊

avatar
j*l
8
http://geeksforgeeks.org/?p=2105

【在 w*****1 的大作中提到】
: log(n)时间找两个排序数组的median.
: 这题能具体说下吗

avatar
l*i
9
长老级的那题据说是中国大陆信息学奥赛选手的基础DP题,原题在USACO上有。这个结
果30年前都不见得能发paper。当然面世的时候要10分钟想出来也不容易。
avatar
j*l
10
开国大老级吧。
另外,像Floyd的龟兔赛跑算法检链表的环,以及Kadane的经典Maximum Sum,事后看起
来都很简单,比这题要好理解的多,代码也很短。就看你是不是第一个想到的人。

【在 l***i 的大作中提到】
: 长老级的那题据说是中国大陆信息学奥赛选手的基础DP题,原题在USACO上有。这个结
: 果30年前都不见得能发paper。当然面世的时候要10分钟想出来也不容易。

avatar
y*i
11
怎么感觉只要元素没有重复,只有前序序列就可以重构二叉树了,只有中序序列无论如
何也不能重构二叉树的。
只有前序序列,第一个元素肯定是根,从第二个元素开始循环,对于每个待插入元素,
如果小于之前的元素,就插入到之前元素的左孩子处;待插入元素如果大于之前的元素
,并且任一祖先不是其父结点的左孩子的时候,就插入到之前元素的右孩子处,如果有
一个(最近一个)祖先是其父结点的左孩子,就比较待插入元素和那个父结点的值,如
果小于,同样插入到之前元素的右孩子处,如果大于,就插入到那个父结点的右孩子处。

【在 w*****1 的大作中提到】
: 前序中序序列重构二叉树并coding.
: 这意思是以数组形式给出pre-order, in-order, 用它们来create the tree?
: 这个挺难的, code起来比reverse words要难啊

avatar
j*l
12
嘉定没有重复元素。这里是指普通的二叉树,不是BST,而且要唯一的重建
另外已知的的事实是
知道前序和中序可以唯一重建
知道中序和后序也可以唯一重建
知道前序和后序不能唯一重建
另外如果左右孩子为空指针时也输出话,一个前序,一个中序,或者一个后序也能唯一
重建。

处。

【在 y**i 的大作中提到】
: 怎么感觉只要元素没有重复,只有前序序列就可以重构二叉树了,只有中序序列无论如
: 何也不能重构二叉树的。
: 只有前序序列,第一个元素肯定是根,从第二个元素开始循环,对于每个待插入元素,
: 如果小于之前的元素,就插入到之前元素的左孩子处;待插入元素如果大于之前的元素
: ,并且任一祖先不是其父结点的左孩子的时候,就插入到之前元素的右孩子处,如果有
: 一个(最近一个)祖先是其父结点的左孩子,就比较待插入元素和那个父结点的值,如
: 果小于,同样插入到之前元素的右孩子处,如果大于,就插入到那个父结点的右孩子处。

avatar
y*i
13
原来指的是普通的二叉树,没注意到。

【在 j**l 的大作中提到】
: 嘉定没有重复元素。这里是指普通的二叉树,不是BST,而且要唯一的重建
: 另外已知的的事实是
: 知道前序和中序可以唯一重建
: 知道中序和后序也可以唯一重建
: 知道前序和后序不能唯一重建
: 另外如果左右孩子为空指针时也输出话,一个前序,一个中序,或者一个后序也能唯一
: 重建。
:
: 处。

avatar
y*i
14
我又想了一下,其实对于普通的二叉树,算法还是一样的,只不过需要依赖中序来实现
BST的“小于到左边,大于到右边”的属性了,这个算法就是确定唯一的重建的(不唯
一的重建有很多种,根本就不需要想算法了)。
同样,在前序序列,第一个元素肯定是根,从第二个元素开始循环,对于每个待插入元
素A[i],如果小于之前的元素A[i-1](对应普通的二叉树,相当于待插入元素在中序序
列里在之前的元素的左边),就插入到之前元素的左孩子处;待插入元素如果大于之前
的元素(类似的,对应普通的二叉树,相当于待插入元素在中序序列里在之前的元素的
右边),并且任一祖先不是其父结点的左孩子的时候,就插入到之前元素的右孩子处,
如果有一个(最近一个)祖先是其父结点的左孩子,就比较待插入元素和那个父结点的
值(同样,对应普通的二叉树,相当于比较待插入元素和那个父结点在中序序列里的位
置),如果小于(思想同上),同样插入到之前元素的右孩子处,如果大于(思想同上
),就插入到那个父结点的右孩子处。
总而言之,中序序列就是二叉树的顺序,是BST的有序序列,也是普通二叉树的一个顺
序参考,甚至可以看做是一个改写后的比较函数(相当

【在 j**l 的大作中提到】
: 嘉定没有重复元素。这里是指普通的二叉树,不是BST,而且要唯一的重建
: 另外已知的的事实是
: 知道前序和中序可以唯一重建
: 知道中序和后序也可以唯一重建
: 知道前序和后序不能唯一重建
: 另外如果左右孩子为空指针时也输出话,一个前序,一个中序,或者一个后序也能唯一
: 重建。
:
: 处。

avatar
c*t
15
这个分类好,以后我们可以分级讨论。
不知hash table 相关的题算哪一类;
还有suffix tree相关问题?
avatar
j*l
16
如果题目看过弄懂了,开国大老的题做起来也就和新手上路一样了。
关键是锻炼自己的思维,举一反三。这样在做从没见过的长老级以上的题目时候很有用。
Hash表算中高级站友,就怕问到解决冲突,再Hash的一些细节。
Suffix和trie,弄懂原理也快,就是怕让你实际写个完整代码,据说在面试短短时间是
不够的。

【在 c********t 的大作中提到】
: 这个分类好,以后我们可以分级讨论。
: 不知hash table 相关的题算哪一类;
: 还有suffix tree相关问题?

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。