FastPrepFastPrep
Problem Brief

Maximize Types After Freeing Shelves

FULLTIMEOA
See Microsoft online assessment and hiring insights

A storeroom is used to organize items stored in it on N shelves. Shelves are numbered from 0 to N-1. The K-th shelf is dedicated to items of only one type, denoted by a positive integer A[K].

Recently it was decided that it is necessary to free R consecutive shelves. Shelves cannot be reordered. What is the maximum number of types of items that can still be stored in the storeroom after freeing R consecutive shelves?

Given:

  • an array A of N integers representing types of items stored on storeroom shelves.
  • an integer R representing the number of consecutive shelves to be freed.

    • Returns the maximum number of different types of items that can be stored in the storeroom after freeing R consecutive shelves.

    1Example 1

    Input
    A = [2, 1, 2, 3, 2, 3, 2], R = 3
    Output
    2
    Explanation
    It can be achieved by freeing shelves 2, 3, 4. The remaining shelves contain item types {2, 3}.

    2Example 2

    Input
    A = [2, 3, 1, 1, 2], R = 2
    Output
    3
    Explanation
    All three types {2, 3, 1} can still be stored by freeing the last two shelves.

    3Example 3

    Input
    A = [20, 10, 10, 10, 30, 20], R = 3
    Output
    3
    Explanation
    It can be achieved by freeing the first three shelves. The remaining item types are {10, 30, 20}.

    4Example 4

    Input
    A = [1, 100000, 1], R = 3
    Output
    0
    Explanation
    All shelves need to be freed, leaving no items.

    Constraints

    Limits and guarantees your solution can rely on.

    • N is an integer within the range [1..100,000].
    • R is an integer within the range [1..N].
    • Each element of array A is an integer within the range [1..100,000].
    public int maximizeTypesAfterFreeingShelves(int[] A, int R) {
  // write your code here
}
    Input

    A

    [2, 1, 2, 3, 2, 3, 2]

    R

    3

    Output

    2

    Sign in to submit your solution.