Discuss what Dijkstra’s Algorithm is and how to implement it

Use case

Dijkstra’s Algorithm is used to calculate the shortest path from a starting node u, to all other vertices in the graph. Dijkstra’s does not work on graphs with negative edge weights.

How It Works

Dijkstra’s works by creating a shortest-path tree, beginning with the source that is passed in as the root. Two sets are then created. One to keep track of the vertices that have been included in the shortest path tree, and one that keeps track of the vertices that have not been included in the shortest path tree. …


Explain Prim’s and Kruskal’s minimum spanning tree algorithms and give similarities and differences.

Prim’s Algorithm

Prim’s works by starting at any vertex, and finding the minimum edge weight between a tree and a non-tree vertex. It will then add that minimum edge and vertex to the minimum spanning tree.

Very simple pseudocode for Prim’s Algorithm

Kruskal’s Algorithm

Kruskal’s first sorts all the edges of a graph by weight, and inserts them into a priority queue. It then loops through the priority queue, getting the edge with the lowest weight, and checks if it will create a cycle in the minimum spanning tree. …


Explain what topological sorting is and how it is implemented.

What is topological sorting?

Topological sorting is used only on Directed Acyclic Graphs(DAG) and is used to produce a linear ordering of vertices such that for all edges (u, v), u always appears before v. The result is not always unique.

Quick Solution

  1. The first step is to identify a node that has an in-degree of 0, there can be multiple. If there are none in the graph, then the graph has cycles.
  2. After identifying a node with an in-degree of 0, the node, and all of its outgoing edges should be removed.
  3. Repeat steps 1…

Given two strings, determine whether or not they are anagrams of each other.

Example of an anagram

Methods

There are a variety of ways to determine anagrams. Some examples are using sorting and calculating the sum of the characters. In this example, we will be doing the first. This method works by sorting both strings, and then iterating through both strings and checking if the indices of both strings are the same.

Simple Solution

The premise of this solution is to first sort both arrays. Then loop through the arrays and checking each index to ensure they are the exact same character. If an index is different…


Provide an algorithm that will detect a cycle in a given Linked List

Example of a cycle within a linked list

Simple Solution

There are a variety of cycle-finding algorithms out there, but the one being discussed will be Floyd’s Cycle-Finding Algorithm. This algorithm traverses the linked list using two pointers, one called the fast pointer that increments by two nodes and another pointer called the slow pointer that increments by one node. If these nodes meet at the same node, there is a loop, and if not, the linked list does not contain a cycle.

In-Depth Solution

  • Initialize the slow and fast pointer to the head of the linked list.
  • Iterate…

Given an array of unique integers, find the longest sub-array that contains integers that can be arranged in order.

Example:

Input : arr[ ] = {1,3,2}

Output: The longest contiguous sub-array is 3.

Input: arr[ ] = {42,41,44,43,47,48}

Output: The longest contiguous sub-array is 4.

Simple Solution:

  • The first step is to acknowledge that the array is unique, therefore you can tell if a sub-array has contiguous elements if the difference between the max and min element in the sub-array is equal to the difference between first and last indices.
  • Then you should iterate through each index of the array, and at each…

The Knuth-Morris-Pratt(KMP) Algorithm, is a pattern searching algorithm that improves on its predecessor, the Naive Pattern Searching Algorithm. Before delving into the KMP Algorithm, let us discuss the Naive Pattern Searching Algorithm to help understand how the KMP Algorithm differs, and what makes it more efficient.

The Predecessor

The Naive Algorithm is, thanks to its’ telling name, almost exactly what you think it is. When first thinking about what one would do to find a pattern in a group of text, or at least what I first thought of, is to begin with the first character of the main text, check the…

Will Strickland

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store