回复: 37
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook 2015暑期实习面经

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

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

public void solution(int ma
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
   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大米 +55 收起 理由
huangyu + 10 感谢分享!
碇真嗣 + 5 感谢分享!
wrj5518 + 40

查看全部评分


上一篇:求groupon ds面经
下一篇:Google 第二轮 phone screen
推荐
shawlin 2015-4-8 03:57:01 | 只看该作者
全局:
是找出_到最近的gate的距离吗?
我记得在地里看到过类似的题,思路是BFS, 但先把所有gates的位置放在queue里面
这是那个类似的题目 http://www.1point3acres.com/bbs/thread-127776-1-1.html
地里的资料看来的好好学习啊
回复

使用道具 举报

全局:
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维数组自动被转成了一维。。擦。。
回复

使用道具 举报

推荐
siren01 2015-4-9 09:11:38 | 只看该作者
全局:
时间空间复杂度都是O(m*n), 每个点遍历一次即可
  1. //Assume '_' is 0, 'G' is 1, 'W' is 2
  2.         private class Position{
  3.                 int x;
  4.                 int y;
  5.                 public Position(int x, int y){
  6.                         this.x = x;
  7.                         this.y = y;
  8.                 }
  9.         }
  10.         public void findLen(int[][] matrix){
  11.                 int m = matrix.length;
  12.                 if(m<1) return;
  13.                 int n = matrix[0].length;
  14.                 int[][] result = new int[m][n];
  15.                 boolean[][] visited = new boolean[m][n];
  16.                 Queue<Position> queue = new LinkedList<Position>();
  17.                 int curLevel_nums = 0;
  18.                 int nextLevel_nums = 0;
  19.                 int level = 1;
  20.                 for(int i=0; i<m; ++i){
  21.                         for(int j=0; j<n; ++j){
  22.                                 if(matrix[i][j] == 1){//enqueue gate
  23.                                         visited[i][j] = true;
  24.                                         queue.add(new Position(i, j));
  25.                                         curLevel_nums++;
  26.                                 }
  27.                         }
  28.                 }
  29.                 while(!queue.isEmpty()){
  30.                         Position cur = queue.poll();
  31.                         curLevel_nums--;
  32.                         int[] arr = {1,-1,1,-1};
  33.                         for(int i=0; i<arr.length; ++i){
  34.                                 Position newP;
  35.                                 if(i<2){
  36.                                         newP = new Position(cur.x+arr[i], cur.y);
  37.                                 }
  38.                                 else{
  39.                                         newP = new Position(cur.x, cur.y+arr[i]);
  40.                                 }
  41.                                 if(newP.x<0 || newP.x>=m || newP.y<0 || newP.y>=n || visited[newP.x][newP.y]){
  42.                                         continue;
  43.                                 }
  44.                                 else{
  45.                                         if(matrix[newP.x][newP.y]==2){
  46.                                                 visited[newP.x][newP.y] = true;
  47.                                                 result[newP.x][newP.y] = -1;
  48.                                         }
  49.                                         else{//matrix[newP.x][newP.y]==0
  50.                                                 visited[newP.x][newP.y] = true;
  51.                                                 result[newP.x][newP.y] = level;
  52.                                                 queue.add(newP);
  53.                                                 nextLevel_nums++;
  54.                                         }
  55.                                 }
  56.                         }
  57.                         if(curLevel_nums==0){
  58.                                 curLevel_nums = nextLevel_nums;
  59.                                 nextLevel_nums = 0;
  60.                                 level++;
  61.                         }
  62.                 }
  63.                
  64.                 //print
  65.                 for(int i=0; i<m; ++i){
  66.                         for(int j=0; j<n; ++j){
  67.                                 System.out.print(result[i][j]+ "  ");
  68.                         }
  69.                         System.out.println();
  70.                 }
  71.         }
复制代码
回复

使用道具 举报

全局:
这题不简单啊...lz啥时候投的intern啊?过了多久让面试的啊?
回复

使用道具 举报

🔗
 楼主| JermaineDing 2015-4-8 03:45:26 | 只看该作者
全局:
flyPacific111 发表于 2015-4-8 03:41
这题不简单啊...lz啥时候投的intern啊?过了多久让面试的啊?

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

使用道具 举报

全局:
实习这么难的题目额
回复

使用道具 举报

🔗
Mr.Sagemaker 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的话,算哪个距离
回复

使用道具 举报

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

嗯,有点类似。
回复

使用道具 举报

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

本版积分规则

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