我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 3330|回复: 10
收起左侧

pocketgem 一轮电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
ruiqin 发表于 2016-7-2 06:47:13 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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.

Data Representation
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
uppercase = door
lowercase = key

Example Maps
'no doors'
map_1 = ["02111",
                "01001", . 一亩-三分-地,独家发布
                "01003",
                "01001",
                "01111"]
Expected solution:. 一亩-三分-地,独家发布
(1,0) with keys ' '
(2,0) with keys ' '
(3,0) with keys ' '. 1point 3acres 论坛
(4,0) with keys ' '
(4,1) with keys ' '
(4,2) with keys ' '

'one door'
map_2 = ["02a11",
                "0100A",
                "01003", . more info on 1point3acres
                "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'. from: 1point3acres
(4,2) with keys 'a'

. 1point 3acres 论坛. 1point3acres

评分

5

查看全部评分


上一篇:有小伙伴面过Machine Zone的吗?
下一篇:Uber面經

本帖被以下淘专辑推荐:

我的人缘0
 楼主| ruiqin 发表于 2016-7-2 07:00:45 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
想了10多分钟  直接放弃了  interview最后把思路告诉我了    的确是用BFS找shortest path    但是graph Node除了要存row,col以外 还要存已经获得的keys    有点像topcoder上关于graph的tutorial    没法贴连接   大家自己google吧   
挂了电话自己又做了一遍   不熟悉topcoder上那个tutorial还真想不出来   现在面pocketgem还要刷topcoder了?
贴个代码   输入输出并不完全符合题目的要求   
. from: 1point3acres
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) {.本文原创自1point3acres论坛
                        this.r = r;
                        this.c = c;
                }

                @Override
                public boolean equals(Object object) {. more info on 1point3acres
                        Node o = (Node)object;
                        return r == o.r && c == o.c && keys.containsAll(o.keys). 一亩-三分-地,独家发布
                                && o.keys.containsAll(keys);
                }.留学论坛-一亩-三分地

                @Override
                public int hashCode() {
                        return keys.hashCode() + r + c;
                }
. From 1point 3acres bbs
                @Override. more info on 1point3acres
                public String toString(){. from: 1point3acres
                        return String.format("[%d,%d], with keys:%s",
                                        r, c, keys);
                }
        }. 1point3acres

        public static Node shortestPath(String[] map, int sx, int sy) {
. visit 1point3acres for more.
               
                Queue<Node> que = new LinkedList<>();
                que.offer(new Node(sx, sy));
                Set<Node> visited = new HashSet<>();

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

                        if (map[node.r].charAt(node.c) == '3') {
                                return node;.本文原创自1point3acres论坛
                        }


                        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];

                                if (r < 0 || r >= map.length || c < 0 || c >= map[0].length()) {
                                        continue;
                                }
                                -google 1point3acres
                                char letter = map[r].charAt(c);
                                if (letter == '0') {
                                        continue;
                                }
.本文原创自1point3acres论坛
                                if ('A' <= letter && letter <= 'Z') {. 1point3acres
                                        // 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);. 围观我们@1point 3 acres
                                                continue;
                                        } else {
                                                // System.out.printf("node:%s contains key\n", node);
                                        }. 一亩-三分-地,独家发布
                                }
. From 1point 3acres bbs
                                Node neighbor = new Node(r, c);. more info on 1point3acres
                                neighbor.parent = node;
                                neighbor.keys.addAll(node.keys);                               
                                if ('a' <= letter && letter <= 'z') {. from: 1point3acres
                                        neighbor.keys.add(letter);. From 1point 3acres bbs
                                }

                                if (visited.contains(neighbor)) {
                                        continue;. 一亩-三分-地,独家发布
                                }.本文原创自1point3acres论坛

                                que.offer(neighbor);
                                visited.add(neighbor);-google 1point3acres

                        }
. from: 1point3acres
                }. visit 1point3acres for more.
                return null;

        }. 一亩-三分-地,独家发布


        public static void main(String[] args) {
                /*
                String[] map = {"02a11", . Waral 博客有更多文章,
                                            "0100A",
                                            "01003",
                                            "01001",
                                            "01111"};                                            
                Node dest = shortestPath(map, 0,1);. 牛人云集,一亩三分地
                if (dest == null) {. Waral 博客有更多文章,
                        System.out.println("no path");
                } else {
                        while (dest != null) {
                                System.out.println(dest);
                                dest = dest.parent;
                        }
                }*/


-google 1point3acres
                String[] map = {"0a2bBA3"};                                            
                Node dest = shortestPath(map, 0,2);
                if (dest == null) {
                        System.out.println("no path");
                } else {
                        while (dest != null) {
                                System.out.println(dest);
                                dest = dest.parent;.本文原创自1point3acres论坛
                        }
                }

. 牛人云集,一亩三分地
        }
        . 留学申请论坛-一亩三分地
}

评分

3

查看全部评分

回复 支持 3 反对 0

使用道具 举报

我的人缘0
hopeisfree 发表于 2016-7-2 23:42:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主啊,你的输出的坐标是不是打反了,是不是应该是
(0, 1) 来源一亩.三分地论坛.
(0, 2)
(0, 3)
(0, 4). 1point 3acres 论坛
(1, 4). From 1point 3acres bbs
(2. 4)
要不然看不懂这个输出啊
还有我大概理解了下,是不是key的tile是可以穿过的,然后穿过了某个key以后,是不是就有点像把这个key拾取了,然后遇到相应的门的话就可以.1point3acres网
通过了?如果是这样的话,我感觉一个自然的做法应该就是bfs找最短路径的上面再加一个数组hold一下当前记已经拾取过的key,用来判断遇到门的时候可以可以通过吧。不过题目里面没有看到能不能走回头路,如果能走回头路的话,感觉有点复杂。-google 1point3acres

请教下楼主,谢谢。
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
ysl12316223 发表于 2016-7-7 12:29:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
想问下lz做完oa,大概过了多久有消息?多谢!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| ruiqin 发表于 2016-7-7 12:45:04 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
做完oa以后四天收到email说要电面
回复 支持 反对

使用道具 举报

我的人缘0
ysl12316223 发表于 2016-7-9 00:07:13 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主,一个key可以开一次门吗?比如key是a, door是A。如果有好几个门是A,那一把a可以开所有的门还是只能开一次?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| ruiqin 发表于 2016-7-9 00:49:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
不是很清楚   我感觉是一把可以开几次   不是的话就开完一次就把钥匙删掉就好了   code稍微改改就行
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
zzwcsong 发表于 2016-11-3 06:24:31 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
被问到同一道题了,面试官态度好差,还是没做出来- -我应该提前写一遍的,哎

他要求输出List<Point>

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

使用道具 举报

我的人缘0
zzwcsong 发表于 2016-11-3 06:29:27 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
哦,又看了下楼主代码,大概明白了,就是在还没有Key时,遇到了Door也不把它加入到Neighbour里?迫使程序继续绕开搜索
回复 支持 反对

使用道具 举报

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

允许走回头路,那么又想不通了...visited应该做怎样相应的改动呢
楼主你这里的处理好像是不走回头路的?遇到visited了就跳过了?
. 围观我们@1point 3 acres
Update:
才注意到楼主override了Node的equals(),所以这样有不同key的同一个位置的node也被视为不同的了!

回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-28 07:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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