一亩三分地论坛

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

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

Google 国内 电面 肉身翻墙

[复制链接] |试试Instant~ |关注本帖
qiangJi 发表于 2016-7-29 11:02:02 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Google - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
楼主的室友,今天早上电话面试了Google,结果还没有出来,由于室友使用了我的地里账号,所以,我要把他电面题目发出来了。
这个题目大家可以参考  Leetcode 305 Number of Islands II, 岛屿是动态变化的。然后输出岛屿的数量。最优的解是使用并查集。
. From 1point 3acres bbs
简单贴一下楼主刷题的时候写的代码吧,由于是加锁的题目,楼主并没有对代码做完全的测试,仅仅使用了若干例子而已,仅供参考。

不过由于楼主上次Google在线笔试排名靠后,并没有拿到这次电面的机会。还好,Indeed电面过了,有需要的可以参考我写的Indeed skype面试篇。

祝大家好运!


import java.util.LinkedList;
import java.util.List;
. from: 1point3acres.com/bbs
public class NumberofIslandsII305 {
      
      
      public static void main(String[] args) {
            
            NumberofIslandsII305 nsss = new NumberofIslandsII305();
             int m =3;
             int n = 3;
             int[][]positions = {{0,0},{0,1},{1,2},{2,1}};
            System. out.println(nsss.numIslands2(m, n, positions));
      }
       int []uniset ;
       int []weight ;
       public List<Integer> numIslands2( int m, int n, int[][] positions) {
             List<Integer> ans = new LinkedList<>();
             if(m == 0 || n==0) return ans;
             int size = m*n;
             uniset = new int[m*n];
             weight = new int[m*n]; // 用于记录每个树中节点的数量
            
             for( int i =0;i<size;i++){
                   uniset = i; // 每个节点初始都是孤立的
             }
             int [][]dirs = {{1,0},{-1,0},{0,-1},{0,1}};
             int count = 0;
             for( int []pos:positions){ // 处理每个节点
                   int index = pos[0]*n + pos[1];
                   // index已经在集合中,无序处理了,这个可能是有重复的输入造成的。
                   if( uniset[index] != index){
                         ans.add(count);
                         continue;
                   }
                   // 如果输入没有重复,那么每次新加入的点都是一个新的island,需要和其上下左右合并
                   // 首先count++,weight[index]++; 表明这是一棵新树。
                   count++;
                   weight[index]++;
                   for( int []oneDir:dirs){
                         int newx = pos[0] + oneDir[0];
                         int newy = pos[1] + oneDir[1];
                         if(newx < 0 || newy< 0 || newx > m-1 || newy > n-1)continue;
                         int newindex = newx*n + newy;
                         if( weight[newindex] < 1) continue; // 这一句忘了。只有当weight大于0的时候,说明这棵树是已经存在的。
                         if(!isConnected(newindex,index)){ // 集合不相交
                              union(newindex,index);
                              count--;
                         }
                   }
                   ans.add(count);
             }
             return ans;
       }
      
       // 合并两个集合
       void union(int x,int y){
             int fx = findFather(x);
             int fy = findFather(y);
             if(fx == fy ) return;
             if( weight[fx] < weight[fy]){
                   uniset[fx] = fy;
                   weight[fy]+= weight[fx];
             } else{
                   uniset[fy] = fx;
                   weight[fx] += weight[fy];
             }
       }
       boolean isConnected( int x, int y){
             return findFather(x) == findFather(y);
       }
       // 带压缩,这里使用递归,也可以首先找到根,然后重新遍历一遍,重置其为根。
       int findFather( int x){
             if( uniset[x] == x) return x;
             uniset[x] = findFather( uniset[x]);
             return uniset[x];
       }
}

评分

1

查看全部评分

adrian_yang84 发表于 2016-7-29 14:52:50 | 显示全部楼层
看来disjoint set很重要。我前同事去年11月电面就是这题,还要能删除(回退)的。当时leetcode上还没这题。他用BFS做的,挂了。。。感觉像被黑了一样。
回复 支持 反对

使用道具 举报

 楼主| qiangJi 发表于 2016-7-29 15:35:45 | 显示全部楼层
adrian_yang84 发表于 2016-7-29 14:52
看来disjoint set很重要。我前同事去年11月电面就是这题,还要能删除(回退)的。当时leetcode上还没这题。 ...

嗯,Google 喜欢dp的题,还有一些高端一点的数据结构的题
回复 支持 反对

使用道具 举报

zkern 发表于 2016-7-29 17:55:57 | 显示全部楼层
日乐购了。
google apac test过了而且无电面onsite。。
indeed居然电面挂了。。
回复 支持 反对

使用道具 举报

zkern 发表于 2016-7-29 17:59:28 | 显示全部楼层
这道题有两个Followe up:
  其一是,在leetcode islandII上支持undo操作,
其二是支持修改任意点的值
回复 支持 反对

使用道具 举报

 楼主| qiangJi 发表于 2016-7-29 22:25:51 | 显示全部楼层
zkern 发表于 2016-7-29 17:55
日乐购了。
google apac test过了而且无电面onsite。。
indeed居然电面挂了。。

这个好悲,有时候运气很开玩笑,很随机
回复 支持 反对

使用道具 举报

wzs9988 发表于 2016-7-30 01:12:37 | 显示全部楼层
zkern 发表于 2016-7-29 04:59
这道题有两个Followe up:
  其一是,在leetcode islandII上支持undo操作,
其二是支持修改任意点的值

请问支持undo是怎样做呢?
回复 支持 反对

使用道具 举报

a27400 发表于 2016-7-30 02:08:27 | 显示全部楼层
楼主您好,请问apac test多少名次才能拿到电面呀,谢谢
回复 支持 反对

使用道具 举报

 楼主| qiangJi 发表于 2016-7-30 10:06:08 | 显示全部楼层
a27400 发表于 2016-7-30 02:08
楼主您好,请问apac test多少名次才能拿到电面呀,谢谢

我快300了,就没有,我室友比我高50左右
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-7-30 10:30:41 | 显示全部楼层
上下左右找邻居那行, 忘记判断是不是陆地了,  position[newx][newy] ==1?
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-7-30 11:41:38 | 显示全部楼层
zkern 发表于 2016-7-29 04:59
这道题有两个Followe up:. From 1point 3acres bbs
  其一是,在leetcode islandII上支持undo操作,. 涓
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-7-30 11:42:54 | 显示全部楼层
lvvvvv 发表于 2016-7-30 10:30-google 1point3acres
上下左右找邻居那行, 忘记判断是不是陆地了,  position[newx][newy] ==1?

网站回复有问题,

同问, 网上找的都看不懂, 比如:
http://blog.csdn.net/a181551981/article/details/6286007

回复 支持 反对

使用道具 举报

a27400 发表于 2016-7-30 12:52:01 | 显示全部楼层
qiangJi 发表于 2016-7-30 10:06. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我快300了,就没有,我室友比我高50左右

好的!多谢楼主!^^
回复 支持 反对

使用道具 举报

wenzhu 发表于 2016-7-30 14:13:43 | 显示全部楼层
qiangJi 发表于 2016-7-30 10:06
我快300了,就没有,我室友比我高50左右

打听几个问题哈..请问国内流程是怎样的呀?这个 test 多长时间有一次呢..题目有几个,难度如何这样子~谢谢啦
回复 支持 反对

使用道具 举报

 楼主| qiangJi 发表于 2016-7-30 20:30:34 | 显示全部楼层
wenzhu 发表于 2016-7-30 14:13
打听几个问题哈..请问国内流程是怎样的呀?这个 test 多长时间有一次呢..题目有几个,难度如何这样子~谢 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
国内就是参加在线机试,在一定名次的,Google会给你发邮件,问你是否想参加面试,如果想,你要填写一些信息,然后就会联系你,然后就电面面试。至于难度,当然是很难了,Leetcode hard的难度。
回复 支持 反对

使用道具 举报

wenzhu 发表于 2016-8-1 02:20:49 | 显示全部楼层
qiangJi 发表于 2016-7-30 20:30
国内就是参加在线机试,在一定名次的,Google会给你发邮件,问你是否想参加面试,如果想,你要填写一些信 ...

简历呢是直接投给 google 美国还是天朝的 google 呀?天朝 google 貌似只有很小的部门了..?
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-8-1 11:26:25 | 显示全部楼层
zkern 发表于 2016-7-29 17:59. From 1point 3acres bbs
这道题有两个Followe up: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  其一是,在leetcode islandII上支持undo操作,. Waral 鍗氬鏈夋洿澶氭枃绔,
其二是支持修改任意点的值

第一个follow up,undo的话,就相当于一步一步逆回去,这个改下并查集就可以做。
第二个,支持修改任意点的值。相当于删除了,这个还用并查集做么?我原来查过一篇论文,讲并查集删除的,非常复杂。这个是不是直接用BFS更好一点呢?
回复 支持 反对

使用道具 举报

wzs9988 发表于 2016-8-2 09:19:15 | 显示全部楼层
adrian_yang84 发表于 2016-7-31 22:26
第一个follow up,undo的话,就相当于一步一步逆回去,这个改下并查集就可以做。
第二个,支持修改任意 ...

第一个follow up,undo能稍微展开讲讲么…… 不是太懂。如何一步一步逆回去呢?谢谢
回复 支持 反对

使用道具 举报

zkern 发表于 2016-8-5 18:13:09 | 显示全部楼层
wzs9988 发表于 2016-8-2 09:19. from: 1point3acres.com/bbs
第一个follow up,undo能稍微展开讲讲么…… 不是太懂。如何一步一步逆回去呢?谢谢

用可持久化数组可以实现回溯,修改任意值可以找论文dynamic graph 方面的,有点像冰茶几,我也不会
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 04:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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