在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1973|回复: 3
收起左侧

Google面试题一条

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

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

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

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

x
朋友面google的一条题
就是给一个矩阵的size: n row, m column可选路径是每个格子周围的8个格 但不可以重复,
求生成一个从(0,0) 走到(n-1, m-1)的random 路径....
我写了一个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;. more info on 1point3acres
  5. import java.util.HashSet;. more info on 1point3acres
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.Random;. from: 1point3acres
  9. import java.util.Scanner;
  10. . visit 1point3acres for more.
  11. public class Solution {
  12.         HashSet<String>routeRecorder = new HashSet<String>();
  13.         public static void main(String args[]){
  14.                 //int a[] = {7,2,4};. 一亩-三分-地,独家发布
  15.                 . 1point 3acres 论坛
  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.                         }-google 1point3acres
  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];
  30.               this.n = n;
  31.               this.m = m;
  32.               dfs(0,0,1,0,0, "");
  33.               return result;
  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();
  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();. 围观我们@1point 3 acres
  43.                 }
  44.                 routeRecorder.add(route);. 1point3acres
  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;. from: 1point3acres
  52.             }
  53.             System.out.println();
  54.             if (x == n-1 && y == m-1){. visit 1point3acres for more.
  55.                     //System.out.println("Route found:"+route);
  56.                 result[x][y] = level;
  57.                 return true;
  58.             }
  59. . From 1point 3acres bbs
  60.             result[x][y] = level;. From 1point 3acres bbs
  61.             boolean found = false;. From 1point 3acres bbs
  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);
  67.               while (directions[random]){ //skip checked direction
  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){
  77.                 found = dfs(x-1, y, level+1,x,y, route+"->("+(x-1)+","+y+")");
  78.               }else if (random == 3){
  79.                 found = dfs(x-1, y+1, level+1,x,y, route+"->("+(x-1)+","+(y+1)+")");
  80.               }else if (random == 4){. 1point3acres
  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){. From 1point 3acres bbs
  85.                 found = dfs(x+1, y+1, level+1,x,y, route+"->("+(x+1)+","+(y+1)+")");
  86.               }else{. 1point 3acres 论坛
  87.                 found = dfs(x+1, y-1, level+1,x,y, route+"->("+(x+1)+","+(y-1)+")");
  88.               }
  89.               /*System.out.println("Random is "+random);
  90.               Scanner aScanner = new Scanner(System.in);.留学论坛-一亩-三分地
  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.             
  99.             
  100.             result[x][y] = 0;
  101.             System.out.println(" - reason: no place to go" + " x: "+x+" y: "+y+" "+route);
  102.             return false;
  103.           }
  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.         . 1point3acres
  118. }. 留学申请论坛-一亩三分地

  119. /*if (dfs(x, y-1, level+1)||
  120. dfs(x, y+1, level+1)||
  121. dfs(x+1, y-1, level+1)||
  122. dfs(x+1, y+1, level+1)||
  123. dfs(x+1, y, level+1)||
  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. . visit 1point3acres for more.
  11.         static boolean fill(List<Integer> result, int[][] matrix, int i, int j){
  12.                 int [] dx = {0,1,1,1,0,-1,-1,-1};. 牛人云集,一亩三分地
  13.                 int [] dy = {1,1,0,-1,-1,-1,0,1};
  14.                 if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length || matrix[i][j] != 0)
  15.                         return false;
  16.                
  17.                 matrix[i][j] = 1;
    . 一亩-三分-地,独家发布
  18.                 result.add(matrix[0].length*i+j);
  19.                 if(i == matrix.length-1 && j == matrix[0].length-1). 一亩-三分-地,独家发布
  20.                         return true; 来源一亩.三分地论坛.
  21.                 int [] directions = new int [8]; 来源一亩.三分地论坛.
  22.                 Random randomGenerator = new Random();
  23.                 int count = 0;
  24.                 while(count != 8){
  25.                         int random = randomGenerator.nextInt(8);. 围观我们@1point 3 acres
  26.                         if(directions[random] == 1)
  27.                                 continue;
  28.                         else{
  29.                                 directions[random] = 1;
  30.                                 count++;. Waral 博客有更多文章,
  31.                                 if(fill(result, matrix, i+dx[random], j+dy[random]))
  32.                                         return true;
  33.                         }
    .本文原创自1point3acres论坛
  34.                 }
  35.                 result.remove(result.size()-1);. From 1point 3acres bbs
  36.                 matrix[i][j] = 0;
  37.                 return false;
  38.         }
  39. }
复制代码
这是运行结果,每个点的值为:列数*当前行+当前列
[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;. more info on 1point3acres
  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;. from: 1point3acres

  9. public class Solution {. 1point 3acres 论坛
  10.         public static void main(String args[]){
    . 1point3acres
  11.                 //int a[] = {7,2,4};. 1point 3acres 论坛
  12.                 Solution s = new Solution();. 留学申请论坛-一亩三分地
  13.                 int [][] result = s.getRandomPath(10, 10);
  14.                 for (int i = 0; i < result.length; i++){
  15.                         for (int j = 0; j < result[0].length; j++){. 1point 3acres 论坛
  16.                                 System.out.print(result[i][j]+" ");
  17.                         }
  18.                         System.out.println();
  19.                 }
  20.         }
    . 一亩-三分-地,独家发布
  21.        
  22.           int [][]result;. visit 1point3acres for more.
  23.           int m,n;. from: 1point3acres
  24.           int[][] getRandomPath(int n, int m){
  25.               //check = new boolean[n][m];
  26.               result = new int[n][m]; //all 0.1point3acres网
  27.               this.n = n;
  28.               this.m = m;
  29.               dfs(0,0,1);
  30.               return result;.留学论坛-一亩-三分地
  31.           }
  32. . more info on 1point3acres
  33.           boolean dfs(int x, int y, int level){
  34.             if (x < 0 || x >= n || y < 0 || y >= m || result[x][y] != 0){
  35.                 return false;
  36.             }
  37.             if (x == n-1 && y == m-1){
  38.                 result[x][y] = level;
  39.                 return true;
  40.             }

  41.             result[x][y] = level;
  42.             boolean found = false;
  43.             boolean[] directions = new boolean[8];. 留学申请论坛-一亩三分地
  44.             Random randomGenerator = new Random();
  45.             int totalCheck = 0;
  46.             while (!found && totalCheck != 8){
  47.               int random = randomGenerator.nextInt(8);
  48.               if (directions[random]){ //skip checked direction.本文原创自1point3acres论坛
  49.                 continue;
  50.               } 来源一亩.三分地论坛.
  51.               totalCheck++;
  52.               directions[random] = true;
  53.               if (random == 0){
  54.                 found = dfs(x-1, y, level+1);. from: 1point3acres
  55.               }else if (random == 1){
  56.                 found = dfs(x+1, y, level+1);
  57.               }else if (random == 2){
  58.                 found = dfs(x, y+1, level+1);
  59.               }else if (random == 3){
  60.                 found = dfs(x, y-1, level+1);
  61.               }else if (random == 4){.留学论坛-一亩-三分地
  62.                 found = dfs(x-1, y-1, level+1);
  63.               }else if (random == 5){
  64.                 found = dfs(x+1, y+1, level+1);
  65.               }else if (random == 6){
  66.                 found = dfs(x-1, y+1, level+1);
  67.               }else{. 一亩-三分-地,独家发布
  68.                 found = dfs(x+1, y-1, level+1);
  69.               }
  70.             }. more info on 1point3acres

  71.             if (found){
  72.               return true;
  73.             }
    .本文原创自1point3acres论坛

  74.             result[x][y] = 0;. 围观我们@1point 3 acres

  75.             return false;
  76.           }
  77.         -google 1point3acres
  78.        
  79. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 04:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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