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

/*
* Question:
* Given an array of integers from 1 <= A[i] <= n,
* some elements repeat twice and others only once.
*
* 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
*
*/

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:

### 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