Algorithm · Microsoft · Medium
You are handed an array of integers. You may pick a collection of distinct integer values, and every element of the array that equals one of the picked values is then deleted. The deletions must eliminate at least half of the elements in the array. Return the smallest number of distinct values you need to pick so that this requirement is satisfied. Interview Notes The candidate reported that this question resembles a well-known public problem about shrinking an array to half…