Interview Algorithms: Difference between revisions
Created page with "Insights from Leetcode problems. ====Finding a cycle in a linked-list==== Use two runners. <math>O(n)</math><br> Runner 1 goes two steps per iteration.<br> Runner 2 goes one..." |
No edit summary |
||
| Line 7: | Line 7: | ||
Runner 2 goes one step per iteration.<br> | Runner 2 goes one step per iteration.<br> | ||
If there is a cycle, runner 2 will lap runner 1 within 2 cycles. | 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 $n$ times and one number appears $m>n$ times where $gcd(n,m)==1$, | |||
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> | |||
Revision as of 19:56, 31 October 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 $n$ times and one number appears $m>n$ times where $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.