Quick Overview

This pair of problems evaluates algorithmic proficiency with nested data structures and grid-based graph traversal, covering concepts such as depth-weighted aggregation and shortest-path computation under obstacles.

Compute nested depth sum and grid distance

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem A: Weighted sum of integers in a nested list You are given a nested list structure that may contain integers or other nested lists. Define the **depth** of top-level elements as 1, their children as depth 2, etc. **Task:** Compute the sum of each integer multiplied by its depth. **Input:** - A nested list, e.g. `[1, [4, [6]]]` **Output:** - An integer weighted sum **Example:** - Input: `[1, [4, [6]]]` - `1` at depth 1 → `1*1` - `4` at depth 2 → `4*2` - `6` at depth 3 → `6*3` - Total = `1 + 8 + 18 = 27` **Constraints (typical):** - Total number of integers across all nesting: up to ~1e5 - Nesting depth may be up to ~1e3 --- ## Problem B: Best empty cell minimizing distance to all buildings You are given an `m x n` grid with values: - `0` = empty land (you may start here) - `1` = building - `2` = obstacle (cannot pass) Movement is 4-directional (up/down/left/right). Distance is the number of steps along empty cells (you cannot pass through obstacles or buildings). **Task:** Choose an empty cell `0` such that the **sum of shortest path distances** from that cell to **every** building is minimized. Return that minimum sum. If there is no empty cell from which all buildings are reachable, return `-1`. **Input:** - `grid`: `m x n` integer matrix **Output:** - Minimum possible sum distance, or `-1` **Example:** - `grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]` → output `7` (one optimal empty cell has total distance 7) **Constraints (typical):** - `1 <= m,n <= 50`

Quick Answer: This pair of problems evaluates algorithmic proficiency with nested data structures and grid-based graph traversal, covering concepts such as depth-weighted aggregation and shortest-path computation under obstacles.

Weighted Sum of Integers in a Nested List

You are given a nested list structure that may contain integers or other nested lists. Define the **depth** of top-level elements as 1, their children as depth 2, and so on. **Task:** Compute the sum of each integer multiplied by its depth. **Example:** `[1, [4, [6]]]` - `1` is at depth 1 → `1 * 1 = 1` - `4` is at depth 2 → `4 * 2 = 8` - `6` is at depth 3 → `6 * 3 = 18` - Total = `1 + 8 + 18 = 27` Return the integer weighted sum. An empty list returns 0.

Constraints

  • Total number of integers across all nesting: up to ~1e5
  • Nesting depth may be up to ~1e3
  • Integers may be negative
  • An empty list returns 0

Examples

Input: ([1, [4, [6]]],)

Expected Output: 27

Explanation: 1*1 + 4*2 + 6*3 = 1 + 8 + 18 = 27.

Input: ([],)

Expected Output: 0

Explanation: Empty list contributes nothing.

Hints

  1. Process the list recursively, passing the current depth down to children. Increment the depth by 1 each time you descend into a sub-list.
  2. For each element: if it is a list, recurse with depth+1 and add the result; if it is an integer, add value * depth.
  3. If recursion depth is a concern (up to 1e3), an explicit stack of (list, depth, index) works too and avoids Python recursion limits.

Best Empty Cell Minimizing Distance to All Buildings

You are given an `m x n` grid with values: - `0` = empty land (you may start here) - `1` = building - `2` = obstacle (cannot pass) Movement is 4-directional (up/down/left/right). Distance is the number of steps along empty cells; you cannot pass through obstacles or buildings. **Task:** Choose an empty cell `0` such that the **sum of shortest path distances** from that cell to **every** building is minimized. Return that minimum sum. If there is no empty cell from which **all** buildings are reachable, return `-1`. **Example:** `grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]` → output `7` (one optimal empty cell has total distance 7 to all three buildings).

Constraints

  • 1 <= m, n <= 50
  • grid[i][j] is one of 0 (empty), 1 (building), 2 (obstacle)
  • Movement is 4-directional through empty cells only
  • Return -1 if no empty cell can reach every building

Examples

Input: ([[1, 0, 2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]],)

Expected Output: 7

Explanation: An optimal empty cell reaches all three buildings with a summed shortest distance of 7.

Input: ([[1, 0, 0]],)

Expected Output: 1

Explanation: Single building; the adjacent empty cell has total distance 1 (the nearer cell is chosen).

Hints

  1. Run a BFS from each building, not from each empty cell. From a building, BFS spreads only through empty (0) cells, accumulating the distance into every reachable empty cell.
  2. Keep two grids: total_dist[i][j] accumulates the summed distance from all buildings, and reach[i][j] counts how many buildings reached that cell.
  3. After all BFS runs, a cell is valid only if reach[i][j] equals the total building count (it can reach every building). Take the minimum total_dist among valid cells; if none, return -1.

Loading coding console...