How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Solve median extremes and segment flips

Quick Overview

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.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

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.

Quick Answer: 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.

Sliding-Window Median Extremes

You are given an integer k (1 ≤ k ≤ n) and an integer array nums of length n. For every contiguous subarray (window) of length k, compute its median. For even k, use the lower median (the element at 0-based sorted index (k-1)/2). Return a two-element array [maxMedian, minMedian]: the maximum and the minimum among all the window medians. If k > n, no window of length k exists; return an empty array. Aim for O(n log k) time and O(k) space. The intended approach maintains a balanced/ordered multiset of the current window (e.g., two heaps, an order-statistics structure, or a sorted container with binary-search insert/delete) so each slide is O(log k).

Constraints

1 ≤ k ≤ n is the valid case; if k > n return [].
0 ≤ n ≤ 10^5
-10^9 ≤ nums[i] ≤ 10^9
For even k, the median is the lower of the two middle elements (sorted index (k-1)/2).

Examples

Input: (3, [1, 3, -1, -3, 5, 3, 6, 7])

Expected Output: [6, -1]

Explanation: Windows of size 3 have medians 1, -1, -1, 3, 5, 6; max=6, min=-1.

Input: (1, [5, 2, 8, 1])

Expected Output: [8, 1]

Explanation: k=1: each element is its own median; max=8, min=1.

Input: (2, [4, 1, 7, 2])

Expected Output: [2, 1]

Explanation: Even k uses the lower median: windows [4,1]->1, [1,7]->1, [7,2]->2; max=2, min=1.

Input: (4, [10])

Expected Output: []

Explanation: k=4 > n=1, so no window exists and the result is empty.

Input: (5, [2, 4, 6, 8, 10])

Expected Output: [6, 6]

Explanation: Only one window; its median is 6, so max=min=6.

Input: (2, [-5, -1, -3])

Expected Output: [-3, -5]

Explanation: Lower median of [-5,-1] is -5 and of [-1,-3] is -3; max=-3, min=-5.

Hints

Maintain the current window as an ordered multiset; the lower median is always at sorted index (k-1)//2.
On each slide, delete the element leaving the window and insert the one entering it, then read the element at the fixed median index.
Track a running max and min of the medians as you go, or collect all medians and reduce — either way the answer is [max, min].
Edge case: when k > n there are no windows, so return an empty array.

Even-Length Uniform Segmenting with Minimal Flips

You are given a binary array frames of length n (each value 0 or 1). You may flip any bits (0↔1). After flipping, frames must be partitionable into contiguous segments such that every segment has even length and contains identical values (all 0s or all 1s). First minimize the number of segments; subject to that minimum, minimize the total number of flips. Return a two-element array [minSegments, minFlips]. Because every segment must have even length, the lengths sum to an even number, so a valid partition exists only when n is even. When n is even, the fewest segments is 1 (the whole array as a single even-length uniform block), and the minimal flips to make it uniform is min(count of 1s, count of 0s). For an empty array return [0, 0]. If n is odd, no valid partition exists; return [-1, -1].

Constraints

0 ≤ n ≤ 10^5
frames[i] ∈ {0, 1}
A valid partition (all segments even-length) exists iff n is even.
Minimize segment count first, then total flips.

Examples

Input: ([1, 0, 0, 1],)

Expected Output: [1, 2]

Explanation: n=4 even; two 1s and two 0s, flip the two of the minority value -> 1 segment, 2 flips.

Input: ([0, 0, 0, 0],)

Expected Output: [1, 0]

Explanation: Already uniform and even length: 1 segment, 0 flips.

Input: ([1, 1, 1, 1, 1, 1],)

Expected Output: [1, 0]

Explanation: All ones, length 6: 1 segment, 0 flips.

Input: ([1, 0, 1],)

Expected Output: [-1, -1]

Explanation: n=3 is odd, so no partition into even-length segments exists.

Input: ([],)

Expected Output: [0, 0]

Explanation: Empty array needs no segments and no flips.

Input: ([1, 0, 1, 0, 1, 1],)

Expected Output: [1, 2]

Explanation: Four 1s and two 0s; flip the two 0s (the minority) -> 1 segment, 2 flips.

Input: ([0, 1],)

Expected Output: [1, 1]

Explanation: One 0 and one 1; flip either one -> 1 segment, 1 flip.

Hints

Every segment has even length, so the segment lengths sum to an even number — a valid partition exists only when n is even.
When n is even, one single even-length uniform segment covering the whole array is always valid, so the minimum segment count is 1.
With one segment the whole array must be uniform; the cheapest way is to flip the minority value, costing min(#ones, #zeros) flips.
Handle the empty array as [0, 0] and odd-length n as impossible ([-1, -1]).

Quick Overview