一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3796|回复: 37
收起左侧

Facebook 2015暑期实习面经

[复制链接] |试试Instant~ |关注本帖
JermaineDing 发表于 2015-4-8 03:37:43 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Facebook - 网上海投 - 技术电面 |Fail其他

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

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

x
刚刚才面试的Facebook的题目,感觉我没有见过。
w是wall,然后g是gates,从“_”开始,找出所有到gates的距离。 我折腾了半天没有做出来,面试官还是挺耐心的,全当是积累经验了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
// _ W G _
// _ _ _ W
// _ W _ W
// G W _ _
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
String [][] maze = new int [width][height];. From 1point 3acres bbs
boolean [][] wasHere = new boolean[width][height];
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public void solution(int maze[x][y], int i, int j, int sol[][]){
    int i = 0;
    string num = "" + i;
    for(int i=0,j=0;i<width.length(),j<height.length(); i++,j++)
    {
        if (maze[j].equals("_")){
            maze[j] = solve_one_position(maze, i, j, 0);
        }-google 1point3acres
    }
}

public int solve_one_position(int maze[x][y], int i, int j, int dist) {
    wasHere[j] = true;
. from: 1point3acres.com/bbs
    if (maze[j] == 'G') {
        return dist;
    }

    if (maze[j+1].equals("_")){. from: 1point3acres.com/bbs
        right = solution(maze, i, j+1, dist + 1);.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }
    if (maze[i+1][j].equals("_")){
        up = solution(maze, i+1, j, dist + 1);
    }
    ...
    wasHere[j] = false;
    return min(left, right, up, down);
}.1point3acres缃

.鐣欏璁哄潧-涓浜-涓夊垎鍦
这是输出的结果:. From 1point 3acres bbs
// 3 W G 1
// 2 2 1 W
// 1 W 2 W. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
// G W 3 4
-google 1point3acres


.鏈枃鍘熷垱鑷1point3acres璁哄潧补充内容 (2015-4-8 03:46):
上面的代码是基本的思路,我没有做出来,最后没时间了。

评分

3

查看全部评分

shawlin 发表于 2015-4-8 03:57:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
是找出_到最近的gate的距离吗?
我记得在地里看到过类似的题,思路是BFS, 但先把所有gates的位置放在queue里面
这是那个类似的题目 http://www.1point3acres.com/bbs/thread-127776-1-1.html. Waral 鍗氬鏈夋洿澶氭枃绔,
地里的资料看来的好好学习啊
回复 支持 1 反对 0

使用道具 举报

flyPacific111 发表于 2015-4-8 03:41:37 | 显示全部楼层
关注一亩三分地微博:
Warald
这题不简单啊...lz啥时候投的intern啊?过了多久让面试的啊?
回复 支持 反对

使用道具 举报

 楼主| JermaineDing 发表于 2015-4-8 03:45:26 | 显示全部楼层
flyPacific111 发表于 2015-4-8 03:41
这题不简单啊...lz啥时候投的intern啊?过了多久让面试的啊?

我是3月下旬投的,面试过了2周左右吧。
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-8 03:49:15 | 显示全部楼层
实习这么难的题目额
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-4-8 03:53:15 | 显示全部楼层
pat pat,以后还有机会啦!
这题G经常考,可以用同步从所有的G开始做DFS

补充内容 (2015-4-8 05:26):
*BFS, not DFS,具体代码在下面的帖子里,请轻拍 =)
回复 支持 反对

使用道具 举报

 楼主| JermaineDing 发表于 2015-4-8 03:55:10 | 显示全部楼层
seabiscuit119 发表于 2015-4-8 03:49. From 1point 3acres bbs
实习这么难的题目额

没办法,实习就是这样。这可能跟Team有关,面试我的是一个team leader,难不难看这个team要什么样的人。
回复 支持 反对

使用道具 举报

 楼主| JermaineDing 发表于 2015-4-8 03:56:55 | 显示全部楼层
marthew777 发表于 2015-4-8 03:53
pat pat,以后还有机会啦!
这题G经常考,可以用同步从所有的G开始做DFS

大神能把代码贴出来吗,谢谢。
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-8 04:03:38 | 显示全部楼层
不是很理解题意。。。是说所有W到所有G的距离?有很多Gate的话,算哪个距离
回复 支持 反对

使用道具 举报

 楼主| JermaineDing 发表于 2015-4-8 04:07:30 | 显示全部楼层
shawlin 发表于 2015-4-8 03:57
是找出_到最近的gate的距离吗?
我记得在地里看到过类似的题,思路是BFS, 但先把所有gates的位置放在queue ...

嗯,有点类似。
回复 支持 反对

使用道具 举报

 楼主| JermaineDing 发表于 2015-4-8 04:09:03 | 显示全部楼层
yuxrose 发表于 2015-4-8 04:03-google 1point3acres
不是很理解题意。。。是说所有W到所有G的距离?有很多Gate的话,算哪个距离
-google 1point3acres
是“_”到G的距离。每一个“_”到G的距离,W是不能经过的,有一点像迷宫。
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-4-8 04:29:01 | 显示全部楼层
JermaineDing 发表于 2015-4-8 03:56
大神能把代码贴出来吗,谢谢。

大概是这个意思,其实很简单达!
. from: 1point3acres.com/bbs
private enum BLOCK {G, W, O};
public void solution(int[][] maze){
        int m = maze.length;
        if(m<1) return;.1point3acres缃
        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[j]==G){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                queue.add(new LinkedList<>(){new Position(i,j)});
                                sol[j] = 1;
                                visited[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[j-1] = sol[j] + 1;
                        visited[j-1]=true;
                }
. 1point3acres.com/bbs                // similarly do: left down and right
                if(isValid(maze, i, j+1, visited)){
                        //....鐣欏璁哄潧-涓浜-涓夊垎鍦
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(isValid(maze, i-1, j, visited)){. visit 1point3acres.com for more.
                        //...                       
                }
                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[j] || maze[j]==W)
                return false;. 鍥磋鎴戜滑@1point 3 acres
        return true;. From 1point 3acres bbs
}
public class Position{
        public int x;
        public int y;
        public Position(int x, int y){
                this.x = x; this.y = y;
        }
}.1point3acres缃
. From 1point 3acres bbs
补充内容 (2015-4-8 04:32):
最后的结果就保存在 int[][] sol里,如果知道W的值的话,也可以再做一次简单的iteration把相应的W的值更新到sol里。。
回复 支持 反对

使用道具 举报

haungge0385 发表于 2015-4-8 21:15:21 | 显示全部楼层
marthew777 发表于 2015-4-8 04:29. 1point 3acres 璁哄潧
大概是这个意思,其实很简单达!
-google 1point3acres
private enum BLOCK {G, W, O};

请问dfs为什么不行?我用dfs实现了,方便的话帮我看下
  1. public List<Integer> pathToGates(char[][] maze) {
  2.                 ArrayList<Integer> res = new ArrayList<Integer>();. 1point 3acres 璁哄潧
  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);. from: 1point3acres.com/bbs
  10.                         }
  11.                        
  12.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.                
  14.                 return res;
  15.         }
  16.        
  17.         public void        help(char[][] maze , int i , int j , ArrayList<Integer> res, int count, int[][] visit) {
    .1point3acres缃
  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';. more info on 1point3acres.com
  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] = '_';. visit 1point3acres.com for more.
  57.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  58.                 System.err.println(rr.pathToGates(maze));
  59.                
  60.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  61.         }
复制代码
回复 支持 反对

使用道具 举报

marthew777 发表于 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
大概是这个意思,其实很简单达!
.1point3acres缃.鏈枃鍘熷垱鑷1point3acres璁哄潧
private enum BLOCK {G, W, O};

哥,你这代码有问题呀,略坑...
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-4-9 07:16:27 | 显示全部楼层
siren01 发表于 2015-4-9 05:30
哥,你这代码有问题呀,略坑...


                               
登录/注册后可看大图
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

使用道具 举报

marthew777 发表于 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];. visit 1point3acres.com for more.
        for(boolean[] row : visited)
                Arrays.fill(row, false);
        int[][] sol = new int[m][n];
        for(int[] row : sol)
                Arrays.fill(row, 0);. From 1point 3acres bbs
        Queue<Queue<Position>> queue = new LinkedList<>();
        for(int i=0;i<m;++i)
                for(int j=0;j<n;++j)
                        if(maze[j]==1){. visit 1point3acres.com for more.
                                Queue<Position> gate = new LinkedList<>();
                                gate.add(new Position(i,j));
                                queue.add(gate);
                                sol[j] = 0;
                                visited[j] = true;
                        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        while(!queue.isEmpty()){
                Queue<Position> bfs = queue.poll();
                Position p = bfs.poll();
                int i = p.x, j = p.y;
                // bfs : up-google 1point3acres
                if(isValid(maze, i, j-1, visited)){
                        bfs.add(new Position(i, j-1)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        sol[j-1] = sol[j] + 1;-google 1point3acres
                        visited[j-1]=true;
                }
                // similarly do: left down and right
                if(isValid(maze, i, j+1, visited)){
                        bfs.add(new Position(i, j+1));
                        sol[j+1] = sol[j] + 1;. From 1point 3acres bbs
                        visited[j+1]=true;
                }
                if(isValid(maze, i-1, j, visited)){. Waral 鍗氬鏈夋洿澶氭枃绔,
                        bfs.add(new Position(i-1, j));
                        sol[i-1][j] = sol[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[j] + 1;
                        visited[i+1][j]=true;   . From 1point 3acres bbs
                }
                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[j] || maze[j]==-1)
                return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
public static class Position{
        public int x;
        public int y;
        public Position(int x, int y){. visit 1point3acres.com for more.
                this.x = x; this.y = y;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
}
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).1point3acres缃
        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++). 鍥磋鎴戜滑@1point 3 acres
                        test[j]=rdm.nextInt(2);
        // Generate Random Walls      
        int num_walls = 2;
        for(int i=0;i<num_walls;++i){. 1point3acres.com/bbs
                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维数组自动被转成了一维。。擦。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-25 09:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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