Interview Algorithms: Difference between revisions

From David's Wiki
Line 22: Line 22:
Print all permutations of an array.<br>
Print all permutations of an array.<br>
The idea here is that you need a for-loop nested for each element of an array.<br>
The idea here is that you need a for-loop nested for each element of an array.<br>
So n element means n nested for-loops. You use recursion to nest the loops.<br>
So n elements means n nested for-loops. You use recursion to nest the loops.<br>
* [https://leetcode.com/problems/permutations/ Permutations]
* [https://leetcode.com/problems/permutations/ Permutations]
* [https://leetcode.com/problems/permutations-ii/ Permutations-iii]
* [https://leetcode.com/problems/permutations-ii/ Permutations-iii]

Revision as of 12:47, 9 January 2020

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.


Permutations

Print all permutations of an array.
The idea here is that you need a for-loop nested for each element of an array.
So n elements means n nested for-loops. You use recursion to nest the loops.

Permute Brute-force solution