一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1799|回复: 9
收起左侧

Snapchat面经

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

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

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

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

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

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

附上代码吧,挺简单的
  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>. 1point 3acres 璁哄潧
  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>
  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):. more info on 1point3acres.com
  3.         self.a = x
  4.         self.b = y. From 1point 3acres bbs

  5. class Solution:
  6.     def findPath(self, matrix):
  7.         if not matrix or not matrix[0]: return []
  8.         m = len(matrix)
  9.         n = len(matrix[0])
  10.         directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
  11.         formerSteps = []. visit 1point3acres.com for more.
  12.         for p in range(m):
  13.             line = []. 1point 3acres 璁哄潧
  14.             for k in range(n):
  15.                 line.append(Coordinates(None, None))
  16.             formerSteps.append(line)

  17.         find = False. Waral 鍗氬鏈夋洿澶氭枃绔,

  18. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.         queue = [(0, 0, (None, None))]

  20.         while queue:
  21.             x, y, formerCoordinates = queue.pop(0)
  22.             formerSteps[x][y].a = formerCoordinates[0]
  23.             formerSteps[x][y].b = formerCoordinates[1]-google 1point3acres

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

  27.             matrix[x][y] = -1

  28.             for k in range(4):
  29.                 newX = x + directions[k][0]
  30.                 newY = y + directions[k][1]

  31.                 if newX < 0 or newX >= m or newY < 0 or newY >= n or matrix[newX][newY] == 1 or matrix[newX][newY] == -1:. From 1point 3acres bbs
  32.                     continue
  33. . From 1point 3acres bbs
  34.                 queue.append((newX, newY, (x, y))). 鍥磋鎴戜滑@1point 3 acres
  35. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.         if not find:
  37.             return []
  38.         else:
  39.             res = []
  40.             i, j = m - 1, n - 1
  41.             while i != None and j != None:
  42.                 res.insert(0, (i, j))
  43.                 temp = formerSteps[i][j]
  44.                 i, j = temp.a, temp.b
  45.             return res

  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?.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 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
能否直接用dp?然后同时记录是从左边来的还是从上面来的

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

使用道具 举报

majiamajia 发表于 2015-11-2 08:44:28 | 显示全部楼层
又见紫风铃 发表于 2015-11-2 08:42
应该可以,但不只是左边和上面了,四个方向都有可能来。
-google 1point3acres
嗯嗯有道理,所以要么就是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<>();. from: 1point3acres.com/bbs
  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();
  12.             int i = cur / m;
  13.             int j = cur % n;
  14.             if (i == m - 1 && j == n - 1) {
  15.                 break;
  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);. From 1point 3acres bbs
  20.             }
  21.             if (i < m - 1 && board[i + 1][j] == 0 && !map.containsKey((i + 1) * n + j)) {
  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)) {. visit 1point3acres.com for more.
  30.                 map.put(i * n + j + 1, cur);. 鍥磋鎴戜滑@1point 3 acres
  31.                 queue.offer(i * n + j + 1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.             }
  33.         }
  34.         int dest = (m - 1) * m + (n - 1);
  35.         while (map.containsKey(dest)) {. 1point3acres.com/bbs
  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.             }
  42.             dest = map.get(dest);
  43.         }
  44.         Collections.reverse(result);
  45.         return result;
  46.     }

  47.     public static void main(String[] args) {
  48.         ShortestPath solution = new ShortestPath();
  49.         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}};
  50.         System.out.println(solution.shortestPath(board));
  51.         
  52.         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}};
  53.         System.out.println(solution.shortestPath(board1));
  54.         
  55.         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}};
  56.         System.out.println(solution.shortestPath(board2));
  57.     }
  58. }
复制代码
回复 支持 反对

使用道具 举报

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

这个code只能输出一条最短路径,不是所有。.1point3acres缃
试试这个例子:
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]]
回复 支持 反对

使用道具 举报

小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吧?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 04:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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