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


一亩三分地论坛

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

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

Google面经1029

[复制链接] |试试Instant~ |关注本帖
740919074 发表于 2015-11-11 23:48:54 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
电面:最长连续数字串

onsite1:两个等长度string S T, swap S里的一对字符让两个string的海明距离最少。 四个点判断是否正方形(思路不用code)。a的b次方模p。
2:3 sum smaller  这轮只面了30分钟因为第一轮进去时间晚了面的时间长了再加上我没刷这题中间脑抽卡了很久。
午饭和黑哥们聊天根本没心思吃。他教育我如果发现别人干活都比自己快那么一定要放平心态。. 1point3acres.com/bbs
3:一个二维矩阵,有start,end,wall,ground。可以一次走一步,n次机会跳跃机会可以隔一个跳一个。不都走或者跳到墙。求最短步数。本来想用曼哈顿距离做heuristic function用A*结果好像不可以因为这题用曼哈顿距离不是consistent的。小哥挺好的说不确定可不可以然后是否有一种search肯定对我说bfs他说对写bfs吧。。。
4:公司有很多office,你可以每周末飞到别的office。只有在比某个数字小的hours内能飞到才可以飞。每个office有很多假期。怎样获得一年内最多的假期。(这轮印度小哥好像很不想让我读懂题似的不往板上写然后信息都是挤牙膏问出来。然后还迟到了十几分钟因为他迷路了最后没时间写剪枝。)

听天由命估计今明两天就出结果了。

评分

7

查看全部评分

本帖被以下淘专辑推荐:

zatarratw 发表于 2015-11-12 05:43:06 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
最後一題我只能想到O(n^2)的解法:每週去更新該office的最大可能假期數
譬如說,在wk i+1,traveler待在office j可以得到的累計最大假期數為 vacations[j][i+1] + max(vacations[x][i] if hour[x][j] < k else 0)
這樣算下去,更新每週的累計數需要O(n^2),總共有52周,所以是O(52 * n ^ 2) = O(n^2)
回复 支持 5 反对 0

使用道具 举报

zatarratw 发表于 2016-2-6 08:32:00 | 显示全部楼层
关注一亩三分地微博:
Warald
codes不知道為啥不見了...
  1. xVacations(vacations, distances, k):
  2.   if len(vacations) == 0 or len(vacations[0]) == 0:
  3.     return 0
  4.   if len(distances) == 0 or len(distances[0]) == 0:
  5.     return 0

  6.   for wk in xrange(1, len(vacations)):
  7.     for officeIdx in xrange(len(distances)):
  8.       lastWk = vacations[wk-1][:]. more info on 1point3acres.com
  9.       for destIdx in xrange(len(distances)):
  10.         if distances[officeIdx][destIdx] > k:
  11.           lastWk[destIdx] = 0

  12.       vacations[wk][officeIdx] += max(lastWk)

  13. -google 1point3acres
  14.   return max(vacations[-1])
复制代码

补充内容 (2016-2-6 08:32):
開頭是 def maxVacations(vacations, distances, k):
回复 支持 1 反对 0

使用道具 举报

marthew777 发表于 2015-11-12 01:41:32 | 显示全部楼层
最后一题,假设不同星期,同一个office假期一样,我们可以用greedy solve 吗?用dp保存计算的结果
Assuming we have total of m weeks, n offices;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴dp[j] : total num of vocations by i weeks, and on week i stay at office j;. 1point 3acres 璁哄潧
V[j] : vocation at office j
T[j] : flight time from office i to j, T[j] = T[j]

dp[j] = dp[i-1][j] + max{V[j]} where T[j] < k hours

max = max{dp[0]~dp[n-1]}

补充内容 (2015-11-12 01:52):
这个recurrence看起来如何,
dp[j] = max {dp[i-1][h]} + V[j] { 0<=h<=n and T[h][j] < k}

补充内容 (2015-11-12 01:54):. from: 1point3acres.com/bbs
论坛自动过滤。。我擦
回复 支持 0 反对 1

使用道具 举报

fatalme 发表于 2015-11-12 01:15:39 | 显示全部楼层
最后一题啥意思?听起来像jumping game.
回复 支持 反对

使用道具 举报

小小平民 发表于 2015-11-12 01:18:12 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

小小平民 发表于 2015-11-12 01:18:56 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!. from: 1point3acres.com/bbs
. From 1point 3acres bbs
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

小小平民 发表于 2015-11-12 01:21:17 | 显示全部楼层
第三题不是很清楚。 求的是什么最短距离?从start到end?  跳跃机会是可以翻墙?还是只是连走两部ground?. 1point3acres.com/bbs
BFS怎样记录使用了几次跳跃啊
回复 支持 反对

使用道具 举报

 楼主| 740919074 发表于 2015-11-12 01:21:32 | 显示全部楼层
fatalme 发表于 2015-11-12 01:15
最后一题啥意思?听起来像jumping game.

就是每周都在一个office然后这个office会有几个假期在这一周里。然后周末可以去另一个office或者留在这然后看下一周能拿到几个假期。
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-12 01:25:47 | 显示全部楼层
多谢分享。。请问最后一题的每个Office 假期是否相同呢. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point 3acres 璁哄潧
补充内容 (2015-11-12 01:36):.1point3acres缃
同一个office,不同星期的假期会不一样咩?
回复 支持 反对

使用道具 举报

@南岸的风 发表于 2015-11-12 01:37:00 | 显示全部楼层
请问楼主怎么知道两天内有结果的呢?
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-11-12 01:41:31 | 显示全部楼层
略囧…1029面的到现在还没结果啊…
回复 支持 反对

使用道具 举报

liruoyuxgd2006 发表于 2015-11-12 01:43:14 | 显示全部楼层
最后一道题听起来像DP,LZ,迟到了难道不给延时吗?这么mean?
回复 支持 反对

使用道具 举报

 楼主| 740919074 发表于 2015-11-12 02:36:26 | 显示全部楼层
更新:已被拒
回复 支持 反对

使用道具 举报

 楼主| 740919074 发表于 2015-11-12 02:36:50 | 显示全部楼层
liruoyuxgd2006 发表于 2015-11-12 01:43
最后一道题听起来像DP,LZ,迟到了难道不给延时吗?这么mean?

因为下面有人reserve房间。。
回复 支持 反对

使用道具 举报

 楼主| 740919074 发表于 2015-11-12 02:37:46 | 显示全部楼层
孤笑客 发表于 2015-11-12 01:41
略囧…1029面的到现在还没结果啊…

刚出。。当时说两周出结果。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 03:15:05 | 显示全部楼层
liruoyuxgd2006 发表于 2015-11-12 01:43. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
最后一道题听起来像DP,LZ,迟到了难道不给延时吗?这么mean?

请问DP是什么思路呢?我现在只想到DFS把所有可能性找出来然后找出假期最多的那个。。。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 03:15:56 | 显示全部楼层
请问LZ能再详细说下第3题吗?
回复 支持 反对

使用道具 举报

 楼主| 740919074 发表于 2015-11-12 03:27:19 | 显示全部楼层
最后一题每周不是固定日子假期。我用的bfs,从第一周开始把上周每个可能的office都展开然后记录到当前有多少假期,然后可以剪枝比如A和B都可以飞到C那么下一层C只留着最大的就行。在最后一层找最大值。
悲剧说是我数据结构太弱。不知道这几个题是不是可以用啥高级数据结构解。
回复 支持 反对

使用道具 举报

 楼主| 740919074 发表于 2015-11-12 03:31:07 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-12 03:15
请问LZ能再详细说下第3题吗?

就是找到start然后bfs,每个位置有八个neighbor,四个走过去的四个跳过去的,然后如果是墙就continue。跳过去的要记录用了一次跳跃。所以在search tree里面每个node存的信息要有步数,还剩下的jump机会,位置。
回复 支持 反对

使用道具 举报

头像被屏蔽
cc11328 发表于 2015-11-12 05:16:55 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| 740919074 发表于 2015-11-12 05:36:59 | 显示全部楼层

忘了说了要O(n)time。我一开始也说char后面跟set然后他要On改成key是一个string了, char pair
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-27 15:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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