一亩三分地论坛

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

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

Google MV onsite 面经

[复制链接] |试试Instant~ |关注本帖
shenglee282 发表于 2015-11-19 13:03:26 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
总共四轮:

1) LC原题(#286 walls and gates),只不过换成博物馆里有小偷和艺术品.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2)若有一排N个位子,上面已坐了一些人,假设已坐的旁边不能再坐人,问最多还可以再坐进多少人
.鐣欏璁哄潧-涓浜-涓夊垎鍦
3)问一些过去的工作经验以及一些Java基本问题(因为履历有写) 如List.addAll是否为deep copy, inheritance,map要怎么一边read一边加或删, 如果用for/while会有什么结果。有问如何做的distributed运算然后问了3Sum smaller

4)假设有很多台机器有一个website,要怎么样利用多台机器去crawl 这个website所有links

大米了谢谢@@~ 
希望面经对大家有些帮助
ps LZ下星期还有一个大的interview再加上上班很忙若没能及时回覆恳请见谅. 1point 3acres 璁哄潧

评分

5

查看全部评分

本帖被以下淘专辑推荐:

杰西Jesse 发表于 2015-11-25 05:22:32 | 显示全部楼层
杰西Jesse 发表于 2015-11-25 04:32
感觉不用吧。。。这不就扫一遍,然后如果找到中间的length,这个interval能坐的人不就是ceil((length-2)/ ...
  1. public class ArrangeSeat{. from: 1point3acres.com/bbs
  2.         public int populate(boolean [] seats){
  3.                 int num = 0;
  4.                 int start = 0;
  5.                 while(start < seats.length && seats[start]==false)
  6.                         start++;
  7.                 num += start / 2;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.                 int end = start+1;-google 1point3acres
  9.                 while(end < seats.length){
  10.                         if(seats[end]==false)
  11.                                 end++;
  12.                         else{
  13.                                 num += Math.max(0,(end-start-2)/2);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.                                 start = end;
  15.                                 end++;
  16.                         }
  17.                 }
  18.                 num += Math.max(0,(end-start-2)/2);
  19.                 return num;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.         }
  21.         public static void main(String args[]){
  22.                 ArrangeSeat as = new ArrangeSeat();
  23.                 boolean [] seats = new boolean [15];
  24.                 seats[2] = true;
  25.                 seats[3] = true;
  26.                 System.out.println(as.populate(seats));
  27.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28. }
复制代码
回复 支持 1 反对 0

使用道具 举报

queeniejing 发表于 2015-11-19 14:31:12 | 显示全部楼层
谢谢LZ分享, 请问下第四题怎么答呢? 用BFS 吗
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-19 14:38:13 | 显示全部楼层
请问第二题能详细说一下吗?
回复 支持 反对

使用道具 举报

say543 发表于 2015-11-23 15:36:28 | 显示全部楼层
LZ第二题感觉可以可以用dp 来解? 考虑邻接不座人和给定的seat arrangement 来找optimum 来做?
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-11-25 04:32:49 | 显示全部楼层
say543 发表于 2015-11-23 15:36
LZ第二题感觉可以可以用dp 来解? 考虑邻接不座人和给定的seat arrangement 来找optimum 来做?

感觉不用吧。。。这不就扫一遍,然后如果找到中间的length,这个interval能坐的人不就是ceil((length-2)/2)么?
xoox-> 0
xooox->1
xoooox->1
xooooox -> 2
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

bobzhang2004 发表于 2015-12-2 06:40:46 来自手机 | 显示全部楼层
请问第四题要代码吗?还是就是mapreduce
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-2 13:10:02 | 显示全部楼层

这个代码有问题吧,只考虑了--11----的这种情况,而没有考虑 --11---111----111---的这些情况,(-代表空位置,1代表有人)。. visit 1point3acres.com for more.

补充内容 (2015-12-2 13:11):.1point3acres缃
开始没看懂,应该是对的,请无视评论
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-2 14:08:57 | 显示全部楼层
杰西Jesse 发表于 2015-11-25 04:32. Waral 鍗氬鏈夋洿澶氭枃绔,
感觉不用吧。。。这不就扫一遍,然后如果找到中间的length,这个interval能坐的人不就是ceil((length-2)/ ...

你说的这个情况是两头坐人中间全部空着吧?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
题目的意思我猜是给一个数组 有一些位置有人,比如
x 0 0 x 0 0 0 0 x x 0
类似如此,
应该还是要DP吧
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-12-2 16:33:54 | 显示全部楼层
yjfox 发表于 2015-12-2 14:08
你说的这个情况是两头坐人中间全部空着吧?
题目的意思我猜是给一个数组 有一些位置有人,比如
x 0 0 x ...
-google 1point3acres
不用DP,就按杰西Jesse说的,每扫到一个interval结算一次就可以了,需要处理一些base case。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-3 00:07:59 | 显示全部楼层
yjfox 发表于 2015-12-2 14:08
你说的这个情况是两头坐人中间全部空着吧?
题目的意思我猜是给一个数组 有一些位置有人,比如
x 0 0 x ...

不需要吧,Jesse的代码应该是对的,我测试了一下,稍微改了下,变成一个while循环
  1.         public int populate1(boolean[] seats) {
  2.                 int num = 0;. 鍥磋鎴戜滑@1point 3 acres
  3.                 int start = -1;
  4.                 int end = 0;
  5.                 while (end < seats.length) {. 1point3acres.com/bbs
  6.                         if (seats[end] == false) {
  7.                                 end++;
  8.                         } else {
  9.                                 if (start == -1) {
  10.                                         num += Math.max(0, (end - start - 1) / 2);
  11.                                 } else {
  12.                                         num += Math.max(0, (end - start - 2) / 2);
  13.                                 }
  14.                                 start = end;
  15.                                 end++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.                         }
  17.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.                 num += Math.max(0, (end - start - 2) / 2);
  19.                 return num;
  20.         }
复制代码
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-3 00:13:15 | 显示全部楼层
面假空虚 发表于 2015-12-2 16:33
不用DP,就按杰西Jesse说的,每扫到一个interval结算一次就可以了,需要处理一些base case。

you are right, 谢谢提醒!
回复 支持 反对

使用道具 举报

lfenjoy9 发表于 2016-1-16 04:46:30 | 显示全部楼层
bless 楼主拿个大offer
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-27 08:53:06 | 显示全部楼层
请问第四题面试官有给什么hint吗?
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-4-13 08:20:59 | 显示全部楼层
map要怎么一边read一边加或删, 如果用for/while会有什么结果? 这个怎么回答
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-4-13 09:09:42 | 显示全部楼层
我觉得那个排椅子的,就是lc抢劫那题的变形啊。先把已经坐人的和他们的左右邻座都mark成不能坐的比如inf。然后剩下的空座位就是抢劫那个题的变形,只不过每次经历了一串inf后,第一次可以坐的座位用的前边最大,选取的是前一段的max。
回复 支持 反对

使用道具 举报

superbeet 发表于 2016-4-18 13:10:31 | 显示全部楼层
kittycerry 发表于 2016-4-13 09:09
我觉得那个排椅子的,就是lc抢劫那题的变形啊。先把已经坐人的和他们的左右邻座都mark成不能坐的比如inf。 ...

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴这题之所以不用用DP原因就是因为不存在house rob里面每个房子金钱不同的这个因素,每个椅子相当于是等价的,这就变成贪心算法了。所以扫面一遍就可以了。
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-4-19 00:13:45 | 显示全部楼层
同问: map要怎么一边read一边加或删, 如果用for/while会有什么结果 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-4-19 01:35:52 | 显示全部楼层
第二题的DP解法,不知道有没有bug。优化一下也能到O(1) memory usage.

int count(vector<int>nums) {
    int size = nums.size();
    vector<int> dp(size+3, 0);. from: 1point3acres.com/bbs
    for(int i = 0; i < nums.size(); ++i) {
        if (nums[i]) {
            dp[i+3] = dp[i+1];
        } else {
            if (i > 0 && nums[i-1])
                dp[i+3] = dp[i];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            else
                dp[i+3] = std::max(dp[i+2], dp[i+1] + 1);   
        }
    }    .鏈枃鍘熷垱鑷1point3acres璁哄潧
    return dp[size+2];
}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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