Given an integer array with possible duplicates, you need to randomly return an index of a given target value. Each occurrence must have equal probability of being chosen.
For example, if the array is and target is , you should return index , , or with equal probability each.
The challenge: the array is given once in the constructor. How can you pick fairly without preprocessing all target values?