Interview Algorithms

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Insights from Leetcode problems.

Finding a cycle in a linked-list

Use two runners. ${\displaystyle O(n)}$
Runner 1 goes two steps per iteration.
Runner 2 goes one step per iteration.
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.

Finding duplicates in an array

If you have an array of ints where each number appears ${\displaystyle n}$ times and one number appears ${\displaystyle m>n}$ times where ${\displaystyle gcd(n,m)==1}$, then you count the number of times each bit appears and take it mod ${\displaystyle n}$.
The remaining bits will remain ${\displaystyle m\mod n}$ times.