Katkat
Back

Solve Matrix, Tree, Nested, LCA, Maze Tasks

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.