一亩三分地论坛

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

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

Facebook 2015暑期实习面经

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

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

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

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

x
刚刚才面试的Facebook的题目,感觉我没有见过。.1point3acres缃
w是wall,然后g是gates,从“_”开始,找出所有到gates的距离。 我折腾了半天没有做出来,面试官还是挺耐心的,全当是积累经验了。
// _ W G _
// _ _ _ W
// _ W _ W
// G W _ _
.1point3acres缃
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;
    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);. more info on 1point3acres.com
        }. more info on 1point3acres.com
    }
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧. From 1point 3acres bbs
public int solve_one_position(int maze[x][y], int i, int j, int dist) {
    wasHere[j] = true;
.1point3acres缃
    if (maze[j] == 'G') {
        return dist;
    }

    if (maze[j+1].equals("_")){
        right = solution(maze, i, j+1, dist + 1);
    }
    if (maze[i+1][j].equals("_")){
        up = solution(maze, i+1, j, dist + 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
    }
    ...
    wasHere[j] = false;. 1point 3acres 璁哄潧
    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 | 显示全部楼层
是找出_到最近的gate的距离吗?
我记得在地里看到过类似的题,思路是BFS, 但先把所有gates的位置放在queue里面
这是那个类似的题目 http://www.1point3acres.com/bbs/thread-127776-1-1.html
地里的资料看来的好好学习啊
回复 支持 1 反对 0

使用道具 举报

flyPacific111 发表于 2015-4-8 03:41:37 | 显示全部楼层
这题不简单啊...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,以后还有机会啦!
这题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的话,算哪个距离. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

 楼主| JermaineDing 发表于 2015-4-8 04:07:30 | 显示全部楼层
shawlin 发表于 2015-4-8 03:57
是找出_到最近的gate的距离吗?
我记得在地里看到过类似的题,思路是BFS, 但先把所有gates的位置放在queue ...
. 鍥磋鎴戜滑@1point 3 acres
嗯,有点类似。
回复 支持 反对

使用道具 举报

 楼主| 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
大神能把代码贴出来吗,谢谢。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
大概是这个意思,其实很简单达!

private enum BLOCK {G, W, O};
public void solution(int[][] maze){
        int m = maze.length;.1point3acres缃
        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).鏈枃鍘熷垱鑷1point3acres璁哄潧
                        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();-google 1point3acres
                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;
. more info on 1point3acres.com                }
                // similarly do: left down and right
                if(isValid(maze, i, j+1, visited)){
                        //...
                }
                if(isValid(maze, i-1, j, visited)){. 1point3acres.com/bbs
                        //...                       
                }
                if(isValid(maze, i+1, j, visited)){
                        //...                . from: 1point3acres.com/bbs
                }
        }
}
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;. from: 1point3acres.com/bbs
        if(i<0 || i >= m || j < 0 || j >= n || visited[j] || maze[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>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.                 }. more info on 1point3acres.com
  13.                
  14.                 return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.         }
  16.         . from: 1point3acres.com/bbs
  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.                         . 1point3acres.com/bbs
  20.                         return;
  21.                 }else if (maze[i][j] == 'G') {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.                         res.add(count);
  23.                        
  24.                         return;
  25.                 }
  26.                 visit[i][j] = 1;. From 1point 3acres bbs
  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);. more info on 1point3acres.com
  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.                 . From 1point 3acres bbs
  38.                
  39.                 rotate rr = new rotate();
  40.                 char[][] maze = new char[4][4];.1point3acres缃
  41.                 maze[0][0] = '_';. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  42.                 maze[0][1] = 'W';
  43.                 maze[0][2] = 'G';.1point3acres缃
  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] = '_';. From 1point 3acres bbs
  52.                 maze[2][3] = 'W';. visit 1point3acres.com for more.
  53.                 maze[3][0] = 'G';
  54.                 maze[3][1] = 'W';
  55.                 maze[3][2] = '_';
  56.                 maze[3][3] = '_';
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  57.                
    . from: 1point3acres.com/bbs
  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吗?
.1point3acres缃
恩,礼拜一面的,我之前在地里也没见过这题,然后我用dfs写的,但是应该是有bug,后来没时间了,昨天收到rej
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-9 05:30:56 | 显示全部楼层
marthew777 发表于 2015-4-8 04:29.1point3acres缃
大概是这个意思,其实很简单达!

private enum BLOCK {G, W, O};
. Waral 鍗氬鏈夋洿澶氭枃绔,
哥,你这代码有问题呀,略坑...
回复 支持 反对

使用道具 举报

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.1point3acres缃
哥,你这代码有问题呀,略坑...

. Waral 鍗氬鏈夋洿澶氭枃绔,上面的代码我说了是给一个算法实现的大概思路,肯定有syntax error的好吗,我花几分钟随手写的。。. Waral 鍗氬鏈夋洿澶氭枃绔,
完整代码我分享出来给大家好了!测试过的,没问题,您看看这次还有问题么.鐣欏璁哄潧-涓浜-涓夊垎鍦
. more info on 1point3acres.com

import java.util.*;
class Solution{
public static int[][] solution(int[][] maze){. more info on 1point3acres.com
        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);. from: 1point3acres.com/bbs
        Queue<Queue<Position>> queue = new LinkedList<>();
        for(int i=0;i<m;++i).鏈枃鍘熷垱鑷1point3acres璁哄潧
                for(int j=0;j<n;++j)
                        if(maze[j]==1){
                                Queue<Position> gate = new LinkedList<>();
                                gate.add(new Position(i,j));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                queue.add(gate);
                                sol[j] = 0;. visit 1point3acres.com for more.
                                visited[j] = true;
                        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        while(!queue.isEmpty()){
                Queue<Position> bfs = queue.poll();
                Position p = bfs.poll();
                int i = p.x, j = p.y;-google 1point3acres
                // 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. more info on 1point3acres.com
                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)){
                        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));.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        sol[i+1][j] = sol[j] + 1;
                        visited[i+1][j]=true;   
                }. 1point3acres.com/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). 1point3acres.com/bbs
                return false;. Waral 鍗氬鏈夋洿澶氭枃绔,
        return true;
}
public static class Position{
        public int x;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        public int y;
        public Position(int x, int y){. from: 1point3acres.com/bbs
                this.x = x; this.y = y;
        }
}
public static void printMaze(int[][] maze){
        System.out.println(Arrays.deepToString(maze));
}
public static void main(String[] args){. From 1point 3acres bbs
        // 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++)
. visit 1point3acres.com for more.                        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);. From 1point 3acres bbs
                int y = rdm.nextInt(size);
                test[x][y] = -1;
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        printMaze(test);
        printMaze(solution(test));
}
}

.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2015-4-9 07:43):
以前没有发过代码到帖子里,发现2维数组自动被转成了一维。。擦。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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