t*********2
发帖数: 43 | 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.) | b**********i
发帖数: 51 | 2 赞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 的三元组.
| t*********2
发帖数: 43 | 3 new grad sde
New
【在 b**********i 的大作中提到】
: 赞LZ发面经。看起来这个比版上的其他Amazon面经偏难呀。LZ面试的什么职位啊？New
: grad吗？
:
: 绍-
| q******n
发帖数: 116 | 4
赞LZ面经，lz你是面完多少天收到rej的？我上周面完这周还没消息，发信HR也不回，
和我一起去的有的已经收到rej这个是不是拒信在路上的节奏。。。
【在 t*********2 的大作中提到】
: new grad sde
:
: New
| t*********2
发帖数: 43 | 5 我是周五面的,然后第二周礼拜四下午收到的rej
【在 q******n 的大作中提到】
:
: 赞LZ面经，lz你是面完多少天收到rej的？我上周面完这周还没消息，发信HR也不回，
: 和我一起去的有的已经收到rej这个是不是拒信在路上的节奏。。。
| g**4
发帖数: 863 | 6 先感谢下LZ！
然后再打击下LZ，LZ肯定没好好准备面试，第1题，3.1和4.1就是他们家题库上的原题
，剩下的除了2之外都是leetcode的上原题。
绍-
【在 t*********2 的大作中提到】
: 上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
: 1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
: 式为(时间 访问者ID 访问网页)
: 每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
: 的log也不一定在一个文件里.
:
: 问:
: 用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
: >另一个产品->.....), 针对每一串 访问序列,仅取前三个网页组成一个三元组(如上
: 面的例子,就是<主页,某搜索页面,某产品页面>), 统计TOP K 的三元组.
| b**********i
发帖数: 51 | 7 恕我孤陋寡闻，Amazon还有题库？可以分享一下吗？
【在 g**4 的大作中提到】
: 先感谢下LZ！
: 然后再打击下LZ，LZ肯定没好好准备面试，第1题，3.1和4.1就是他们家题库上的原题
: ，剩下的除了2之外都是leetcode的上原题。
:
: 绍-
| g**4
发帖数: 863 | 8 glassdoor
【在 b**********i 的大作中提到】
: 恕我孤陋寡闻，Amazon还有题库？可以分享一下吗？
| q****x
发帖数: 7404 | 9 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 的大作中提到】
: 上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
: 1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
: 式为(时间 访问者ID 访问网页)
: 每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
: 的log也不一定在一个文件里.
:
: 问:
: 用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
: >另一个产品->.....), 针对每一串 访问序列,仅取前三个网页组成一个三元组(如上
: 面的例子,就是<主页,某搜索页面,某产品页面>), 统计TOP K 的三元组.
| q****x
发帖数: 7404 | 10 edit distance也在leetcode上？够狠。
【在 g**4 的大作中提到】
: 先感谢下LZ！
: 然后再打击下LZ，LZ肯定没好好准备面试，第1题，3.1和4.1就是他们家题库上的原题
: ，剩下的除了2之外都是leetcode的上原题。
:
: 绍-
| | | b*******g
发帖数: 57 | 11 4.2不是edit distance,是word ladder I | x****m
发帖数: 1084 | 12 感觉都是常规题目吧
【在 b*******g 的大作中提到】
: 4.2不是edit distance,是word ladder I
| q****m
发帖数: 177 | 13 第一题中，访问序列没给吧，是不是需要从log里面得出？ log里面的每个记录里面只
有一个网页地址吧，如何由那些记录找出访问序列感觉不好搞啊。或者我理解错了
绍-
【在 t*********2 的大作中提到】
: 上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
: 1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
: 式为(时间 访问者ID 访问网页)
: 每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
: 的log也不一定在一个文件里.
:
: 问:
: 用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
: >另一个产品->.....), 针对每一串 访问序列,仅取前三个网页组成一个三元组(如上
: 面的例子,就是<主页,某搜索页面,某产品页面>), 统计TOP K 的三元组.
| w****i
发帖数: 17 | 14 希望有大牛详述下第一题思路啊，最近好多人面试到。只是看Map/reduce的文章还是不
大明白T_T | s******d
发帖数: 424 | 15 非牛，没做过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******d
发帖数: 424 | 16 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******d
发帖数: 424 | 17 有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******d
发帖数: 424 | 18 有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 | f*******r
发帖数: 976 | |
|
