Katkat
Back

Solve median extremes and segment flips

AmazonSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Solve median extremes and segment flips evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Part A — Sliding-window median extremes:

  • Input: an integer k (1 ≤ k ≤ n) and an array nums of length n.
  • For every contiguous subarray of length k, compute its median (for even k, use the lower median).
  • Output: the maximum and the minimum among these medians.
  • Design an algorithm that runs in O(n log k) time and O(k) space, and describe the data structures used.

Part B — Even-length uniform segmenting with minimal flips:

  • Input: a binary array frames of length n.
  • You may flip any bits (0↔ 1).
  • After flipping, the array must be partitionable into contiguous segments, each of even length and containing identical values (all 0s or all 1s).
  • Objective: minimize the number of segments; subject to that minimum, minimize the total number of flips.
  • Output: the minimal number of segments and the minimal flips needed to achieve it.
  • Describe an algorithm and provide its time and space complexity.