推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1640|回复: 27
收起左侧

玄学昂赛跪经,攒人品为下一次

[复制链接] |试试Instant~ |关注本帖
dwiller 发表于 2017-6-23 04:59:40 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Amazon - 猎头 - Onsite |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
5月底做完OA得到了onsite机会,一共四轮, OA是base ball和根据array建立BST,onsite完了后一周内收到拒信:
每轮都是先15分钟左右的BQ,然后就是算法设计啥的:
1. Hiring Manager, 算法题,numbers of island小变种,求所有岛屿的最大值,依然是DFS增加一个全局的max值标识即可;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
2. Other team member,系统设计,设计chat system,其中问到太大并发和局部异常如何处理,如何能够精确找到对方,聊的过程中忘了分析在线和不在线的情况怎么处理了;.鏈枃鍘熷垱鑷1point3acres璁哄潧
3. Other team member,OOD,餐馆预定座位,设计了customer,restaurant, table类,在面试官提示下补上了reservation类(最关键的类没第一时间说出),用的command pattern; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
4. Team member, 算法题, 判断一个graph是否是n-ary tree,bi 这道题没见过,和面试官讨论了一下思路也没理清,一开始把所有grpah的点和其关联点用hashmap存了,然后遍历出每个点去判断是否有环,dfs去判断是否n-ary tree,后来照着自己写的东西给面试官讲的时候就发现走不通,应该先找到root点,然后判断,而且图的表示法应该用adjacent table,这轮应该是失败的。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Amazon|主题: 85, 订阅: 33
mchzh 发表于 2017-6-23 06:04:42 | 显示全部楼层
bless,onsite考的比较全面,不能有弱的地方,最后一个算法题在google怎么也搜不到
回复 支持 反对

使用道具 举报

 楼主| dwiller 发表于 2017-6-23 07:13:01 | 显示全部楼层
mchzh 发表于 2017-6-23 06:04
bless,onsite考的比较全面,不能有弱的地方,最后一个算法题在google怎么也搜不到
. From 1point 3acres bbs
这题短时间内我也想不明白,自己猜想是挂这题上了,不过也不知道其他三轮有问题没
回复 支持 反对

使用道具 举报

701chang 发表于 2017-6-23 09:48:57 | 显示全部楼层
最后一题应该bfs做吧。。?判断每个父节点的子节点数是否不大于N
回复 支持 反对

使用道具 举报

helloterran 发表于 2017-6-23 22:39:59 来自手机 | 显示全部楼层
是无向图吗?

如果是树状结构,从任何一个点出发都是树状结构阿


先dfs判断无环,然后有一点连通度<=n,其他点连通度<n+1就可以了吧
. From 1point 3acres bbs
补充内容 (2017-6-24 01:21):
所有非叶子节点中,至少一点连通度<=n, 其他点连通度<=n+1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

 楼主| dwiller 发表于 2017-6-24 01:15:16 | 显示全部楼层
701chang 发表于 2017-6-23 09:48
最后一题应该bfs做吧。。?判断每个父节点的子节点数是否不大于N

bfs应该是也能做,我当时脑子里只有dfs的概念,根本没有很清楚的思路去想到bfs
回复 支持 反对

使用道具 举报

 楼主| dwiller 发表于 2017-6-24 01:23:04 | 显示全部楼层
helloterran 发表于 2017-6-23 22:39
是无向图吗?

如果是树状结构,从任何一个点出发都是树状结构阿
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
因为拿到题我没思路,所以我就没想到问有向图还是无向图,现在回想起来应该是无向图,因为有向图就更难了吧。首先对图如何表示我的概念不清楚,导致后面的分析也没有章法
回复 支持 反对

使用道具 举报

 楼主| dwiller 发表于 2017-6-24 01:24:02 | 显示全部楼层
helloterran 发表于 2017-6-23 22:39.1point3acres缃
是无向图吗?

如果是树状结构,从任何一个点出发都是树状结构阿

dfs怎么判断无向图无环?
回复 支持 反对

使用道具 举报

helloterran 发表于 2017-6-24 01:32:23 | 显示全部楼层
dwiller 发表于 2017-6-24 01:24
dfs怎么判断无向图无环?

每个edge用两条边表示,dfs每前进一步就标记visited v,删除刚经过的边。如果是联通的有环无向图,一定会回到某个之前已经visited的v上
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-6-24 02:13:09 | 显示全部楼层
helloterran 发表于 2017-6-24 01:32
每个edge用两条边表示,dfs每前进一步就标记visited v,删除刚经过的边。如果是联通的有环无向图,一定会 ...

那图用的什么表示法?不是adjacent tables吧是叫什么边十字星啥的?
回复 支持 反对

使用道具 举报

helloterran 发表于 2017-6-24 03:06:50 | 显示全部楼层
mchzh 发表于 2017-6-24 02:13
那图用的什么表示法?不是adjacent tables吧是叫什么边十字星啥的?

写了一个2 scan的解法,应该有bug,大家来找茬啊
  1. bool isNAryTree(vector<pair<int, int> edges>){
  2.         unordered_map<int, unordered_set<int>> graph
  3.         for (auto p : edges) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.           graph[p.first].insert(p.second);
  5.           graph[p.second].insert(p.first);
  6.         }

  7.         bool hasRoot;
  8.         for (auto v : graph){
  9.           if (v.second.size()) > n+1)
  10.                 return false;
  11.           else if (v.second.size() <= n ) {
  12.                 if (v.second.size() > 1){
  13.                         hasRoot = true;
  14.                 }
  15.           }
  16.         }
  17.        
  18.         unordered_set<int> visited(graph.size(), false);
  19.         return (hasRoot && !(hasLoop(graph.begin().first, graph, visited));. more info on 1point3acres.com
  20. }

  21. bool hasLoop (int v, unordered_map<int, unordered_set<int>> &graph, unordered_set<int> &visited) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.         visited.insert(v);
  23.         for (auto n : graph[v]) {
  24.                 graph[n].erase(v);
  25.                 if (visited.count(n) || hasLoop(n, graph, visited) ) {. 1point 3acres 璁哄潧
  26.                         return true;
  27.                 }
  28.         }
  29.         return false;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码

补充内容 (2017-6-24 04:09):
上面的代码假定这个图是全联通的。否则的话hasLoop还得负责递归退出以后得数visited 节点的数量。
回复 支持 反对

使用道具 举报

helloterran 发表于 2017-6-24 03:08:45 | 显示全部楼层
另外,玄学是哪个公司啊?
回复 支持 反对

使用道具 举报

 楼主| dwiller 发表于 2017-6-24 03:26:55 | 显示全部楼层
helloterran 发表于 2017-6-24 03:08. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外,玄学是哪个公司啊?

亚麻,层主是哪个公司的?
回复 支持 反对

使用道具 举报

 楼主| dwiller 发表于 2017-6-24 03:27:46 | 显示全部楼层
helloterran 发表于 2017-6-24 03:06
写了一个2 scan的解法,应该有bug,大家来找茬啊
-google 1point3acres
graph是用二维数据表示?
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2017-6-24 05:06:25 | 显示全部楼层
为什么楼主没有manager单独面BQ的一轮呢
回复 支持 反对

使用道具 举报

 楼主| dwiller 发表于 2017-6-24 05:21:17 | 显示全部楼层
cgxy1991 发表于 2017-6-24 05:06
为什么楼主没有manager单独面BQ的一轮呢

不知道欸,manager第一轮就来了,还介绍他们是干什么,我听得也晕的m乎的,我感觉第一轮的manager对我印象还可以,BQ了二十多分钟,然后就是上的island的题目
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-6-24 05:22:49 | 显示全部楼层
cgxy1991 发表于 2017-6-24 05:06-google 1point3acres
为什么楼主没有manager单独面BQ的一轮呢

难道是所有面试官都给过,manager才会单独面一轮BQ?
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2017-6-24 05:42:12 | 显示全部楼层
mchzh 发表于 2017-6-24 05:22
难道是所有面试官都给过,manager才会单独面一轮BQ?
. visit 1point3acres.com for more.
不可能那么快出结果吧,我记得有些人是面5轮。4论技术,一轮纯BQ
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-6-24 05:49:16 | 显示全部楼层
cgxy1991 发表于 2017-6-24 05:42
不可能那么快出结果吧,我记得有些人是面5轮。4论技术,一轮纯BQ
.1point3acres缃
估计是面试官不够用,给整合了一轮
回复 支持 反对

使用道具 举报

cgxy1991 发表于 2017-6-24 06:36:14 | 显示全部楼层
mchzh 发表于 2017-6-24 05:49
估计是面试官不够用,给整合了一轮
. From 1point 3acres bbs
如果是的话,那还真是运气好,否则一轮BQ真是会死
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-24 09:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表