湖人队要去中国比赛，注意事项 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

湖人队要去中国比赛，注意事项

湖人队要去中国比赛，注意事项# Joke - 肚皮舞运动

t*22013-10-15 07:10

1 楼

上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
式为(时间访问者ID 访问网页)
每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
的log也不一定在一个文件里.

问:
用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
>另一个产品->.....), 针对每一串访问序列,仅取前三个网页组成一个三元组(如上
面的例子,就是), 统计TOP K 的三元组.
(跪在这题上了,先要确定如何判断用户的一次访问,然后是怎样从好多log文件中高效地
提取每个用户每次访问的前三个网页,存在什么地方,最后把这堆信息用heap或者其他什
么取top k).
2. 给一个二叉树,找到与给定节点距离为N的所有节点(没有parent link,有parent
link),两个节点间隔着几条边,就是距离为几
3. 1) Remove duplicate in an array
2) Longest common prefix in an array of strings.
4. 1) Top K elements in an array.
2) 两个单词,长度一样,找出从一个单词变到另一个单词的最短路径,每次只能改变
一个字母,且改变字母后的单词必须是有效的单词(我是假定有字典能判断一个单词是否
有效,然后BFS.)

j*02013-10-15 07:10

2 楼

y*e2013-10-15 07:10

3 楼

"湖人在周五给我们都发了邮件，提醒注意事项。里面写了很多公用厕所不带卫生纸，
因特殊国情出行最好结伴。结伴？我听说科比和加索尔在飞机上聊了很多，不知道他俩
会不会结伴……"

b*i2013-10-15 07:10

4 楼

赞LZ发面经。看起来这个比版上的其他Amazon面经偏难呀。LZ面试的什么职位啊？New
grad吗？

绍-

【在 t*********2 的大作中提到】

: 上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
: 1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
: 式为(时间访问者ID 访问网页)
: 每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
: 的log也不一定在一个文件里.
:
: 问:
: 用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
: >另一个产品->.....), 针对每一串访问序列,仅取前三个网页组成一个三元组(如上
: 面的例子,就是), 统计TOP K 的三元组.

G*82013-10-15 07:10

5 楼

昨天1刀结束了，现在是$1.50.

t*22013-10-15 07:10

6 楼

new grad sde

New

【在 b**********i 的大作中提到】

: 赞LZ发面经。看起来这个比版上的其他Amazon面经偏难呀。LZ面试的什么职位啊？New
: grad吗？
:
: 绍-

j*02013-10-15 07:10

7 楼

555。。10张$0.75的COUPON还在路上，它家会经常有这种DEAL吗？

q*n2013-10-15 07:10

8 楼

赞LZ面经，lz你是面完多少天收到rej的？我上周面完这周还没消息，发信HR也不回，
和我一起去的有的已经收到rej这个是不是拒信在路上的节奏。。。

【在 t*********2 的大作中提到】

: new grad sde
:
: New

d*w2013-10-15 07:10

9 楼

online says $1.79 ah

【在 G*8 的大作中提到】

: 昨天1刀结束了，现在是$1.50.

t*22013-10-15 07:10

10 楼

我是周五面的,然后第二周礼拜四下午收到的rej

【在 q******n 的大作中提到】

:
: 赞LZ面经，lz你是面完多少天收到rej的？我上周面完这周还没消息，发信HR也不回，
: 和我一起去的有的已经收到rej这个是不是拒信在路上的节奏。。。

G*82013-10-15 07:10

11 楼

我今天店里看的是1。5，我眼花了？

【在 d**w 的大作中提到】

: online says $1.79 ah

g*42013-10-15 07:10

12 楼

先感谢下LZ！
然后再打击下LZ，LZ肯定没好好准备面试，第1题，3.1和4.1就是他们家题库上的原题
，剩下的除了2之外都是leetcode的上原题。

绍-

【在 t*********2 的大作中提到】

G*82013-10-15 07:10

13 楼

还好那个胖子明年才到期，再等等。有我帮你帖一个。

【在 j**********0 的大作中提到】

: 555。。10张$0.75的COUPON还在路上，它家会经常有这种DEAL吗？

b*i2013-10-15 07:10

14 楼

恕我孤陋寡闻，Amazon还有题库？可以分享一下吗？

【在 g**4 的大作中提到】

: 先感谢下LZ！
: 然后再打击下LZ，LZ肯定没好好准备面试，第1题，3.1和4.1就是他们家题库上的原题
: ，剩下的除了2之外都是leetcode的上原题。
:
: 绍-

d*w2013-10-15 07:10

15 楼

你天天上sfw？

【在 G*8 的大作中提到】

: 我今天店里看的是1。5，我眼花了？

g*42013-10-15 07:10

16 楼

glassdoor

【在 b**********i 的大作中提到】

: 恕我孤陋寡闻，Amazon还有题库？可以分享一下吗？

G*82013-10-15 07:10

17 楼

2／wk，以后1／m？sd都成 ghost town了，还去啥。

【在 d**w 的大作中提到】

: 你天天上sfw？

q*x2013-10-15 07:10

18 楼

1是map/reduce吧。
2就是BFS，没有parent用递归，有就用queue。
3/4.1经典。
4.2 edit distance，难了点。

上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
式为(时间访问者ID 访问网页)
每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
的log也不一定在一个文件里.

问:
用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
>另一个产品->.....), 针对每一串访问序列,仅取前三个网页组成一个三元组(如上
面的例子,就是), 统计TOP K 的三元组.
(跪在这题上了,先要确定如何判断用户的一次访问,然后是怎样从好多log文件中高效地
提取每个用户每次访问的前三个网页,存在什么地方,最后把这堆信息用heap或者其他什
么取top k).
2. 给一个二叉树,找到与给定节点距离为N的所有节点(没有parent link,有parent
link),两个节点间隔着几条边,就是距离为几
3. 1) Remove duplicate in an array
2) Longest common prefix in an array of strings.
4. 1) Top K elements in an array.
2) 两个单词,长度一样,找出从一个单词变到另一个单词的最短路径,每次只能改变
一个字母,且改变字母后的单词必须是有效的单词(我是假定有字典能判断一个单词是否
有效,然后BFS.)

【在 t*********2 的大作中提到】

j*02013-10-15 07:10

19 楼

好啊，给你个热心包哈！

【在 G*8 的大作中提到】

: 还好那个胖子明年才到期，再等等。有我帮你帖一个。

q*x2013-10-15 07:10

20 楼

edit distance也在leetcode上？够狠。

【在 g**4 的大作中提到】

: 先感谢下LZ！
: 然后再打击下LZ，LZ肯定没好好准备面试，第1题，3.1和4.1就是他们家题库上的原题
: ，剩下的除了2之外都是leetcode的上原题。
:
: 绍-

G*82013-10-15 07:10

21 楼

收到，谢谢！

【在 j**********0 的大作中提到】

: 好啊，给你个热心包哈！

b*g2013-10-15 07:10

22 楼

4.2不是edit distance,是word ladder I

x*m2013-10-15 07:10

23 楼

感觉都是常规题目吧

【在 b*******g 的大作中提到】

: 4.2不是edit distance,是word ladder I

q*m2013-10-15 07:10

24 楼

第一题中，访问序列没给吧，是不是需要从log里面得出？ log里面的每个记录里面只
有一个网页地址吧，如何由那些记录找出访问序列感觉不好搞啊。或者我理解错了

绍-

【在 t*********2 的大作中提到】

w*i2013-10-15 07:10

25 楼

希望有大牛详述下第一题思路啊，最近好多人面试到。只是看Map/reduce的文章还是不
大明白T_T

s*d2013-10-15 07:10

26 楼

非牛，没做过Map/reduce，只看了几篇文章，不对的请赐教
试着分析下第一题
Map按照ID partition,输出 ID Time, URL,按照 ID Time排序
Reducer接收后，对每个ID,如果和上一个Time差别小于某个值，比如10分钟，就认为为
相同访问序列，并保存最初三个URL，直到Time差别大于10分钟，重新开始计算
需要2次MapReduce，Reducer也是Mapper
Reducer的结果是三元组，再次做MapReduce。也就是再次Emit出去
Reducer2接收三元组，统计数量并维护一个最小堆，结束所有数据后将自己的TOP K输
出到文件
将所有Reducer2的输出文件读入并取最大的K个三元组得到结果

s*d2013-10-15 07:10

27 楼

2. 给一个二叉树,找到与给定节点距离为N的所有节点(没有parent link,有parent
link),两个节点间隔着几条边,就是距离为几
开始没看清题意，认为是找到所有距离为N的节点对，先写出来吧
没有parent link 的方法，伪代码，递归，对每层，分左右找到下面n层的所有节点，
root到n层节点
AddPairToResult(TreeNode* root, vector< pair >& result)
{
vector< vector > left_vnodes(n)
vector< vector > right_vnodes(n)
left_vnodes[0] = {left} left_vnodes[1] = {left->left,left->right};...
left_vnodes[0] = {right} left_vnodes[1] = {right->left, right->right};...
add (root, i in left_vnodes[n-1)] to result
add (root, i in right_vnodes[n-1)] to result
for (int i = 0; i <= n-2; ++I)
{
add (node in left_vnodes[i], node in right_vnodes[n-2-i]) to result
}
AddPairToResult(root->left, result);
AddPairToResult(root->right, result);

}

s*d2013-10-15 07:10

28 楼

有parent的
vector FindDistanceN(TreeNode* start, int N)
{
vector result;
if(!start || N < 1)
return result;
unordered_set visited;
queue curr, next;
curr.push(start);
int dis = 0;
while(!curr.empty() && dis < N)
{
while(!curr.empty())
{
TreeNode* n = curr.front();
curr.pop();
visited.insert(n);
if(n->parent && visited.find(n->parent) != visited.end())
next.push(n->parent);
if(n->left && visited.find(n->left) != visited.end())
next.push(n->left);
if(n->right && visited.find(n->right) != visited.end())
next.push(n->right);
}
swap(curr,next);
++dis;
}

while(!curr.empty())
{
TreeNode* n = curr.front();
curr.pop();
result.push_back(n);
}
return result;
}

s*d2013-10-15 07:10

29 楼

有parent的
写一个函数
vector FindDistandNChildren(TreeNode* root, int N)
{
// 返回所有第N层子节点
}
AddNodes(FindDistandNChildren(start,N))
从root 用DFS找到 start并记录路径
root->...->start，假设长度为M，从root找到距离root为M-N的节点开始
n[M-N+1]为从root开始，路径上的第M-N+1个节点
AddNodes(FindDistandNChildren(n[M-N+1],1))
AddNodes(FindDistandNChildren(n[M-N+2],2))
。。。
当然去掉start