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)