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

Snapchat面经

全局:

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

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

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

x
人生最糟糕的一次电面,两小时本来要做两道题的,最后一道都没有debug出来,而且还是我很熟悉的BFS找路径类的问题,snapchat还是很喜欢的,这两天把地里的snapchat面经全部刷了写了一遍,结果因为python的初始化矩阵的问题挂了,觉得很遗憾,不能去venice bea
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
该初始化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>
  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大米 +5 收起 理由
kennethinsnow + 5 感谢分享!

查看全部评分


上一篇:小公司面经贴- amplitude
下一篇:面试资料分享

本帖被以下淘专辑推荐:

🔗
 楼主| 又见紫风铃 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 []
  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 = []
  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.         while queue:
  20.             x, y, formerCoordinates = queue.pop(0)
  21.             formerSteps[x][y].a = formerCoordinates[0]
  22.             formerSteps[x][y].b = formerCoordinates[1]

  23.             if x == m - 1 and y == n - 1:
  24.                 find = True
  25.                 break

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

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

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

  32.                 queue.append((newX, newY, (x, y)))

  33.         if not find:
  34.             return []
  35.         else:
  36.             res = []
  37.             i, j = m - 1, n - 1
  38.             while i != None and j != None:
  39.                 res.insert(0, (i, j))
  40.                 temp = formerSteps[i][j]
  41.                 i, j = temp.a, temp.b
  42.             return res

  43. solution = Solution()
  44. matrix = [[0, 0, 0], [0,0,0], [0, 0, 0]]
  45. matrix = [[0,0,0], [1,1,0], [0,0,0], [0,1,1], [0,0,0]]
  46. 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的。。。所以应该第一次发现是终点的这条路径就是最短的了吧
回复

使用道具 举报

全局:
能否直接用dp?然后同时记录是从左边来的还是从上面来的
回复

使用道具 举报

🔗
 楼主| 又见紫风铃 2015-11-2 08:42:28 | 只看该作者
全局:
majiamajia 发表于 2015-11-2 08:39
能否直接用dp?然后同时记录是从左边来的还是从上面来的

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

使用道具 举报

全局:
又见紫风铃 发表于 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();
  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);
  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)) {
  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.             }
  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 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

全局:
importcoder 发表于 2016-9-13 01:45
只求能否到达的话应该可以用dp,如果要求所有路径的话可能要用dfs

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

使用道具 举报

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

本版积分规则

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