Q. Given an array, you have to write a function to select a random number from the array such that it has not appeared in the last K calls to this function.

Approach : Used a combination of deque and unordered_set to generate the random number in O(N) time. Further, the interviewer required an optimisation of O(1), used a vector to do so. The vector contains the unselected elements so far. As soon as an element is visited, swap the element with the last element in the vector & do a pop_back operation to get the answer in O(1).