Katkat
Back

Implement substring search and weighted sampling

GoogleMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement a fast substring matching algorithm and a data structure that supports weighted random sampling from a dynamic collection of items.

Part 1: Substring Search

Implement a function find_occurrences(text, pattern) that returns the starting indices of all occurrences of pattern in text. Your solution should perform better than the naive O(N*M) approach.

Part 2: Weighted Sampling

Design a data structure WeightedSampler that supports the following operations:

  • update(item, weight): Adds or updates the weight of an item. If weight is 0, the item should effectively be removed from sampling.
  • sample(): Returns an item chosen randomly based on the probability distribution defined by its weights (i.e., the probability of picking an item is weight_i / sum_of_all_weights).

Constraints

  • For find_occurrences, assume len(text) <= 10^6 and len(pattern) <= 10^4.
  • For WeightedSampler, update should be O(log N) where N is the number of unique items.

Examples

# Part 1
find_occurrences("ababcababa", "aba") # Returns [0, 5, 7]

# Part 2
sampler = WeightedSampler()
sampler.update("A", 1)
sampler.update("B", 3)
sampler.sample() # Returns 'B' with 75% probability, 'A' with 25%

Edge Cases

  • Pattern longer than the text.
  • Updating a weight to 0 or negative values.
  • Calling sample() when no items have weights > 0.

Hints

Hint 1

For Part 1, consider using the Knuth-Morris-Pratt (KMP) algorithm to pre-process the pattern and avoid redundant comparisons.

Hint 2

For Part 2, a Fenwick Tree (Binary Indexed Tree) or a Segment Tree can store prefix sums of weights, allowing both updates and random selection in logarithmic time.

Hint 3

To perform sampling in the Fenwick Tree, use binary lifting to find the smallest index where the prefix sum is greater than a random value in `[0, total_weight)`.

Follow-up questions

  • How would you modify the substring search if you needed to handle a large set of patterns against a single text simultaneously?
  • If the weights are updated very frequently but sampling is rare, how might you optimize the `WeightedSampler`?
  • What are the numerical stability considerations when dealing with very large weights in the sampling data structure?