The day will come when I will be sitting across the desk, asking someone interview questions.
In preparation for those far, far-away, distant future days, here is a question I read yesterday.
“An array of ‘n’ items where each cell contains a number from the set [1,n-1] with every number in the set occurring at least once. Since, the set has n-1 members and the array is n item long, one number is duplicated. Give a linear time, constant space algorithm to search for this duplicate number.”