Quick Overview

This question evaluates understanding of array and matrix manipulation, sliding-window and streaming statistics, and appropriate data-structure choices for maintaining aggregates and order-statistics such as moving averages and sliding-window medians.

Check diagonal and compute window statistics

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given a square matrix, determine whether all elements on its main diagonal are identical. LeetCode 346. Moving Average from Data Stream – design a class that maintains a sliding window of size k over a data stream and returns the current moving average on each insertion. LeetCode 480. Sliding Window Median – for an integer array and window size k, output the median of the numbers inside the window as it slides one position at a time. https://leetcode.com/problems/moving-average-from-data-stream/ https://leetcode.com/problems/sliding-window-median/

Quick Answer: This question evaluates understanding of array and matrix manipulation, sliding-window and streaming statistics, and appropriate data-structure choices for maintaining aggregates and order-statistics such as moving averages and sliding-window medians.

Identical Main Diagonal

Given an n x n square matrix, determine whether all elements on its main diagonal (the cells where the row index equals the column index) are identical. Return true if every diagonal element is equal to the others, and false otherwise. An empty matrix is considered to have an identical (vacuously equal) diagonal. Example: Input: matrix = [[5,1,2],[3,5,4],[6,7,5]] Output: true (diagonal is 5, 5, 5) Input: matrix = [[5,1,2],[3,9,4],[6,7,5]] Output: false (diagonal is 5, 9, 5)

Constraints

  • 0 <= n <= 1000 (matrix is n x n)
  • Matrix is square: every row has length n
  • -10^9 <= matrix[i][j] <= 10^9

Examples

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

Expected Output: true

Explanation: Diagonal values are 5, 5, 5 — all identical.

Input: [[5, 1, 2], [3, 9, 4], [6, 7, 5]]

Expected Output: false

Explanation: Diagonal values are 5, 9, 5 — the middle one differs.

Hints

  1. The main diagonal consists of the cells matrix[i][i] for i from 0 to n-1; you never need to look at off-diagonal cells.
  2. Pick the first diagonal value as a reference and compare every other diagonal value against it, returning false on the first mismatch.
  3. Handle the empty matrix as a special case — with no elements there is nothing to contradict equality, so return true.

Moving Average from Data Stream

Design the logic for a class that maintains a sliding window of size k over a stream of integers and returns the current moving average each time a new value arrives (LeetCode 346). To make this executable in a single call, implement solution(k, stream): you receive the window size k and the full list of stream values in order, and you must return a list whose i-th entry is the moving average of the most recent up-to-k values right after the i-th value was inserted. Example: Input: k = 3, stream = [1, 10, 3, 5] Output: [1.0, 5.5, 4.666666666666667, 6.0] - after 1: [1] -> 1/1 = 1.0 - after 10: [1, 10] -> 11/2 = 5.5 - after 3: [1, 10, 3] -> 14/3 = 4.6666... - after 5: [10, 3, 5] -> 18/3 = 6.0 (1 slides out)

Constraints

  • 1 <= k <= 10^5
  • 0 <= len(stream) <= 10^5
  • -10^5 <= stream[i] <= 10^5
  • The window holds the most recent min(k, count_so_far) values

Examples

Input: k = 3, stream = [1, 10, 3, 5]

Expected Output: [1.0, 5.5, 4.666666666666667, 6.0]

Explanation: Window fills then 1 slides out when 5 arrives, leaving [10,3,5] -> 18/3 = 6.0.

Input: k = 1, stream = [4, 8, 2]

Expected Output: [4.0, 8.0, 2.0]

Explanation: Window of size 1 always holds just the latest value, so each average equals that value.

Hints

  1. Maintain a running sum instead of re-summing the window on every insertion, so each average is O(1) to compute.
  2. Use a queue (deque): push each new value on the right; when the window exceeds size k, pop the oldest value on the left and subtract it from the running sum.
  3. Before the window is full, divide by the current count (len(window)), not by k — early averages use fewer than k elements.

Sliding Window Median

Given an integer array nums and a window size k, output the median of the numbers inside the window as it slides one position at a time from the left end of the array to the right (LeetCode 480). For a window of odd size the median is the middle element; for an even size it is the average of the two middle elements (as a float). If k is 0 or larger than the array length, return an empty list. Implement solution(nums, k) returning the list of window medians. Example: Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Windows: [1,3,-1] [3,-1,-3] [-1,-3,5] [-3,5,3] [5,3,6] [3,6,7] Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]

Constraints

  • 0 <= len(nums) <= 10^5
  • 0 <= k <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • Return [] when k == 0 or k > len(nums)
  • Even-size windows average the two middle values as a float

Examples

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Expected Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]

Explanation: Each odd-size window's median is its middle sorted value, e.g. sorted([1,3,-1]) = [-1,1,3] -> 1.0.

Input: nums = [1, 2, 3, 4], k = 2

Expected Output: [1.5, 2.5, 3.5]

Explanation: Even window: median is the average of the two elements, e.g. (1+2)/2 = 1.5.

Hints

  1. Keep the current window in sorted order; the median is then read directly from the middle index (odd k) or averaged from the two middle indices (even k).
  2. When the window slides, the element leaving is nums[i-k] — remove it with a binary search (bisect_left) before inserting the new element nums[i] in sorted position.
  3. Use floats for the result so odd-size windows like a median of 3 still report 3.0 and even-size windows can carry a .5 fraction; guard the edge cases where k is 0 or exceeds the array length.

Loading coding console...