Solve matrix diagonal and sliding-window statistics
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
1) Given an m x n integer matrix, determine whether every top-left to bottom-right diagonal has the same value (Toeplitz property). Return true/false, analyze time and space complexity, and describe how to handle a streaming input of rows.
2) Design a data structure that maintains the moving average of the last k numbers in a real-time stream. Support push(x) and query() in amortized O(
1) time and O(k) space. Address numerical precision, overflow, and behavior when the stream has fewer than k elements.
3) Given an array nums and a window size k, output the median of each sliding window across the array. Achieve O(n log k) time or better. Explain the data structures you would use, how you handle duplicates and even k, and discuss memory trade-offs.
Quick Answer: This question evaluates algorithmic problem-solving and data-structure design skills, covering streaming algorithms, sliding-window statistics (moving average and median), and matrix property recognition (Toeplitz), and is categorized under Coding & Algorithms for Machine Learning Engineer roles.