How should I practice Randomized String Multiset?

Start by reading the full statement, solve the visible examples, then compare the pattern against related LinkedIn phone screen problems in FastPrep.

Is Randomized String Multiset associated with LinkedIn?

FastPrep tags this as a LinkedIn phone screen coding practice problem when the problem catalog has that company and stage context.

Randomized String Multiset

LinkedIn● HardFULLTIMEPHONE SCREEN

Learn

Problem statement

Maintain a multiset of strings, allowing duplicate occurrences. Process the equally sized arrays actions, words and drawIndices in order. Return one string per operation.

INSERT adds one occurrence of words[i]. Return "true" if that word was absent immediately before insertion, otherwise "false".
REMOVE removes one occurrence of words[i] if present and returns "true"; otherwise return "false".
GET_RANDOM returns the occurrence selected by the supplied draw index. It is called only when the multiset is nonempty.

Reproducible random draws

For this exercise, assume active occurrences occupy a dense ordered sequence, initially empty. Insertions append. Removal chooses the most recently inserted active occurrence of the requested word, replaces its slot with the sequence's last occurrence, and removes the last slot. Failed removals do nothing. Each occurrence has its own insertion identity even when its word is duplicated.

For GET_RANDOM, drawIndices[i] is a supplied zero-based index into that current sequence; return the word at that slot. The input index represents an external uniform random draw. If each draw is independent and uniform on the current slot range, a word with c occurrences among s total occurrences is returned with probability c / s. The supplied test draws need not look random; do not generate new draws, deduplicate the sequence, or sort its slots.

For this exercise, assume words[i] = "" for GET_RANDOM and drawIndices[i] = 0 for the other actions. Mutation results and sampled words are all returned as strings. Aim for expected constant time per operation, excluding the cost of processing a string and amortized dynamic-array resizing.

Function

runStringMultiset(actions: String[], words: String[], drawIndices: int[]) → String[]

Examples

Example 1

actions = ["INSERT","INSERT","INSERT","GET_RANDOM","GET_RANDOM","GET_RANDOM"]words = ["cat","cat","dog","","",""]drawIndices = [0,0,0,0,1,2]return = ["true","false","true","cat","cat","dog"]

The dense slots are cat,cat,dog: two of three uniform indices select cat.

Example 2

actions = ["INSERT","INSERT","INSERT","INSERT","REMOVE","GET_RANDOM","REMOVE","GET_RANDOM"]words = ["red","blue","red","green","red","","red",""]drawIndices = [0,0,0,0,0,2,0,0]return = ["true","true","false","true","true","green","true","green"]

The newest red is in slot2, so green fills it; removing the remaining red then moves green to slot0.

Example 3

actions = ["REMOVE","INSERT","REMOVE","INSERT","GET_RANDOM"]words = ["x","x","x","x",""]drawIndices = [0,0,0,0,0]return = ["false","true","true","true","x"]

A missing removal is false. Once the last occurrence is removed, a later insertion is new again.

Constraints

The three input arrays have the same length n, where 0 <= n <= 1000.
Each action is INSERT, REMOVE, or GET_RANDOM.
Inserted and removed words contain between 1 and 30 lowercase English letters.
Every random operation has 0 <= drawIndices[i] < current occurrence count; its word field is empty.
Non-random operations have draw index 0.