Google 国内 电面 肉身翻墙

楼主的室友，今天早上电话面试了Google，结果还没有出来，由于室友使用了我的地里账号，所以，我要把他电面题目发出来了。
这个题目大家可以参考  Leetcode 305 Number of Islands II， 岛屿是动态变化的。然后输出岛屿的数量。最优的解是使用并查集。

简单贴一下楼主刷题的时候写的代码吧，由于是加锁的题目，楼主并没有对代码做完全的测试，仅仅使用了若干例子而已，仅供参考。

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

祝大家好运！

import java.util.LinkedList;

import java.util.List;

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;

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

>[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];

       }

}

zkern 发表于 2016-7-29 04:59
这道题有两个Followe up：. From 1point 3acres bbs
  其一是，在leetcode islandII上支持undo操作，. 涓

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感谢分享

看来disjoint set很重要。我前同事去年11月电面就是这题，还要能删除（回退）的。当时leetcode上还没这题。他用BFS做的，挂了。。。感觉像被黑了一样。

adrian_yang84 发表于 2016-7-29 14:52
看来disjoint set很重要。我前同事去年11月电面就是这题，还要能删除（回退）的。当时leetcode上还没这题。 ...

嗯，Google 喜欢dp的题，还有一些高端一点的数据结构的题

日乐购了。
google apac test过了而且无电面onsite。。
indeed居然电面挂了。。

这道题有两个Followe up：
  其一是，在leetcode islandII上支持undo操作，
其二是支持修改任意点的值

zkern 发表于 2016-7-29 17:55
日乐购了。
google apac test过了而且无电面onsite。。
indeed居然电面挂了。。

这个好悲，有时候运气很开玩笑，很随机

zkern 发表于 2016-7-29 04:59
这道题有两个Followe up：
  其一是，在leetcode islandII上支持undo操作，
其二是支持修改任意点的值

请问支持undo是怎样做呢？

楼主您好，请问apac test多少名次才能拿到电面呀，谢谢

a27400 发表于 2016-7-30 02:08
楼主您好，请问apac test多少名次才能拿到电面呀，谢谢

我快300了，就没有，我室友比我高50左右