5,322
edits
Interview Algorithms: Difference between revisions
no edit summary
No edit summary |
|||
| Line 1: | Line 1: | ||
Insights from Leetcode problems. | Insights from Leetcode problems. | ||
==Linear Searching== | |||
====Finding a cycle in a linked-list==== | ====Finding a cycle in a linked-list==== | ||
Use two runners. <math>O(n)</math><br> | Use two runners. <math>O(n)</math><br> | ||
| Line 10: | Line 10: | ||
==== | ==Backtracking== | ||
====Permutations==== | ====Permutations==== | ||
Print all permutations of an array.<br> | Print all permutations of an array.<br> | ||
| Line 75: | Line 67: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
}} | }} | ||
==Misc Tricks== | |||
====Finding duplicates in an array==== | |||
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> | |||
The remaining bits will remain <math>m \mod n</math> times.<br> | |||
* [https://leetcode.com/problems/single-number/ single-number] | |||
* [https://leetcode.com/problems/single-number-ii/ single-number-ii] | |||
* [https://leetcode.com/problems/single-number-iii/ single-number-iii] | |||