Interview Algorithms: Difference between revisions

From David's Wiki
Line 11: Line 11:


====Finding duplicates in an array====
====Finding duplicates in an array====
If you have an array of ints where each number appears $n$ times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>,  
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>,  
then you count the number of times each bit appears and take it mod <math>n</math>.<br>
then you count the number of times each bit appears and take it mod <math>n</math>.<br>
The remaining bits will remain <math>m \mod n</math> times.<br>
The remaining bits will remain <math>m \mod n</math> times.<br>

Revision as of 03:54, 5 November 2019

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.