Software Engineer

You are given a string ‘STR’. Your task is to return a prefix among all the prefixes of ‘STR’ that occurs the maximum number of times as a substring in ‘STR’. In case of a tie, return the longest prefix.

For example:

You are given ‘STR’ = “ababcd”. Then our answer will be “ab”. The prefixes “a” and “ab” occur the maximum number of times, i.e., 2. As the prefix “ab” is longer than “a” so, our answer will be “ab”.

We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase vaccination following safety measures. Time is running out. Can you help the nation?

You are given two positive integers: ‘n,’ ‘maxVaccines’ denoting the number of days for which this vaccination drive will go on and the total number of vaccines available for the drive, respectively. You have to find the number of vaccines administered each day. You are also given a number ‘dayNumber,’ and we are interested to know the maximum number of vaccines that can be administered on ‘dayNumber’ th day.

The rules of the vaccination drive :

1. There should be a positive number of vaccines administered each day during the vaccination drive.

2. The absolute difference between the number of vaccines in two consecutive days should not exceed 1.

3. The sum of all the elements of the vaccines array does not exceed maxVaccines, that is, you cannot administer more vaccines than what is provided to you.

4. Vaccines administered on ‘dayNumber’ th day should be maximized.

Design and implement a data structure which supports the following operations:

insert(X): Inserts an element X in the data structure and returns true if the element was not present, and false otherwise.

remove(X): Removes the element X from the data structure, if present. Returns true if the element was present and false otherwise.

search(X): Search the element X in the data structure. Returns true if the element was present and false otherwise.

getRandom(): Return a random element present in the data structure.

Four types of queries denote these operations:

Type 1: for insert(X) operation.
Type 2: for remove(X) operation.
Type 3: for search(X) operation.
Type 4: for getRandom() operation.

Note:

It is guaranteed that at least one element will be present in the data structure when getRandom() operation is performed.

Follow Up:

Can you implement every operation such that it works in O(1) time?

You are given a string 'STR' consisting of lower and upper case characters. You need to remove the consecutive duplicates characters, and return the new string.

Note :

You don't have to print anything, it has already been taken care of. Just implement the given function.