How should I practice All About Medians?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is All About Medians associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

All About Medians

Learn this problem

● EasyAmazonNEW GRADOA

See Amazon hiring insights

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] → median 1
[1, 3] → median 1
[2, 3] → median 2

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] → median 56
[21] → median 21

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 index floor((5-1)/2) = 2 is 16

Since there is only one subsequence, both the maximum and minimum median are 16.

Constraints

1 ≤ n ≤ 10^5
0 ≤ nums[i] ≤ 10^9
1 ≤ k ≤ n