# Interview Algorithms

$$\newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits}$$

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\gt 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.