How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve Matrix, Tree, Nested, LCA, Maze Tasks

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Answer the following independent coding tasks. For each task, implement a clean API, handle edge cases, and analyze time and space complexity. 1. Traverse a matrix by alternating diagonals. Given an m by n integer matrix, return all elements in the order obtained by visiting cells with the same row + column sum together, starting at cell 0,0. The direction alternates by diagonal: the first diagonal goes upward/right when possible, the next goes downward/left, and so on. Handle empty matrices. 2. Sum root-to-leaf digit values. Given a binary tree where each node contains a digit from 0 to 9, each root-to-leaf path represents a base-10 number formed by concatenating the digits along the path. Return the sum of all such numbers. For example, paths 1->2->3 and 1->4 represent 123 and 14, so the answer is 137. 3. Compute a depth-weighted sum of nested integers. You are given a nested list whose elements are either integers or nested lists. Return the sum of every integer multiplied by its depth. The outermost list has depth 1. 4. Find the lowest common ancestor using parent pointers only. Each node in a binary tree has fields value, left, right, and parent. You are given two node references from the same tree, but not the root. Return their lowest common ancestor. 5. Solve four maze variations. You are given a rectangular grid where 0 means open and 1 means wall, plus start and target cells. A ball moves in one of four directions and keeps rolling until it hits a wall or boundary; it can stop only at the last open cell before the obstacle. Implement the following methods: (a) determine whether the ball can stop at the target, (b) return the minimum number of grid cells traveled to stop at the target or -1 if impossible, (c) if a hole cell is provided and the ball falls into it as soon as it passes over it, return the lexicographically smallest instruction string among all shortest paths using d, l, r, u, and (d) explain or implement how you would optimize repeated reachability or shortest-path queries on the same static maze.

Quick Answer: This set of tasks evaluates algorithm design and data structure competencies across matrix traversal, tree path-sum aggregation, nested-list depth weighting, lowest common ancestor discovery using parent pointers, and several rolling-maze reachability and shortest-path variants.

Part 1: Traverse a Matrix by Alternating Diagonals

Given an m x n integer matrix, return its elements grouped by diagonals with equal row + column index. Start from the diagonal containing cell (0, 0). Traverse the first diagonal upward/right, the next downward/left, and keep alternating direction. If the matrix is empty, return an empty list.

Constraints

0 <= m, n <= 200
matrix may be empty
All rows, if present, have the same length

Examples

Input: ([ [1, 2, 3], [4, 5, 6], [7, 8, 9] ],)

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

Explanation: Alternate direction on each diagonal.

Input: ([ [1, 2], [3, 4], [5, 6] ],)

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

Explanation: Works for rectangular matrices too.

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

Expected Output: [1, 2, 3]

Explanation: Single row edge case.

Input: ([],)

Expected Output: []

Explanation: Empty matrix returns an empty list.

Hints

All cells on the same diagonal have the same value of row + col.
For each diagonal index d, choose a different starting point depending on whether d is even or odd.

Part 2: Sum Root-to-Leaf Digit Values in a Binary Tree

You are given a binary tree where each node stores a digit from 0 to 9. Every root-to-leaf path forms a base-10 number by concatenating the digits along that path. Return the sum of all such numbers. The tree is given in level-order form using None for missing children.

Constraints

0 <= number of list entries <= 10^5
Each non-None value is an integer from 0 to 9
Missing children are represented with None in the level-order array

Examples

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

Expected Output: 25

Explanation: Paths are 12 and 13.

Input: ([4, 9, 0, 5, 1],)

Expected Output: 1026

Explanation: Paths are 495, 491, and 40.

Input: ([0, 1],)

Expected Output: 1

Explanation: Path 0->1 forms the number 1.

Input: ([],)

Expected Output: 0

Explanation: Empty tree has sum 0.

Hints

Carry the number built so far as you move down the tree.
A node contributes a full number only when it is a leaf.

Part 3: Depth-Weighted Sum of Nested Integers

Given a nested list where each element is either an integer or another nested list, return the sum of every integer multiplied by its depth. The outermost list has depth 1.

Constraints

The input is a list
Elements are either integers or nested lists
Total number of integers and sublists is at most 10^5

Examples

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

Expected Output: 27

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

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

Expected Output: 10

Explanation: The four 1s are at depth 2 and 2 is at depth 1.

Input: ([],)

Expected Output: 0

Explanation: Empty list gives 0.

Input: ([-1, [2, -3]],)

Expected Output: -3

Explanation: -1*1 + 2*2 + (-3)*2 = -3.

Hints

Use DFS or BFS while tracking the current depth.
An integer contributes value * depth at the depth where it appears.

Part 4: Lowest Common Ancestor Using Parent Pointers Only

A binary tree is represented only by parent pointers. You are given a parent array where parent[i] is the parent of node i and the root has parent -1. Given two node indices p and q from the same tree, return their lowest common ancestor. Solve it using only upward moves through parent links.

Constraints

1 <= n <= 10^5
parent[root] = -1
0 <= p, q < n
p and q belong to the same tree

Examples

Input: ([-1, 0, 0, 1, 1, 2, 2], 3, 4)

Expected Output: 1

Explanation: Nodes 3 and 4 share parent 1.

Input: ([-1, 0, 0, 1, 1, 2, 2], 3, 5)

Expected Output: 0

Explanation: Their first shared ancestor is the root.

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

Expected Output: 1

Explanation: In a chain, the ancestor node is the LCA.

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

Expected Output: 2

Explanation: A node is its own LCA with itself.

Hints

Walk upward from one node and record all ancestors.
Then walk upward from the other node until you hit a recorded ancestor.

Part 5: Maze Variation (a) - Can the Ball Stop at the Target?

You are given a maze where 0 means open and 1 means wall. A ball starts at start and can roll up, down, left, or right. Once it starts moving, it keeps rolling until it hits a wall or the maze boundary, and it stops at the last open cell before the obstacle. Return whether the ball can stop exactly at the destination.

Constraints

1 <= m, n <= 100
maze[r][c] is 0 or 1
start and destination are row/column pairs

Examples

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

Expected Output: True

Explanation: There is a sequence of rolls that stops exactly at the destination.

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

Expected Output: False

Explanation: The ball can pass through nearby cells but cannot stop at this one.

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

Expected Output: True

Explanation: Start already equals destination.

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

Expected Output: False

Explanation: Empty maze cannot be traversed.

Hints

Search over stopping positions, not over every cell the ball rolls through.
From each stopped cell, simulate rolling in all four directions until you hit an obstacle.

Part 6: Maze Variation (b) - Minimum Distance to Stop at the Target

Using the same rolling-ball maze rules, return the minimum number of grid cells traveled for the ball to stop exactly at the destination. If it is impossible, return -1. The distance counts how many open cells the ball moves through, not how many times it changes direction.

Constraints

1 <= m, n <= 100
maze[r][c] is 0 or 1
start and destination are row/column pairs

Examples

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

Expected Output: 12

Explanation: The shortest valid rolling path has total distance 12.

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

Expected Output: -1

Explanation: The destination cannot be a stopping point from any valid path.

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

Expected Output: 0

Explanation: Already at the destination.

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

Expected Output: 2

Explanation: One shortest path is down then right.

Hints

Different rolls can have different travel lengths, so plain BFS is not enough.
Treat each stopping cell as a graph node and use Dijkstra's algorithm.

Part 7: Maze Variation (c) - Lexicographically Smallest Shortest Path to the Hole

You are given a rolling-ball maze, a start position, and a hole. The ball rolls in one of four directions and keeps moving until it hits a wall or boundary. However, if the ball passes over the hole, it falls in immediately and stops there. Return the lexicographically smallest instruction string among all shortest paths to the hole using the letters d, l, r, u. If the hole cannot be reached, return 'impossible'.

Constraints

1 <= m, n <= 100
maze[r][c] is 0 or 1
ball and hole are open cells

Examples

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

Expected Output: 'lul'

Explanation: This is the lexicographically smallest path among all shortest ones.

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

Expected Output: 'impossible'

Explanation: No valid rolling path reaches the hole.

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

Expected Output: ''

Explanation: Already at the hole, so the path is empty.

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

Expected Output: 'ru'

Explanation: Both 'ru' and 'ur' have the same distance, but 'ru' is lexicographically smaller.

Hints

You need to optimize first by distance, then by path string.
A priority queue ordered by (distance, path) is a natural fit.

Part 8: Maze Variation (d) - Optimize Repeated Shortest-Path Queries on a Static Maze

You are given one static rolling-ball maze and many shortest-path queries. Each query asks for the minimum number of cells traveled for the ball to stop at a destination, using the same rules as in Part 6. Implement a batched solver that reuses work across queries. A good approach is to precompute the roll result from every open cell in each direction once, then group queries by start cell and run Dijkstra only once per distinct start.

Constraints

1 <= m, n <= 100
1 <= number of queries <= 10^4
maze is static across all queries
start and destination may repeat across queries

Examples

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

Expected Output: [12, -1, 0]

Explanation: All three queries share the same start, so one Dijkstra run can answer them.

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

Expected Output: [2, 0, 2]

Explanation: Simple open grid with repeated and reversed queries.

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

Expected Output: [-1]

Explanation: Empty maze makes every query impossible.

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

Expected Output: [-1, 1]

Explanation: The first destination is a wall; the second is reachable in one roll.

Hints

Precompute, for every open cell and direction, the final stopping cell and travel distance.
If many queries share the same start, one Dijkstra run can answer all of them.

Quick Overview

Quick Overview