Random Picks Excluding Recent Values
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
You are given an array of distinct integer values, an exclusion length k, a requested number of accepted picks picks, and recorded random candidate indices draws.
Process draws from left to right. A candidate index selects values[draws[i]]. Reject that candidate when its value appears among the most recent k accepted values. Otherwise, accept it, append it to the result, and update the recent-value history.
Rejected candidates do not change the recent-value history. Stop as soon as picks values have been accepted and return them in acceptance order.
When k is 0, every candidate is accepted. The input guarantees that draws contains enough acceptable candidates to produce the requested result.
Function
pickWithoutRecent(values: int[], k: int, picks: int, draws: int[]) → int[]Examples
Example 1
values = [10,20,30]k = 1picks = 4draws = [0,0,1,1,2,0]return = [10,20,30,10]Accept 10, reject the repeated 10, accept 20, reject the repeated 20, then accept 30 and 10.
Example 2
values = [1,2,3,4]k = 2picks = 5draws = [0,1,0,2,1,3,0]return = [1,2,3,4,1]After accepting 1 and 2, the next 1 is rejected. After accepting 3, the next 2 is still recent and is rejected.
Example 3
values = [5,7]k = 0picks = 4draws = [1,1,0,1]return = [7,7,5,7]With k = 0, no accepted value is excluded, so every recorded candidate is returned.
Constraints
1 <= values.length <= 10^5.- All values are distinct and satisfy
-10^9 <= values[i] <= 10^9. 0 <= k < values.length.1 <= picks <= 10^5.picks <= draws.length <= 2 * 10^5.0 <= draws[i] < values.length.- The recorded candidates contain enough accepted values to produce exactly
picksresults.