s*******i
发帖数: 712 | 1 1. 很长的log file记录了用户访问amazon.com的过程，两列分别为 userID 和
pageName.
log从上倒下按照点击发生的时间顺序。找出最popular的3连击。
eg:
zhang welcome
Li Hello
Wang welcome
Li books
Wang Hello
zhang books
Li shopping cart
Li checkout
zhang shopping cart
Wang camera
zhang checkout
最popular的3 combo是books -> shopping cart -> checkout
2. Permutation of a string.这题最郁闷，我把programming expose里的code默写了出
来。但这个方法是不管字符重复的，假设都是不同的。现在考官要不显示重复的，而且
他要求不能先
都列出来再剔除，而要在发现重复的时候及时制止。没想出来
3. Design a fight ticket booking system. |
k***e
发帖数: 556 | 2 赞题目
1. (a) first divide table by the user. get a vector for each user, then for
each a[i][i+1][i+2] from all users clicks do a counting. sure hash should be
used
space length(all records) time length(all records).
It is worth thinking about extending this to k-click
2. check next_permutation function in stl and you will see how to do it.
I think some ppl post recursive solutions before. I did not remember that.
3. no idea :<
4. network? cache? indexing? more memory? more servers around?
Than
【在 s*******i 的大作中提到】
: 1. 很长的log file记录了用户访问amazon.com的过程，两列分别为 userID 和
: pageName.
: log从上倒下按照点击发生的时间顺序。找出最popular的3连击。
: eg:
: zhang welcome
: Li Hello
: Wang welcome
: Li books
: Wang Hello
: zhang books
|
s*******i
发帖数: 712 | 3 3. Fight booking system补充一下，一下他要UML diagram那种表示。然后要细分复杂一
点，refine到比较小的class那种。而不是一个很高层面的MVC结构。
4. 她说amazon很抠，more mem和more server都不可能。caching是一个方法没错，但
具体怎
么做？当时因为不了解DB怎么用caching我也不敢放开讲。
I got my interview referred by a nice guy on this board. Thank him very
much. My resume never made this far with Amazon before.
then for
should be
it.
that.
【在 k***e 的大作中提到】
: 赞题目
: 1. (a) first divide table by the user. get a vector for each user, then for
: each a[i][i+1][i+2] from all users clicks do a counting. sure hash should be
: used
: space length(all records) time length(all records).
: It is worth thinking about extending this to k-click
: 2. check next_permutation function in stl and you will see how to do it.
: I think some ppl post recursive solutions before. I did not remember that.
: 3. no idea :<
: 4. network? cache? indexing? more memory? more servers around?
|
k***e
发帖数: 556 | 4 2. recursive solution
I guess you know how to generate permutation for nonrepeated numbers already
.
Given an array with some equal numbers, for example 1, 2, 2, 2, 3, 3, 4
I will make them different:
1, 2.1, 2.2, 2.3, 3.1, 3.2, 4
Now you can apply the permutation algorithm for different numbers for it.
However, always make sure that a.x will not appear before a.1, a.2, ..., a.(
x-1)
I just found out that the change of 2 to 2.1 is redundant. Just remember
when you you insert a new char to the ex
【在 k***e 的大作中提到】
: 赞题目
: 1. (a) first divide table by the user. get a vector for each user, then for
: each a[i][i+1][i+2] from all users clicks do a counting. sure hash should be
: used
: space length(all records) time length(all records).
: It is worth thinking about extending this to k-click
: 2. check next_permutation function in stl and you will see how to do it.
: I think some ppl post recursive solutions before. I did not remember that.
: 3. no idea :<
: 4. network? cache? indexing? more memory? more servers around?
|
k***e
发帖数: 556 | 5 caching用的地方不少吧，比如网页缓存，就是算个hash值看看在不在
ps，能私下告诉我推荐你的人吗？我投了简历好像没反应。
杂一
【在 s*******i 的大作中提到】
: 3. Fight booking system补充一下，一下他要UML diagram那种表示。然后要细分复杂一
: 点，refine到比较小的class那种。而不是一个很高层面的MVC结构。
: 4. 她说amazon很抠，more mem和more server都不可能。caching是一个方法没错，但
: 具体怎
: 么做？当时因为不了解DB怎么用caching我也不敢放开讲。
: I got my interview referred by a nice guy on this board. Thank him very
: much. My resume never made this far with Amazon before.
:
: then for
: should be
|
c*********n
发帖数: 1057 | 6 2的话加个判断就好了吧
permute(char *str,int start)
int i;
if(start==strlen(str)-1)
printf("%s\n",str);
for(i=start;i
if(start != i && str[i]==str[start])
continue;//eliminate duplicates
swap(str[i],str[start]);
permute(str,start+1);
swap(str[i],str[start]);
}
}
【在 s*******i 的大作中提到】
: 1. 很长的log file记录了用户访问amazon.com的过程，两列分别为 userID 和
: pageName.
: log从上倒下按照点击发生的时间顺序。找出最popular的3连击。
: eg:
: zhang welcome
: Li Hello
: Wang welcome
: Li books
: Wang Hello
: zhang books
|
k*k
发帖数: 49 | 7 this might not work.. try "12334"
【在 c*********n 的大作中提到】
: 2的话加个判断就好了吧
: permute(char *str,int start)
: int i;
: if(start==strlen(str)-1)
: printf("%s\n",str);
: for(i=start;i: if(start != i && str[i]==str[start])
: continue;//eliminate duplicates
: swap(str[i],str[start]);
: permute(str,start+1);
|
m*****f
发帖数: 1243 | 8 为什么不work?
【在 k*k 的大作中提到】
: this might not work.. try "12334"
|
k*k
发帖数: 49 | 9 #include
void swap(char* arr, int f, int t){
char tmp = arr[f];
arr[f] = arr[t];
arr[t] = tmp;
}
void permute(char *str,int start){
int i;
if(start==strlen(str)-1)
printf("%s\n",str);
for(i=start;i
if(start != i && str[i]==str[start])
continue;//eliminate duplicates
swap(str, i, start);
permute(str,start+1);
swap(str, i, start);
}
}
int main(){
char str[] = "1233";
permute(str, 0);
}
$ ./pm | wc -l
22
but sh |
S****X
发帖数: 507 | 10 回头我给你个 recruiter 的邮件， 如果你数据结构，C++ 和 design 很彪悍的话，
我知道这个组还在招， 因为他们没找到满意的
【在 k***e 的大作中提到】
: caching用的地方不少吧，比如网页缓存，就是算个hash值看看在不在
: ps，能私下告诉我推荐你的人吗？我投了简历好像没反应。
:
: 杂一
|
|
|
g*******y
发帖数: 1930 | 11 我想了一下，简单的改改好像不照
因为：
1.我们需要数组是sort的，这样对于重复的一串字母，可以只选第一个
2.swap后，数组变成unsorted了
解决方案，不用数组，该用链表
在那个for循环里面：
原来把a[i]和a[start] swap的操作，
简单的改为把a[i]从链表中提出来放到start之前的位置
然后递归
递归完了后，再把a[i]放回原来的位置
这样实现起来稍微复杂一点点，不过就可以work了，而且输出的顺序也是按照123 132
213 231 312 321这样是有序的
另外指出一个这个code里面的问题：
if(start != i && str[i]==str[start])
continue;//eliminate duplicates
要改成
if(start != i && str[i]==str[i-1])
continue;//eliminate duplicates
【在 k*k 的大作中提到】
: #include
: void swap(char* arr, int f, int t){
: char tmp = arr[f];
: arr[f] = arr[t];
: arr[t] = tmp;
: }
: void permute(char *str,int start){
: int i;
: if(start==strlen(str)-1)
: printf("%s\n",str);
|
b****j
发帖数: 78 | 12 把判重的if改成：
if (strchr(str + start, str[i]) != str + i)
continue; // eliminate duplicates
就可以了
【在 k*k 的大作中提到】
: #include
: void swap(char* arr, int f, int t){
: char tmp = arr[f];
: arr[f] = arr[t];
: arr[t] = tmp;
: }
: void permute(char *str,int start){
: int i;
: if(start==strlen(str)-1)
: printf("%s\n",str);
|
b****j
发帖数: 78 | 13 请把程序运行结果贴一下
【在 g*******y 的大作中提到】
: 我想了一下，简单的改改好像不照
: 因为：
: 1.我们需要数组是sort的，这样对于重复的一串字母，可以只选第一个
: 2.swap后，数组变成unsorted了
: 解决方案，不用数组，该用链表
: 在那个for循环里面：
: 原来把a[i]和a[start] swap的操作，
: 简单的改为把a[i]从链表中提出来放到start之前的位置
: 然后递归
: 递归完了后，再把a[i]放回原来的位置
|
g*******y
发帖数: 1930 | 14 又想了下，貌似是work的
不过，复杂度增加了n倍啊
还是改成list的好，呵呵
【在 b****j 的大作中提到】
: 请把程序运行结果贴一下
|
b****j
发帖数: 78 | 15 你可以写一下list的版本然后比较一下速度
【在 g*******y 的大作中提到】
: 又想了下，貌似是work的
: 不过，复杂度增加了n倍啊
: 还是改成list的好，呵呵
|
r********t
发帖数: 395 | 16 第三题属于系统分析题；可以考虑结构系统分析或者面向对象系统分析。
设计一些模块，如“用户注册/登录”，“航班查询”，“付费”等等等等。
要是面向对象，把UML用例图，类图，交互图等等画出来并且make sense，肯定会博得
好感。
没有确切的答案，考官估计要考查一下系统分析与设计的能力，属于软件工程范畴～ |
k*k
发帖数: 49 | 17 as mentioned in the previous post by krone
use the well know get-next-permutation algorithm should work fine.
i believe....
public String nextPermute(String str){
char[] arr = str.toCharArray();
//1.0 find a[i] < a[i+1];
int pos=-1;
for(int i=0; i
if (arr[i]
pos = i;
}
if (pos==-1)
return null; //all done
//2.0 find last a[j] > a[i];
|
r********t
发帖数: 395 | 18 第三题那就对了，UML图不难画，只要了解一下就明白了；如果设计MVC，那就比较麻烦
了。。。
杂一
【在 s*******i 的大作中提到】
: 3. Fight booking system补充一下，一下他要UML diagram那种表示。然后要细分复杂一
: 点，refine到比较小的class那种。而不是一个很高层面的MVC结构。
: 4. 她说amazon很抠，more mem和more server都不可能。caching是一个方法没错，但
: 具体怎
: 么做？当时因为不了解DB怎么用caching我也不敢放开讲。
: I got my interview referred by a nice guy on this board. Thank him very
: much. My resume never made this far with Amazon before.
:
: then for
: should be
|
g*******y
发帖数: 1930 | 19 理论分析上list肯定更优
我知道，有些理论上性能更优的东西，也许因为常数因子的原因在某些小规模问题上，
可能反而更慢
list分析一下，插入删除操作，常数因子就好几了(假设是8)，这个问题本来就是n！的
复杂度，假设你用的strchr的平均性能是n/2
这也得n>=16，list才能体现优势，但是16!我们的机子算不过来，呵呵
【在 b****j 的大作中提到】
: 你可以写一下list的版本然后比较一下速度
|
r********t
发帖数: 395 | 20 麻烦你也给我一个呗？谢谢好心人。。。
【在 S****X 的大作中提到】
: 回头我给你个 recruiter 的邮件， 如果你数据结构，C++ 和 design 很彪悍的话，
: 我知道这个组还在招， 因为他们没找到满意的
|
|
|
r********t
发帖数: 395 | |
L*********d
发帖数: 1019 | 22 Problems like No4 are very popular. These are testing your problem solving
skill, troubleshooting skill and past experience.
Mostly it is not expected to have perfect answer for these problems. Most
likely how you troubleshoot these problems. For example, for application
being slow:
- checking what has changed (data volume, code, hardware, database?)
- adding metrics collection/profiling [to figure out which part is taking
most of the time]
- adding monitoring [when it is slow, can you trigger s
【在 s*******i 的大作中提到】
: 1. 很长的log file记录了用户访问amazon.com的过程，两列分别为 userID 和
: pageName.
: log从上倒下按照点击发生的时间顺序。找出最popular的3连击。
: eg:
: zhang welcome
: Li Hello
: Wang welcome
: Li books
: Wang Hello
: zhang books
|
s*******i
发帖数: 712 | 23 两轮电面
【在 r********t 的大作中提到】
: onsite 之前的面试是什么流程？
|
c*********n
发帖数: 1057 | 24 都是technical的么？
【在 s*******i 的大作中提到】
: 两轮电面
|
a********a
发帖数: 219 | 25 你的code是背下来的？太强大了。
我个人认为这个是所有里面最惨的。因为你能做出这个而做不出面试官要求的那个就表
明你是背的或者
做过这道题。而不是理解了算法。
2. Permutation of a string.这题最郁闷，我把programming expose里的code默写了出
来。但这个方法是不管字符重复的，假设都是不同的。现在考官要不显示重复的，而且
他要求不能先
都列出来再剔除，而要在发现重复的时候及时制止。没想出来
【在 s*******i 的大作中提到】
: 1. 很长的log file记录了用户访问amazon.com的过程，两列分别为 userID 和
: pageName.
: log从上倒下按照点击发生的时间顺序。找出最popular的3连击。
: eg:
: zhang welcome
: Li Hello
: Wang welcome
: Li books
: Wang Hello
: zhang books
|
m*******y
发帖数: 68 | 26 I have a different understanding of the 2nd problem from you guys.
For input: aabb
You should generate:
aabb
bbaa
abab
abba
...
instead of
ab
ba
By repetition, I guess it means that, if you rename the first two "a" into "
a.1" and "a.2",
a.1 a.2 bb
should be viewed the same as
a.2 a.1 bb,
and you should only generate it once.
It is not that you get rid of repetition of characters in each individual
string.
Not sure which understanding is correct. |
i****h
发帖数: 321 | 27 第一题可以用generalized suffix tree
但是onsite应该不会要求写这么复杂的程序吧。
for
be
【在 k***e 的大作中提到】
: 赞题目
: 1. (a) first divide table by the user. get a vector for each user, then for
: each a[i][i+1][i+2] from all users clicks do a counting. sure hash should be
: used
: space length(all records) time length(all records).
: It is worth thinking about extending this to k-click
: 2. check next_permutation function in stl and you will see how to do it.
: I think some ppl post recursive solutions before. I did not remember that.
: 3. no idea :<
: 4. network? cache? indexing? more memory? more servers around?
|
s*******i
发帖数: 712 | 28 我和你想的差不多，最后说的算法就是suffix array。但真的没法code啊，太复杂了。
而且page
name都是string，要处理过才方便用suffix的办法。最绝望的是我把算法说了一下，
interviewer
对这类suffix算法貌似完全没有概念，听得很蒙。不知他想要什么样的答案。
【在 i****h 的大作中提到】
: 第一题可以用generalized suffix tree
: 但是onsite应该不会要求写这么复杂的程序吧。
:
: for
: be
|
i****h
发帖数: 321 | 29 呵呵，我的GST是写了差不多一周才调通的。。。
【在 s*******i 的大作中提到】
: 我和你想的差不多，最后说的算法就是suffix array。但真的没法code啊，太复杂了。
: 而且page
: name都是string，要处理过才方便用suffix的办法。最绝望的是我把算法说了一下，
: interviewer
: 对这类suffix算法貌似完全没有概念，听得很蒙。不知他想要什么样的答案。
|
H*M
发帖数: 1268 | 30 这个第一题，可不可以这样：
因为这种点击的可能数目是很小的，可以把所有的用个某种alphabet表示，比如, welc
ome->a Hello->b, books->c
这样把整个log过一遍，每个用户分开，每个用户的连续点击用array表示，比如zhang:
abceafe
Li: acdef
Wang: abc
After that,根据这个表生成一个trie,节点的value记录发生的次数。比如abceafe,则在
节点 c,e,a,f,e（都是可能的连续三的点击）上都要记录1，然后处理下一个用户，把相
应的节点value值加1。
到最后traverse这个trie,找出最大的value的节点，然后从它往加上parent和grand pa
rent就是最大的连续点击的三连击。可以拓展到3以上的。
【在 s*******i 的大作中提到】
: 1. 很长的log file记录了用户访问amazon.com的过程，两列分别为 userID 和
: pageName.
: log从上倒下按照点击发生的时间顺序。找出最popular的3连击。
: eg:
: zhang welcome
: Li Hello
: Wang welcome
: Li books
: Wang Hello
: zhang books
|
|
|
H*M
发帖数: 1268 | 31 这个post很有启发性！收藏了
【在 L*********d 的大作中提到】
: Problems like No4 are very popular. These are testing your problem solving
: skill, troubleshooting skill and past experience.
: Mostly it is not expected to have perfect answer for these problems. Most
: likely how you troubleshoot these problems. For example, for application
: being slow:
: - checking what has changed (data volume, code, hardware, database?)
: - adding metrics collection/profiling [to figure out which part is taking
: most of the time]
: - adding monitoring [when it is slow, can you trigger s
|
t***b
发帖数: 38 | 32 Can we use a hash table instead of a trie?
What are the pros and cons here?
welc
zhang:
则在
把相
【在 H*M 的大作中提到】
: 这个第一题，可不可以这样：
: 因为这种点击的可能数目是很小的，可以把所有的用个某种alphabet表示，比如, welc
: ome->a Hello->b, books->c
: 这样把整个log过一遍，每个用户分开，每个用户的连续点击用array表示，比如zhang:
: abceafe
: Li: acdef
: Wang: abc
: After that,根据这个表生成一个trie,节点的value记录发生的次数。比如abceafe,则在
: 节点 c,e,a,f,e（都是可能的连续三的点击）上都要记录1，然后处理下一个用户，把相
: 应的节点value值加1。
|
p********7
发帖数: 549 | 33 为什么用prefix，找common longest substring不是用reffix么？
welc
zhang:
则在
把相
【在 H*M 的大作中提到】
: 这个第一题，可不可以这样：
: 因为这种点击的可能数目是很小的，可以把所有的用个某种alphabet表示，比如, welc
: ome->a Hello->b, books->c
: 这样把整个log过一遍，每个用户分开，每个用户的连续点击用array表示，比如zhang:
: abceafe
: Li: acdef
: Wang: abc
: After that,根据这个表生成一个trie,节点的value记录发生的次数。比如abceafe,则在
: 节点 c,e,a,f,e（都是可能的连续三的点击）上都要记录1，然后处理下一个用户，把相
: 应的节点value值加1。
|
c******f
发帖数: 2144 | |
l******c
发帖数: 2555 | 35 you are right.
How to program?
【在 m*******y 的大作中提到】
: I have a different understanding of the 2nd problem from you guys.
: For input: aabb
: You should generate:
: aabb
: bbaa
: abab
: abba
: ...
: instead of
: ab
|
l******c
发帖数: 2555 | 36 not right.
As descibed,
input :aabb
output:
aabb,
abab
baba,
abba
baab
bbaa
【在 b****j 的大作中提到】
: 把判重的if改成：
: if (strchr(str + start, str[i]) != str + i)
: continue; // eliminate duplicates
: 就可以了
|
