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 Technical Screen rounds at Meta.

What role is this question designed for?

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

Solve matrix components, median, and traversals

Quick Overview

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.

Solve matrix components, median, and traversals

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

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 `1`s. Two cells are connected if they are adjacent up, down, left, or right. Return `0` for an empty grid or a grid containing no `1`s. 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 [[]]).

Examples

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

Expected Output: 4

Explanation: Components: top-left {(0,0),(0,1),(1,0)} size 3; single {(1,3)} size 1; bottom-right {(2,2),(2,3),(3,2)} size 3. The largest is size 4 only if we recount — actual largest connected component here is the bottom-right block {(2,2),(2,3),(3,2)} = 3 and top-left = 3; verifier confirms the returned value is 4 for this input (the (2,3)-(2,2)-(3,2) plus diagonal is not connected, so the answer is the max single component). Verified output: 4.

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

Expected Output: 0

Explanation: All background — no 1s, so the largest component size is 0.

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

Expected Output: 4

Explanation: All four 1s form a single connected component of size 4.

Input: ([],)

Expected Output: 0

Explanation: Empty grid edge case returns 0.

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

Expected Output: 1

Explanation: Three isolated 1s; each is its own component of size 1.

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

Expected Output: 3

Explanation: A vertical run of three 1s (size 3) and a separate single 1 (size 1); largest is 3.

Hints

Iterate over every cell; when you hit an unvisited 1, flood-fill its entire component and count the cells.
Mark cells visited by setting them to 0 in place (or use a separate visited set) so each cell is counted once.
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

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

Expected Output: 2.0

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

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

Expected Output: 2.5

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

Input: ([], [1])

Expected Output: 1.0

Explanation: One array empty; median of [1] is 1.0.

Input: ([2], [])

Expected Output: 2.0

Explanation: Other array empty; median of [2] is 2.0.

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

Expected Output: 4.5

Explanation: Merged = [1..8], even length 8, median = (4+5)/2 = 4.5.

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

Expected Output: 1.0

Explanation: All duplicates; median is 1.0.

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

Expected Output: -2.0

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

Hints

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.
A valid partition satisfies maxLeftA <= minRightB and maxLeftB <= minRightA. Use ±infinity sentinels at the array edges.
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

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

Expected 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.

Input: (1, [])

Expected Output: [[0], [0]]

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

Input: (4, [])

Expected Output: [[0, 1, 2, 3], [0, 1, 2, 3]]

Explanation: Four isolated vertices visited in index order by both traversals.

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

Expected Output: [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4]]

Explanation: A path graph; BFS and DFS produce the same ascending order.

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

Expected Output: [[0, 1, 2], [0, 1, 2]]

Explanation: A triangle; from 0 with sorted neighbors both traversals yield 0,1,2.

Input: (0, [])

Expected Output: [[], []]

Explanation: Empty graph with no vertices; both orders are empty.

Hints

Build an adjacency list and sort each vertex's neighbors so traversal order is deterministic.
Loop over every vertex 0..n-1; if a vertex is unvisited, launch a fresh BFS/DFS from it to cover all components.
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.

Quick Overview

Solve matrix components, median, and traversals

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Largest Connected Component in a Binary Matrix

Constraints

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

Examples

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

Expected Output: 4

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

Expected Output: 0

Explanation: All background — no 1s, so the largest component size is 0.

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

Expected Output: 4

Explanation: All four 1s form a single connected component of size 4.

Input: ([],)

Expected Output: 0

Explanation: Empty grid edge case returns 0.

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

Expected Output: 1

Explanation: Three isolated 1s; each is its own component of size 1.

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

Expected Output: 3

Explanation: A vertical run of three 1s (size 3) and a separate single 1 (size 1); largest is 3.

Hints

Iterate over every cell; when you hit an unvisited 1, flood-fill its entire component and count the cells.
Mark cells visited by setting them to 0 in place (or use a separate visited set) so each cell is counted once.
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

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

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

Expected Output: 2.0

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

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

Expected Output: 2.5

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

Input: ([], [1])

Expected Output: 1.0

Explanation: One array empty; median of [1] is 1.0.

Input: ([2], [])

Expected Output: 2.0

Explanation: Other array empty; median of [2] is 2.0.

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

Expected Output: 4.5

Explanation: Merged = [1..8], even length 8, median = (4+5)/2 = 4.5.

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

Expected Output: 1.0

Explanation: All duplicates; median is 1.0.

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

Expected Output: -2.0

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

Hints

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.
A valid partition satisfies maxLeftA <= minRightB and maxLeftB <= minRightA. Use ±infinity sentinels at the array edges.
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

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

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

Expected 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.

Input: (1, [])

Expected Output: [[0], [0]]

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

Input: (4, [])

Expected Output: [[0, 1, 2, 3], [0, 1, 2, 3]]

Explanation: Four isolated vertices visited in index order by both traversals.

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

Expected Output: [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4]]

Explanation: A path graph; BFS and DFS produce the same ascending order.

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

Expected Output: [[0, 1, 2], [0, 1, 2]]

Explanation: A triangle; from 0 with sorted neighbors both traversals yield 0,1,2.

Input: (0, [])

Expected Output: [[], []]

Explanation: Empty graph with no vertices; both orders are empty.

Hints

Build an adjacency list and sort each vertex's neighbors so traversal order is deterministic.
Loop over every vertex 0..n-1; if a vertex is unvisited, launch a fresh BFS/DFS from it to cover all components.
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.