Leetcode 25: Reverse nodes in k-group

My first thoughts for reversing the group was to have start and end pointers, switching those and then moving pointers one step inwards. This is logically how I would tackle reversing array elements but it does not work well with a linked lists (lots of traversing for end pointers and then keeping track of surrounding pointers). I then realised that we could reverse a group of nodes by traversing along the group using three pointers and adjusting those pointers as we go. We can then keep track of the last pointer of the previous group to link groups together. Here are my whiteboard notes:

And here is the c++ source code for the solution:
https://gist.github.com/adamkorg/9f6326b58db32210d9542bd1287133f9

Posted in programming | Tagged , , | Leave a comment

Leetcode 23: Merge k sorted lists

Here are my whiteboard notes for solving this problem:

And here is my c++ source code for the solution:

https://gist.github.com/adamkorg/fb698c0785845576ff0b42a091547691

Initially I started off with what I thought was a simple inefficient way of finding the next smallest node but the implementation was actually a little complicated. The multimap version is more time efficient and possibly has less complicated edge cases. I think an even more efficient way to keep track of the smallest node would be to use a priority queue.

Posted in programming | Tagged , , | Leave a comment

Leetcode 17: Phone key combinations

Recursion is a very natural fit for this problem. Iterate through each letter of each digit and recursively go into each of those letters to the next digit. If we are at the last digit then we add the current whole combination while we iterate the letters. We need to keep track of the progress of each digit through recursion. I used a vector size of digits to keep track of progress. Here is a gist of the source code:

Posted in programming | Tagged , , | Leave a comment

Median Of Two Sorted Arrays problem

This is a tricky little leetcode problem:
https://leetcode.com/problems/median-of-two-sorted-arrays/

Here are some of my observations on a whiteboard:

There are a lot of fiddly edge cases. I think my solution could be simplified but here is the gist anyway:

https://gist.github.com/adamkorg/ffba283f298e7c2c2b748acb49ccc9f1

Posted in programming | Tagged , , | Leave a comment

Shortest Path – Dijkstra’s algorithm

Here are my whiteboard notes on how to implement the Dijkstra’s algorithm to find the shortest path of a graph:

Here is my simple c++ implementation of this:

The above is a very simple implementation of the algorithm. It is O(V²). We can optimise this to be something like O(E log V) by using a heap, map, or set data structure in the next_vertex_to_visit() function.

The above implementation is also not very object oriented. I felt that putting this functionality into classes would increase the complexity a bit and I wanted this to be as easy to understand as possible. If I was to implement this in production code then I would have a Graph class to encapsulate the logic.

Posted in programming | Tagged , | Leave a comment

Shortest Path – Bellman Ford algorithm

Here are my notes on how to implement the Bellman Ford algorithm to find the shortest path of a graph:

This is along the lines of what Rob Conery describes in The Imposter’s Handbook. And here is my c++ implementation of this:

The above is a vertex oriented walk through the graph, where we visit each vertex and calculate the costs to every outwardly connected vertex. I have found it simpler to just walk through an array of edges, which cuts down some complexity:

To keep this simple, I left out the optimisation to break out of the outer loop when no more updates are made.

Posted in programming | Tagged , | Leave a comment

Fibonacci spiral

Here are my whiteboard plans for drawing the Fibonacci spiral. The main issues were figuring out the x and y positions of each of the squares. I knew that I would need a loop that iterates around North, West, South and East directions anti-clockwise.

Once those x and y positions were figured out, it was easy to code this up in JavaScript:

Here is the JavaScript running to draw the spiral:

Posted in programming | Tagged , | Leave a comment

Maximum Subarray Sum problem

I had to write down an example and work through it to figure this out. Here are my resulting whiteboard notes:

A few different implementations can be found here:

https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6

I think Kadane’s algorithm can also be used to solve the problem of finding the maximum profit from buying and selling shares from an array of daily prices:

https://www.geeksforgeeks.org/stock-buy-sell/

I think we can calculate the differences between the daily prices and then treat this as a maximum subarray problem. So when the share price goes down and the total goes below zero, we reset this by setting the count to zero.

Posted in programming | Tagged , | Leave a comment

Nth Fibonacci number matrix solution

It’s easy to implement a 2^n recursive solution and also easy to implement an iterative O(n) solution but implementing an O(log n) solution is trickier. The following has a nice summary of various solutions:

https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

I just wanted to add some commentary to matrix solution is Method 4 and 5 above. Here are my whiteboard notes/calculations:

So the key thing is to realise that raising the base matrix below to the power of n will give a value for the nth fibonacci number:

One part of the implementation challenge is dealing with matrices and doing multiplication on them. The other part of the challenge is raising the matrices to a power efficiently. A naive power function will result in O(n) but we can optimise that function to O(log n). This is normally done recursively but can be simulated iteratively using binary operators – see section 4 of the following for an implementation:

https://www.techiedelight.com/power-function-implementation-recursive-iterative/

Posted in programming | Tagged , | Leave a comment

Sum of two problem

I have signed up to leetcode. The first problem I did was called “Two Sum”, where you need to find two numbers in an array that when added together match a target number. I thought I’d write some notes here to remind myself about the details in the future.

Brute force solution

So, the most obvious solution is comparing all combinations of each two numbers with two nested for loops. This is easy to code and simple but doesn’t scale well as it is O(n²).

Hash map solution

The next easiest solution for me was to store the numbers in a hash map (in c++ std::unordered_map<>) and use that to find the required complement of each number. This is the most scalable solution as it has O(n) time complexity but also has O(n) space complexity.

Ordered list iterating solution

The solution that didn’t come as easily to me as it probably should have was an algorithm to pass through the numbers in a linear way if they are already sorted. I intuitively knew this was possible but it didn’t come to me until I drew out an example of the numbers on a whiteboard:

Once written down like this, it becomes clear that we can iterate from the start and end of the array heading towards the centre while comparing values. If the sum of the values is bigger than target then we decrement j. If the sum is smaller than target then we increment i. If i and j cross then we don’t have a match.

By the way, I think some of the leetcode test case arrays are not sorted. If we sort the array first then we have an O(n log n) solution, which in theory should not be as fast as the hash map solution. However I found that this was in fact quicker than the hash map solution. I guess the leetcode test cases must be small and possibly mostly sorted. I don’t think there is UI in leetcode to check the submission test cases, so I don’t know for sure.

So the moral of the story is to write out an example even if it is simple.

I have since found this google interview example video that is a nice walkthrough of this problem:

Posted in programming | Tagged , , | Leave a comment