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


一亩三分地论坛

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

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

狗家Fall Intern电面

[复制链接] |试试Instant~ |关注本帖
catherineycycy 发表于 2017-6-30 07:12:16 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
保持队形再来贡献一个面经。
6月28号面的,刚好赶上他们mountain view的有很多人据说组织去游乐场玩了大概这是为啥面我的都是两个纽约的白人妹子。
第一面是read two files. 1point3acres.com/bbs
File 1:
USD, GBP, ...
Meter, Yard, ...
YEN, EUR, ...
GBP, YEN, ...

File 2:
USD, EUR.鐣欏璁哄潧-涓浜-涓夊垎鍦
Yard, Meter

第一个file中...是汇率数字,我不记得具体多少了用这个表示一下,而且不止这么多,会有很多不同的单位之间的转换。然后要求output一个file,计算第二个file中给出的单位之间从第一个到第二个的汇率数。. more info on 1point3acres.com

第二面是给a list of dices, 每个骰子不是用数字表示,而是用字母,相当于给一个list的包含六个各种字母的String,然后再给一个target word,判断这个word是否可以由这些骰子摇出,要求不能两个或两个字母以上由同一个骰子出来,但骰子数量可以很多,骰子上字母可以是任意字母,重复也行。
. 鍥磋鎴戜滑@1point 3 acres

评分

1

查看全部评分

zhengwei 发表于 2017-6-30 07:50:24 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
请问第二题roll到char的顺序有关系吗?比如第一个拿到的字母需要是target word的开始的第一个char
回复 支持 反对

使用道具 举报

 楼主| catherineycycy 发表于 2017-6-30 08:00:00 | 显示全部楼层
关注一亩三分地微博:
Warald
zhengwei 发表于 2017-6-30 07:50
请问第二题roll到char的顺序有关系吗?比如第一个拿到的字母需要是target word的开始的第一个char

顺序没有关系,一个骰子只能roll一个字母,只要能roll到这个target word就行
回复 支持 反对

使用道具 举报

kiddyym 发表于 2017-7-6 00:41:37 | 显示全部楼层
这么难的题,摸摸头~~~
回复 支持 反对

使用道具 举报

331412073 发表于 2017-7-6 01:16:42 | 显示全部楼层
楼主你做过coding sample么。。过了多久收到电面邮件?。。我等了一星期了,估计GG了。
回复 支持 反对

使用道具 举报

wxl3691 发表于 2017-7-6 01:19:12 | 显示全部楼层
这还要考文件操作??
回复 支持 反对

使用道具 举报

magicsets 发表于 2017-7-6 02:55:03 | 显示全部楼层
第二个问题本质上是求二分图的最大匹配... 算法是“匈牙利算法”或者网络流的”最大流算法“,复杂度是O(V^3),V = dices数量 + word长度。

具体来说就是建立两个节点集合S和T,word中每个字母为S中一个节点,每个dice为T中一个节点,然后对于任意节点s∈S,t∈T,s与t之间建立一条边当且仅当dice t包含字母s。

然后S和T构成一个二分图,求得这个二分图的最大匹配数为W,那么结果“是否可以由这些骰子摇出”等价于(W == word长度)。. visit 1point3acres.com for more.

这种图论题目确实很难(而且工作中没用),自己去想基本上只能弄出来指数级的穷举方法,leetcode上好像也是没有的,一些学校的算法课程会在最后一两章讲网络流。
回复 支持 反对

使用道具 举报

jinxihexi0411 发表于 2017-7-6 03:16:45 | 显示全部楼层
第二题有什么思路吗?
回复 支持 反对

使用道具 举报

 楼主| catherineycycy 发表于 2017-7-6 04:45:23 | 显示全部楼层
331412073 发表于 2017-7-6 01:16
楼主你做过coding sample么。。过了多久收到电面邮件?。。我等了一星期了,估计GG了。

我做完coding sample第二天一早就收到约电面的邮件了,那时候是六月初了,现在可能时间有点晚了,你再等等
回复 支持 反对

使用道具 举报

 楼主| catherineycycy 发表于 2017-7-6 04:46:08 | 显示全部楼层
wxl3691 发表于 2017-7-6 01:19
这还要考文件操作??

我当时一听也是懵,文件操作不是重点考察应该
回复 支持 反对

使用道具 举报

 楼主| catherineycycy 发表于 2017-7-6 05:05:41 | 显示全部楼层
jinxihexi0411 发表于 2017-7-6 03:16 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二题有什么思路吗?

见楼上大神~
回复 支持 反对

使用道具 举报

david.fang 发表于 2017-7-6 05:47:29 | 显示全部楼层
楼主po个代码呀?好难哦。。。
回复 支持 反对

使用道具 举报

 楼主| catherineycycy 发表于 2017-7-7 07:02:09 | 显示全部楼层
david.fang 发表于 2017-7-6 05:47
楼主po个代码呀?好难哦。。。

我也觉得很难。。。
回复 支持 反对

使用道具 举报

knight0clk 发表于 2017-7-11 12:24:26 | 显示全部楼层
问下,楼主当时把第二题A掉了?
回复 支持 反对

使用道具 举报

knight0clk 发表于 2017-7-11 12:27:29 | 显示全部楼层
magicsets 发表于 2017-7-6 02:55
第二个问题本质上是求二分图的最大匹配... 算法是“匈牙利算法”或者网络流的”最大流算法“,复杂度是O(V^ ...

谢谢,分析的很好,但是楼主说了一个条件,“但骰子数量可以很多”,那是不是说每一种骰子有任意多个?如果每种只有一个,是二分图匹配,否则的话,就是普通的简单题目吧。
回复 支持 反对

使用道具 举报

knight0clk 发表于 2017-7-11 12:37:59 | 显示全部楼层
请问下,第一题楼主怎么做的?对于每个pair,然后搜索找到答案?感觉这个速度比较慢吧,有什么更好的办法吗?弗洛伊德?
回复 支持 反对

使用道具 举报

 楼主| catherineycycy 发表于 2017-7-12 05:43:18 | 显示全部楼层
knight0clk 发表于 2017-7-11 12:37
请问下,第一题楼主怎么做的?对于每个pair,然后搜索找到答案?感觉这个速度比较慢吧,有什么更好的办法吗 ...
. more info on 1point3acres.com
我前面read file纠结了比较久,后来在面试官提示下用DFS,最后并没有来得及讨论时间复杂度和更好的办法
回复 支持 反对

使用道具 举报

vegito2002 发表于 2017-7-12 11:20:53 | 显示全部楼层
秋季 intern 的题居然也这么难, 摸摸
回复 支持 反对

使用道具 举报

knight0clk 发表于 2017-7-12 12:25:15 | 显示全部楼层
catherineycycy 发表于 2017-7-12 05:43. visit 1point3acres.com for more.
我前面read file纠结了比较久,后来在面试官提示下用DFS,最后并没有来得及讨论时间复杂度和更好的办法
.鏈枃鍘熷垱鑷1point3acres璁哄潧
OK。谢谢楼主!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 01:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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