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 Google.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Google during technical interviews.

Implement substring search and weighted sampling

Quick Overview

This question evaluates algorithm design and analysis skills across string processing (efficient substring search) and randomized/data-structure techniques (weighted random sampling with update considerations), testing time/space complexity reasoning and probabilistic thinking for large-scale inputs.

Loading coding console...

Part 2: Deterministic Weighted Picker

You are given an array of positive integer `weights`. Index `i` should be chosen with probability `weights[i] / sum(weights)`. To make the problem deterministic and testable, instead of generating random numbers inside the function, you are also given a list `draws`. Each draw is an integer in the range `[1, sum(weights)]`, representing the random value that would have been generated. For each draw, return the index that would be picked. Formally, build the weighted picker so that draw `d` selects the smallest index `i` such that the prefix sum up to `i` is at least `d`. Follow-up discussion: if weights changed frequently, a Fenwick tree or segment tree would support both updates and picks in `O(log n)`.

Constraints

1 <= len(weights) <= 200000
1 <= weights[i] <= 1000000000
0 <= len(draws) <= 200000
Each draw satisfies 1 <= draw <= sum(weights)

Examples

Input: ([1, 3], [1, 2, 4])

Expected Output: [0, 1, 1]

Explanation: Prefix sums are [1, 4]. Draw 1 maps to index 0, while draws 2 and 4 map to index 1.

Input: ([2, 5, 3], [1, 2, 3, 7, 8, 10])

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

Explanation: Prefix sums are [2, 7, 10], so ranges 1-2, 3-7, and 8-10 map to indices 0, 1, and 2.

Input: ([10], [1, 5, 10])

Expected Output: [0, 0, 0]

Explanation: With only one weight, every draw selects index 0.

Input: ([3, 1, 2], [3, 4, 6])

Expected Output: [0, 1, 2]

Explanation: This checks exact prefix boundaries: prefix sums are [3, 4, 6].

Input: ([4, 1, 1], [])

Expected Output: []

Explanation: No draws means no picks to return.

Hints

If you know the prefix sums of the weights, each draw becomes a search for the first prefix sum that is at least that draw value.
For static weights, prefix sums plus binary search are enough. For frequent updates, think about Fenwick trees or segment trees.

Quick Overview