bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
HardArrays & HashingLC 710

Random Pick with Blacklist

You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1] that is not in blacklist. Any integer that is in the mentioned range and not in blacklist should be equally likely to be returned. Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language. Implement the Solution class: Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist. int pick() Returns a random integer in the range [0, n - 1] and not in blacklist.

Asked at 4 companies
AmazonGoogleTwo Sigma
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode