G家onsite

一共四轮：
第一轮，一个泰国小哥，deep copy一个无向图成有向图，方向是从value小的node指向value大的
第二轮，一个中国姐

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

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

dit distance变种，change的cost是2，delete和insert是1

frank11118 发表于 2016-8-21 06:40
求問二題二問解法

比如 “aaaaaaaaa” (9a) 对映的 failure function是 0, 0, 1, 2, 3, 4, 5, 6, 7, 8  (10个 第一个 默认为0)
然后 len － 8 ＝ 1  就是 最小的 循环的 单位，9 ／ 1 ＝ 9 可以 拆分成 3 ＊ 3 所以 最后 应该是 3 个 ‘aaa’

比如 “abcabcabcabcabcabc” （6abc） 对映的 failure function 是 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, ..., 15
所以 len － 15 ＝ 3 就是 最小 循环单位，18 ／ 3 ＝ 6 ＝ 2 ＊ 3 额们 取3按 倍数乘3 所以是 2 ＊ 9
就是 2个 abcabcabc

say543 发表于 2016-8-26 12:47
感觉是一个BFS 加上visited array 就搞定?

是的~~~~~~~~~~

求周长的，大家看呢？
public class Color{
final static int[] move=new int[]{0,-1,0,1,0};
Pair{
  int i;
  int j;
  Pair(int i, int j){
    this.i=i;
    this.j=j;
  }
}

public int find(int[][] color, int i, int j){
Queue<Pair> q=new Queue<>();
Set<Pair> set=new HashSet<>();
set.add(new Pair(i,j));
q.add(new Pair(i,j));
int res=0;
while(!q.isEmpty()){
  Pair cur=q.peek();
  for(int i=0;i<4;i++){
    int x=cur.x+move[i];
    int y=cur.y+move[i+1];
  if(x<0 || x>=color.length) res++;
  else if(y<0 || y>=color[0].length) res++;
  else if(color[i][j]!=color[x][y]) res++;
  else {
    Pair newP=new Pair(x,y);
    if(!set.contains(newP))
    q.push(new Pair(x,y));
  }
  }
}
return res;
}

}

第二题需要kmp算法吗？

第三题是max square的变种吗

1370786136.1.3 发表于 2016-8-20 07:34
第三题是number of islands 的变形吗？改成求岛的周长了？

dfs发现颜色不对直接加一

1. 暴力？
2. KMP ? KMP? size(string) - KMP最后一位的值是最小循环节 如果循环的话？
3. bfs ?
4. dp ?

taobingxue 发表于 2016-8-20 12:40
1. 暴力？
2. KMP ? KMP? size(string) - KMP最后一位的值是最小循环节 如果循环的话？
3. bfs ?

2题 2问 用 kmp的 点子 不错

补充内容 (2016-8-20 15:47):
要得到解 应该还得 求 小于 len ／ 最小循环长度 的 prime

补充内容 (2016-8-21 07:41):
上面 说的 prime 不对，， 应该是 看能不能 拆分成 除了 1 ＊ 自己 以外的 两个数乘积 然后 取较大的

第一题 也该就和 clone graph 一样吧
就是 判断一下 给不给 加边就 可以了

3 题 之前有过类似的 面经 块的边长是 4 所以 bfs  有相邻的 减掉
公共边

larry_cn 发表于 2016-8-20 14:56
2题 2问 用 kmp的 点子 不错

补充内容 (2016-8-20 15:47):

求問二題二問解法