How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Pinterest during technical interviews.

Implement weighted random choice | Pinterest Coding Question

Quick Overview

This question evaluates understanding of weighted random sampling, probability distributions, input validation, and algorithmic time and space complexity in the context of implementing a sampling routine.

Loading coding console...

Part 2: Deterministic Weighted Random Choice for k Samples With Replacement

You are given a list `items`, an optional probability list `p`, an integer `size`, and a list `random_values` of length `size`. For each value `random_values[j]` in `[0, 1)`, independently simulate one weighted random choice and return all results in order. Sampling is with replacement, so the same item may appear multiple times. If `p` is `None`, sample uniformly. If the input is invalid, return the string `'INVALID'`. Invalid input includes: empty `items`, negative `size`, `random_values` length mismatch, any `random_values[j]` outside `[0,1)`, `p` length mismatch, negative probabilities, or probabilities whose sum differs from `1` by more than `1e-9`.

Constraints

`1 <= len(items) <= 10^5` for valid inputs
`0 <= size <= 10^5`
`len(random_values) == size`
Each `random_values[j]` must satisfy `0 <= random_values[j] < 1`
If `p` is not `None`, then `len(p) == len(items)`
Each probability must be a non-negative number
For valid weighted input, `abs(sum(p) - 1.0) <= 1e-9`

Examples

Input: (['a', 'b', 'c'], [0.2, 0.5, 0.3], 4, [0.05, 0.2, 0.69, 0.95])

Expected Output: ['a', 'b', 'b', 'c']

Explanation: Using cumulative probabilities [0.2, 0.7, 1.0], the four draws map to a, b, b, c.

Input: ([1, 2, 3], None, 5, [0.0, 0.34, 0.35, 0.99, 0.66])

Expected Output: [1, 2, 2, 3, 2]

Explanation: Uniform sampling over 3 items maps each value by bucket index `int(r * 3)`.

Input: (['x', 'y'], [0.5, 0.5], 0, [])

Expected Output: []

Explanation: Requesting zero samples should return an empty list.

Input: ([7], None, 3, [0.1, 0.5, 0.999])

Expected Output: [7, 7, 7]

Explanation: With one item, every sample returns that same item.

Input: (['a', 'b'], [0.5, 0.5], 3, [0.1, 0.2])

Expected Output: 'INVALID'

Explanation: The number of random values must exactly match `size`.

Hints

Precompute cumulative probabilities once instead of rescanning `p` from scratch for every sample.
After building prefix sums, binary search can locate the bucket for each random value.

Quick Overview