一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 621|回复: 3
收起左侧

Google面试题一条

[复制链接] |试试Instant~ |关注本帖
nelson16 发表于 2015-10-26 12:29:48 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 校园招聘会 - HR筛选 |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
朋友面google的一条题
就是给一个矩阵的size: n row, m column可选路径是每个格子周围的8个格 但不可以重复,
求生成一个从(0,0) 走到(n-1, m-1)的random 路径..... 1point3acres.com/bbs
我写了一个solution..正常情况下都work..但当n 和m大的时候 (例如n=10, m=10)的时候 就会无尽循环...不知道为什么,求大神看code
  1. package testSyn;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.HashMap;
  5. import java.util.HashSet;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.Random;
  9. import java.util.Scanner;
  10. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  11. public class Solution {
  12.         HashSet<String>routeRecorder = new HashSet<String>();
  13.         public static void main(String args[]){. 1point3acres.com/bbs
  14.                 //int a[] = {7,2,4};
  15.                
  16.                 Solution s = new Solution();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.                 int [][] aaa = s.getRandomPath(10, 10);
  18.                 for (int i = 0; i < aaa.length; i++){
  19.                         for (int j = 0; j < aaa[0].length; j++){
  20.                                 System.out.print(aaa[i][j]+" ");
  21.                         }
  22.                         System.out.println();
  23.                 }
  24.         }
  25.        
  26.           int [][]result;
  27.           int m,n;
  28.           int[][] getRandomPath(int n, int m){
  29.               result = new int[n][m]; .鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.               this.n = n;.1point3acres缃
  31.               this.m = m;
  32.               dfs(0,0,1,0,0, "");
  33.               return result;
    . more info on 1point3acres.com
  34.           }

  35.           boolean dfs(int x, int y, int level, int previousX, int previousY, String route){
  36.                 System.out.print("From x:"+previousX+" y:"+previousY+" --->Entering: "+"x: "+x+" y: "+y+" Level: "+level);
  37.                 printBoard();. 鍥磋鎴戜滑@1point 3 acres
  38.                 if (routeRecorder.contains(route)){
  39.                         System.out.println("Duplicate route found!!");
  40.                         System.out.println(route);
  41.                       Scanner aScanner = new Scanner(System.in);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  42.                       aScanner.next();
  43.                 }
  44.                 routeRecorder.add(route);
  45.             if (x < 0 || x >= n || y < 0 || y >= m){
  46.                     System.out.println("No way to go: "+route);
  47.                 return false;
  48.             }
  49.             if (result[x][y] != 0){
  50.                     System.out.println(" - reason: place taken, value"+result[x][y]+" "+route); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  51.                     return false;
  52.             }. 1point3acres.com/bbs
  53.             System.out.println();
  54.             if (x == n-1 && y == m-1){
  55.                     //System.out.println("Route found:"+route);
  56.                 result[x][y] = level;
  57.                 return true;
  58.             }
  59. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  60.             result[x][y] = level;
  61.             boolean found = false;
  62.             boolean[] directions = new boolean[8];
  63.             Random randomGenerator = new Random();
  64.             int totalCheck = 0;
  65.             while (!found && totalCheck != 8){
  66.               int random = randomGenerator.nextInt(8);. From 1point 3acres bbs
  67.               while (directions[random]){ //skip checked direction. more info on 1point3acres.com
  68.                       random = randomGenerator.nextInt(8);
  69.               }
  70.               totalCheck++;
  71.               directions[random] = true;
  72.               if (random == 0){
  73.                 found = dfs(x, y+1, level+1,x,y, route+"->("+x+","+(y+1)+")");
  74.               }else if (random == 1){
  75.                 found = dfs(x, y-1, level+1,x,y, route+"->("+x+","+(y-1)+")");
  76.               }else if (random == 2){. 1point 3acres 璁哄潧
  77.                 found = dfs(x-1, y, level+1,x,y, route+"->("+(x-1)+","+y+")");
    . 1point 3acres 璁哄潧
  78.               }else if (random == 3){
  79.                 found = dfs(x-1, y+1, level+1,x,y, route+"->("+(x-1)+","+(y+1)+")");.1point3acres缃
  80.               }else if (random == 4){
  81.                 found = dfs(x-1, y-1, level+1,x,y, route+"->("+(x-1)+","+(y-1)+")");
  82.               }else if (random == 5){
  83.                 found = dfs(x+1, y, level+1,x,y, route+"->("+(x+1)+","+y+")");
  84.               }else if (random == 6){. visit 1point3acres.com for more.
  85.                 found = dfs(x+1, y+1, level+1,x,y, route+"->("+(x+1)+","+(y+1)+")");
  86.               }else{
  87.                 found = dfs(x+1, y-1, level+1,x,y, route+"->("+(x+1)+","+(y-1)+")");
  88.               }. 鍥磋鎴戜滑@1point 3 acres
  89.               /*System.out.println("Random is "+random);
  90.               Scanner aScanner = new Scanner(System.in);. from: 1point3acres.com/bbs
  91.               aScanner.next();*/
  92.             }
  93.             System.out.println("Found: "+found+ " total: "+totalCheck);
  94.             if (found){
  95.               System.out.println("Route found:"+route);
  96.               return true;
  97.             }
  98.             . from: 1point3acres.com/bbs
  99.             . 鍥磋鎴戜滑@1point 3 acres
  100.             result[x][y] = 0;
  101.             System.out.println(" - reason: no place to go" + " x: "+x+" y: "+y+" "+route);
  102.             return false;
  103.           }. From 1point 3acres bbs
  104.           void printBoard(){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  105.                   System.out.println();
  106.                         for (int i = 0; i < result.length; i++){
  107.                                 for (int j = 0; j < result[0].length; j++){
  108.                                         String temp = result[i][j]+" ";
  109.                                         while (temp.length() <= 4){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  110.                                                 temp = " "+temp;
  111.                                         }
  112.                                         System.out.print(temp);
  113.                                 }
  114.                                 System.out.println();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  115.                         }
  116.           }
  117.        
  118. }

  119. /*if (dfs(x, y-1, level+1)||
  120. dfs(x, y+1, level+1)||. more info on 1point3acres.com
  121. dfs(x+1, y-1, level+1)||
  122. dfs(x+1, y+1, level+1)||
  123. dfs(x+1, y, level+1)||. From 1point 3acres bbs
  124. dfs(x-1, y-1, level+1)||
  125. dfs(x-1, y+1, level+1)||. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  126. dfs(x-1, y, level+1))        {
  127. return true;
  128. }*/
复制代码

本帖被以下淘专辑推荐:

oaknova 发表于 2015-10-27 23:33:58 | 显示全部楼层
  1. package leetcode;
  2. import java.util.*;

  3. public class Leetcode {
  4.         public static void main(String[] args){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.                 int[][] matrix = new int[10][10];
  6.                 List<Integer> result = new ArrayList<Integer>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7.                 if(fill(result, matrix, 0, 0))
  8.                         System.out.print(result);
  9.         }

  10.         static boolean fill(List<Integer> result, int[][] matrix, int i, int j){
  11.                 int [] dx = {0,1,1,1,0,-1,-1,-1};
  12.                 int [] dy = {1,1,0,-1,-1,-1,0,1};
  13.                 if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length || matrix[i][j] != 0)
  14.                         return false;
  15.                
  16.                 matrix[i][j] = 1;
  17.                 result.add(matrix[0].length*i+j);
  18.                 if(i == matrix.length-1 && j == matrix[0].length-1)
  19.                         return true;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.                 int [] directions = new int [8];
  21.                 Random randomGenerator = new Random();
  22.                 int count = 0;
  23.                 while(count != 8){
  24.                         int random = randomGenerator.nextInt(8);
  25.                         if(directions[random] == 1)
  26.                                 continue;
  27.                         else{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.                                 directions[random] = 1;
  29.                                 count++;. 鍥磋鎴戜滑@1point 3 acres
  30.                                 if(fill(result, matrix, i+dx[random], j+dy[random]))
  31.                                         return true;
  32.                         }
  33.                 }
  34.                 result.remove(result.size()-1);
  35.                 matrix[i][j] = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  36.                 return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  37.         }
  38. }
复制代码
这是运行结果,每个点的值为:列数*当前行+当前列
[0, 1, 10, 21, 31, 22, 13, 24, 23, 34, 44, 33, 32, 43, 53, 64, 75, 86, 95, 84, 93, 94, 83, 92, 81, 90, 80, 71, 70, 61, 62, 72, 63, 52, 42, 51, 40, 41, 30, 20, 11, 2, 12, 3, 4, 14, 25, 15, 5, 6, 16, 7, 8, 9, 18, 28, 19, 29, 38, 48, 47, 37, 46, 55, 65, 56, 57, 67, 68, 78, 89, 99]
回复 支持 1 反对 0

使用道具 举报

 楼主| nelson16 发表于 2015-10-26 12:30:42 | 显示全部楼层
帖子里面说错了 是当n 和 m大得时候 有时候会出solution有时候会inifnity loop
回复 支持 反对

使用道具 举报

 楼主| nelson16 发表于 2015-10-26 12:32:26 | 显示全部楼层
主贴的代码是debug的。。。不知道怎么编辑帖子 在这里重新发个去掉print的代码

  1. package testSyn;

  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.HashMap;
  5. import java.util.HashSet;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.Random;

  9. public class Solution {
  10.         public static void main(String args[]){
  11.                 //int a[] = {7,2,4};
  12.                 Solution s = new Solution();
  13.                 int [][] result = s.getRandomPath(10, 10);
  14.                 for (int i = 0; i < result.length; i++){. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                         for (int j = 0; j < result[0].length; j++){
  16.                                 System.out.print(result[i][j]+" ");
  17.                         }
  18.                         System.out.println();
  19.                 }
    . from: 1point3acres.com/bbs
  20.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.         . 1point 3acres 璁哄潧
  22.           int [][]result;.1point3acres缃
  23.           int m,n;
  24.           int[][] getRandomPath(int n, int m){
  25.               //check = new boolean[n][m];
  26.               result = new int[n][m]; //all 0
  27.               this.n = n;
  28.               this.m = m;
  29.               dfs(0,0,1);
  30.               return result;
  31.           }

  32.           boolean dfs(int x, int y, int level){
  33.             if (x < 0 || x >= n || y < 0 || y >= m || result[x][y] != 0){
  34.                 return false;. From 1point 3acres bbs
  35.             }
  36.             if (x == n-1 && y == m-1){
  37.                 result[x][y] = level;
  38.                 return true;
  39.             }. from: 1point3acres.com/bbs

  40.             result[x][y] = level;
  41.             boolean found = false;
  42.             boolean[] directions = new boolean[8];
  43.             Random randomGenerator = new Random();. From 1point 3acres bbs
  44.             int totalCheck = 0;
  45.             while (!found && totalCheck != 8){
  46.               int random = randomGenerator.nextInt(8);
  47.               if (directions[random]){ //skip checked direction
  48.                 continue;
  49.               }
  50.               totalCheck++;
  51.               directions[random] = true;. from: 1point3acres.com/bbs
  52.               if (random == 0){
  53.                 found = dfs(x-1, y, level+1);
  54.               }else if (random == 1){
  55.                 found = dfs(x+1, y, level+1);
  56.               }else if (random == 2){
  57.                 found = dfs(x, y+1, level+1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  58.               }else if (random == 3){. 1point3acres.com/bbs
  59.                 found = dfs(x, y-1, level+1);
  60.               }else if (random == 4){
  61.                 found = dfs(x-1, y-1, level+1);
  62.               }else if (random == 5){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  63.                 found = dfs(x+1, y+1, level+1);
  64.               }else if (random == 6){
  65.                 found = dfs(x-1, y+1, level+1);
  66.               }else{
  67.                 found = dfs(x+1, y-1, level+1);
  68.               }
  69.             }

  70.             if (found){. 1point3acres.com/bbs
  71.               return true;
  72.             }

  73.             result[x][y] = 0;

  74.             return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  75.           }
  76.        
  77.         -google 1point3acres
  78. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 11:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表