Snap Inc. Technical Interview: BFS Grid Traversal for Nearest k Restaurants

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

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