📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 20
跳转到指定楼层
上一主题 下一主题
收起左侧

Pocket Gems 两轮电面.

全局:

2017(7-9月) 码农类General 硕士 全职@pocketgems - 内推 - 技术电面  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
刚结束2面,碰到一到疑似新题,所以发个帖。
美国小哥,最后问他说自己是oversee别人的,感觉类似技术manager

两道题
1.sort color 批了件外皮。一个Object里面有个char variable,可能的value有‘r' 'g' 'b'。

2. 给一个Robot class, 有moveUp()等向4个方向移动的function。给
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
se pairs 想了白天没思路 提示divide and conquer,还是没思路,最后说没事这道是extra的。

补充内容 (2017-8-2 04:57):
已经收到邮件挂了 大家好运

评分

参与人数 2大米 +53 收起 理由
夏虫不知雪花 + 50
dukecat0613 + 3 感谢分享!

查看全部评分


上一篇:2017 SDE intern amazon OA2 面经
下一篇:Nerd钱包 简单电面挂。。。
全局:
  1. import java.util.*;

  2. class Main {
  3.   public static void main(String[] args) {
  4.     Robot r = new Robot();
  5.     char[][] maze = {
  6.       {'T', 'T', 'T', 'F'},
  7.       {'F', 'T', 'F', 'T'},
  8.       {'F', 'T', 'T', 'T'}
  9.     };
  10.     List<String> res = r.findPath(maze, 1, 1);
  11.     System.out.println(String.join(" ", res));
  12.   }
  13. }

  14. class Robot {
  15.   private List<String> path;
  16.   private final Map<Integer, String> dirMap;
  17.   private int count;
  18.   Robot() {
  19.     this.dirMap = new HashMap<>();
  20.     dirMap.put(0, "up");
  21.     dirMap.put(1, "right");
  22.     dirMap.put(2, "down");
  23.     dirMap.put(3, "left");
  24.   }
  25.   public List<String> findPath(char[][] maze, int x, int y) {
  26.     path = null;
  27.     int m = maze.length;
  28.     int n = maze[0].length;
  29.     count = 0;
  30.     for (int i = 0; i < m; i++) {
  31.       for (int j = 0; j < n; j++) {
  32.         if (maze[i][j] == 'T') {
  33.           count++;
  34.         }
  35.       }
  36.     }
  37.    
  38.     boolean[][] visited = new boolean[m][n];
  39.     dfs(maze, x, y, visited, new ArrayList<>(), -1);
  40.    
  41.     return path == null ? new ArrayList<String>() : path;
  42.   }
  43.   
  44.   private void dfs(char[][] maze, int x, int y, boolean[][] visited, List<String> curPath, int comingDirection) {
  45.     int m = maze.length;
  46.     int n = maze[0].length;
  47.     visited[x][y] = true;
  48.     count--;
  49.    
  50.     if (count == 0) {
  51.       if (path == null) {
  52.         path = curPath;
  53.       }
  54.       return;
  55.     }
  56.    
  57.     int[][] dirs = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
  58.     for (int i = 0; i < 4; i++) {
  59.       int xx = x + dirs[i][0];
  60.       int yy = y + dirs[i][1];
  61.       
  62.       if (xx < 0 || xx >= m || yy < 0 || yy >= n || visited[xx][yy] || maze[xx][yy] == 'F') {
  63.         continue;
  64.       }
  65.       curPath.add(dirMap.get(i));
  66.       dfs(maze, xx, yy, visited, curPath, i);
  67.     }
  68.    
  69.     if (comingDirection != -1 && path == null) {
  70.       curPath.add(dirMap.get((comingDirection + 2) % 4));
  71.     }
  72.   }
  73. }
复制代码
贴个解法https://repl.it/JkZ4/2

补充内容 (2017-7-26 20:44):
大概思路就是纯dfs,记录每次所到点来的方向,在每个路口所有4个方向走完返回前,把一个反方向加到路径里(L71-73)
回复

使用道具 举报

推荐
milanow 2017-7-25 05:46:11 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
wangkd93 2017-7-25 12:28:40 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
wangkd93 2017-7-24 02:32:42 | 只看该作者
全局:
这道robot maze的问题有要求路径最短么
回复

使用道具 举报

🔗
 楼主| Soap.cmu 2017-7-25 03:49:43 | 只看该作者
全局:
wangkd93 发表于 2017-7-24 02:32
这道robot maze的问题有要求路径最短么

没有。字数字数字数
回复

使用道具 举报

🔗
wangkd93 2017-7-25 04:54:07 | 只看该作者
全局:
Soap.cmu 发表于 2017-7-25 03:49
没有。字数字数字数

LZ能分享下这道题的你的大概思路么, 主要是什么时候该往回走这部分我有点不太清楚
回复

使用道具 举报

🔗
ydyfeatherlet 2017-7-25 15:35:23 | 只看该作者
全局:
请问楼主是18年春季毕业吗?
回复

使用道具 举报

🔗
milanow 2017-7-26 00:24:47 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| Soap.cmu 2017-7-27 03:29:20 | 只看该作者
全局:
milanow 发表于 2017-7-25 05:46
第二题感觉其实只要follow一个策略就好了,我的策略是建立一个stack和visited的map,先按照“逢岔左走”找 ...

正解。字数字数字数
回复

使用道具 举报

🔗
 楼主| Soap.cmu 2017-7-27 03:31:59 | 只看该作者
全局:
wangkd93 发表于 2017-7-25 12:28
 我理解的你的思路就是首先给robot设定一个移动方向的优先级,比如说“上左下右”,上的优先级最高 ...

可以每逢岔路的时候都一个记录,选择一条路的时候这个记号告诉你还需不需要回头。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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