[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5455|回复: 5
收起左侧

google foobar题目

[复制链接] |试试Instant~ |关注本帖
wujingzhishui 发表于 2016-9-27 01:01:38 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类General 硕士 全职@Google - Other - 在线笔试  | Other | fresh grad应届毕业生

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

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

x
同学在google foobar上的一道题, 提交时候一直是400 bad request,估计是超时了,分享给我题目和他的解法,求优化
Prepare the Bunnies' Escape. From 1point 3acres bbs
===========================

You're awfully close to destroying the LAMBCHOPdoomsday device and freeing Commander Lambda's bunny prisoners, but oncethey're free of the prison blocks, the bunnies are going to need to escapeLambda's space station via the escape pods as quickly as possible.Unfortunately, the halls of the space station are a maze of corridors and deadends that will be a deathtrap for the escaping bunnies. Fortunately, CommanderLambda has put you in charge of a remodeling project that will give you theopportunity to make things a little easier for the bunnies. Unfortunately(again), you can't just remove all obstacles between the bunnies and the escapepods - at most you can remove one wall per escape pod path, both to maintainstructural integrity of the station and to avoid arousing Commander Lambda'ssuspicions.

You have maps of parts of the space station, each starting at a prison exit andending at the door to an escape pod. The map is represented as a matrix of 0sand 1s, where 0s are passable space and 1s are impassable walls. The door outof the prison is at the top left (0,0) and the door into an escape pod is atthe bottom right (w-1,h-1).

Write a function answer(map) that generates the length of the shortest pathfrom the prison door to the escape pod, where you are allowed to remove onewall as part of your remodeling plans. The path length is the total number ofnodes you pass through, counting both the entrance and exit nodes. The startingand ending positions are always passable (0). The map will always be solvable,though you may or may not need to remove a wall. The height and width of themap can be from 2 to 20. Moves can only be made in cardinal directions; nodiagonal moves are allowed.. visit 1point3acres for more.
Test cases
==========. from: 1point3acres

Inputs:
    (int) maze = [[0, 1, 1, 0], [0, 0, 0,1], [1, 1, 0, 0], [1, 1, 1, 0]]. from: 1point3acres
Output:
    (int) 7.1point3acres网

Inputs:
    (int) maze = [[0, 0, 0, 0, 0, 0], [1,1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0,0, 0, 0, 0, 0]]. Waral 博客有更多文章,
Output:
    (int) 11
未通过答案:(其实我两都在自己机子上通过的,跑的很快,方法就是dfs变形):
public static int answer(int[][] maze) {

        // Your code goes here.
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return dfs(0, 0, true, visited, maze, 1);
    }
    private static int dfs(int x, int y, boolean allowRemove, boolean[][] visited, int[][] maze, int len){
        if(x == maze.length - 1 && y == maze[0].length - 1){
            return len;
        }
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        visited[x][y] = true;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < 4; i++){
           int nx = dx + x;
           int ny = dy + y;
           if(nx < 0 || ny < 0 || nx >= maze.length || ny >= maze[0].length || visited[nx][ny]){
               continue;
           }
           if(maze[nx][ny] == 0){
               min = Math.min(dfs(nx, ny, allowRemove, visited, maze, len + 1), min);
           }else if(allowRemove){
               min = Math.min(dfs(nx, ny, false, visited, maze, len + 1), min);
           }
           if(min == maze.length + maze[0].length - 1){
               break;
           }
        }
        visited[x][y] = false;
        return min;
    }

评分

1

查看全部评分

WhatsFLAG 发表于 2016-9-27 04:02:42 | 显示全部楼层
第一次听说Foobar,Google了一下感觉赞爆了!
回复 支持 反对

使用道具 举报

kolanery 发表于 2016-10-1 08:19:45 | 显示全部楼层
400 bad request好像是foobar的bug...
回复 支持 反对

使用道具 举报

ja0b 发表于 2017-6-17 11:49:22 | 显示全部楼层
所以楼主最后做出来了吗?我也在做这题,想请教一下谢谢!
回复 支持 反对

使用道具 举报

chengguan914 发表于 2017-9-24 06:42:24 | 显示全部楼层
ja0b 发表于 2017-6-17 11:49
所以楼主最后做出来了吗?我也在做这题,想请教一下谢谢!

请问朋友,你做出来了吗?我还在研究这道题。
回复 支持 反对

使用道具 举报

qlwfby 发表于 2017-10-12 04:21:30 | 显示全部楼层
我也写了这题,用两边BFS,第一遍记录最短,第二遍的时候从终点出发,遇到墙就试图拆
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 03:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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