【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

Facebook 2015暑期实习面经

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

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

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

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

x
刚刚才面试的Facebook的题目,感觉我没有见过。
w是wall,然后g是gates,从“_”开始,找出所有到gates的距离。 我折腾了半天没有做出来,面试官还是挺耐心的,全当是积累经验了。. From 1point 3acres bbs
// _ W G _
// _ _ _ W. 1point 3acres 璁哄潧
// _ W _ W
// G W _ _. 1point3acres.com/bbs

String [][] maze = new int [width][height];
boolean [][] wasHere = new boolean[width][height];

public void solution(int maze[x][y], int i, int j, int sol[][]){
    int i = 0;. from: 1point3acres.com/bbs
    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);
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }
}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public int solve_one_position(int maze[x][y], int i, int j, int dist) {
    wasHere[j] = true;

    if (maze[j] == 'G') {
        return dist;
    }

    if (maze[j+1].equals("_")){
        right = solution(maze, i, j+1, dist + 1);. 1point 3acres 璁哄潧
    }
    if (maze[i+1][j].equals("_")){
        up = solution(maze, i+1, j, dist + 1);
    }
    ...
    wasHere[j] = false;
    return min(left, right, up, down);
}


这是输出的结果:
// 3 W G 1
// 2 2 1 W
// 1 W 2 W
// G W 3 4 鏉ユ簮涓浜.涓夊垎鍦拌鍧.



补充内容 (2015-4-8 03:46):
上面的代码是基本的思路,我没有做出来,最后没时间了。

评分

3

查看全部评分

shawlin 发表于 2015-4-8 03:57:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
是找出_到最近的gate的距离吗?
我记得在地里看到过类似的题,思路是BFS, 但先把所有gates的位置放在queue里面. 1point 3acres 璁哄潧
这是那个类似的题目 http://www.1point3acres.com/bbs/thread-127776-1-1.html
地里的资料看来的好好学习啊
回复 支持 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 | 显示全部楼层
实习这么难的题目额
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-4-8 03:53:15 | 显示全部楼层
pat pat,以后还有机会啦!. visit 1point3acres.com for more.
这题G经常考,可以用同步从所有的G开始做DFS
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2015-4-8 05:26):
*BFS, not DFS,具体代码在下面的帖子里,请轻拍 =)
回复 支持 反对

使用道具 举报

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

没办法,实习就是这样。这可能跟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
不是很理解题意。。。是说所有W到所有G的距离?有很多Gate的话,算哪个距离

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

使用道具 举报

marthew777 发表于 2015-4-8 04:29:01 | 显示全部楼层
JermaineDing 发表于 2015-4-8 03:56.鐣欏璁哄潧-涓浜-涓夊垎鍦
大神能把代码贴出来吗,谢谢。

大概是这个意思,其实很简单达!
. more info on 1point3acres.com
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];
. 1point 3acres 璁哄潧        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;. more info on 1point3acres.com
                                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));
. from: 1point3acres.com/bbs                         sol[j-1] = sol[j] + 1;
                        visited[j-1]=true;
                }
                // similarly do: left down and right. visit 1point3acres.com for more.
                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){. visit 1point3acres.com for more.
        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).鏈枃鍘熷垱鑷1point3acres璁哄潧
                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. visit 1point3acres.com for more.
大概是这个意思,其实很简单达!

private enum BLOCK {G, W, O};
.1point3acres缃
请问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) {. from: 1point3acres.com/bbs
  4.                         return res; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.                 }-google 1point3acres
  6.                 int[][] visit = new int[maze.length][maze[0].length];
  7.                 for (int i = 0; i < maze.length; i++) {
    . 1point 3acres 璁哄潧
  8.                         for (int j = 0; j < maze[0].length; j++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9.                                 help(maze, i, j, res, 0 , visit);. more info on 1point3acres.com
  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) {.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.                         . Waral 鍗氬鏈夋洿澶氭枃绔,
  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);. 1point 3acres 璁哄潧
  31.                 help(maze, i, j-1, res, count,visit);. 1point 3acres 璁哄潧
  32.                 visit[i][j] = 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  33.                 count--;
  34.         }
  35.        
  36.         public static void main(String[] args) {
  37.                
  38.                
  39.                 rotate rr = new rotate();. from: 1point3acres.com/bbs
  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] = '_';
    .1point3acres缃
  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';.1point3acres缃
  53.                 maze[3][0] = 'G';. 1point3acres.com/bbs
  54.                 maze[3][1] = 'W';
  55.                 maze[3][2] = '_';
  56.                 maze[3][3] = '_';
  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.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主和我的题目一模一样。。

是什么时候面的?是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
大概是这个意思,其实很简单达!-google 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次测试;
每次测试的输出,第一行是输入的maze: -1 代表Wall, 1代表Gate; 第二行是输出的solution;
回复 支持 反对

使用道具 举报

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

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

. from: 1point3acres.com/bbs
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];.鏈枃鍘熷垱鑷1point3acres璁哄潧
        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[j]==1){
                                Queue<Position> gate = new LinkedList<>();.1point3acres缃
                                gate.add(new Position(i,j));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                queue.add(gate);. 1point 3acres 璁哄潧
                                sol[j] = 0;
                                visited[j] = true;
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        while(!queue.isEmpty()){
                Queue<Position> bfs = queue.poll();
                Position p = bfs.poll();
                int i = p.x, j = p.y;. 鍥磋鎴戜滑@1point 3 acres
                // 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; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                }
                // 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;
                        visited[j+1]=true;
                }
                if(isValid(maze, i-1, j, visited)){. from: 1point3acres.com/bbs
                        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;   .鐣欏璁哄潧-涓浜-涓夊垎鍦
                }. Waral 鍗氬鏈夋洿澶氭枃绔,
                if(!bfs.isEmpty())
                        queue.add(bfs);.1point3acres缃
        }
        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). visit 1point3acres.com for more.
                return false;
        return true;. from: 1point3acres.com/bbs
}
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[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;. 1point 3acres 璁哄潧
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        printMaze(test);
        printMaze(solution(test));
}
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-4-9 07:43):. 鍥磋鎴戜滑@1point 3 acres
以前没有发过代码到帖子里,发现2维数组自动被转成了一维。。擦。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-21 04:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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