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)