一亩三分地论坛

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

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

Google面经1029

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

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

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

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

x
电面:最长连续数字串

onsite1:两个等长度string S T, swap S里的一对字符让两个string的海明距离最少。 四个点判断是否正方形(思路不用code)。a的b次方模p。
2:3 sum smaller  这轮只面了30分钟因为第一轮进去时间晚了面的时间长了再加上我没刷这题中间脑抽卡了很久。
午饭和黑哥们聊天根本没心思吃。他教育我如果发现别人干活都比自己快那么一定要放平心态。
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 | 显示全部楼层
最後一題我只能想到O(n^2)的解法:每週去更新該office的最大可能假期數. from: 1point3acres.com/bbs
譬如說,在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 | 显示全部楼层
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][:]
  9.       for destIdx in xrange(len(distances)):
  10.         if distances[officeIdx][destIdx] > k:
  11.           lastWk[destIdx] = 0
  12. . more info on 1point3acres.com
  13.       vacations[wk][officeIdx] += max(lastWk)

  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;
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. From 1point 3acres bbs

max = max{dp[0]~dp[n-1]}
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2015-11-12 01:52):
这个recurrence看起来如何, .1point3acres缃
dp[j] = max {dp[i-1][h]} + V[j] { 0<=h<=n and T[h][j] < k}

补充内容 (2015-11-12 01:54):
论坛自动过滤。。我擦
回复 支持 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!

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

使用道具 举报

小小平民 发表于 2015-11-12 01:21:17 | 显示全部楼层
第三题不是很清楚。 求的是什么最短距离?从start到end?  跳跃机会是可以翻墙?还是只是连走两部ground?
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 假期是否相同呢

补充内容 (2015-11-12 01:36):
同一个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. more info on 1point3acres.com
请问LZ能再详细说下第3题吗?

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

使用道具 举报

cc11328 发表于 2015-11-12 05:16:55 | 显示全部楼层
  1. #include <iostream>
  2. #include <vector>. from: 1point3acres.com/bbs
  3. #include <unordered_map>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4. using namespace std;
  5. pair<int,int> minDistance(string s,string t){. From 1point 3acres bbs
  6.     pair<int,int> dis1 = {-1,-1};
  7.     pair<int,int> dis2 = {-1,-1};
  8.     unordered_map<char,vector<int>> record_s;
  9.     unordered_map<char,vector<int>> record_t;
  10.     for(int i = 0; i < s.size(); i++) {
  11.         if(s[i] != t[i]) {. 鍥磋鎴戜滑@1point 3 acres
  12.             record_s[s[i]].push_back(i);-google 1point3acres
  13.             record_t[t[i]].push_back(i);
  14.             if(record_t.find(s[i]) != record_t.end()){
  15.                 if(dis1 == make_pair(-1, -1)) {. 1point 3acres 璁哄潧
  16.                     dis1 = {record_t[s[i]][0], i};
  17.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.                 for(int j = 0; j < record_t[s[i]].size(); j++) {
  19.                     if(s[record_t[s[i]][j]] == t[i]) {
  20.                         dis2 = {record_t[s[i]][j],i};
  21.                         return dis2;
  22.                     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24.             }
  25.             if(record_s.find(t[i]) != record_s.end()){
  26.                 if(dis1 == make_pair(-1, -1)) {
  27.                     dis1 = {record_s[t[i]][0], i};. more info on 1point3acres.com
  28.                 }. 鍥磋鎴戜滑@1point 3 acres
  29.                 for(int j = 0; j < record_s[t[i]].size(); j++) {
  30.                     if(t[record_s[t[i]][j]] == s[i]) {
  31.                         dis2 = {record_s[t[i]][j],i};
  32.                         return dis2;
  33.                     }-google 1point3acres
  34.                 }
  35.             }. more info on 1point3acres.com
  36.         }
  37.     }
  38.     return dis1;
  39. }
  40. int main() {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  41.         //code
  42.         string t = "abcbf";
  43.         string s = "aabcf";
  44.         pair<int,int> res = minDistance(s,t);
  45.         cout << res.first << " " << res.second;
  46.         return 0;
  47. }
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 14:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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