Katkat
Back

Solve matrix components, median, and traversals

MetaMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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.