Amazon·Software Engineer·Online Assessment (OA)·Junior

Junior

Apr 2026

Summary

Amazon OA for a SWE role, one algorithmic problem about medians in subsequences. Pretty standard online assessment format but the problem had a bit of a twist that tripped me up at first.

Questions Asked (1)

Given an array of integers and a number k, find both the maximum and minimum possible median values across all subsequences of length k. Return them as a two-element array [max_median, min_median].

Algorithms & Data Structures

Author's notes

Spent way too long second-guessing what 'median' means for even-length subsequences before just going with lower-middle index.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that a subsequence preserves the original order, but since we only care about the multiset of chosen elements, we can sort the array and consider any k elements. Then, the median of a sorted subsequence of length k is the element at index floor((k-1)/2) (0-indexed) in that subsequence. To maximize the median, choose the largest possible element that can serve as the median, which is the element at index n - ceil(k/2) in the sorted array; to minimize it, choose the smallest possible, which is the element at index floor((k-1)/2).

Pro tip: Mention that the order of elements in a subsequence doesn't affect the median, so sorting is valid. Also, explicitly state the indices and handle edge cases like k=1 or k=n.

1. Clarify definitions and constraints

Confirm that a subsequence maintains relative order but the median depends only on the multiset of values. Ask about constraints (e.g., array size, k range) to determine if sorting is acceptable.

2. Sort the array

Sort the array in non-decreasing order. This allows us to easily select any k elements and reason about the median position.

3. Determine median index

For a sorted subsequence of length k, the median is at index m = floor((k-1)/2) (0-indexed). This is the lower median for even k.

4. Find maximum median

To maximize the median, we want the largest possible value at position m. This is achieved by taking the m-th element from the end of the sorted array, i.e., sorted[n - k + m].

5. Find minimum median

To minimize the median, we want the smallest possible value at position m. This is achieved by taking the m-th element from the start, i.e., sorted[m].

Key Points to Mention

Median definition for even and odd k (lower median for even k).
Sorting the array does not change the set of possible subsequences because order within the subsequence doesn't affect the median.
The median of a sorted subsequence of length k is at index floor((k-1)/2).
Maximum median is the element at index n - k + floor((k-1)/2) in the sorted array.
Minimum median is the element at index floor((k-1)/2) in the sorted array.
Time complexity: O(n log n) due to sorting, which is optimal for this problem.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.