cswork / libraryOpen practice workspace

Coding questions · Meta

Solve matrix components, median, and traversals

This question evaluates algorithmic problem-solving across grid and graph algorithms, selection algorithms, and traversal techniques—specifically connected-component detection in binary matrices, median-finding across two sorted arrays, and BFS/DFS traversal variants—measuring competence in data structures, complexity analysis, and handling edge cases. Commonly asked in Coding & Algorithms interviews for Machine Learning Engineer roles, it assesses efficiency and correctness concerns such as time and space complexity and traversal orders, testing both conceptual understanding of algorithmic principles and practical implementation distinctions like iterative versus recursive variants.

  1. Binary matrix component: Given an m x n grid of 0s (background) and 1s (objects), return the size of the largest connected component where connectivity is 4-directional (up, down, left, right). Describe the algorithm, time and space complexity, and edge cases (e.g., empty grid, all zeros, all ones).

  2. Median of two sorted arrays: Given two sorted arrays A (length m) and B (length n), compute the median of the combined multiset without fully merging them. Explain the fastest approach you would implement, its time and space complexity, and how you would handle even total length.

  3. Graph traversals: Given an undirected graph that may be disconnected, implement BFS and DFS that return the visitation order for all vertices. Provide both recursive and iterative variants where applicable, and analyze time and space complexity.

Largest Connected Component in a Binary Matrix

Given an m x n grid where 0 is background and 1 is part of an object, return the size (number of cells) of the largest 4-directionally connected component of 1s. Two cells are connected if they are adjacent up, down, left, or right.

Return 0 for an empty grid or a grid containing no 1s.

Example: for [[1,1,0,0],[1,0,0,1],[0,0,1,1],[0,0,1,0]] the largest component has size 4 (the L-shaped block in the bottom-right plus the top-left triangle each have size 3 and 4 respectively; the top-left {(0,0),(0,1),(1,0)} is size 3, the bottom {(2,2),(2,3),(3,2)} is size 3 — wait, see test cases for exact counts).

Constraints

  • 0 <= m, n <= 300
  • grid[i][j] is 0 or 1
  • The grid may be empty ([] or [[]]).

Hints

  1. Iterate over every cell; when you hit an unvisited 1, flood-fill its entire component and count the cells.
  2. Mark cells visited by setting them to 0 in place (or use a separate visited set) so each cell is counted once.
  3. Use an explicit stack/queue (DFS/BFS) to avoid recursion-depth limits on large grids. Track the running max component size.

Median of Two Sorted Arrays

Given two sorted arrays A (length m) and B (length n), return the median of the combined multiset of all m + n elements without fully merging the arrays. The target run time is O(log(min(m, n))).

If the total length is odd, the median is the middle element. If even, it is the average of the two middle elements (return a float).

Constraints

  • 0 <= m, n; m + n >= 1
  • A and B are each sorted in non-decreasing order
  • -10^6 <= A[i], B[i] <= 10^6
  • Exactly one of A or B may be empty.

Examples

Example 1

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

Explanation: Merged = [1,2,3], odd length, median is the middle element 2.

Example 2

Input: ([1, 2], [3, 4])
Output: 2.5

Explanation: Merged = [1,2,3,4], even length, median = (2+3)/2 = 2.5.

Hints

  1. Binary-search a partition of the smaller array. The partition of the larger array is then forced so the left side holds exactly half of all elements.
  2. A valid partition satisfies maxLeftA <= minRightB and maxLeftB <= minRightA. Use ±infinity sentinels at the array edges.
  3. Odd total: the median is max(maxLeftA, maxLeftB). Even total: average max of the left side with min of the right side.

BFS and DFS Traversal Orders of a Disconnected Graph

Given an undirected graph with n vertices labeled 0..n-1 and an edge list edges, return the BFS and DFS visitation orders that cover all vertices (the graph may be disconnected).

Return a list [bfs_order, dfs_order].

To make the output deterministic:

  • Start a new traversal from the smallest unvisited vertex index.
  • Within a traversal, visit neighbors in ascending order.

BFS uses a queue; DFS uses an iterative stack (push neighbors in reverse-sorted order so the smallest is popped first).

Constraints

  • 0 <= n <= 10^4
  • 0 <= edges.length <= 10^5
  • Each edge connects two distinct vertices in [0, n-1]
  • The graph is undirected and may be disconnected.

Examples

Example 1

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

Explanation: Component {0,1,2,3,4? no} — {0,1,2,3} and {4,5}. BFS from 0: 0,1,2,3 then component starting at 4: 4,5. DFS from 0 goes deep: 0->1->3 then back to 2, then 4->5.

Example 2

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

Explanation: Single isolated vertex; both orders are [0].

Hints

  1. Build an adjacency list and sort each vertex's neighbors so traversal order is deterministic.
  2. Loop over every vertex 0..n-1; if a vertex is unvisited, launch a fresh BFS/DFS from it to cover all components.
  3. For iterative DFS that visits the smallest neighbor first, push neighbors onto the stack in reverse-sorted order, and skip a popped vertex if it was already seen.