qualtrics 面筋

Qualtrics 4 轮
1. 幺儿起
2. 岛数量加最大岛面积加最大有宝藏的岛面

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

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

reasing path. 起点和终点不定

第三道题是一个图的遍历。dfs，bfs，unionfind都可解。那个半径指的是曼哈顿距离，对吧？

补充内容 (2019-10-26 07:38):
不同地雷的半径可能不一样。两个区间的重叠部分没必要再判断了。不知道有没有优化的算法

第四道，好像力扣有原题。是一个拓扑排序，对吧

codeyy 发表于 2019-10-26 15:34
第三道题是一个图的遍历。dfs，bfs，unionfind都可解。那个半径指的是曼哈顿距离，对吧？

补充内容 (2019- ...

Union Find不行，UnionFind你只能找到最大能炸多少个，但是你找不到应该第一个炸哪个

lz 第三四题可以再多解释一下吗

请问楼主有收到什么update吗？

楼主最大宝藏能多讲一下吗？还有后两道题有没有比较好的思路？

感觉楼主你考得蛮难的。

第四题有点像LeetCode 329

写了一下最大宝藏的那题，在返回值里加了一个boolean判断当前岛有没有宝藏在传回来，因为java不允许一次return多个值，就改成return object。不知道有没有更加优雅的办法。

1. public class MaxAreaWithTreasure {
   
2.     int[][] DIRS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   
3. 
   
4.     class Island {
   
5.         int num;
   
6.         boolean hasTreature;
   
7. 
   
8.         public Island(int num, boolean hasTreature) {
   
9.             this.num = num;
   
10.             this.hasTreature = hasTreature;
    
11.         }
    
12.     }
    
13. 
    
14.     private int solution(int[][] grid) {
    
15.         int res = 0;
    
16.         for (int i = 0; i < grid.length; i++) {
    
17.             for (int j = 0; j < grid[0].length; j++) {
    
18.                 Island cur = helper(grid, i, j);
    
19.                 if (cur.hasTreature) {
    
20.                     res = Math.max(res, cur.num);
    
21.                 }
    
22.             }
    
23.         }
    
24. 
    
25.         return res;
    
26.     }
    
27. 
    
28.     private Island helper(int[][] grid, int row, int col) {
    
29.         if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) {
    
30.             return new Island(0, false);
    
31.         }
    
32.         boolean hasTreasure = false;
    
33.         if (grid[row][col] == 2) {
    
34.             hasTreasure = true;
    
35.         }
    
36.         grid[row][col] = 0;
    
37.         int res = 1;
    
38. 
    
39.         for (int[] dir : DIRS) {
    
40.             int x = row + dir[0];
    
41.             int y = col + dir[1];
    
42.             Island curChild = helper(grid, x, y);
    
43.             if (curChild.hasTreature) {
    
44.                 hasTreasure = true;
    
45.             }
    
46.             res += curChild.num;
    
47.         }
    
48. 
    
49.         if (hasTreasure) {
    
50.             return new Island(res, true);
    
51.         } else {
    
52.             return new Island(res, false);
    
53.         }
    
54.     }
    
55. 
    
56.     public static void main(String[] args) {
    
57.         MaxAreaWithTreasure solution = new MaxAreaWithTreasure();
    
58.         int[][] grid = new int[][]{{2, 1, 0, 0}, {1, 0, 0, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}};
    
59.         System.out.println(solution.solution(grid));
    
60.     }
    
61. }
    

复制代码

地雷那道题还挺麻烦的，想了一段时间才有头绪。直接用BFS不大方面，要同时考虑有地雷的格子和空格。我的解决办法是在BFS里用DFS， 在level order BFS里的每个level之后把用DFS得到的下一层的位置放到queue里。

1. public int solution2(int[][] grid, int row, int col) {
   
2.         Queue<int[]> q = new LinkedList<>();
   
3.         q.add(new int[]{row, col});
   
4.         Queue<int[]> bombsPos = new LinkedList<>();
   
5.         boolean[][] visited = new boolean[grid.length][grid[0].length];
   
6.         visited[row][col] = true;
   
7.         bombsPos.add(new int[]{row, col});
   
8.         int res = 1;
   
9.         while (!bombsPos.isEmpty()) {
   
10.             int size = bombsPos.size();
    
11.             List<int[]> tempBombPos = new LinkedList<>();
    
12.             for (int i = 0; i < size; i++) {
    
13.                 int[] pos = bombsPos.remove();
    
14.                 int r = pos[0];
    
15.                 int c = pos[1];
    
16.                 int range = grid[r][c];
    
17. 
    
18.                 helper(tempBombPos, grid, visited, r, c, r, c, range);
    
19.             }
    
20.             res += tempBombPos.size();
    
21.             for (int[] pos : tempBombPos) {
    
22.                 bombsPos.add(pos);
    
23.             }
    
24.         }
    
25. 
    
26.         return res;
    
27.     }
    
28. 
    
29.     private void helper(List<int[]> bombPos, int[][] grid, boolean[][] visited, int row, int col, int startRow, int startCol, int range) {
    
30.         for (int[] dir : DIRS) {
    
31.             int newRow = row + dir[0];
    
32.             int newCol = col + dir[1];
    
33.             if (newRow < 0 || newRow >= grid.length || newCol < 0 || newCol >= grid[0].length || visited[newRow][newCol] || (newRow - startRow) * (newRow - startRow) + (newCol - startCol) * (newCol - startCol) > range * range) continue;
    
34.             visited[newRow][newCol] = true;
    
35.             if (grid[newRow][newCol] != 0) {
    
36.                 bombPos.add(new int[]{newRow, newCol});
    
37.             }
    
38.             helper(bombPos, grid, visited, newRow, newCol, startRow, startCol, range);
    
39.         }
    
40. 
    
41.     }
    
42. 
    
43.     public static void main(String[] args) {
    
44.         Bomb solution = new Bomb();
    
45.         int[][] grid = new int[][]{{1, 2, 0, 0},{0, 0, 1, 0}, {0, 2, 0, 0}, {1, 0, 0, 1}};
    
46.         System.out.println(solution.solution2(grid, 0, 0));
    
47.     }

复制代码