《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4672|回复: 5
收起左侧

google foobar题目

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

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

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

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

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

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). .鏈枃鍘熷垱鑷1point3acres璁哄潧

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.
Test cases
==========.鏈枃鍘熷垱鑷1point3acres璁哄潧

Inputs: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    (int) maze = [[0, 1, 1, 0], [0, 0, 0,1], [1, 1, 0, 0], [1, 1, 1, 0]]
Output:
    (int) 7

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]]
Output:
. visit 1point3acres.com for more.    (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;
    }
. 1point3acres.com/bbs

评分

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,第一遍记录最短,第二遍的时候从终点出发,遇到墙就试图拆
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 15:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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