Google 电面和 onsite

kelvinzhong 发表于 2015-9-16 01:41
你这个解法也是O(n^4)的e.

如果e很大的话确实，但是如果e很大的话也可以对空余的位置做BFS

补充内容 (2015-9-16 01:45):
所以是min(e*n^2, (n^2-e)*n^2)

为什么我觉得第一题的不需要证明啊，这个不就是latin square的性质吗？ 最多就举个反例。。。

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

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

从器材开始bfs到所有点，时间复杂度是O(e*n^2)，空间O(n^2)，累加每个点到e个器材的距离和，O(n^2)选取最小

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。。。。

楼主拿到HR提供的各个面试的feedback了吗？方便分享一下吗？谢谢。

楼主拿到HR提供的各个面试的feedback了吗？方便分享一下吗？谢谢。

lxia 发表于 2015-5-2 15:23
为什么我觉得证明不出来。
比如
{1 2 x y

感觉latin square还是只能backtracking吧，没法确定啊

第一题应该就是和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. }
    

复制代码

靠 第一题简直就是数学题啊  google真是狗血  要是因为这个挂人。。简直没法生存