一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3320|回复: 28
收起左侧

Google电面挂经 + 求助

[复制链接] |试试Instant~ |关注本帖
user123456 发表于 2016-3-29 08:13:05 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1个小时前结束的电面,开始时问了两次他的名字,仍然没有听清,只能作罢。

就问了句:你是PhD是吧,我说是ECE的PhD,然后就直接开始coding

题目是: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给你两个文件f1和f2,f1是10M的量级,f2是10G的量级。f1的每一行有三个东西:str1, str2, ratio,ratio代表str1和str2的比值,示例:
  1. A, B, 0.5         // 解释:A / B = 0.5
  2. A, E, 2.3         // 解释:A / E = 2.3
  3. C, E, 1.5         // 解释:C / E = 1.5. 1point3acres.com/bbs
  4. C, D, 1.0         // 解释:C / D = 1.0
  5. ...
复制代码
f2的每一行只存了str1, str2,示例:
  1. C, B
  2. A, D
  3. ...
复制代码
需要返回一个新的文件叫f3,f3是在f2的基础上更新,并且和f1的格式一样,即你需要算出f2中每一行两个string的ratio,比如上面的例子的话,就是返回下面这样:
  1. C, B, 0.33     // 即:C / B = C/E * E/A * A/B = 1.5*1/2.3*0.5 = 0.33
  2. A, D, 1.53     // 即:A / D = A/E * E/C * C/D = 2.3*1/1.5*1 = 1.53
复制代码
电面具体结果:. 鍥磋鎴戜滑@1point 3 acres
他出完题目后,问我有什么想法,我说用Map<Key1, Map<Key2, Ratio>>来存遍历f1后的关系。然后他想了会,给出了一个反例,说你后来求ratio的时候会进入死循环,就好比 A -> B -> C -> A这样。我说这种情况下可以backtrack。他好像有些听不下去了,说你有没有想到什么data structure。我才反应过来是f1遍历后实际形成了一个类似于weighted graph,每个node存他的邻居和他与邻居间的ratio。然后他问:那怎么求两个node之间的ratio呢?我说类似于shortest path。然后他说用什么algorithm呢?我说用DFS,BFS应该都可以。然后告诉他BFS的思路:从sourceNode开始每层每层地走,更新对每个邻居的ratio,直到抵达targetNode。然后他说你可以写代码了。

然后就是最悲剧的事情了:先想着怎么定义这个Graph的Node就想了半天,后来才想到每个Node有一个name和adj的Map,adj的Map存的是邻居Node -> ratio的映射

然后思路和他说了:
先遍历f1,创建这个graph // 这个方法思路说了下,代码写完了,但肯定有错。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后遍历f2,对每一行的两个node(一个是sourceNode,另一个是targetNode)进行一个bfs找到ratio,加到f3里面。但这里写代码完全卡壳。直到时间到了也没有理顺。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

目测肯定是挂了,但想问下,这种情况怎么样向HR要求加面会增加被电面的可能性呢?-google 1point3acres

真诚感各位!







补充内容 (2016-3-29 08:15):
更准确地说不是weighted graph,只不过node的adj里面除了存node外,还要存一个ratio而以,所以为什么BFS就行,而不需要用bellman ford / dijkstra 之类的东西

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴补充内容 (2016-4-2 04:26):
. 1point 3acres 璁哄潧今天HR告诉我加面,可能面试官没有fail我

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
omega094 发表于 2016-9-12 09:40:42 | 显示全部楼层
leetcode 399 . more info on 1point3acres.com
ORZ...ORZ....ORZ
回复 支持 1 反对 0

使用道具 举报

ScottShao 发表于 2016-4-2 06:18:32 | 显示全部楼层
bless 楼主

我也觉得union find应该比较好做:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可以分成两步:
union:
需要三个数据结构:
Edge: src, dest, ratio. from: 1point3acres.com/bbs
HashSet<Edge>:从点到其root的dest,key是src和dest
HashMap<Node, Set<Node>>:点和他的root集,因为某个点可能有很多root,比如说A——C,B——C,c的root就是a和b
然后复杂度是O(n^2)-google 1point3acres
find:
直接在HashSet里面找就可以,总复杂度是O(N)
回复 支持 1 反对 0

使用道具 举报

 楼主| user123456 发表于 2016-3-29 08:15:09 | 显示全部楼层
更准确地说不是weighted graph,只不过node的adj里面除了存node外,还要存一个ratio而以,所以为什么BFS就行,而不需要用bellman ford / dijkstra 之类的东西
回复 支持 反对

使用道具 举报

ruokua 发表于 2016-3-29 09:05:18 | 显示全部楼层
Map<Key1, Map<Key2, Ratio>> 没什么不对啊
这其实就是一个graph
Key 1 means start point
Key 2 means end point
ratio is cost of path
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
A -> B -> C -> A 这种情况 保留一个set 看 是否visit 过就可以了吗
回复 支持 反对

使用道具 举报

yuan311 发表于 2016-3-29 09:15:10 | 显示全部楼层
F2 需要的path在f1中一定存在吗?F1和F2的量级的差别有什么说法?
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-3-29 09:15:48 | 显示全部楼层
ruokua 发表于 2016-3-29 09:05
Map 没什么不对啊
这其实就是一个graph
Key 1 means start point

具体就不知道了。我说这个说了半天,他后来让我换思路,于是就到了graph
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-3-29 09:18:59 | 显示全部楼层
yuan311 发表于 2016-3-29 09:15
F2 需要的path在f1中一定存在吗?F1和F2的量级的差别有什么说法?

不一定存在,如果两个Node没有连接,他让在两个Node后面写x

量级的差别的话,我的理解是,在你遍历f2的过程中,需要不断给graph添加edge,这样越到后面,BFS的时候越快
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-3-29 09:45:54 | 显示全部楼层
求助:这种情况怎么样向HR要求加面会增加被电面的可能性呢?
回复 支持 反对

使用道具 举报

waikai 发表于 2016-3-29 10:14:10 | 显示全部楼层
好详实的面经。谢谢lz。
我有一些其他思路,但没有具体码出来。先抛砖引玉了。
首先可以对f1做Union Find。比如在f1中,从A点出发可以到达的点都在UnionA中, 所以可以自己写一个数据结构。和楼主的

Map<Key1, Map<Key2, Ratio>>类似。A{A, 1}即A点在集合A中,到A的R是1。只要任意一点X也在集合A中我们在处理f1文件是就算出他到A的R。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
所以处理f2时候,就不用BFS,而是直接看点是否在一个集合中。如果在则直接R * 1/R。所以时间复杂度为O(1)。如果不在一个集合中,就为X。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-3-29 13:10:01 | 显示全部楼层
按照图这个搞,45分钟写完还真不容易。。。
不过就是用图,还是得用map. more info on 1point3acres.com
bless lz!
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-3-29 14:03:56 | 显示全部楼层
处理完f1后应该要根据graph来建立一个HashMap来存任意两个string的ratio吧,比如HashMap<pair<str1, str2>, ratio>, 这样在处理f2时就能做到O(1),速度就会快很多。这个hashMap跟LZ说的Map<Key1, Map<Key2, Ratio>>类似。
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-3-29 19:18:37 | 显示全部楼层
店面面这个 感觉好难啊。。。
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-3-29 20:48:31 | 显示全部楼层
这题是不是用有向图的bfs就可以解决了? 举个例子,比如说Given A, B, 0.5,就可以建立一条边A->B,权重是0.5; 另一条边B->A,权重是1/0.5。以此类推,然后比如要求C,B,的那个ratio,其实就是等价于以C为起点,B为终点经过的所有路径权重的乘积。
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-3-29 23:20:29 | 显示全部楼层
yueliu2366 发表于 2016-3-29 20:48. more info on 1point3acres.com
这题是不是用有向图的bfs就可以解决了? 举个例子,比如说Given A, B, 0.5,就可以建立一条边A->B,权重是0.5 ...

有向图 + BFS可行。但在推进的过程中,除了需要像普通的BFS需要存一个queue和一个visited的标记外,visited标记不能存成set,因为层层推进的过程中,每一个node的ratio都有不同的值,所以visited要存成map。

昨天后来又写了下这个题目,算是写出来了,没有真正地创建graph,而是将每一个Node存在一个Map<String, Map<String, Double>>里面

为了提高效率,在BFS的过程中,可以进行类似Union Find的path compression操作,就是将root和所有中间经过的node都connect起来,让graph越来越接近complete

另外union find应该也可以解这个题
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-3-29 23:22:51 | 显示全部楼层
waikai 发表于 2016-3-29 10:14
好详实的面经。谢谢lz。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我有一些其他思路,但没有具体码出来。先抛砖引玉了。
首先可以对f1做Union Find ...

嗯,Union Find做这个题是比较好的,尤其是在告知f2比较大的时候.鏈枃鍘熷垱鑷1point3acres璁哄潧

我后来自己写的是在BFS的过程中不断地connect从root到每一个level经过的node,让这个graph更加complete,相当于进行了UF的path compression
回复 支持 反对

使用道具 举报

simplessssss 发表于 2016-4-1 10:52:40 | 显示全部楼层
lz最后怎么,有要到加面的机会吗?
回复 支持 反对

使用道具 举报

dimi 发表于 2016-4-1 10:54:57 | 显示全部楼层
仔細想想這題目不難。bfs+backtracking
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-4-1 23:16:13 | 显示全部楼层
[quote][url=forum.php?mod=redirect

bfs的话不需要backtrack
回复 支持 反对

使用道具 举报

 楼主| user123456 发表于 2016-4-1 23:16:38 | 显示全部楼层
[quote][url=forum.php?mod=redirect

还没有消息
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 01:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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