r****i
发帖数: 528 | 1 1. Coding, given a list of words (string), let compound word be the
combination of any two words in the array, check the numbers of duplicated
words (to check if there are duplicated compound words, and if the compound
word is the same as some word in the original list,
it is also considered as duplicated)
{"am", "eat", "a", "meat"} "am"+"eat"="a"+"meat" outout =1
2. OO design. Design a system for members to borrow books from a library
and a followup question is how to guarantee the performance if there are
millions of members and even more books. |
C***U
发帖数: 2406 | 2 第一个用hash table?
compound
【在 r****i 的大作中提到】
: 1. Coding, given a list of words (string), let compound word be the
: combination of any two words in the array, check the numbers of duplicated
: words (to check if there are duplicated compound words, and if the compound
: word is the same as some word in the original list,
: it is also considered as duplicated)
: {"am", "eat", "a", "meat"} "am"+"eat"="a"+"meat" outout =1
: 2. OO design. Design a system for members to borrow books from a library
: and a followup question is how to guarantee the performance if there are
: millions of members and even more books.
|
r****i
发帖数: 528 | |
h****n
发帖数: 1093 | 4 第一个只能想到O(N^2)的算法
对每一个单词,以sort之后的string为Key value出现次数插入hash
然后对两两单词合成的string也做同样的事
最后走一遍hash统计一下value即可
有更好的解法吗 |
c*****a
发帖数: 808 | 5 每2个单词合成很耗时间啊，2个单词的substring算不算:
{am,ate, me}
am + ate = a+ at + me |
e***s
发帖数: 799 | |
E********e
发帖数: 63 | 7 wt if there are duplicate in the array, |
b***m
发帖数: 5987 | 8 我也贡献个Amazon电面吧，不过其实不值一提：实现binary tree的preorder遍历，如
果用的是递归，再改成非递归，然后自己用一个例子来测试。够水的吧！ |
h****n
发帖数: 1093 | 9 一个stack搞定？
【在 b***m 的大作中提到】
: 我也贡献个Amazon电面吧，不过其实不值一提：实现binary tree的preorder遍历，如
: 果用的是递归，再改成非递归，然后自己用一个例子来测试。够水的吧！
|
b***m
发帖数: 5987 | 10
嗯。不过我用的非递归有些另类，把考官搞蒙了（他心里准备的是常规的连续push左右
child）。我写完code问他怎么想，他说“I don't know”，然后俩人花了10分钟走完
一圈实例。其实我写的code是inorder的变种，稍稍修改了一下，就成了preorder，结
果把丫（三哥）搞晕了。;-)
【在 h****n 的大作中提到】
: 一个stack搞定？
|
|
|
K*********n
发帖数: 2852 | 11 嗯，inorder也可以，postorder就不好写了，非递归的
【在 b***m 的大作中提到】
: 我也贡献个Amazon电面吧，不过其实不值一提：实现binary tree的preorder遍历，如
: 果用的是递归，再改成非递归，然后自己用一个例子来测试。够水的吧！
|
p*****2
发帖数: 21240 | 12
大牛报报offer把。
【在 b***m 的大作中提到】
:
: 嗯。不过我用的非递归有些另类，把考官搞蒙了（他心里准备的是常规的连续push左右
: child）。我写完code问他怎么想，他说“I don't know”，然后俩人花了10分钟走完
: 一圈实例。其实我写的code是inorder的变种，稍稍修改了一下，就成了preorder，结
: 果把丫（三哥）搞晕了。;-)
|
l*****a
发帖数: 14598 | 13 贴出来给大家review一下吧
【在 b***m 的大作中提到】
:
: 嗯。不过我用的非递归有些另类，把考官搞蒙了（他心里准备的是常规的连续push左右
: child）。我写完code问他怎么想，他说“I don't know”，然后俩人花了10分钟走完
: 一圈实例。其实我写的code是inorder的变种，稍稍修改了一下，就成了preorder，结
: 果把丫（三哥）搞晕了。;-)
|
b***m
发帖数: 5987 | 14 嗯，那个没法儿玩。
【在 K*********n 的大作中提到】
: 嗯，inorder也可以，postorder就不好写了，非递归的
|
b***m
发帖数: 5987 | 15 电面完了哪儿有什么offer啊。练练手而已。
【在 p*****2 的大作中提到】
:
: 大牛报报offer把。
|
b***m
发帖数: 5987 | 16 明儿吧，今天不开电脑了。
【在 l*****a 的大作中提到】
: 贴出来给大家review一下吧
|
l*****a
发帖数: 14598 | 17 为了备战骨骼？
【在 b***m 的大作中提到】
: 电面完了哪儿有什么offer啊。练练手而已。
|
p*****2
发帖数: 21240 | 18
牛。啥时候onsite？
【在 b***m 的大作中提到】
: 电面完了哪儿有什么offer啊。练练手而已。
|
l*****a
发帖数: 14598 | 19 为什么post-order非递归不好玩？
跟pre-order非低贵差不多吧
【在 b***m 的大作中提到】
: 嗯，那个没法儿玩。
|
K*********n
发帖数: 2852 | 20 写起来难很多
【在 l*****a 的大作中提到】
: 为什么post-order非递归不好玩？
: 跟pre-order非低贵差不多吧
|
|
|
l*****a
发帖数: 14598 | 21 really?
不都是用stack吗？
【在 K*********n 的大作中提到】
: 写起来难很多
|
b***m
发帖数: 5987 | 22 不知道呢。上次onsite面一个Sr. Technical PM的职位，铩羽而归。头天食物中毒，吐
个天翻地覆，第二天连续说了五个小时，我容易么我。
【在 p*****2 的大作中提到】
:
: 牛。啥时候onsite？
|
b***m
发帖数: 5987 | 23 你写一个我学习学习。
【在 l*****a 的大作中提到】
: 为什么post-order非递归不好玩？
: 跟pre-order非低贵差不多吧
|
K*********n
发帖数: 2852 | 24 实践一下或者搜一下代码就知道了，很别扭，细节很繁复，考虑需要特别周全。不像re
cursive版，三种order颠倒一下顺序就行了。
非recuesive版本，按照实现难度从易到难是preorder, inorder, postorder。
preorder随便写，inorder要仔细琢磨。如果面试碰到写postorder，我这水平基本上就
跪了。
【在 l*****a 的大作中提到】
: really?
: 不都是用stack吗？
|
p*****2
发帖数: 21240 | 25
re
他说的意思应该是有一种简洁的办法，3种order都能cover
【在 K*********n 的大作中提到】
: 实践一下或者搜一下代码就知道了，很别扭，细节很繁复，考虑需要特别周全。不像re
: cursive版，三种order颠倒一下顺序就行了。
: 非recuesive版本，按照实现难度从易到难是preorder, inorder, postorder。
: preorder随便写，inorder要仔细琢磨。如果面试碰到写postorder，我这水平基本上就
: 跪了。
|
K*********n
发帖数: 2852 | 26 太深了……
【在 p*****2 的大作中提到】
:
: re
: 他说的意思应该是有一种简洁的办法，3种order都能cover
|
l*****a
发帖数: 14598 | 27 en,pre-order是可以简单一点。
Post order with stack
void traverse(Node* root)
{
Node* current = root;
Stack stack;
while (1)
{
if(current->left) { stack.push(current); current=current->left; }
else if(current->right)
{ stack.push(current); current=current->right; }
else {
while(1)
{
cout<data<
if(stack.empty() ) return;
temp=stack.top();
if(temp->left==current)&&(temp->right)
{ current=temp->right; break}
else {current=temp; stack.pop(); }
}
}
}
【在 b***m 的大作中提到】
: 你写一个我学习学习。
|
b***m
发帖数: 5987 | 28 俺已经看晕了。;-)
【在 l*****a 的大作中提到】
: en,pre-order是可以简单一点。
: Post order with stack
: void traverse(Node* root)
: {
: Node* current = root;
: Stack stack;
: while (1)
: {
: if(current->left) { stack.push(current); current=current->left; }
: else if(current->right)
|
p*****2
发帖数: 21240 | 29
见识大牛的程序了吧。
【在 b***m 的大作中提到】
: 俺已经看晕了。;-)
:
:
|
l*****a
发帖数: 14598 | 30 找个例子试试，不保证没问题 :)
简单说就是有左子树就往左，否则就往右
左右都结束了，就可以打印当前了。
stack里似乎保存的是当前到跟的path
【在 b***m 的大作中提到】
: 俺已经看晕了。;-)
:
:
|
|
|
l*****a
发帖数: 14598 | 31 我是从库存里copy paste的
【在 p*****2 的大作中提到】
:
: 见识大牛的程序了吧。
|
p*****2
发帖数: 21240 | 32
赞题库。可以出本书了。
【在 l*****a 的大作中提到】
: 我是从库存里copy paste的
|
b***m
发帖数: 5987 | 33 如果有面试官让我写非递归后序遍历，我就直接说不会。;-)
【在 l*****a 的大作中提到】
: 我是从库存里copy paste的
|
l*****a
发帖数: 14598 | 34 那可能会错过20W offer的，要慎重
【在 b***m 的大作中提到】
: 如果有面试官让我写非递归后序遍历，我就直接说不会。;-)
|
c*****a
发帖数: 808 | 35 preorder的iterative跟postorder可以很接近啊，差别就是2条stack...多一两行code |
b***m
发帖数: 5987 | 36 不应该啊，差别还是比较大的吧。
code
【在 c*****a 的大作中提到】
: preorder的iterative跟postorder可以很接近啊，差别就是2条stack...多一两行code
|
c*****a
发帖数: 808 | 37 简洁版，差别不大
public void preOrderTraverse(BSTNode node){
Stack> stack = new Stack>();
stack.push(node);
while(stack.size()>0){
BSTNode current = stack.pop();
System.out.print(current.data+" ");
if(current.right!=null)
stack.push(current.right);
if(current.left!=null)
stack.push(current.left);
}
}
private void postOrderTraverse(BSTNode node){
Stack> stack = new Stack>();
Stack> out = new Stack>();
stack.push(node);
while(stack.size()>0){
BSTNode current = stack.pop();
out.push(current);
if(current.left!=null)
stack.push(current.left);
if(current.right!=null)
stack.push(current.right);
}
while(out.size()>0)
System.out.print(out.pop().data+ " ");
} |
b***m
发帖数: 5987 | 38 手机上看格式都是乱的，我明儿仔细看看。
【在 c*****a 的大作中提到】
: 简洁版，差别不大
: public void preOrderTraverse(BSTNode node){
: Stack> stack = new Stack>();
: stack.push(node);
: while(stack.size()>0){
: BSTNode current = stack.pop();
: System.out.print(current.data+" ");
: if(current.right!=null)
: stack.push(current.right);
: if(current.left!=null)
|
l*****a
发帖数: 14598 | 39 写个一个stack的post-order吧
要简洁版，谢谢！
【在 c*****a 的大作中提到】
: 简洁版，差别不大
: public void preOrderTraverse(BSTNode node){
: Stack> stack = new Stack>();
: stack.push(node);
: while(stack.size()>0){
: BSTNode current = stack.pop();
: System.out.print(current.data+" ");
: if(current.right!=null)
: stack.push(current.right);
: if(current.left!=null)
|
p*****2
发帖数: 21240 | 40
两个确实感觉不太好。
【在 l*****a 的大作中提到】
: 写个一个stack的post-order吧
: 要简洁版，谢谢！
|
|
|
c********t
发帖数: 5706 | 41 深奥，请问temp是不是一定是current的parent?
【在 l*****a 的大作中提到】
: en,pre-order是可以简单一点。
: Post order with stack
: void traverse(Node* root)
: {
: Node* current = root;
: Stack stack;
: while (1)
: {
: if(current->left) { stack.push(current); current=current->left; }
: else if(current->right)
|
h****n
发帖数: 1093 | 42 一个的stack只会写改动TreeNode的结构体的post traversal版本呵呵
假设允许改动treenode，加个bool标志位visited，初始都初始化为false
够简洁吧。。
void PostOrder(TreeNode * root)
{
TreeNode* cur;
if(root)
{
stack st;
st.push(root);
while(!st.empty())
{
cur = st.top();
st.pop();
if(cur->visited)
cout<val<
else
{
cur->visited = true;
st.push(cur);
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
}
}
}
}
【在 l*****a 的大作中提到】
: 写个一个stack的post-order吧
: 要简洁版，谢谢！
|
p*****2
发帖数: 21240 | 43
这不行吧？怎么能自己改变数据结构呢？
【在 h****n 的大作中提到】
: 一个的stack只会写改动TreeNode的结构体的post traversal版本呵呵
: 假设允许改动treenode，加个bool标志位visited，初始都初始化为false
: 够简洁吧。。
: void PostOrder(TreeNode * root)
: {
: TreeNode* cur;
: if(root)
: {
: stack st;
: st.push(root);
|
l*****a
发帖数: 14598 | 44 那就写个没有visited flag的
没听说2叉树里有这个咚咚
【在 h****n 的大作中提到】
: 一个的stack只会写改动TreeNode的结构体的post traversal版本呵呵
: 假设允许改动treenode，加个bool标志位visited，初始都初始化为false
: 够简洁吧。。
: void PostOrder(TreeNode * root)
: {
: TreeNode* cur;
: if(root)
: {
: stack st;
: st.push(root);
|
h****n
发帖数: 1093 | 45 呵呵，那估计没有通用模式了
如果允许加visited flag那么就有通用模式了
只需要调整else语句块里面几句的顺序即可：
post order:
cur->visited = true;
st.push(cur);
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
in order:
if(cur->right) st.push(cur->right);
cur->visited = true;
st.push(cur);
if(cur->left) st.push(cur->left);
pre order:
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
cur->visited = true;
st.push(cur);
【在 l*****a 的大作中提到】
: 那就写个没有visited flag的
: 没听说2叉树里有这个咚咚
|
