Pocket Gems 两轮电面.

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

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

2. 给一个Robot class, 有moveUp()等向4个方向移动的func

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

se pairs 想了白天没思路 提示divide and conquer，还是没思路，最后说没事这道是extra的。

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

1. import java.util.*;
   
2. 
   
3. class Main {
   
4.   public static void main(String[] args) {
   
5.     Robot r = new Robot();
   
6.     char[][] maze = {
   
7.       {'T', 'T', 'T', 'F'},
   
8.       {'F', 'T', 'F', 'T'},
   
9.       {'F', 'T', 'T', 'T'}
   
10.     };
    
11.     List<String> res = r.findPath(maze, 1, 1);
    
12.     System.out.println(String.join(" ", res));
    
13.   }
    
14. }
    
15. 
    
16. class Robot {
    
17.   private List<String> path;
    
18.   private final Map<Integer, String> dirMap;
    
19.   private int count;
    
20.   Robot() {
    
21.     this.dirMap = new HashMap<>();
    
22.     dirMap.put(0, "up");
    
23.     dirMap.put(1, "right");
    
24.     dirMap.put(2, "down");
    
25.     dirMap.put(3, "left");
    
26.   }
    
27.   public List<String> findPath(char[][] maze, int x, int y) {
    
28.     path = null;
    
29.     int m = maze.length;
    
30.     int n = maze[0].length;
    
31.     count = 0;
    
32.     for (int i = 0; i < m; i++) {
    
33.       for (int j = 0; j < n; j++) {
    
34.         if (maze[i][j] == 'T') {
    
35.           count++;
    
36.         }
    
37.       }
    
38.     }
    
39.    
    
40.     boolean[][] visited = new boolean[m][n];
    
41.     dfs(maze, x, y, visited, new ArrayList<>(), -1);
    
42.    
    
43.     return path == null ? new ArrayList<String>() : path;
    
44.   }
    
45.   
    
46.   private void dfs(char[][] maze, int x, int y, boolean[][] visited, List<String> curPath, int comingDirection) {
    
47.     int m = maze.length;
    
48.     int n = maze[0].length;
    
49.     visited[x][y] = true;
    
50.     count--;
    
51.    
    
52.     if (count == 0) {
    
53.       if (path == null) {
    
54.         path = curPath;
    
55.       }
    
56.       return;
    
57.     }
    
58.    
    
59.     int[][] dirs = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    
60.     for (int i = 0; i < 4; i++) {
    
61.       int xx = x + dirs[i][0];
    
62.       int yy = y + dirs[i][1];
    
63.       
    
64.       if (xx < 0 || xx >= m || yy < 0 || yy >= n || visited[xx][yy] || maze[xx][yy] == 'F') {
    
65.         continue;
    
66.       }
    
67.       curPath.add(dirMap.get(i));
    
68.       dfs(maze, xx, yy, visited, curPath, i);
    
69.     }
    
70.    
    
71.     if (comingDirection != -1 && path == null) {
    
72.       curPath.add(dirMap.get((comingDirection + 2) % 4));
    
73.     }
    
74.   }
    
75. }

复制代码

贴个解法https://repl.it/JkZ4/2

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

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这道robot maze的问题有要求路径最短么

wangkd93 发表于 2017-7-24 02:32
这道robot maze的问题有要求路径最短么

没有。字数字数字数

Soap.cmu 发表于 2017-7-25 03:49
没有。字数字数字数

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

请问楼主是18年春季毕业吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

milanow 发表于 2017-7-25 05:46
第二题感觉其实只要follow一个策略就好了，我的策略是建立一个stack和visited的map，先按照“逢岔左走”找 ...

正解。字数字数字数

wangkd93 发表于 2017-7-25 12:28
 我理解的你的思路就是首先给robot设定一个移动方向的优先级，比如说“上左下右”，上的优先级最高 ...

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