Random Pick Index

Random Pick Index

What is this problem about?

The Random Pick Index problem asks you to design a class that randomly picks an index of a given target value in an array with equal probability when multiple indices have that value. This coding problem uses reservoir sampling for space-efficient random selection without preprocessing all indices. The math, hash table, reservoir sampling, and randomized interview pattern is demonstrated.

Why is this asked in interviews?

Meta, Amazon, TikTok, and Google ask this because reservoir sampling is the elegant O(1) space solution to "pick random index of target." The preprocessing approach (store all indices in a hash map) uses O(n) space — reservoir sampling achieves the same result with O(1) extra space per pick call.

Algorithmic pattern used

Reservoir sampling. pick(target): scan the array once. For each index i where nums[i] == target: increment a counter. With probability 1/counter, set result = i. After the full scan, return result. This gives uniform probability for any index of the target value.

Example explanation

nums=[1,2,3,3,3]. pick(3): encounter 3 at indices 2,3,4.

• i=2: counter=1. prob=1/1=1. result=2.
• i=3: counter=2. prob=1/2. With 50% chance, result=3.
• i=4: counter=3. prob=1/3. With 33% chance, result=4. Each index has exactly 1/3 probability. ✓

Common mistakes candidates make

• Preprocessing all indices (O(n) space, defeats the purpose of reservoir sampling).
• Not understanding the 1/k probability at step k gives uniform distribution.
• Generating random number incorrectly (must be in [0, counter)).
• Returning wrong index when only one occurrence exists.

Interview preparation tip

Reservoir sampling is a fundamental algorithm for streaming data. The principle: when you see the k-th qualifying element, replace the current result with probability 1/k. This ensures uniform distribution without knowing total count in advance. Practice: "random element from stream," "random node from linked list," "random index from unseen data." Reservoir sampling is a must-know for data engineering and ML engineering roles.