PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

This question evaluates tree traversal and column-based grouping skills along with grid-based graph search, state modeling, and handling dynamic maze behaviors such as directional constraints, impassable walls, and bomb-triggered grid updates.

  • medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

Solve Tree Columns And Maze Variants

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Answer the following coding tasks from the interview. 1. Binary-tree column grouping: Given the root of a binary tree, group node values by vertical column. The root is in column 0, a left child is in column parent_column - 1, and a right child is in column parent_column + 1. Return the groups from the leftmost column to the rightmost column. If multiple nodes are in the same row and column, output them in the order they would be visited by a level-order traversal from left to right. 2. Progressive maze search: Given an m by n grid, a start cell, and a target cell, implement reachability or shortest-path search as the rules become more complex: - Part 1: The grid may be empty; handle empty input safely. - Part 2: Some cells are walls and cannot be entered. - Part 3: Some cells contain arrows `^`, `v`, `<`, or `>`. If the current cell contains an arrow, the next move must follow that arrow; otherwise movement is allowed in the four cardinal directions. - Part 4: Combine arrow cells and wall cells. - Part 5: Some cells contain bombs. When a bomb cell is entered, it clears adjacent wall cells, after which the search may continue under the updated grid state. The maze portion was conducted in an AI-assisted coding format.

Quick Answer: This question evaluates tree traversal and column-based grouping skills along with grid-based graph search, state modeling, and handling dynamic maze behaviors such as directional constraints, impassable walls, and bomb-triggered grid updates.

Part 1: Binary Tree Column Grouping

Given a binary tree, group node values by vertical column. The root is in column 0. A left child is in column parent_column - 1, and a right child is in column parent_column + 1. Return the columns from leftmost to rightmost. If multiple nodes share the same row and column, keep them in the order they would appear in a left-to-right level-order traversal. The tree is provided as a level-order Python list where None means a missing node.

Constraints

  • 0 <= number of list entries <= 10^4
  • Each non-None value is an integer
  • The input list represents a valid level-order binary tree serialization

Examples

Input: [3, 9, 20, None, None, 15, 7]

Expected Output: [[9], [3, 15], [20], [7]]

Explanation: Node 9 is in column -1, nodes 3 and 15 are in column 0, node 20 is in column 1, and node 7 is in column 2.

Input: [1, 2, 3, 4, 6, 5, 7]

Expected Output: [[4], [2], [1, 6, 5], [3], [7]]

Explanation: Nodes 6 and 5 share the same row and column, so they appear in level-order left-to-right order: 6 before 5.

Input: []

Expected Output: []

Explanation: An empty tree has no columns.

Input: [1]

Expected Output: [[1]]

Explanation: A single-node tree has one column.

Hints

  1. A breadth-first traversal naturally preserves the required left-to-right order for nodes that land in the same row and column.
  2. Track each node together with its column index, then gather values by column.

Part 2: Maze Search - Handle Empty Grid Input Safely

You are given an open grid with no walls. Find the minimum number of moves needed to go from a start cell to a target cell using only the four cardinal directions. This version focuses on robust input handling: the grid may be empty, so your code must safely handle empty input before reading dimensions. Return -1 if the grid is empty, the coordinates are invalid, or the target cannot be reached.

Constraints

  • 0 <= m, n <= 200
  • All rows in `grid` have the same length
  • Movement is allowed only up, down, left, and right

Examples

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

Expected Output: 3

Explanation: A shortest path is Right, Right, Down.

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

Expected Output: -1

Explanation: The grid is empty, so no path search is possible.

Input: (["."], (0, 0), (0, 0))

Expected Output: 0

Explanation: Start and target are the same valid cell.

Input: (["..", ".."], (0, 0), (2, 0))

Expected Output: -1

Explanation: The target coordinates are outside the grid.

Hints

  1. Check `not grid` or `not grid[0]` before using `len(grid[0])`.
  2. Because every move costs 1, breadth-first search gives the shortest path.

Part 3: Maze Search - Add Wall Cells

You are given a grid where '.' is an open cell and '#' is a wall. Find the minimum number of moves needed to reach the target from the start using four-directional movement. You may not enter wall cells. Return -1 if the grid is empty, coordinates are invalid, the start or target is blocked, or no path exists.

Constraints

  • 0 <= m, n <= 200
  • All rows in `grid` have the same length
  • Cells are either '.' or '#'

Examples

Input: (["...", ".#.", "..."], (0, 0), (2, 2))

Expected Output: 4

Explanation: The path goes around the center wall.

Input: ([".#.", "###", "..."], (0, 0), (2, 2))

Expected Output: -1

Explanation: The start region is completely cut off by walls.

Input: (["#"], (0, 0), (0, 0))

Expected Output: -1

Explanation: The start cell is a wall, so the state is invalid.

Input: (["."], (0, 0), (0, 0))

Expected Output: 0

Explanation: Start already equals target.

Hints

  1. This is a standard shortest-path-on-an-unweighted-grid problem, so BFS is a good fit.
  2. Treat walls as cells that simply never become neighbors.

Part 4: Maze Search - Add Forced Movement from Arrow Cells

You are given a grid with open cells '.' and arrow cells '^', 'v', '<', '>'. Find the minimum number of moves needed to reach the target from the start. If the current cell contains an arrow, your next move must follow that arrow exactly. Otherwise, you may move one step in any of the four cardinal directions. Return -1 if the grid is empty, coordinates are invalid, or the target cannot be reached.

Constraints

  • 0 <= m, n <= 200
  • All rows in `grid` have the same length
  • Cells are '.', '^', 'v', '<', or '>'

Examples

Input: ([".>.", "..."], (0, 0), (1, 2))

Expected Output: 3

Explanation: One shortest path is Right to '>', forced Right, then Down.

Input: (["v.", "^."], (0, 0), (1, 1))

Expected Output: -1

Explanation: The arrow cells create a loop between (0,0) and (1,0), so the target is unreachable.

Input: (["^"], (0, 0), (0, 0))

Expected Output: 0

Explanation: Being already at the target requires zero moves, even if the cell is an arrow.

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

Expected Output: -1

Explanation: An empty grid is invalid input for search.

Hints

  1. The allowed outgoing moves depend on the current cell, not on the destination cell.
  2. Even with forced moves, BFS still works because every move has equal cost.

Part 5: Maze Search - Combine Arrow Cells and Wall Cells

You are given a grid containing open cells '.', walls '#', and arrow cells '^', 'v', '<', '>'. Find the minimum number of moves from the start to the target. You may never enter a wall. If the current cell contains an arrow, your next move must follow that arrow; otherwise, you may move in any of the four cardinal directions. Return -1 if the grid is empty, coordinates are invalid, the start or target is blocked, or the target is unreachable.

Constraints

  • 0 <= m, n <= 200
  • All rows in `grid` have the same length
  • Cells are '.', '#', '^', 'v', '<', or '>'

Examples

Input: ([".>.", ".#.", "..."], (0, 0), (2, 2))

Expected Output: 4

Explanation: A shortest path is Right to '>', forced Right, then Down, Down.

Input: ([">#", ".."], (0, 0), (1, 1))

Expected Output: -1

Explanation: The start cell is an arrow that immediately points into a wall, so no move is possible.

Input: (["#"], (0, 0), (0, 0))

Expected Output: -1

Explanation: The start cell is blocked.

Input: (["v.", ".."], (0, 0), (0, 0))

Expected Output: 0

Explanation: Start already equals target.

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

Expected Output: -1

Explanation: An empty grid should be handled safely.

Hints

  1. Generate neighbors based on the current cell: arrows give one possible move, while normal cells give four.
  2. If an arrow points out of bounds or into a wall, that state simply has no valid outgoing move in that direction.

Part 6: Maze Search - Add Bomb Cells That Clear Adjacent Walls

You are given a grid containing open cells '.', walls '#', arrow cells '^', 'v', '<', '>', and bomb cells 'B'. Find the minimum number of moves from the start to the target. Movement is four-directional. If the current cell contains an arrow, your next move must follow that arrow; otherwise, you may move freely in the four directions. Walls cannot be entered unless they have been cleared. When you enter a bomb cell, all wall cells directly adjacent to that bomb (up, down, left, right) become passable for the rest of that path. If the start cell is a bomb, it triggers immediately at step 0. Return -1 if no valid path exists.

Constraints

  • 0 <= m, n <= 30
  • All rows in `grid` have the same length
  • The number of bomb cells is at most 12
  • Movement is only up, down, left, and right

Examples

Input: ([".B#", "##.", "..."], (0, 0), (1, 2))

Expected Output: 3

Explanation: Move to the bomb in 1 step, which clears adjacent walls, then continue through a newly passable route to the target.

Input: ([".>B", "#.#", "..."], (0, 0), (2, 2))

Expected Output: 4

Explanation: The arrow forces you into the bomb, and the bomb clears the wall below it so the target becomes reachable.

Input: (["B#.", "..."], (0, 0), (0, 2))

Expected Output: 2

Explanation: The start cell is a bomb, so the wall at (0,1) is cleared immediately.

Input: ([">#", "B."], (0, 0), (1, 1))

Expected Output: -1

Explanation: The start arrow points directly into a wall, so the bomb can never be reached.

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

Expected Output: -1

Explanation: An empty grid is invalid input.

Hints

  1. Reaching the same cell with different bombs already triggered can lead to different future options, so position alone is not a sufficient visited state.
  2. A bitmask over triggered bombs is a compact way to represent which walls are currently cleared on that path.
Last updated: May 23, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve a Key-Door Corridor Maze - Meta (medium)
  • Solve Array Merge and Parentheses Cleanup - Meta (medium)
  • Solve Two Backtracking Array Problems - Meta (hard)
  • Solve Maze and Suffix Problems - Meta (medium)
  • Solve Tree View and Triplet Sum - Meta (easy)