Snap Inc. Coding Interview

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 ?

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