Randomized Algorithms

Utilize randomness to solve problems efficiently.

Topics in the full lesson

Concept and Use Cases
Key Concepts
Time and Space Complexity
Randomized Algorithms and Methods
Practical Tips and Tricks
Common Gotchas
Advanced Topics
Interview Tips and Tricks
Common Mistakes

Try the free interview questions

Work through a question before revealing its explanation. These questions and answers are free; Premium adds the full lesson walkthrough, examples and implementation detail.

CodingMedium

Random Pick with Weight

Mark complete

Question

You are given a 0-indexed array w, where w[i] is the weight of index i. Implement pickIndex(), which returns an index in [0, n) chosen at random with probability proportional to its weight — that is, index i is returned with probability w[i] / sum(w).

Take a moment to think about this before revealing the answer

Explain your reasoning or try an implementation before comparing answers.

Practice on LeetCode

CodingMedium