Solve median extremes and segment flips

Q: Solve median extremes and segment flips

This question evaluates proficiency in algorithm design, efficient data structures for dynamic order-statistics and sliding-window median computation, and combinatorial optimization for binary-array segmentation with minimal flips.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Solve median extremes and segment flips

Overview

Comments (0)