What's your favorite algorithm?

adtm profile image Tomas Eglinskas ・1 min read

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);

Posted on by:

adtm profile

Tomas Eglinskas


A Software Engineer on the path to find oneself by doing projects, meeting new people and learning various topics, even non tech included


markdown guide