logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
Amazon 电面
avatar
Amazon 电面# JobHunting - 待字闺中
r*i
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.
avatar
C*U
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.
avatar
r*i
3 楼
I used hashtable
avatar
h*n
4 楼
第一个只能想到O(N^2)的算法
对每一个单词,以sort之后的string为Key value出现次数插入hash
然后对两两单词合成的string也做同样的事
最后走一遍hash统计一下value即可
有更好的解法吗
avatar
c*a
5 楼
每2个单词合成很耗时间啊，2个单词的substring算不算:
{am,ate, me}
am + ate = a+ at + me
avatar
e*s
6 楼
第二题能不能讨论一下?
avatar
E*e
7 楼
wt if there are duplicate in the array,
avatar
b*m
8 楼
我也贡献个Amazon电面吧，不过其实不值一提：实现binary tree的preorder遍历，如
果用的是递归，再改成非递归，然后自己用一个例子来测试。够水的吧！
avatar
h*n
9 楼
一个stack搞定？

【在 b***m 的大作中提到】
: 我也贡献个Amazon电面吧，不过其实不值一提：实现binary tree的preorder遍历，如
: 果用的是递归，再改成非递归，然后自己用一个例子来测试。够水的吧！
avatar
b*m
10 楼

嗯。不过我用的非递归有些另类，把考官搞蒙了（他心里准备的是常规的连续push左右
child）。我写完code问他怎么想，他说“I don't know”，然后俩人花了10分钟走完
一圈实例。其实我写的code是inorder的变种，稍稍修改了一下，就成了preorder，结
果把丫（三哥）搞晕了。;-)

【在 h****n 的大作中提到】
: 一个stack搞定？
avatar
K*n
11 楼
嗯，inorder也可以，postorder就不好写了，非递归的

【在 b***m 的大作中提到】
: 我也贡献个Amazon电面吧，不过其实不值一提：实现binary tree的preorder遍历，如
: 果用的是递归，再改成非递归，然后自己用一个例子来测试。够水的吧！
avatar
p*2
12 楼

大牛报报offer把。

【在 b***m 的大作中提到】
:
: 嗯。不过我用的非递归有些另类，把考官搞蒙了（他心里准备的是常规的连续push左右
: child）。我写完code问他怎么想，他说“I don't know”，然后俩人花了10分钟走完
: 一圈实例。其实我写的code是inorder的变种，稍稍修改了一下，就成了preorder，结
: 果把丫（三哥）搞晕了。;-)
avatar
l*a
13 楼
贴出来给大家review一下吧

【在 b***m 的大作中提到】
:
: 嗯。不过我用的非递归有些另类，把考官搞蒙了（他心里准备的是常规的连续push左右
: child）。我写完code问他怎么想，他说“I don't know”，然后俩人花了10分钟走完
: 一圈实例。其实我写的code是inorder的变种，稍稍修改了一下，就成了preorder，结
: 果把丫（三哥）搞晕了。;-)
avatar
b*m
14 楼
嗯，那个没法儿玩。

【在 K*********n 的大作中提到】
: 嗯，inorder也可以，postorder就不好写了，非递归的
avatar
b*m
15 楼
电面完了哪儿有什么offer啊。练练手而已。

【在 p*****2 的大作中提到】
:
: 大牛报报offer把。
avatar
b*m
16 楼
明儿吧，今天不开电脑了。

【在 l*****a 的大作中提到】
: 贴出来给大家review一下吧
avatar
l*a
17 楼
为了备战骨骼？

【在 b***m 的大作中提到】
: 电面完了哪儿有什么offer啊。练练手而已。
avatar
p*2
18 楼

牛。啥时候onsite？

【在 b***m 的大作中提到】
: 电面完了哪儿有什么offer啊。练练手而已。
avatar
l*a
19 楼
为什么post-order非递归不好玩？
跟pre-order非低贵差不多吧

【在 b***m 的大作中提到】
: 嗯，那个没法儿玩。
avatar
K*n
20 楼
写起来难很多

【在 l*****a 的大作中提到】
: 为什么post-order非递归不好玩？
: 跟pre-order非低贵差不多吧
avatar
l*a
21 楼
really?
不都是用stack吗？

【在 K*********n 的大作中提到】
: 写起来难很多
avatar
b*m
22 楼
不知道呢。上次onsite面一个Sr. Technical PM的职位，铩羽而归。头天食物中毒，吐
个天翻地覆，第二天连续说了五个小时，我容易么我。

【在 p*****2 的大作中提到】
:
: 牛。啥时候onsite？
avatar
b*m
23 楼
你写一个我学习学习。

【在 l*****a 的大作中提到】
: 为什么post-order非递归不好玩？
: 跟pre-order非低贵差不多吧
avatar
K*n
24 楼
实践一下或者搜一下代码就知道了，很别扭，细节很繁复，考虑需要特别周全。不像re
cursive版，三种order颠倒一下顺序就行了。
非recuesive版本，按照实现难度从易到难是preorder, inorder, postorder。
preorder随便写，inorder要仔细琢磨。如果面试碰到写postorder，我这水平基本上就
跪了。

【在 l*****a 的大作中提到】
: really?
: 不都是用stack吗？
avatar
p*2
25 楼

re
他说的意思应该是有一种简洁的办法，3种order都能cover

【在 K*********n 的大作中提到】
: 实践一下或者搜一下代码就知道了，很别扭，细节很繁复，考虑需要特别周全。不像re
: cursive版，三种order颠倒一下顺序就行了。
: 非recuesive版本，按照实现难度从易到难是preorder, inorder, postorder。
: preorder随便写，inorder要仔细琢磨。如果面试碰到写postorder，我这水平基本上就
: 跪了。
avatar
K*n
26 楼
太深了……

【在 p*****2 的大作中提到】
:
: re
: 他说的意思应该是有一种简洁的办法，3种order都能cover
avatar
l*a
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 的大作中提到】
: 你写一个我学习学习。
avatar
b*m
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)
avatar
p*2
29 楼

见识大牛的程序了吧。

【在 b***m 的大作中提到】
: 俺已经看晕了。;-)
:
:
avatar
l*a
30 楼
找个例子试试，不保证没问题　:)
简单说就是有左子树就往左，否则就往右
左右都结束了，就可以打印当前了。
stack里似乎保存的是当前到跟的path

【在 b***m 的大作中提到】
: 俺已经看晕了。;-)
:
:
avatar
l*a
31 楼
我是从库存里copy paste的

【在 p*****2 的大作中提到】
:
: 见识大牛的程序了吧。
avatar
p*2
32 楼

赞题库。可以出本书了。

【在 l*****a 的大作中提到】
: 我是从库存里copy paste的
avatar
b*m
33 楼
如果有面试官让我写非递归后序遍历，我就直接说不会。;-)

【在 l*****a 的大作中提到】
: 我是从库存里copy paste的
avatar
l*a
34 楼
那可能会错过20W offer的，要慎重

【在 b***m 的大作中提到】
: 如果有面试官让我写非递归后序遍历，我就直接说不会。;-)
avatar
c*a
35 楼
preorder的iterative跟postorder可以很接近啊，差别就是2条stack...多一两行code
avatar
b*m
36 楼
不应该啊，差别还是比较大的吧。

code

【在 c*****a 的大作中提到】
: preorder的iterative跟postorder可以很接近啊，差别就是2条stack...多一两行code
avatar
c*a
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+ " ");
}
avatar
b*m
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)
avatar
l*a
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)
avatar
p*2
40 楼

两个确实感觉不太好。

【在 l*****a 的大作中提到】
: 写个一个stack的post-order吧
: 要简洁版，谢谢！
avatar
c*t
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)
avatar
h*n
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吧
: 要简洁版，谢谢！
avatar
p*2
43 楼

这不行吧？怎么能自己改变数据结构呢？

【在 h****n 的大作中提到】
: 一个的stack只会写改动TreeNode的结构体的post traversal版本呵呵
: 假设允许改动treenode，加个bool标志位visited，初始都初始化为false
: 够简洁吧。。
: void PostOrder(TreeNode * root)
: {
: TreeNode* cur;
: if(root)
: {
: stack st;
: st.push(root);
avatar
l*a
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);
avatar
h*n
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叉树里有这个咚咚
相关阅读
看到板上有人吐槽公司面试报销，我也吐槽一个雅虎为F的面试官点赞One Kings Lane这公司怎么样？是不是做software test很没前途啊Amazon ReferralJava Blocking Queue问题H1B一共六年，如果同时有两个H1B世风日下 人心不古 现在找工作的都不择手段今年H1B可能只有130KSTEM的H1B是允许有2份H1B且第二份不用重新占抽签的？ (转载)满版抱怨烙印，签名寥寥无几 (转载)【工作机会】Data Analyst Production Analytics Sr. Developer in Bank of大家看看我的情况大致的目标应该是什么感觉被G家歧视了，fresh PhD给了T3再来bitch一下去年h1b抽签的统计每次和Manager出去喝酒喝到high处他都会跟我说明天就给你办绿卡，然后第二天酒醒之后他就忘了怎么破serialize n-ary tree 一问offer二选一，真心求比较Apple onsite
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。