Solve sampling and streaming tasks
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement the following algorithmic tasks:
1. **Weighted random selection**: You are given an array of positive integer weights `w`, where `w[i]` is the relative probability of selecting index `i`. Design a class with:
- a constructor that preprocesses `w`
- a method `pickIndex()` that returns an index such that the probability of returning `i` is `w[i] / sum(w)`
Aim for fast repeated sampling.
2. **Find anagram windows**: Given two strings `s` and `p`, return all starting indices in `s` where the substring of length `len(p)` is an anagram of `p`.
3. **Streaming mean**: Design a data structure for a stream of numbers that supports:
- `add(x)`: add a new number to the stream
- `getMean()`: return the arithmetic mean of all numbers seen so far
Discuss edge cases such as an empty stream and large input volume.
Quick Answer: This question evaluates algorithmic problem-solving, data structure design, probabilistic reasoning for weighted random selection, sliding-window string processing for anagram detection, and streaming/online statistical computation.