
Recent Posts
Recent Comments
Archives
Categories
Meta
Author Archives: adam
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 … Continue reading
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 … Continue reading
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 … Continue reading
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/kadanesalgorithmexplained50316f4fd8a6 I think Kadane’s algorithm can also be used to solve … Continue reading
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/programfornthfibonaccinumber/ I just wanted to add … Continue reading
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 … Continue reading
Heap Sort
Time complexity: O(n log n) Heapsort is O(n log n) even in worst case scenario. It uses a heap data structure (tree). You build the tree by adding each new value to the end and then bubbling that value up … Continue reading
Quick Sort
Time complexity average case: O(n log n) Time complexity worst case: O(n²) Quicksort is nlogn most of the time & usually 2 or 3 times quicker than MergeSort but can be n² in some cases, e.g when the numbers are … Continue reading
Merge Sort
Time complexity: O(nlogn) The most common way to implement Merge Sort is with recursion:https://gist.github.com/adamkorg/99cae1fa4da0bc8431d040c1e8f516fd This uses divide and conquer. Divide in half repeatedly until we have list of single elements. Then we start comparing those elements to build up a … Continue reading
Bubble Sort
This is going to be the first in a series of sorting algorithm posts. I thought I’d make these posts so I can quickly refresh my memory of the algorithms in the future. Time Complexity: O(n²) Bubble sort is simple … Continue reading