adamk.org

I came up with 5 different solutions for this:

• Simple recursive O(n!)
• Recursive with dynamic programming memoization O(nm)
• Iterative with dynamic programming O(nm)
• Mathematical using binomial coefficient O(max(n,m))
• Mathematical using binomial coefficient optimised

Source code for the different solutions:
Recursive
Recursive with dynamic programming
Iterative with dynamic programming
Mathematical using binomial coefficient
Mathematical using binomial coefficient optimised

This is an O(n) time, O(1) space solution. Find out list length by iterating through it. Recalculate k by mod len to reduce k to less than len. If new k is 0 return. Use slow and fast pointers to navigate fast to one before last and slow to one before new head. Rewire the pointers in these positions. So, split list after slow and join fast (last) to head. Return new head (node after slow).

The simple, obvious, inefficient way to solve this is to call next_permutation() k times. But that results in O(n!), which is slow. It is also possible in O(n) time, which relies on cutting through the problem space for each digit. So when k=4, on an n=3 problem, we know that the first digit will appear twice as 1, twice as 2 and twice as 3. We know that k=4 lands on the middle third of the problem space, so the first digit must be 2. We can progress like this through the rest of the digits. It is quite confusing to code. I found I had to plan it all out with formulas before (see whiteboard).

Process using one layer at a time, starting from the outer layer. The fiddly bit is getting the matrix coordinates correct and I plan that up front taking out the complication of layers.

Here is the code for the above plan:
https://gist.github.com/adamkorg/7e4a25b9b5961e0f133e9d2f6d23a948
And here is a more concise version, where I don’t have a separate layer function:

This is an easy problem, iterate from end of string counting characters until we reach a space. I just wanted to make this post as a reminder to myself about creating a table of variable values when running through a test case before compiling/executing.

Alternative, more concise solution:
https://gist.github.com/adamkorg/eda4764ec11da3c3ce932e614636f224

This was a little bit fiddly with some edge cases to consider. Iterate through the intervals array attempting to insert the new range or merge it. So at every step we need to check if the new range is before the current range or overlapping. There are a few different overlap conditions to consider. Also check to see if we need to insert the new entry at the back of the array.

Code from above:
https://gist.github.com/adamkorg/6fcf6ef13a04ab6967c6af3b4762be72
And, slightly cleaned up version:

Key insight is that it is much easier and more efficient to merge if we sort the ranges by the range begin. That results in O(nlogn) solution and I don’t think it can be done quicker than that.

The key insight to find the optimal O(n) solution is that we should evaluate our situation at every step as we iterate through the array, trying to maximise our remaining steps available. So in the first whiteboard example [2,3,1,1,4], we start at 2 so we have 2 steps available. We move on to the second element, so our remaining steps from the first element has gone down to one. Now we decide if we stop on this element and use its steps, which is 3, which is greater than our 1 step left, so we do. We now have 3 steps available. We continue like this until the last element.

Recursive with memoization solution timed out on leetcode test cases:
https://gist.github.com/adamkorg/f0e1ab8394dede0fd36ce6267e56bd96

The n-queens problem is about arranging n queens on an n x n chessboard such that no queen attacks another queen.

It turns out that this is quite a common example for using a backtracking algorithm. However my initial solution involved going through permutations of the column positions for each queen. Here are my whiteboard notes and source code for this solution and then my implementation of a more traditional backtracking solution further down:

And here is my explanation and implementation of backtracking solution (iterative):