How should I practice Find Array Uniqueness Median 🐈?

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

Is Find Array Uniqueness Median 🐈 associated with Microsoft?

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

FastPrep

Problem · Array

Find Array Uniqueness Median 🐈

● HardMicrosoftFULLTIMEOA

See Microsoft hiring insights

The uniqueness of an array of integers is defined as the number of distinct elements present. For example, the uniqueness of [1, 5, 2, 1, 3, 5] is 4, element values 1, 2, 3, and 5.

For an array arr of n integers, the uniqueness values of its subarrays is generated and stored in another array, call it subarray_uniqueness.

Notes:

The median of a list is defined as the middle value of the list when it is sorted in non-decreasing order. If there are multiple choices for median, the smaller of the two values is taken.

For example, the median of [1, 5, 8] is 5, and [2, 3, 7, 11] is 3.

A subarray is a contiguous part of the array.

For example, [1, 2, 3] is a subarray of [6, 1, 2, 3, 5] but [6, 2] is not.

Function Description

Complete the function findArrayUniquenessMedian in the editor.

findArrayUniquenessMedian has the following parameter:

int[] arr: an array of integers

Returns

int: the median of the uniqueness values of all subarrays of arr

Examples

01 · Example 1

arr = [1, 2, 1]
return = 1

There are n = 3 elements in arr = [1, 2, 1]. The subarrays along with their uniqueness values are:

[1]: uniqueness = 1
[1, 2]: uniqueness = 2
[1, 2, 1]: uniqueness = 2
[2]: uniqueness = 1
[2, 1]: uniqueness = 2
[1]: uniqueness = 1

The subarray_uniqueness array is [1, 2, 2, 1, 2, 1]. After sorting, the array is [1, 1, 1, 2, 2, 2]. The choice is between the two bold values. Return the minimum of the two, 1. Output: 1

02 · Example 2

arr = [1, 2, 3]
return = 1

arr = [1, 2, 3]

[1]: uniqueness = 1
[1, 2]: uniqueness = 2
[1, 2, 3]: uniqueness = 3
[2]: uniqueness = 1
[2, 3]: uniqueness = 2
[3]: uniqueness = 1

After sorting, the array is [1, 1, 1, 2, 2, 3]. Output: 1.

Constraints

1 <= n <= 1e5
1 <= arr[i] <= 1e5