一亩三分地论坛

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

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

pocketgem 一轮电面

[复制链接] |试试Instant~ |关注本帖
ruiqin 发表于 2016-7-2 06:47:13 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@PoketGem - 网上海投 - 技术电面 |Fail在职跳槽

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

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

x
pocketgem第一轮电面, 并没有碰到面经里的题, 直接难跪了-google 1point3acres
没办法贴图,只能自己手动贴题了
. 1point 3acres 璁哄潧
suppose you have a 2-D grid, each point is either a land or water. There is also a start point and a goal.
There are now keys that open up door. Each key corresponds to one door.
Implement a function that returns the shortest path from start to goal using land tiles, keys and open doors.

Data Representation. more info on 1point3acres.com
The map will be passes as an array of strings.

A map can have the following tiles.
0=water
1=land
2=start
3=goal.鏈枃鍘熷垱鑷1point3acres璁哄潧
uppercase = door
lowercase = key
. Waral 鍗氬鏈夋洿澶氭枃绔,
Example Maps
'no doors'
map_1 = ["02111", . Waral 鍗氬鏈夋洿澶氭枃绔,
                "01001",
                "01003", . visit 1point3acres.com for more.
                "01001",
                "01111"] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Expected solution:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
(1,0) with keys ' '
(2,0) with keys ' '
(3,0) with keys ' '.鐣欏璁哄潧-涓浜-涓夊垎鍦
(4,0) with keys ' '
(4,1) with keys ' '
(4,2) with keys ' '
-google 1point3acres
'one door'
map_2 = ["02a11",
                "0100A", . 1point 3acres 璁哄潧
                "01003",
                "01001",
                "01111"]
Expected solution:
keeys needed: a
(1,0) with keys ' '
(2,0) with keys ' '
(3,0) with keys 'a'
(4,1) with keys 'a'-google 1point3acres
(4,2) with keys 'a'


. more info on 1point3acres.com

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| ruiqin 发表于 2016-7-2 07:00:45 | 显示全部楼层
想了10多分钟  直接放弃了  interview最后把思路告诉我了    的确是用BFS找shortest path    但是graph Node除了要存row,col以外 还要存已经获得的keys    有点像topcoder上关于graph的tutorial    没法贴连接   大家自己google吧   
挂了电话自己又做了一遍   不熟悉topcoder上那个tutorial还真想不出来   现在面pocketgem还要刷topcoder了?
贴个代码   输入输出并不完全符合题目的要求   .鐣欏璁哄潧-涓浜-涓夊垎鍦

import java.util.*;

public class Solution {
        public static class Node {
                int r;
                int c;
                Set<Character> keys = new HashSet<>();
                Node parent = null;

.鐣欏璁哄潧-涓浜-涓夊垎鍦                Node(int r, int c) {
.鐣欏璁哄潧-涓浜-涓夊垎鍦                        this.r = r;
                        this.c = c;
                }

                @Override
                public boolean equals(Object object) {. From 1point 3acres bbs
                        Node o = (Node)object;. From 1point 3acres bbs
                        return r == o.r && c == o.c && keys.containsAll(o.keys)
                                && o.keys.containsAll(keys);
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦

                @Override
                public int hashCode() {
                        return keys.hashCode() + r + c;
                }
. 1point3acres.com/bbs
                @Override. 1point 3acres 璁哄潧
                public String toString(){
                        return String.format("[%d,%d], with keys:%s",
                                        r, c, keys);
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
-google 1point3acres
        public static Node shortestPath(String[] map, int sx, int sy) {
. from: 1point3acres.com/bbs
                . more info on 1point3acres.com
                Queue<Node> que = new LinkedList<>();
                que.offer(new Node(sx, sy));.鐣欏璁哄潧-涓浜-涓夊垎鍦
                Set<Node> visited = new HashSet<>();

                while (!que.isEmpty()) {
                        Node node = que.poll();

                        if (map[node.r].charAt(node.c) == '3') {
                                return node;
                        }


                        int[] arr = {-1,0,1,0,-1};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        for (int i = 0; i < 4; i++) {

                                int r = node.r + arr[i];
                                int c = node.c + arr[i+1];
. visit 1point3acres.com for more.
                                if (r < 0 || r >= map.length || c < 0 || c >= map[0].length()) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                        continue;
                                }
                               
                                char letter = map[r].charAt(c);
                                if (letter == '0') {
                                        continue;-google 1point3acres
                                }

                                if ('A' <= letter && letter <= 'Z') {
                                        // System.out.printf("DOOR:%c\n", letter);
                                        char key = (char)('a' + (letter - 'A'));
                                        if (!node.keys.contains(key)) {
                                                // System.out.printf("node:%s does NOT contains key\n", node);
                                                continue;
                                        } else {
                                                // System.out.printf("node:%s contains key\n", node);
                                        }
                                }

                                Node neighbor = new Node(r, c);
                                neighbor.parent = node;
                                neighbor.keys.addAll(node.keys);                               
                                if ('a' <= letter && letter <= 'z') {
                                        neighbor.keys.add(letter);
                                }

                                if (visited.contains(neighbor)) {
                                        continue;
                                }

                                que.offer(neighbor);
                                visited.add(neighbor);
. more info on 1point3acres.com
                        }. 1point3acres.com/bbs

                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                return null;

        }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

        public static void main(String[] args) {
                /*
                String[] map = {"02a11",
                                            "0100A",
                                            "01003",
                                            "01001",
. Waral 鍗氬鏈夋洿澶氭枃绔,                                            "01111"};                                            
                Node dest = shortestPath(map, 0,1);
                if (dest == null) {
                        System.out.println("no path");
                } else {
                        while (dest != null) {
                                System.out.println(dest);. more info on 1point3acres.com
                                dest = dest.parent;
                        }. Waral 鍗氬鏈夋洿澶氭枃绔,
                }*/
. Waral 鍗氬鏈夋洿澶氭枃绔,


                String[] map = {"0a2bBA3"};                                            
                Node dest = shortestPath(map, 0,2);
                if (dest == null) {.1point3acres缃
                        System.out.println("no path");. 1point3acres.com/bbs
                } else {
                        while (dest != null) {
                                System.out.println(dest);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                dest = dest.parent;
                        }
                }. 1point 3acres 璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 1point3acres.com/bbs
        }
        . 鍥磋鎴戜滑@1point 3 acres
}

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

hopeisfree 发表于 2016-7-2 23:42:32 | 显示全部楼层
楼主啊,你的输出的坐标是不是打反了,是不是应该是
(0, 1)
(0, 2)
(0, 3)
(0, 4)
(1, 4)
(2. 4)
要不然看不懂这个输出啊. visit 1point3acres.com for more.
还有我大概理解了下,是不是key的tile是可以穿过的,然后穿过了某个key以后,是不是就有点像把这个key拾取了,然后遇到相应的门的话就可以
通过了?如果是这样的话,我感觉一个自然的做法应该就是bfs找最短路径的上面再加一个数组hold一下当前记已经拾取过的key,用来判断遇到门的时候可以可以通过吧。不过题目里面没有看到能不能走回头路,如果能走回头路的话,感觉有点复杂。
. 鍥磋鎴戜滑@1point 3 acres
请教下楼主,谢谢。
回复 支持 反对

使用道具 举报

 楼主| ruiqin 发表于 2016-7-3 00:56:47 | 显示全部楼层
原题上的输出就是这样的   可能他们是用图像里的(x,y)做输出   不是我们常用的(row, col)   所以和我们是反过来的
的确是要先拿到key然后才能过门   
可以走回头路   比如这个map: ”0a2bBA3“    从2开始  先到a  然后再回到2   然后再一直往右走到3
回复 支持 反对

使用道具 举报

ysl12316223 发表于 2016-7-7 12:29:35 | 显示全部楼层
想问下lz做完oa,大概过了多久有消息?多谢!
回复 支持 反对

使用道具 举报

 楼主| ruiqin 发表于 2016-7-7 12:45:04 | 显示全部楼层
做完oa以后四天收到email说要电面
回复 支持 反对

使用道具 举报

ysl12316223 发表于 2016-7-9 00:07:13 | 显示全部楼层
楼主,一个key可以开一次门吗?比如key是a, door是A。如果有好几个门是A,那一把a可以开所有的门还是只能开一次?
回复 支持 反对

使用道具 举报

 楼主| ruiqin 发表于 2016-7-9 00:49:03 | 显示全部楼层
不是很清楚   我感觉是一把可以开几次   不是的话就开完一次就把钥匙删掉就好了   code稍微改改就行
回复 支持 反对

使用道具 举报

zzwcsong 发表于 2016-11-3 06:24:31 | 显示全部楼层
被问到同一道题了,面试官态度好差,还是没做出来- -我应该提前写一遍的,哎

他要求输出List<Point>

想问问楼主,你这里是怎么处理搜索时遇到Door,但是还没有Key的情况啊?感觉考虑这种情况后,很难确定最短路径了
另外,楼主你说的Topcoder链接是下面这两个吗?
https://www.topcoder.com/communi ... ructures-section-2/
http://topcoder.bgcoder.com/print.php?id=180
回复 支持 反对

使用道具 举报

zzwcsong 发表于 2016-11-3 06:29:27 | 显示全部楼层
哦,又看了下楼主代码,大概明白了,就是在还没有Key时,遇到了Door也不把它加入到Neighbour里?迫使程序继续绕开搜索
回复 支持 反对

使用道具 举报

zzwcsong 发表于 2016-11-3 06:37:54 | 显示全部楼层
本帖最后由 zzwcsong 于 2016-11-3 06:59 编辑
ruiqin 发表于 2016-7-3 00:56. From 1point 3acres bbs
原题上的输出就是这样的   可能他们是用图像里的(x,y)做输出   不是我们常用的(row, col)   所以和我们是反 ...

允许走回头路,那么又想不通了...visited应该做怎样相应的改动呢
楼主你这里的处理好像是不走回头路的?遇到visited了就跳过了?

Update:. visit 1point3acres.com for more.
才注意到楼主override了Node的equals(),所以这样有不同key的同一个位置的node也被视为不同的了!

. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 09:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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