t*****g 发帖数: 113 | 1 1. You have two arrays X and Y. Each are having say M and N elements already
sorted increasingly. We have to find the k-th largest one of the whole set
M + N elements.
2. Regular expression match,可以match的符号只有3种:
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
3. boggle puzzle 找到里面所有的单词,写code
4. Given preorder of a binary tree, print out all the binary trees
5. Given a sequence of alphabetically sorted strings, try to find out the
alphabet order there. |
B*******1 发帖数: 2454 | 2 可以详细说说第2,怎么样的? 看得不是很懂问题。
第4题你是怎么做的? 第一次看到这个问题。
第5题是toplogical sort吧。
thanks |
l*****a 发帖数: 14598 | 3 4:
root is fixed,
next is the root of left sub-tree or right sub-tree
do recursion for each sub-tree.
具体写出来还要花点功夫
5:
咋玩?介绍一下你的玩法
2:
根据输入pattern,构造一个状态表与输入字符的数组/map
initial state is s0, end state is sn
for example, pattern is ab+d
(s0,a)->s1
(s1,b)->s1
(s1,d)->s2
s2 is end state,once your input can goto s2,that is correct
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可以详细说说第2,怎么样的? 看得不是很懂问题。 : 第4题你是怎么做的? 第一次看到这个问题。 : 第5题是toplogical sort吧。 : thanks
|
l*****a 发帖数: 14598 | 4 3嘛意思?
already
set
【在 t*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. You have two arrays X and Y. Each are having say M and N elements already : sorted increasingly. We have to find the k-th largest one of the whole set : M + N elements. : 2. Regular expression match,可以match的符号只有3种: : : a-z : match a-z : a+ : match any numbers of a : .+ : repeat 1 - arbitrary times : 3. boggle puzzle 找到里面所有的单词,写code : 4. Given preorder of a binary tree, print out all the binary trees
|
B*******1 发帖数: 2454 | 5 第4题我跟你想法一样,写出来没有错的确有点难度,
不但要recursion,还要不断排列组合
譬如preorder是a,b,c,d,e,f
a是root,可能的情况有:
1. bcdef 构成left tree
2. bcdef 构成right tree
3. b left tree, cdef构成right tree
3. bc构成left tree,def构成right tree
。。。。。
第5题
对于每一个string,根据字母先后顺序建立dag,譬如abc, a->b a->c b->c
处理完所有string后,进行toplogical sort, 就得到order了。
第2题,似乎很多regex的题目要求都不一样,不知道楼主这里的这个要求是怎么样的。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 4: : root is fixed, : next is the root of left sub-tree or right sub-tree : do recursion for each sub-tree. : 具体写出来还要花点功夫 : 5: : 咋玩?介绍一下你的玩法 : 2: : 根据输入pattern,构造一个状态表与输入字符的数组/map : initial state is s0, end state is sn
|
m**q 发帖数: 189 | 6 第四题我也是一样的想法,不过感觉把这些tree都打印出来
挺麻烦的,没想到太好的办法
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第4题我跟你想法一样,写出来没有错的确有点难度, : 不但要recursion,还要不断排列组合 : 譬如preorder是a,b,c,d,e,f : a是root,可能的情况有: : 1. bcdef 构成left tree : 2. bcdef 构成right tree : 3. b left tree, cdef构成right tree : 3. bc构成left tree,def构成right tree : 。。。。。 : 第5题
|
a**********2 发帖数: 340 | 7 把结果存到一个vector里面,用#来表示节点为空
【在 m**q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第四题我也是一样的想法,不过感觉把这些tree都打印出来 : 挺麻烦的,没想到太好的办法
|
b*******y 发帖数: 232 | 8 我觉得第四题的思路是这样的
记得preorder和inorder能完全决定一棵binary tree
那么现在有了preorder,只要找出所有的inorder的组合,就相当于找出了所有的
binary tree
例如preorder是 4 2 1 3 6 5 7
我们知道4是root,那么可以把4插到任何一个地方,例如 2 1 3 4 6 5 7
那么2 1 3是左子树的元素,6,5,7是右子树的元素;2和6分别是左右子树的root
再分别对左右子树做操作,这样可以recursively求出所有的inorder
already
set
【在 t*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. You have two arrays X and Y. Each are having say M and N elements already : sorted increasingly. We have to find the k-th largest one of the whole set : M + N elements. : 2. Regular expression match,可以match的符号只有3种: : : a-z : match a-z : a+ : match any numbers of a : .+ : repeat 1 - arbitrary times : 3. boggle puzzle 找到里面所有的单词,写code : 4. Given preorder of a binary tree, print out all the binary trees
|
y*******g 发帖数: 6599 | 9 太难了,,,难怪google不理我
already
set
【在 t*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. You have two arrays X and Y. Each are having say M and N elements already : sorted increasingly. We have to find the k-th largest one of the whole set : M + N elements. : 2. Regular expression match,可以match的符号只有3种: : : a-z : match a-z : a+ : match any numbers of a : .+ : repeat 1 - arbitrary times : 3. boggle puzzle 找到里面所有的单词,写code : 4. Given preorder of a binary tree, print out all the binary trees
|
f*******t 发帖数: 7549 | 10 我申google暑假实习第二场电面就碰到了第5题,完全没答上来,悲剧 |
|
|
h*********n 发帖数: 915 | 11 建图,周游,挺简单啊。
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我申google暑假实习第二场电面就碰到了第5题,完全没答上来,悲剧
|
d*******d 发帖数: 2050 | 12 哪有那么简单!你这只是第一小步而已.
这个题的关键在于要找到所有的可能的顺序.
【在 h*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 建图,周游,挺简单啊。
|
h*********n 发帖数: 915 | 13 为何要找所有顺序?拓扑排序即可。
【在 d*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哪有那么简单!你这只是第一小步而已. : 这个题的关键在于要找到所有的可能的顺序.
|
B*******1 发帖数: 2454 | 14 以前是要求输出所有顺序得,但是这里楼主似乎没有要输出所有的。 |
l*****a 发帖数: 14598 | 15 这种知名算法题没意思
知道的就会,不知道就不会
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我申google暑假实习第二场电面就碰到了第5题,完全没答上来,悲剧
|
b*******y 发帖数: 232 | 16 第五题是啥意思?
sorted strings是不是说一组string其实按“大小”排列了
bag < bad < aee
说明 g
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前是要求输出所有顺序得,但是这里楼主似乎没有要输出所有的。
|
c****p 发帖数: 6474 | 17 是的
【在 b*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第五题是啥意思? : sorted strings是不是说一组string其实按“大小”排列了 : bag < bad < aee : 说明 g
|
r********t 发帖数: 395 | |
f*******t 发帖数: 7549 | 19 主要是topsort的概念
其实是学过的,但一时没联想到
【在 h*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 建图,周游,挺简单啊。
|
g*****i 发帖数: 2162 | 20 topsort要用额外空间吧,至少要建个图?
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要是topsort的概念 : 其实是学过的,但一时没联想到
|
k****n 发帖数: 369 | 21 图是必须要建的,不过这没啥吧,没说要O(1) space阿
【在 g*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : topsort要用额外空间吧,至少要建个图?
|