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:
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.
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:
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.
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.
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.
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.
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:
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:
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: