推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

Snapchat面经

[复制链接] |试试Instant~ |关注本帖
又见紫风铃 发表于 2015-10-31 06:40:21 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
人生最糟糕的一次电面,两小时本来要做两道题的,最后一道都没有debug出来,而且还是我很熟悉的BFS找路径类的问题,snapchat还是很喜欢的,这两天把地里的snapchat面经全部刷了写了一遍,结果因为python的初始化矩阵的问题挂了,觉得很遗憾,不能去venice beach了。

清华的国人大哥,非常亲切,觉得没面好真的对不起
M*N的地图上0表示可以走,1表示不能走,求从左上角到右下角的最短路径
很显然的BFS,也很快把基本的写出来了,然而我BFS每一步存了路径,大哥说这样内存消耗太大,怎么improve,然后在提示下想到每个node存一个路径上从哪来的信息,最后反过来打印。. from: 1point3acres.com/bbs
然而悲剧就此来了,因为存的坐标信息是(x,y),python的tuple是immutable的,存[x,y]的list初始化成M*N又有问题。然后想着建个class用coordinates表示x,y,然后一直有bug,到结束了都没有run出来,面完多看了眼就发现初始化coordinate的class应该初始化M*N个而不是直接复制(那样都是引用,导致最后改一个都改了)。因为这种问题跪了真是不甘心

附上代码吧,挺简单的
  1. <div>class Coordinates:</div><div>    def __init__(self, x, y):</div><div>        self.a = x</div><div>        self.b = y</div><div>
  2. </div><div>class Solution:</div><div>    def findPath(self, matrix):</div><div>        if not matrix or not matrix[0]: return []</div><div>        m = len(matrix)</div><div>        n = len(matrix[0])</div><div>        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]</div><div>        formerSteps = []</div><div>        for p in range(m):</div><div>            line = []</div><div>            for k in range(n):</div><div>                line.append(Coordinates(None, None))</div><div>            formerSteps.append(line)</div><div>
  3. </div><div>        find = False</div><div>
  4. </div><div>        queue = [(0, 0, (None, None))]</div><div>
  5. </div><div>        while queue:</div><div>            x, y, formerCoordinates = queue.pop(0)</div><div>            formerSteps[x][y].a = formerCoordinates[0]</div><div>            formerSteps[x][y].b = formerCoordinates[1]</div><div>
  6. </div><div>            if x == m - 1 and y == n - 1:</div><div>                find = True</div><div>                break</div><div>
  7. </div><div>            matrix[x][y] = -1</div><div>-google 1point3acres
  8. </div><div>            for k in range(4):</div><div>                newX = x + directions[k][0]</div><div>                newY = y + directions[k][1]</div><div>
  9. </div><div>                if newX < 0 or newX >= m or newY < 0 or newY >= n or matrix[newX][newY] == 1 or matrix[newX][newY] == -1:</div><div>                    continue</div><div>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10. </div><div>                queue.append((newX, newY, (x, y)))</div><div>
  11. </div><div>        if not find:</div><div>            return []</div><div>        else:</div><div>            res = []</div><div>            i, j = m - 1, n - 1</div><div>            while i != None and j != None:</div><div>                res.insert(0, (i, j))</div><div>                temp = formerSteps[i][j]</div><div>                i, j = temp.a, temp.b</div><div>            return res</div><div>
  12. </div><div>solution = Solution()</div><div>matrix = [[0, 0, 0], [0,0,0], [0, 0, 0]]</div><div>matrix = [[0,0,0], [1,1,0], [0,0,0], [0,1,1], [0,0,0]]</div><div>print solution.findPath(matrix)</div>
复制代码

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 又见紫风铃 发表于 2015-10-31 06:40:39 | 显示全部楼层
  1. class Coordinates:
  2.     def __init__(self, x, y):
  3.         self.a = x
  4.         self.b = y

  5. class Solution:
  6.     def findPath(self, matrix):
  7.         if not matrix or not matrix[0]: return [].1point3acres缃
  8.         m = len(matrix)
  9.         n = len(matrix[0])
  10.         directions = [(1, 0), (-1, 0), (0, 1), (0, -1)].鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.         formerSteps = []
  12.         for p in range(m):
  13.             line = [].鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.             for k in range(n):
  15.                 line.append(Coordinates(None, None))
  16.             formerSteps.append(line)

  17.         find = False

  18.         queue = [(0, 0, (None, None))]
  19. . 鍥磋鎴戜滑@1point 3 acres
  20.         while queue:
  21.             x, y, formerCoordinates = queue.pop(0)
  22.             formerSteps[x][y].a = formerCoordinates[0]
  23.             formerSteps[x][y].b = formerCoordinates[1]

  24.             if x == m - 1 and y == n - 1:
  25.                 find = True
  26.                 break
  27. . 1point3acres.com/bbs
  28.             matrix[x][y] = -1

  29.             for k in range(4):
  30.                 newX = x + directions[k][0] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                 newY = y + directions[k][1]

  32.                 if newX < 0 or newX >= m or newY < 0 or newY >= n or matrix[newX][newY] == 1 or matrix[newX][newY] == -1:
  33.                     continue

  34.                 queue.append((newX, newY, (x, y))). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  35.         if not find:
  36.             return []
  37.         else:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  38.             res = []
  39.             i, j = m - 1, n - 1
  40.             while i != None and j != None:. 鍥磋鎴戜滑@1point 3 acres
  41.                 res.insert(0, (i, j))
  42.                 temp = formerSteps[i][j]
  43.                 i, j = temp.a, temp.b. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  44.             return res.1point3acres缃
  45. . 1point 3acres 璁哄潧
  46. solution = Solution()
  47. matrix = [[0, 0, 0], [0,0,0], [0, 0, 0]]
  48. matrix = [[0,0,0], [1,1,0], [0,0,0], [0,1,1], [0,0,0]]
  49. print solution.findPath(matrix)
复制代码
回复 支持 反对

使用道具 举报

han275 发表于 2015-11-2 07:31:42 | 显示全部楼层
这个只是找到路径啊,没有最短啊,最短是不是应该用DP?
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-2 07:34:12 | 显示全部楼层
han275 发表于 2015-11-2 07:31
这个只是找到路径啊,没有最短啊,最短是不是应该用DP?

BFS的话从起点出发先处理所有距离为1的,再处理所有距离为2的。。。所以应该第一次发现是终点的这条路径就是最短的了吧
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-11-2 08:39:53 | 显示全部楼层
能否直接用dp?然后同时记录是从左边来的还是从上面来的
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-2 08:42:28 | 显示全部楼层
majiamajia 发表于 2015-11-2 08:39. from: 1point3acres.com/bbs
能否直接用dp?然后同时记录是从左边来的还是从上面来的

应该可以,但不只是左边和上面了,四个方向都有可能来。
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-11-2 08:44:28 | 显示全部楼层
又见紫风铃 发表于 2015-11-2 08:42
应该可以,但不只是左边和上面了,四个方向都有可能来。

嗯嗯有道理,所以要么就是DP里面每个CELL存从哪个方向来的。
回复 支持 反对

使用道具 举报

importcoder 发表于 2016-9-13 01:45:14 | 显示全部楼层
只求能否到达的话应该可以用dp,如果要求所有路径的话可能要用dfs
  1. public class ShortestPath {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.     鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.     public List<List<Integer>> shortestPath(int[][] board) {
  4.         List<List<Integer>> result = new ArrayList<>();
  5.         int m = board.length;
  6.         int n = board[0].length;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7.         Queue<Integer> queue = new LinkedList<>();
  8.         queue.offer(0 * n + 0);
  9.         Map<Integer, Integer> map = new HashMap<>();
  10.         while (!queue.isEmpty()) {
  11.             int cur = queue.poll();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.             int i = cur / m;
  13.             int j = cur % n;
  14.             if (i == m - 1 && j == n - 1) {-google 1point3acres
  15.                 break;
    -google 1point3acres
  16.             }
  17.             if (i > 0 && board[i - 1][j] == 0 && !map.containsKey((i - 1) * n + j)) {
  18.                 map.put((i - 1) * n + j, cur);
  19.                 queue.offer((i - 1) * n + j);
  20.             }
  21.             if (i < m - 1 && board[i + 1][j] == 0 && !map.containsKey((i + 1) * n + j)) {. From 1point 3acres bbs
  22.                 map.put((i + 1) * n + j, cur);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.                 queue.offer((i + 1) * n + j);
  24.             }
  25.             if (j > 0 && board[i][j - 1] == 0 && !map.containsKey(i * n + j - 1)) {
  26.                 map.put(i * n + j - 1, cur);
  27.                 queue.offer(i * n + j - 1);
  28.             }
  29.             if (j < n - 1 && board[i][j + 1] == 0 && !map.containsKey(i * n + j + 1)) {
  30.                 map.put(i * n + j + 1, cur);
  31.                 queue.offer(i * n + j + 1);
  32.             }
  33.         }
  34.         int dest = (m - 1) * m + (n - 1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.         while (map.containsKey(dest)) {
  36.             int i = dest / m;
  37.             int j = dest % n;
  38.             result.add(Arrays.asList(i, j));
  39.             if (i == 0 && j == 0) {
  40.                 break;
  41.             }. 1point 3acres 璁哄潧
  42.             dest = map.get(dest);
  43.         }
  44.         Collections.reverse(result);
  45.         return result;
  46.     }
  47. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  48.     public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  49.         ShortestPath solution = new ShortestPath();
  50.         int[][] board = {{0, 1, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {1, 0, 1, 1, 0}, {0, 0, 0, 1, 0}};. From 1point 3acres bbs
  51.         System.out.println(solution.shortestPath(board));
  52.         
  53.         int[][] board1 = {{0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}, {1, 0, 1, 1, 0}, {0, 0, 0, 1, 0}};
  54.         System.out.println(solution.shortestPath(board1));
  55.         
  56.         int[][] board2 = {{0, 1, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 0, 1, 1, 0}, {0, 0, 0, 1, 0}};
  57.         System.out.println(solution.shortestPath(board2));
  58.     }-google 1point3acres
  59. }
复制代码
回复 支持 反对

使用道具 举报

stacies 发表于 2016-10-2 03:26:50 | 显示全部楼层
importcoder 发表于 2016-9-13 01:45
只求能否到达的话应该可以用dp,如果要求所有路径的话可能要用dfs

这个code只能输出一条最短路径,不是所有。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
试试这个例子:
int[][] board = {{0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {1, 0, 1, 1, 0}, {0, 0, 0, 1, 0}};
输出:
[[0, 0], [1, 0], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [4, 4]]. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-9 23:53:01 | 显示全部楼层
importcoder 发表于 2016-9-13 01:45
只求能否到达的话应该可以用dp,如果要求所有路径的话可能要用dfs

第11行和第36行的代码应该是 int i = cur / n和int i = dest / m吧?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-23 20:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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