Category Archives: programming

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:RecursiveRecursive with … Continue reading →

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 … Continue reading →

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. … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →