Ever wondered how google maps calculate the shortest path to your destination? This is the problem it must solve every time you search for the nearest Italian restaurant or the quickest route to visit your family.
The app obviously needs your geolocation, destination, and a mapping of the road/interstate highway system in your area to complete this task. From a hardware perspective, this problem requires a global satellite system with real-time ground communication.
This leaves a question. On the software side, how does it calculate the fastest path from the given data? This is especially challenging given the number of…
In 1959 British computer scientist Tony Hoare developed the QuickSort algorithm. He came up with the idea while visiting Moscow state university when he was tasked with alphabetically sorting Russian words to look up in a Russian-English dictionary.
Quick Sort is similar to many “divide and conquer” algorithms both in function and performance. If you are not familiar with recursive divide and conquer type algorithms, I advise you to review my previous article on merge sort. Grasping merge sort is a good stepping stone to mastering quick sort as their foundations are similar.
Quick sort’s procedure consists of three basic…
In 1945 John von Neumann, the Hungarian mathematician, physicist, and computer scientist, developed the merge sort algorithm. Merge sort is a general-purpose sorting method that uses a ‘divide and conquer’ approach. It was developed to address weaknesses in less efficient algorithms such as bubble sort. It is the classic example of a recursive bottom-up ‘divide and conquer’ algorithm in many ways. Despite this, a top-down looping approach is possible. For this article, I will explain merge sort with the former perspective.
IF(ARRAY.LENGTH == 1) THEN
ELSE IF(ARRAY.LENGTH ==2) THEN…
Find All the Permutations of a Set of Elements
A classic technical interview question is finding the permutations of characters in a string. This is a subset of a larger problem of finding all the permutations of elements in a set. One of the most common algorithms to tackle this problem is Heap’s Algorithm. Heap’s is a relatively young algorithm being first proposed by B. R. Heap in 1963.
I’ve laid out the algorithm's pseudocode with explanation below:
IF n == 1 THEN
FOR i := 0…
Finding Prime Numbers from 1 to n
Sieve of Eratosthenes is one of the most ancient algorithms dating from the 2nd century in ancient Greece. Old does not mean obsolete, however. This algorithm is still relevant today, being a space and time-efficient way to find prime numbers. The idea is straightforward and depicted in the grid below.
Say we have an integer input. It could be any natural number, big or small. Our task is to find all the prime numbers from one to this integer. Let’s take a simple example: 23. First, let’s write out all the intermediate integers.
Another trick in software is to avoid rewriting the software by using a piece that’s already been written, so called component approach which the latest term for this in the most advanced form is what’s called Object-Oriented Programming.
Object-oriented programming has been around since at least the 1960s. The first generally accepted object-oriented programming language was Simula, developed in 1967. Since then, the “object-oriented paradigm” has taken over computer science. Nearly every modern programming language is considered object-oriented or heavily influenced by object-oriented principles. …
cryptocurrencies and how they work
I have been fascinated by cryptocurrencies for a while now. It is an understatement to say they have a mixed reputation. Opinions about them range from unending praise to scorn. Some say they will usher in a new age overturning old economics. Others believe they are a Ponzi scheme only used by drug dealers that will destabilize national economies. I look at them as a fascinating space that could potentially change how people interact and relate with each other in the marketplace.
Whatever you think about them, I’d like to give you a brief introduction…
Two underrated data types
A set is a collection of values of any data type. Unlike arrays and objects, each of the values in a set must be unique. Also, unlike arrays and objects, the values of a set are not accessible directly by key. The set’s values are…
searching from root to leaves
The depth-first search algorithm is a handy algorithm highly applicable to a wide variety of computer science problems. This algorithm involves searching through a sequence of nodes in a tree or data structure. However, unlike a breadth-first search, a depth-first search follows a different pattern. In the depth-first search pattern, the algorithm goes ‘deep’ instead of ‘wide.’ In other words, it searches for a path from the root node to the lowest leaf before moving onto the next possible path.
The animation above shows the flow of depth-first search. The algorithm finds all paths from…
Amongst the most common and useful algorithms is the breadth-first search algorithm. This algorithm involves traversing or searching nodes or data points in a tree or graph data structure. These algorithms often arise in technical interviews and are a stepping stone to understanding more advanced problems. What’s excellent about breadth-first search is its applicability to a variety of issues not involving trees or graphs such as sorting an array, finding a maximum sum of number combinations, and finding the shortest distance between two nodes in a graph.
Bread-first search is an algorithm that governs the movement from one node to…
A full-stack software developer who likes writing about tech.