Snapchat面经

又见紫风铃 · 2015-10-31 06:40:21

注册一亩三分地论坛，查看更多干货！

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

x

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

清华

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

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

该初始化M*N个而不是直接复制（那样都是引用，导致最后改一个都改了）。因为这种问题跪了真是不甘心

附上代码吧，挺简单的

<div>class Coordinates:</div><div> def __init__(self, x, y):</div><div> self.a = x</div><div> self.b = y</div><div>
</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>
</div><div> find = False</div><div>
</div><div> queue = [(0, 0, (None, None))]</div><div>
</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>
</div><div> if x == m - 1 and y == n - 1:</div><div> find = True</div><div> break</div><div>
</div><div> matrix[x][y] = -1</div><div>
</div><div> for k in range(4):</div><div> newX = x + directions[k][0]</div><div> newY = y + directions[k][1]</div><div>
</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>
</div><div> queue.append((newX, newY, (x, y)))</div><div>
</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>
</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>

复制代码

又见紫风铃 · 2015-10-31 06:40:39

class Coordinates:
def __init__(self, x, y):
self.a = x
self.b = y
class Solution:
def findPath(self, matrix):
if not matrix or not matrix[0]: return []
m = len(matrix)
n = len(matrix[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
formerSteps = []
for p in range(m):
line = []
for k in range(n):
line.append(Coordinates(None, None))
formerSteps.append(line)
find = False
queue = [(0, 0, (None, None))]
while queue:
x, y, formerCoordinates = queue.pop(0)
formerSteps[x][y].a = formerCoordinates[0]
formerSteps[x][y].b = formerCoordinates[1]
if x == m - 1 and y == n - 1:
find = True
break
matrix[x][y] = -1
for k in range(4):
newX = x + directions[k][0]
newY = y + directions[k][1]
if newX < 0 or newX >= m or newY < 0 or newY >= n or matrix[newX][newY] == 1 or matrix[newX][newY] == -1:
continue
queue.append((newX, newY, (x, y)))
if not find:
return []
else:
res = []
i, j = m - 1, n - 1
while i != None and j != None:
res.insert(0, (i, j))
temp = formerSteps[i][j]
i, j = temp.a, temp.b
return res
solution = Solution()
matrix = [[0, 0, 0], [0,0,0], [0, 0, 0]]
matrix = [[0,0,0], [1,1,0], [0,0,0], [0,1,1], [0,0,0]]
print solution.findPath(matrix)

复制代码

han275

这个只是找到路径啊，没有最短啊，最短是不是应该用DP？

又见紫风铃

han275 发表于 2015-11-2 07:31
这个只是找到路径啊，没有最短啊，最短是不是应该用DP？

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

kennynoodlehous

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

又见紫风铃

majiamajia 发表于 2015-11-2 08:39
能否直接用dp?然后同时记录是从左边来的还是从上面来的

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

kennynoodlehous

又见紫风铃发表于 2015-11-2 08:42
应该可以，但不只是左边和上面了，四个方向都有可能来。

嗯嗯有道理，所以要么就是DP里面每个CELL存从哪个方向来的。

importcoder

只求能否到达的话应该可以用dp，如果要求所有路径的话可能要用dfs

public class ShortestPath {
public List<List<Integer>> shortestPath(int[][] board) {
List<List<Integer>> result = new ArrayList<>();
int m = board.length;
int n = board[0].length;
Queue<Integer> queue = new LinkedList<>();
queue.offer(0 * n + 0);
Map<Integer, Integer> map = new HashMap<>();
while (!queue.isEmpty()) {
int cur = queue.poll();
int i = cur / m;
int j = cur % n;
if (i == m - 1 && j == n - 1) {
break;
}
if (i > 0 && board[i - 1][j] == 0 && !map.containsKey((i - 1) * n + j)) {
map.put((i - 1) * n + j, cur);
queue.offer((i - 1) * n + j);
}
if (i < m - 1 && board[i + 1][j] == 0 && !map.containsKey((i + 1) * n + j)) {
map.put((i + 1) * n + j, cur);
queue.offer((i + 1) * n + j);
}
if (j > 0 && board[i][j - 1] == 0 && !map.containsKey(i * n + j - 1)) {
map.put(i * n + j - 1, cur);
queue.offer(i * n + j - 1);
}
if (j < n - 1 && board[i][j + 1] == 0 && !map.containsKey(i * n + j + 1)) {
map.put(i * n + j + 1, cur);
queue.offer(i * n + j + 1);
}
}
int dest = (m - 1) * m + (n - 1);
while (map.containsKey(dest)) {
int i = dest / m;
int j = dest % n;
result.add(Arrays.asList(i, j));
if (i == 0 && j == 0) {
break;
}
dest = map.get(dest);
}
Collections.reverse(result);
return result;
}
public static void main(String[] args) {
ShortestPath solution = new ShortestPath();
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}};
System.out.println(solution.shortestPath(board));
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}};
System.out.println(solution.shortestPath(board1));
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}};
System.out.println(solution.shortestPath(board2));
}
}

复制代码

stacies

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

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

小A要当码农

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

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

Snapchat面经

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

本帖被以下淘专辑推荐:

浏览过的版块