All About Medians
Updated
Problem statement
A new Amazon intern encountered a challenging task. Currently, the intern has n integers, where the value of the ith element is represented by the array element nums[i]. The intern is curious to play with arrays and subsequences and thus asks you to join him.
Given an array nums of n integers and an integer k, the intern needs to find the maximum and minimum median over all subsequences of length k.
The median of a subsequence of length k is defined as follows: sort the k chosen elements in non-decreasing order, then the median is the element at 0-indexed position floor((k-1)/2). In other words, for odd k it is the middle element, and for even k it is the lower-middle element.
Function
medians(nums: int[], k: int) → int[] Complete the function medians in the editor below.
medians has the following parameter(s):
int nums[n]: the value of integers.int k: the given integer.
Returns int[]: the maximum and minimum median over all subsequences of length k, in the form [maximum median, minimum median].
Examples
Example 1
nums = [1, 2, 3]k = 2return = [2, 1]The subsequences of length k = 2 and their medians (using the lower-middle element of the sorted pair) are:
[1, 2]→ median1[1, 3]→ median1[2, 3]→ median2
The maximum median is 2 and the minimum median is 1.
Example 2
nums = [56, 21]k = 1return = [56, 21]The subsequences of length k = 1 and their medians are:
[56]→ median56[21]→ median21
The maximum median is 56 and the minimum median is 21.
Example 3
nums = [16, 21, 9, 2, 78]k = 5return = [16, 16]There is only one subsequence of length k = 5:
[16, 21, 9, 2, 78]→ sorted[2, 9, 16, 21, 78], median at indexfloor((5-1)/2) = 2is16
Since there is only one subsequence, both the maximum and minimum median are 16.
Constraints
1 ≤ n ≤ 10^50 ≤ nums[i] ≤ 10^91 ≤ k ≤ n
More Amazon interview questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Count User Mentions in Chat MessagesRamp · OARamp interview questions
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Word Frequency Counts in Alphabetical OrderAbridge · OAAbridge interview questions
- Rank Football TeamsCapital One · OACapital One interview questions
- Maximum Apples That Fit in a BoxVirtu Financial · OAVirtu Financial interview questions
- Rank Football TeamsPersona · OAPersona interview questions
- Meandering ArrayVerisk · OA
- Minimum Magic Stones After MergesElevenLabs · OAElevenLabs interview questions
- Find Top Two TeamsAutodesk · OAAutodesk interview questions
- Total Server DowntimeVisa · OAVisa interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences