一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
把贵司信息放这里
查看: 2755|回复: 29
收起左侧

狗家新鲜面经

[复制链接] |试试Instant~ |美国面经, 面试经验, 码农类general, google
我的人缘0

分享帖子到朋友圈
lyt.tim | 显示全部楼层 |阅读模式
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (10)
 
 
0% (0)    👎

2019(10-12月) 码农类General 博士 全职@Google - 内推 - 技术电面  | Fail/Rej | fresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
Google 新鲜面镜:

左边有一点集M,右边有一点集N。从M往N连线,每条线有不同的权值。要求M所有的点必须与N相连,N所有的点必须与M相连,并且总权值
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
里各位大神指点。。顺求大米看面经。。


评分

参与人数 7大米 +15 收起 理由
small_pupple + 1 很有用的信息!
xiaobai123 + 1 给你点个赞!
AliceLin2019 + 2 给你点个赞!
StupidCorn + 1 给你点个赞!
reliveinfire + 2 给你点个赞!
清道神君 + 5
uestchx1 + 3 很有用的信息!

查看全部评分


上一篇:HRT Summer Intern OA
下一篇:亚麻实习新鲜oa2面经

本帖被以下淘专辑推荐:

  • · google|主题: 191, 订阅: 109
我的人缘0
波风水门 2019-11-12 15:27:03 | 显示全部楼层
本楼: 👍   80% (4)
 
 
20% (1)   👎
全局: 👍   90% (166)
 
 
9% (18)    👎
感觉这道题并没有适用于面试的多项式复杂度的算法,贪心一定是错的,楼里也有人给出反例了。这题也不是什么匈牙利算法什么匹配,因为每个点可以连向另一侧不止一个点。

一种可行的方法是状态压缩动态规划。用 f[mask][j] 表示左侧已经被连过的节点的情况为 mask(长度为 M 的二进制数,0 表示未连,1 表示已连),右侧前 j 个节点已经被连过的最小花费,状态转移有下面几种情况:

1. j 是从左侧 mask 中的某个 1 连过来的,那么 f[mask][j] = f[mask][j - 1] + cost[j],其中 mask & (1 << i) != 0;
2. j 连向了左侧 mask 中若干个之前为 0 的位置,因为它们连向了 j,所以从 0 变成了 1,那么 f[mask][j] = f[mask'][j - 1] + sum(cost[j]),其中 mask' 是 mask 的子集(即 mask' & mask = mask'),i 是所有在 mask 但不在 mask' 中的位置。

时间复杂度大概是 O(3^M * N),因为枚举子集的时间复杂度是 O(3^M),动态规划中 j 也贡献了 O(N)。

补充内容 (2019-11-13 03:58):
@peter666 的贪心也是错误的,考虑权值矩阵[[4 3 4][7 5 8][4 6 6]],他给的贪心会依次选取权值为3 4 4 4 5的五条边,并且从后向前遍历没有多余的边可以去掉,但实际上我们只要选取第i行第i列的三条边 4 5 6 即可。

补充内容 (2019-11-13 04:00):
我还想说一句,大家讨论问题就好好讨论,我没搞懂给我的楼踩一脚是什么意思,如果你觉得我提出的算法不对,你大可以直接回复我。我认真思考写个做法被你踩一脚,你觉得我以后还会在地里写东西么。

补充内容 (2019-11-13 04:04):
第一条补充内容里面有点小笔误。在从后向前遍历时,会去掉权值为 3 的这条多余边,剩下的权值总和为 4+4+4+5=17,但仍然没有直接选择 4 5 6 优。
回复

使用道具 举报

我的人缘0
本楼: 👍   60% (3)
 
 
40% (2)   👎
全局: 👍   88% (16)
 
 
11% (2)    👎
可以把所有m到n的edge放到list 或者heap里sort,每次取最小的,同时把两边的点放在一个visited set 当中,知道所有的点都被visited O(nlogn),n是所有edge的数量

评分

参与人数 2大米 +6 收起 理由
codeyy + 1 赞一个
清道神君 + 5

查看全部评分

回复

使用道具 举报

我的人缘0
peter666 2019-11-12 10:59:52 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   95% (20)
 
 
4% (1)    👎
有一个方法, 首先sort edges, 然后traverse 每个edge, 如果edge相连的node都没有被连过,那么就记下这个edge(List<Edge> 来存), 同时两个node 相连node数各加1 (nodes[] 来记录),最后从后向前遍历得到的List<Edges>,  把多余的edge去掉(多余的edge就是相连的两个node 都有连着大于1个其他node)。 比如左面有3两个点(1,2,3) 右边有3个点(a,b,c) 1 -> a = 1, 2 -> a = 1, 3 -> a = 1, 3 -> b = 10, 3 -> c = 10, 1 -> b = 100, 1 -> c = 100, 2 -> b = 100, 2-> c = 100, 我们就可以去掉多余的3 -> a。

感觉解法还是很怪,不确定能不能行。

补充内容 (2019-11-12 17:22):
说的不太清楚, 应该是edge 相连的node 不是两个都已经被连结过,加到list中..如果两个都没被连,或其中一个没被连,都加到list.
回复

使用道具 举报

我的人缘0
oney 2019-11-11 03:41:04 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   98% (71)
 
 
1% (1)    👎
用dijkstra's algorithm变体来解?
首先加一个dummy node连接所有M的点(edges' weights为0)
然后一直拓展直到连接N的所有点 (连到N其中一点 那这个点往后当然就不需要处理)
正确性证明是
对于任一Ni点 这个方法找到的都是对所有Mi来说 能连到Ni的最短路径
回复

使用道具 举报

我的人缘0
codyman 2019-11-13 11:52:33 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   85% (405)
 
 
14% (67)    👎
这题不就是求MST吗?UF完事儿
回复

使用道具 举报

我的人缘0
波风水门 2019-11-13 13:06:45 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   90% (166)
 
 
9% (18)    👎
lightwings 发表于 2019-11-13 04:24
多谢给出解法!我有一个疑问,为什么枚举子集的时间复杂度是O(3^M)而不是O(2^M)?

这里的 O(3^M) 是枚举所有二进制表示(即 00...00 ~ 11...11)的子集的总复杂度。

M 位的二进制表示中,包含 k 个 1 的表示有 C(M, k) 个,其中 C 表示组合数。每一个包含 k 个 1 的表示都有 2^k 个子集,因此所有的 M 位的二进制表示一共包含 sigma(k=0..M)(C(M, k) * 2^k) 个子集,这个恰好是 (2+1)^M = 3^M 的二项式展开。
回复

使用道具 举报

我的人缘0
fatalme 2019-11-12 18:45:06 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   61% (19)
 
 
38% (12)    👎
https://en.wikipedia.org/wiki/Edge_cover

A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all vertices are covered.[1][2]
回复

使用道具 举报

我的人缘0
smallpig1988 2019-11-12 13:09:42 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
本帖最后由 smallpig1988 于 2019-11-12 14:03 编辑
落落落 发表于 2019-11-10 17:21
可以把所有m到n的edge放到list 或者heap里sort,每次取最小的,同时把两边的点放在一个visited set 当中, ...

这个方法感觉是greedy貌似不太work。如果edge cost:00,01,10,11=3,5,1,2。那么它会visit 10,11,00才把两边都visit完,cost=1+2+3=6。最优应是visit 00,11, cost=5。感觉做法和campus2一样,只是可以重复assign。 具体的,heap里放(cost,i(M的序号),state(N的visit情况mask)),只不过不需要check node j in N是否已被taken。return cost if i == M and state == 2**N-1. 注意和campus2不一样,visited里要放(i,state)才行,因为这里给了state不能唯一确定i。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (51)
 
 
0% (0)    👎
感觉是max flow变种
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   73% (19)
 
 
26% (7)    👎
N 集合内点都不准连接 还是可以连有权值 minimum spanning tree

补充内容 (2019-11-10 01:33):
应该是纯点集 好吧
回复

使用道具 举报

我的人缘0
烟雨秋枫 2019-11-11 09:20:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
这道题是不是 利口 campus 2呢?
回复

使用道具 举报

我的人缘0
Judy_922 2019-11-11 09:36:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (49)
 
 
0% (0)    👎
全职电面还开着的么。。。
回复

使用道具 举报

我的人缘0
yiliaobailiao 2019-11-11 10:01:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (178)
 
 
6% (13)    👎
烟雨秋枫 发表于 2019-11-11 09:20
这道题是不是 利口 campus 2呢?

是变种吧,不完全一样。那个自行车的数量是多于人的,不需要把自行车都分完。
回复

使用道具 举报

我的人缘0
peter666 2019-11-12 10:52:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (20)
 
 
4% (1)    👎
oney 发表于 2019-11-11 03:41
用dijkstra's algorithm变体来解?
首先加一个dummy node连接所有M的点(edges' weights为0)
然后一直拓展 ...

不太明白楼主的做法,这个图的最长路径就是2(不加dummy node 的话就是1) 感觉不是dijkstra's 的题。然后,比如左面有3两个点(1,2,3) 右边有3个点(a,b,c) 1 -> a = 1, 2 -> a = 1, 3 -> a = 1, 3 -> b = 10, 3 -> c = 10, 1 -> b = 100, 1 -> c = 100, 2 -> b = 100, 2-> c = 100  其按照dijstra会找到前5个路径,但其实3 -> a 是多余的,请问dijkstra怎么解决这一问题
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-12-12 06:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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