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 的大作中提到】
: 可以详细说说第2,怎么样的？ 看得不是很懂问题。
: 第4题你是怎么做的？ 第一次看到这个问题。
: 第5题是toplogical sort吧。
: thanks
|
l*****a
发帖数: 14598 | 4 3嘛意思？
already
set
【在 t*****g 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 第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 的大作中提到】
: 第四题我也是一样的想法，不过感觉把这些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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 我申google暑假实习第二场电面就碰到了第5题，完全没答上来，悲剧
|
d*******d
发帖数: 2050 | 12 哪有那么简单!你这只是第一小步而已.
这个题的关键在于要找到所有的可能的顺序.
【在 h*********n 的大作中提到】
: 建图，周游，挺简单啊。
|
h*********n
发帖数: 915 | 13 为何要找所有顺序？拓扑排序即可。
【在 d*******d 的大作中提到】
: 哪有那么简单!你这只是第一小步而已.
: 这个题的关键在于要找到所有的可能的顺序.
|
B*******1
发帖数: 2454 | 14 以前是要求输出所有顺序得，但是这里楼主似乎没有要输出所有的。 |
l*****a
发帖数: 14598 | 15 这种知名算法题没意思
知道的就会，不知道就不会
【在 f*******t 的大作中提到】
: 我申google暑假实习第二场电面就碰到了第5题，完全没答上来，悲剧
|
b*******y
发帖数: 232 | 16 第五题是啥意思？
sorted strings是不是说一组string其实按“大小”排列了
bag < bad < aee
说明 g
【在 B*******1 的大作中提到】
: 以前是要求输出所有顺序得，但是这里楼主似乎没有要输出所有的。
|
c****p
发帖数: 6474 | 17 是的
【在 b*******y 的大作中提到】
: 第五题是啥意思？
: sorted strings是不是说一组string其实按“大小”排列了
: bag < bad < aee
: 说明 g
|
r********t
发帖数: 395 | |
f*******t
发帖数: 7549 | 19 主要是topsort的概念
其实是学过的，但一时没联想到
【在 h*********n 的大作中提到】
: 建图，周游，挺简单啊。
|
g*****i
发帖数: 2162 | 20 topsort要用额外空间吧,至少要建个图?
【在 f*******t 的大作中提到】
: 主要是topsort的概念
: 其实是学过的，但一时没联想到
|
k****n
发帖数: 369 | 21 图是必须要建的，不过这没啥吧，没说要O(1) space阿
【在 g*****i 的大作中提到】
: topsort要用额外空间吧,至少要建个图?
|
