Snap Inc. Coding Interview

171

Apr 05, 2026

The interview started with around 10–15 minutes of background discussion, where the interviewer asked about my experience — especially around backend systems and ML-related work.

After that, we moved into a live coding round on HackerRank. The problem was a grid-based traversal question focused on finding the nearest k entities using shortest path logic.

Problem Statement: You are given a 2D grid representing a map.

Each cell in the grid contains one of the following:

' ' (space) → an empty cell that can be traversed
'-' → a wall that cannot be traversed
'A' to 'Z' → a restaurant

You are also given:

a** starting position (row, col)**
an integer k

Task: Return the top k nearest restaurants from the starting position based on the minimum number of steps required to reach them.

Movement Rules
You can move in 4 directions:

up → (r - 1, c)
down → (r + 1, c)
left → (r, c - 1)
right → (r, c + 1)

Output: Return a dictionary/map:

At most k restaurants
If fewer than k are reachable → return all reachable ones

Constraints
Grid size: m x n
1 ≤ m, n
k ≥ 1
Starting position is within bounds
Restaurants are labeled 'A'–'Z'

from collections import deque
from typing import List, Dict

def nearest_restaurants(grid: List[List[str]], start_row: int, start_col: int, k: int) -> Dict[str, int]:

# Edge case: empty grid or invalid k
if not grid or not grid[0] or k <= 0:
    return {}

rows, cols = len(grid), len(grid[0])

# Edge case: invalid starting position
if not (0 <= start_row < rows and 0 <= start_col < cols):
    return {}

# Edge case: starting cell is a wall → cannot move
if grid[start_row][start_col] == '-':
    return {}

# Helper to check if a cell is a restaurant
def is_restaurant(ch: str) -> bool:
    return len(ch) == 1 and 'A' <= ch <= 'Z'

# BFS initialization
queue = deque([(start_row, start_col, 0)])  # (row, col, distance)
visited = {(start_row, start_col)}

result = {}

# 4-directional movement
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# BFS traversal
while queue:
    r, c, dist = queue.popleft()
    
    # If current cell is a restaurant → record it
    if is_restaurant(grid[r][c]):
        label = grid[r][c]
        
        # Avoid duplicate entries
        if label not in result:
            result[label] = dist
            
            # Early stop: we found k nearest restaurants
            if len(result) == k:
                return result
    
    # Explore neighbors
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        
        # Valid move conditions:
        # 1. Inside grid bounds
        # 2. Not visited
        # 3. Not a wall
        if (
            0 <= nr < rows and
            0 <= nc < cols and
            (nr, nc) not in visited and
            grid[nr][nc] != '-'
        ):
            visited.add((nr, nc))
            queue.append((nr, nc, dist + 1))

# Return whatever restaurants we found (if < k)
return result

Time Complexity
Time: O(m × n)
Space: O(m × n)

Each cell is visited at most once.

Why BFS ?
Because:

All moves have equal cost
BFS guarantees shortest path
First visit = minimum distance

Comments (0)