📣 独立日限时特惠: VIP通行证立减$68
楼主: JermaineDing
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook 2015暑期实习面经

🔗
 楼主| JermaineDing 2015-4-8 04:09:03 | 只看该作者
全局:
yuxrose 发表于 2015-4-8 04:03
不是很理解题意。。。是说所有W到所有G的距离?有很多Gate的话,算哪个距离

是“_”到G的距离。每一个“_”到G的距离,W是不能经过的,有一点像迷宫。
回复

使用道具 举报

🔗
Mr.Sagemaker 2015-4-8 04:29:01 | 只看该作者
全局:
JermaineDing 发表于 2015-4-8 03:56
大神能把代码贴出来吗,谢谢。

大概是这个意思,其实很简单达!

private enum BLOCK {G, W, O};
public void solution(int[][] maze){
        int m = maze.length;
        if(m<1) return;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        Arrays.fill(visited, false);
        int[][] sol = new int[m][n];
        Arrays.fill(sol, 0);
        Queue<Queue<Position>> queue = new LinkedList<>();
        for(int i=0;i<m;++i)
                for(int j=0;j<n;++j)
                        if(maze[i][j]==G){
                                queue.add(new LinkedList<>(){new Position(i,j)});
                                sol[i][j] = 1;
                                visited[i][j] = true;
                        }
        while(!queue.isEmpty()){
                Queue<Position> bfs = queue.poll();
                Position p = bfs.poll();
                // bfs : up
                if(isValid(maze, i, j-1, visited)){
                        bfs.add(new Position(i, j-1));
                        sol[i][j-1] = sol[i][j] + 1;
                        visited[i][j-1]=true;
                }
                // similarly do: left down and right
                if(isValid(maze, i, j+1, visited)){
                        //...
                }
                if(isValid(maze, i-1, j, visited)){
                        //...                       
                }
                if(isValid(maze, i+1, j, visited)){
                        //...               
                }
        }
}
public boolean isValid(int[][] maze, int i, int j, boolean[][] visited){
        int m = maze.length;
        if(m<1)
                return false;
        int n = maze[0].length;
        if(i<0 || i >= m || j < 0 || j >= n || visited[i][j] || maze[i][j]==W)
                return false;
        return true;
}
public class Position{
        public int x;
        public int y;
        public Position(int x, int y){
                this.x = x; this.y = y;
        }
}

补充内容 (2015-4-8 04:32):
最后的结果就保存在 int[][] sol里,如果知道W的值的话,也可以再做一次简单的iteration把相应的W的值更新到sol里。。
回复

使用道具 举报

🔗
haungge0385 2015-4-8 21:15:21 | 只看该作者
全局:
marthew777 发表于 2015-4-8 04:29
大概是这个意思,其实很简单达!

private enum BLOCK {G, W, O};

请问dfs为什么不行?我用dfs实现了,方便的话帮我看下
  1. public List<Integer> pathToGates(char[][] maze) {
  2.                 ArrayList<Integer> res = new ArrayList<Integer>();
  3.                 if (maze.length == 0 && maze[0].length == 0) {
  4.                         return res;
  5.                 }
  6.                 int[][] visit = new int[maze.length][maze[0].length];
  7.                 for (int i = 0; i < maze.length; i++) {
  8.                         for (int j = 0; j < maze[0].length; j++) {
  9.                                 help(maze, i, j, res, 0 , visit);
  10.                         }
  11.                        
  12.                 }
  13.                
  14.                 return res;
  15.         }
  16.        
  17.         public void        help(char[][] maze , int i , int j , ArrayList<Integer> res, int count, int[][] visit) {
  18.                 if (i < 0 || i >= maze.length || j < 0 || j >= maze[0].length ||visit[i][j] == 1 || maze[i][j] == 'W') {
  19.                        
  20.                         return;
  21.                 }else if (maze[i][j] == 'G') {
  22.                         res.add(count);
  23.                        
  24.                         return;
  25.                 }
  26.                 visit[i][j] = 1;
  27.                 count++;
  28.                 help(maze, i+1, j, res, count,visit);
  29.                 help(maze, i-1, j, res, count,visit);
  30.                 help(maze, i, j+1, res, count,visit);
  31.                 help(maze, i, j-1, res, count,visit);
  32.                 visit[i][j] = 0;
  33.                 count--;
  34.         }
  35.        
  36.         public static void main(String[] args) {
  37.                
  38.                
  39.                 rotate rr = new rotate();
  40.                 char[][] maze = new char[4][4];
  41.                 maze[0][0] = '_';
  42.                 maze[0][1] = 'W';
  43.                 maze[0][2] = 'G';
  44.                 maze[0][3] = '_';
  45.                 maze[1][0] = '_';
  46.                 maze[1][1] = '_';
  47.                 maze[1][2] = '_';
  48.                 maze[1][3] = 'W';
  49.                 maze[2][0] = '_';
  50.                 maze[2][1] = 'W';
  51.                 maze[2][2] = '_';
  52.                 maze[2][3] = 'W';
  53.                 maze[3][0] = 'G';
  54.                 maze[3][1] = 'W';
  55.                 maze[3][2] = '_';
  56.                 maze[3][3] = '_';
  57.                
  58.                 System.err.println(rr.pathToGates(maze));
  59.                
  60.                
  61.         }
复制代码
回复

使用道具 举报

🔗
Mr.Sagemaker 2015-4-8 21:59:32 | 只看该作者
全局:
haungge0385 发表于 2015-4-8 21:15
请问dfs为什么不行?我用dfs实现了,方便的话帮我看下

要求是找到最短的距离,显然是BFS啊。。
回复

使用道具 举报

🔗
chm34 2015-4-8 22:24:35 | 只看该作者
全局:
楼主和我的题目一模一样。。
回复

使用道具 举报

🔗
 楼主| JermaineDing 2015-4-9 01:52:52 | 只看该作者
全局:
chm34 发表于 2015-4-8 22:24
楼主和我的题目一模一样。。

是什么时候面的?是Facebook吗?
回复

使用道具 举报

🔗
chm34 2015-4-9 04:32:35 | 只看该作者
全局:
JermaineDing 发表于 2015-4-9 01:52
是什么时候面的?是Facebook吗?

恩,礼拜一面的,我之前在地里也没见过这题,然后我用dfs写的,但是应该是有bug,后来没时间了,昨天收到rej
回复

使用道具 举报

🔗
siren01 2015-4-9 05:30:56 | 只看该作者
全局:
marthew777 发表于 2015-4-8 04:29
大概是这个意思,其实很简单达!

private enum BLOCK {G, W, O};

哥,你这代码有问题呀,略坑...
回复

使用道具 举报

🔗
Mr.Sagemaker 2015-4-9 07:16:27 | 只看该作者
全局:
siren01 发表于 2015-4-9 05:30
哥,你这代码有问题呀,略坑...



补充内容 (2015-4-9 07:20):
测试用的是 每次随机生成5x5 maze,Gate 和 Wall 都是在随机的位置; 总共进行了10次测试;
每次测试的输出,第一行是输入的maze: -1 代表Wall, 1代表Gate; 第二行是输出的solution;
回复

使用道具 举报

🔗
Mr.Sagemaker 2015-4-9 07:26:23 | 只看该作者
全局:
siren01 发表于 2015-4-9 05:30
哥,你这代码有问题呀,略坑...

上面的代码我说了是给一个算法实现的大概思路,肯定有syntax error的好吗,我花几分钟随手写的。。
完整代码我分享出来给大家好了!测试过的,没问题,您看看这次还有问题么


import java.util.*;
class Solution{
public static int[][] solution(int[][] maze){
        int m = maze.length;
        if(m<1) return new int[m][m];
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        for(boolean[] row : visited)
                Arrays.fill(row, false);
        int[][] sol = new int[m][n];
        for(int[] row : sol)
                Arrays.fill(row, 0);
        Queue<Queue<Position>> queue = new LinkedList<>();
        for(int i=0;i<m;++i)
                for(int j=0;j<n;++j)
                        if(maze[i][j]==1){
                                Queue<Position> gate = new LinkedList<>();
                                gate.add(new Position(i,j));
                                queue.add(gate);
                                sol[i][j] = 0;
                                visited[i][j] = true;
                        }
        while(!queue.isEmpty()){
                Queue<Position> bfs = queue.poll();
                Position p = bfs.poll();
                int i = p.x, j = p.y;
                // bfs : up
                if(isValid(maze, i, j-1, visited)){
                        bfs.add(new Position(i, j-1));
                        sol[i][j-1] = sol[i][j] + 1;
                        visited[i][j-1]=true;
                }
                // similarly do: left down and right
                if(isValid(maze, i, j+1, visited)){
                        bfs.add(new Position(i, j+1));
                        sol[i][j+1] = sol[i][j] + 1;
                        visited[i][j+1]=true;
                }
                if(isValid(maze, i-1, j, visited)){
                        bfs.add(new Position(i-1, j));
                        sol[i-1][j] = sol[i][j] + 1;
                        visited[i-1][j]=true;           
                }
                if(isValid(maze, i+1, j, visited)){
                        bfs.add(new Position(i+1, j));
                        sol[i+1][j] = sol[i][j] + 1;
                        visited[i+1][j]=true;   
                }
                if(!bfs.isEmpty())
                        queue.add(bfs);
        }
        return sol;
}
public static boolean isValid(int[][] maze, int i, int j, boolean[][] visited){
        int m = maze.length;
        if(m<1)
                return false;
        int n = maze[0].length;
        if(i<0 || i >= m || j < 0 || j >= n || visited[i][j] || maze[i][j]==-1)
                return false;
        return true;
}
public static class Position{
        public int x;
        public int y;
        public Position(int x, int y){
                this.x = x; this.y = y;
        }
}
public static void printMaze(int[][] maze){
        System.out.println(Arrays.deepToString(maze));
}
public static void main(String[] args){
        // For simplicity, assuming W(-1), O(0), G(1)
        Random rdm = new Random();
        int size = 5;
        int[][] test = new int[size][size];
        // Generate Random Gates and initilize rest cells on maze
        for(int i=0;i<size;i++)
                for(int j=0;j<size;j++)
                        test[i][j]=rdm.nextInt(2);
        // Generate Random Walls      
        int num_walls = 2;
        for(int i=0;i<num_walls;++i){
                int x = rdm.nextInt(size);
                int y = rdm.nextInt(size);
                test[x][y] = -1;
        }
        printMaze(test);
        printMaze(solution(test));
}
}


补充内容 (2015-4-9 07:43):
以前没有发过代码到帖子里,发现2维数组自动被转成了一维。。擦。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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