FastPrepRandomized Collection with Duplicate Values

Randomized Collection with Duplicate Values

Okta logoOkta● HardFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Process a finite operation sequence against a collection that stores duplicate integers.

  • INSERT adds values[i] and returns whether that value was absent before the operation.
  • REMOVE removes the oldest still-present occurrence of values[i] and returns whether an occurrence existed.
  • GET returns the element at index floorMod(values[i], size) in the collection's internal dense array. A GET operation is provided only when the collection is non-empty.

Removal fills the removed dense-array slot with the previous final element before shortening the array. Return one string per operation: "true" or "false" for mutations and the selected decimal integer for GET.

The injected integer on GET models a random-number source. Design insertion, removal, and indexed selection to run in expected O(1) time.

Function

randomizedCollectionOperations(operations: String[], values: int[]) → String[]

Examples

Example 1

operations = ["INSERT","INSERT","INSERT","REMOVE","GET"]values = [1,1,2,1,3]return = ["true","false","true","true","1"]

After removing one 1, the dense array contains two values. The injected draw 3 selects index 1.

Example 2

operations = ["REMOVE","INSERT","GET"]values = [5,5,-1]return = ["false","true","5"]

The first removal fails. With one stored value, every injected draw selects that value.

Example 3

operations = ["INSERT","INSERT","REMOVE","REMOVE","INSERT"]values = [7,7,7,7,7]return = ["true","false","true","true","true"]

After both occurrences are removed, inserting 7 again reports that it was absent.

Constraints

  • operations.length == values.length.
  • 1 <= operations.length <= 100000.
  • Every operation is INSERT, REMOVE, or GET.
  • -10^9 <= values[i] <= 10^9.
  • Every GET occurs when the collection is non-empty.

More Okta problems

See Okta hiring insights
public String[] randomizedCollectionOperations(String[] operations, int[] values) {
    // Write your solution here.
}
operations["INSERT","INSERT","INSERT","REMOVE","GET"]
values[1,1,2,1,3]
expected["true", "false", "true", "true", "1"]
Checking account…