This is my favorite question to ask for technical recruiters - everyone has a unique story, you can have a better understanding of the company and the person, and of course, a conversation can easily follow afterward. I heard various shuffle algorithms, bloom filters, HyperLogLog and etc.
Mine is more of a technique, but I really liked it because of its simplicity. 
Including a mini explanation below (for the curious).
What's your favorite algorithm? :)
/* 
 * Question:
 * Given an array of integers from 1 <= A[i] <= n, 
 * some elements repeat twice and others only once.
 *
 * Your task is to find the elements which repeat twice.
 * Without using any extra space and in O(n) time.
 */
/*
 * The key here is not to use a hashmap, O(N) space, 
 * but to flip the numbers from positive to negative.
 *
 * When you traverse the array you can map the number 5 to index 4 
 * (we will check by sign and not value for duplicates) and if it is not negative 
 * - meaning it has not repeated - negate it. If it is negative, you know it has been 
 * already encountered. 
 * 
*/
const A = [5,2,1,4,2,1,7];
function findDuplicates(A) {
 const oldLength = A.length;
 for (let i = 0; i < oldLength; ++i) {
   const value = Math.abs(A[i]) - 1; // ignoring the sign and get the value
   if (A[value] > 0) A[value] *= -1;
   else A.push(value + 1);
 }
 return A.slice(oldLength);
}
    
Top comments (0)