[Google SDE5 面经2022]

为什么是2轮design，一开始是target l6吗？

您好！
本帖隐藏的内容需要积分高于 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

您好！
本帖隐藏的内容需要积分高于 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

匿名用户 发表于 2022-6-21 21:23
就借鉴N-Queen， 一个一个放， 递归+backtrack。 找到第一个解就return。 每个位置选宝石的时候用个随机 ...

应该没有更好的办法了，这里不知道3个连续的是指行和列嘛，还是对角线也算

求指正

1. public int[][] generateMaze(int m, int n, int k) {
   
2.         int[][] res = new int[m][n];
   
3.         Random rand = new Random();
   
4.         if (canMaze(res, 0, k, rand)) {
   
5.             return res;
   
6.         }
   
7.         return new int[m][n];
   
8.     }
   
9. 
   
10.     private boolean canMaze(int[][] res, int index, int k, Random rand) {
    
11.         int m = res.length;
    
12.         int n = res[0].length;
    
13.         if (index == m * n) {
    
14.             return true;
    
15.         }
    
16.         int i = index / n;
    
17.         int j = index % n;
    
18.         int color = rand.nextInt(k);
    
19.         while ((i >= 2 && res[i - 2][j] == color && res[i - 1][j] == color) ||
    
20.                 (j >= 2 && res[i][j - 2] == color && res[i][j - 1] == color)) {
    
21.            color = rand.nextInt(k);
    
22.         }
    
23. 
    
24.         res[i][j] = color;
    
25.         if (canMaze(res, index + 1, k, rand)) {
    
26.             return true;
    
27.         }
    
28.         return false;
    
29.     }

复制代码

rekoko555 发表于 2022-6-23 09:33
好像不用backtrack？每次放的时候确定是valid再放下去，不valid再随机选一个，到最后应当是valid，直接re ...

那如果K很小，然后你到了一个地方，发现所有的选项都无法满足要求呢>.<
所以还是要backtrack

匿名用户 发表于 2022-6-24 14:15
1. 可以简单得把10T的数据当成是key-value 的格式。 找出这里面出现频次最高的100 个key。 可以重复读取 ...

请问输入是stream吗，如果是file可能没法依一来就按key shard吧？

rekoko555 发表于 2022-06-23 06:33:11
好像不用backtrack？每次放的时候确定是valid再放下去，不valid再随机选一个，到最后应当是valid，直接return
好像string with k characters apart

某些分支会走到死胡同的，当然要backtrack