Google 电面和 onsite

电面是 find range.

onsite:
1

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

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

求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.


没给 offer.

为什么我觉得证明不出来。
比如
{1 2 x y
2 1 w z
3 4 1 2
4 3 2 1}
x y w z可以是4 3 3 4
也可以是3 4 4 3
它们就是对称的。
题目还有其他要求？

第一题应该就是和sudoku差不多吧，写了下代码

1. public class LatinSquare {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 LatinSquare ls = new LatinSquare();
   
5.                 int[][] matrix = {{1, 2, 0, 0},
   
6.                         {2, 1, 0, 0},
   
7.                         {3, 4, 1, 2},
   
8.                         {4, 3, 2, 1}};
   
9.                 ls.latinSquareSolver(matrix);
   
10.                 for (int[] arr : matrix) {
    
11.                         for (int i : arr) {
    
12.                                 System.out.print(i + " ");
    
13.                         }
    
14.                         System.out.println();
    
15.                 }
    
16.         }
    
17.         public void latinSquareSolver(int[][] matrix) {
    
18.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
19.                         return;
    
20.                 }
    
21.                 solve(matrix);
    
22.         }
    
23.        
    
24.         public boolean solve(int[][] matrix) {
    
25.                 int n = matrix.length;
    
26.                 for (int i = 0; i < n; i++) {
    
27.                         for (int j = 0; j < n; j++) {
    
28.                                 if (matrix[i][j] == 0) {
    
29.                                         for (int k = 1; k <= 9; k++) {
    
30.                                                 matrix[i][j] = k;
    
31.                                                 if (valid(i, j, matrix) && solve(matrix)) {
    
32.                                                         return true;
    
33.                                                 }
    
34.                                                 matrix[i][j] = 0;
    
35.                                         }
    
36.                                         return false;
    
37.                                 }
    
38.                         }
    
39.                 }
    
40.                
    
41.                 return true;
    
42.         }
    
43. 
    
44.         private boolean valid(int i, int j, int[][] matrix) {
    
45.                 int n = matrix.length;
    
46.                 for (int p = 0; p < n; p++) {
    
47.                         if (p != i && matrix[p][j] == matrix[i][j]) {
    
48.                                 return false;
    
49.                         }
    
50.                 }
    
51.                 for (int p = 0; p < n; p++) {
    
52.                         if (p != j && matrix[i][p] == matrix[i][j]) {
    
53.                                 return false;
    
54.                         }
    
55.                 }
    
56.                
    
57.                 return true;
    
58.         }
    
59. }
    

复制代码

1. void Fill(vector<vector<int>>& v){
   
2.   //1..n, others 0
   
3.   int n = v.size();
   
4.   return dfs(0, 0, v);
   
5. }
   
6. 
   
7. bool dfs(int nowi, int nowj, vector<vector<int>>& v){
   
8.   int n=v.size();
   
9.   if(nowi>=n) return 1;
   
10.   else if(nowj>=n) return dfs(nowi+1, 0, v);
    
11.   if(v[nowi][nowj]){
    
12.     return dfs(nowi, nowj+1, v);
    
13.   }else{
    
14.     for(int i=1;i<=n;i++){
    
15.       if(!valid(nowi, nowj, v, i)) continue;
    
16.       v[nowi][nowj] = i;
    
17.       if(dfs(nowi, nowj+1)) return 1;
    
18.     }
    
19.     v[nowi][nowj] = 0;
    
20.     return 0;
    
21.   }
    
22. }
    
23. 
    
24. bool valid(int nowi, int nowj, vector<vector<int>>& v, int c){
    
25.   int n=v.size();
    
26.   for(int j=0;j<n;j++){
    
27.     if(v[nowi][j] == c) return 0;
    
28.   }
    
29.   for(int i=0;i<n;i++){
    
30.     if(v[i][nowj] == c) return 0;
    
31.   }
    
32.   return 1;
    
33. }

复制代码

感觉就是suduko solver吧 至于时间复杂度，(n^2) ^ n 暴力dfs。。。。

第一题啥意思啊

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

Mahalkita 发表于 2015-5-2 04:34
但是这个假设怎么得到呢 感觉不太好证明呀

不知道啊，我没证出来。

更新一下，第二道题 Read4K 是 LeetCode 上的原题 Read N Characters Given Read4.

最后一题不是一个NP hard问题么？楼主是对每个可能的点做BFS么？中间的障碍怎么考虑呢？