近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2591|回复: 10
收起左侧

pocketgem 一轮电面

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

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

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

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

x
pocketgem第一轮电面, 并没有碰到面经里的题, 直接难跪了
没办法贴图,只能自己手动贴题了

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

Data Representation
The map will be passes as an array of strings.

A map can have the following tiles.
0=water. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1=land.鏈枃鍘熷垱鑷1point3acres璁哄潧
2=start.1point3acres缃
3=goal. 1point3acres.com/bbs
uppercase = door
lowercase = key

Example Maps
'no doors'
map_1 = ["02111", . from: 1point3acres.com/bbs
                "01001", . Waral 鍗氬鏈夋洿澶氭枃绔,
                "01003",
                "01001",
                "01111"]
Expected solution:
(1,0) with keys ' '
(2,0) with keys ' '
(3,0) with keys ' '
(4,0) with keys ' '
(4,1) with keys ' '. Waral 鍗氬鏈夋洿澶氭枃绔,
(4,2) with keys ' '-google 1point3acres

'one door'
map_2 = ["02a11",
                "0100A",
                "01003", . 鍥磋鎴戜滑@1point 3 acres
                "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'
(4,2) with keys 'a'
-google 1point3acres


评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| ruiqin 发表于 2016-7-2 07:00:45 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
想了10多分钟  直接放弃了  interview最后把思路告诉我了    的确是用BFS找shortest path    但是graph Node除了要存row,col以外 还要存已经获得的keys    有点像topcoder上关于graph的tutorial    没法贴连接   大家自己google吧    . 1point3acres.com/bbs
挂了电话自己又做了一遍   不熟悉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) {-google 1point3acres
                        Node o = (Node)object;
                        return r == o.r && c == o.c && keys.containsAll(o.keys). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                && o.keys.containsAll(keys);. 鍥磋鎴戜滑@1point 3 acres
                }
. more info on 1point3acres.com
                @Override
                public int hashCode() {
                        return keys.hashCode() + r + c;
                }

                @Override
                public String toString(){
                        return String.format("[%d,%d], with keys:%s", . 1point 3acres 璁哄潧
                                        r, c, keys);
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }

        public static Node shortestPath(String[] map, int sx, int sy) {

               
                Queue<Node> que = new LinkedList<>();
                que.offer(new Node(sx, sy));
                Set<Node> visited = new HashSet<>();
-google 1point3acres
                while (!que.isEmpty()) {
                        Node node = que.poll();. 鍥磋鎴戜滑@1point 3 acres

                        if (map[node.r].charAt(node.c) == '3') {
                                return node;
                        }
.鏈枃鍘熷垱鑷1point3acres璁哄潧
-google 1point3acres
                        int[] arr = {-1,0,1,0,-1};-google 1point3acres
                        for (int i = 0; i < 4; i++) {

                                int r = node.r + arr[i];. visit 1point3acres.com for more.
                                int c = node.c + arr[i+1];

                                if (r < 0 || r >= map.length || c < 0 || c >= map[0].length()) {
                                        continue;
                                }
                                . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                char letter = map[r].charAt(c);
                                if (letter == '0') {
                                        continue;
                                }

                                if ('A' <= letter && letter <= 'Z') {
                                        // System.out.printf("DOOR:%c\n", letter);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                        char key = (char)('a' + (letter - 'A'));.1point3acres缃
                                        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);

                        }

                }
                return null;

        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.鏈枃鍘熷垱鑷1point3acres璁哄潧

        public static void main(String[] args) {
                /*
                String[] map = {"02a11",
                                            "0100A",
                                            "01003", .鐣欏璁哄潧-涓浜-涓夊垎鍦
                                            "01001",
                                            "01111"};                                            
                Node dest = shortestPath(map, 0,1);
                if (dest == null) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        System.out.println("no path");
                } else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        while (dest != null) {
                                System.out.println(dest);
                                dest = dest.parent;
                        }
                }*/
.鏈枃鍘熷垱鑷1point3acres璁哄潧


                String[] map = {"0a2bBA3"};                                            
                Node dest = shortestPath(map, 0,2);. more info on 1point3acres.com
                if (dest == null) {
                        System.out.println("no path");. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                } else {
                        while (dest != null) {
                                System.out.println(dest);. 1point3acres.com/bbs
                                dest = dest.parent;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        }
                }

. 鍥磋鎴戜滑@1point 3 acres
        }
       
}

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

 楼主| 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>.1point3acres缃

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

使用道具 举报

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

使用道具 举报

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

允许走回头路,那么又想不通了...visited应该做怎样相应的改动呢
楼主你这里的处理好像是不走回头路的?遇到visited了就跳过了?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Update:
才注意到楼主override了Node的equals(),所以这样有不同key的同一个位置的node也被视为不同的了!

回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-23 04:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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