一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2129|回复: 43
收起左侧

狗家Fall Intern电面

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

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

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

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

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

File 2:
USD, EUR
Yard, Meter

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

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

评分

1

查看全部评分

zhangsikai123 发表于 2017-7-13 10:26:55 | 显示全部楼层
第二题个人感觉应该属于人工智能领域的CSP问题,类似八皇后问题,本身是NP-hard,但也有很多优化方法,这里感觉考官就是靠暴力的backtracking吧?
但是似乎也可以用 Bottom-up 的DP解,如果没错的话应该是n的三次方:
n = word.length
Let M[ ] [ ]  be a 2-D share matrix with shape of (n,n)  
For i = 0 to n:
        set = [ ]
        for dice in all dices:
                if dice has char[ i ]
                set.append( {dices-dice} ) (one possible state after crossing this one ). from: 1point3acres.com/bbs
         if set.isEmpty():.1point3acres缃
                return "don’t exist!"
                m[ i ][ i ] = set
For offset = 0 to n-1:
        for i = 0 to n - offset:
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴                j = i + offset
                //fill M[ i ][ j ]:
                for dice_set in M[ i+1 ][ j ]:
                        keep_dice_set = false
                        for dice in dice_set:
                                if dice has char[ i ]
                                remove this dice from this dice_set. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                keep_dice_set = true // this state is possible
                                if char[ i ] is last char:
                                        return “Yes, there exits!”  //goal test
                                break
                        if keep_dice_set is false:
                                remove this dice_set  (the state is impossible or unsatisfactory). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                for dice_set in M[ i ][ j-1 ]:
                        do the same as M[ i+1 ][ j ] case
                M[ i ][ j ] =  Natural join(M[ i+1 ][ j ], M[ i ][ j-1 ] )
                If M [ i ][ j ] is an empty set:. visit 1point3acres.com for more.
                        return  “don’t exists!”-google 1point3acres
return “don’t exits” // the algorithm will probably never reach this line

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| catherineycycy 发表于 2017-6-30 08:00:00 | 显示全部楼层
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长度。. 1point 3acres 璁哄潧

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

然后S和T构成一个二分图,求得这个二分图的最大匹配数为W,那么结果“是否可以由这些骰子摇出”等价于(W == word长度)。. Waral 鍗氬鏈夋洿澶氭枃绔,
.1point3acres缃
这种图论题目确实很难(而且工作中没用),自己去想基本上只能弄出来指数级的穷举方法,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. From 1point 3acres bbs
这还要考文件操作??
. From 1point 3acres bbs
我当时一听也是懵,文件操作不是重点考察应该
回复 支持 反对

使用道具 举报

 楼主| 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^ ...
. From 1point 3acres bbs
谢谢,分析的很好,但是楼主说了一个条件,“但骰子数量可以很多”,那是不是说每一种骰子有任意多个?如果每种只有一个,是二分图匹配,否则的话,就是普通的简单题目吧。
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| catherineycycy 发表于 2017-7-12 05:43:18 | 显示全部楼层
knight0clk 发表于 2017-7-11 12:37
请问下,第一题楼主怎么做的?对于每个pair,然后搜索找到答案?感觉这个速度比较慢吧,有什么更好的办法吗 ...

我前面read file纠结了比较久,后来在面试官提示下用DFS,最后并没有来得及讨论时间复杂度和更好的办法
回复 支持 反对

使用道具 举报

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

使用道具 举报

knight0clk 发表于 2017-7-12 12:25:15 | 显示全部楼层
catherineycycy 发表于 2017-7-12 05:43
我前面read file纠结了比较久,后来在面试官提示下用DFS,最后并没有来得及讨论时间复杂度和更好的办法

OK。谢谢楼主!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-11 08:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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