Algorithms and Data Structures

This repository contains basic data structures and algorithms implementations as prepared for a Google Interview. This repo should help anyone interviewing at Google or who would like to look at basic algorithm implementations. Amongst some of the most fun in this process was creating the adjacency list graph. In it I was able to apply algorithms such as topological sort, Dijikstra's and Bellman Ford single source shortest path, Floyd Warshall all-pairs shortest path, and Primm's minimum spanning tree. Enjoy the use of this code. The below graph implementations support output in GraphViz dot format so that you can view the graphs in a visual tool. This works with both directed and undirected graphs. The below randomly generated weighted directed graph was generated by putting an alphabatized wordlist into a hash table and then randomly pulling a word out and inserting into each node.

This repo has both a C# and Java version of the code. The Java code was recently ported to Java. This includes all except the Adjacency and Matrix graphs. The structure of this page looks good so I will maintain the below descriptions on each subpage.

Project Directories

• Core Algorithms - This is the core algorithms and data structures code directory. This contains the most up to date and complete view of the core code.
• Firstpass Algorithms - This contains the original source code that was created.
• Secondpass Algorithms - This contains a second pass at some of the algorithms and data structures.

Core Algorithm Descriptions

Array and String Implementations (core/arraystrings)

• ArrayStrings - This object contains methods to perform binary search and to search for weather or not a string is an anagram or a permutation of another string.
• Combinatorics - This object contains the core code to handle calculating combinations and permutations of strings.
• Sorting - The sorting file contains all of the standard 0(nlogn) and 0(n^2) sorting algorithms (insertion, selection, buttble, radix, heapsort, quicksort, as well as merging and partitioning functions.

Linked List Implementations (core/lists)

• CircularDLinkedList - This is a circular doubly linked list that contains 0(1) and 0(n) operations for insertion and deletion.
• CircularSLinkedList - This is a circular sinly linked list that contains 0(1) and 0(n) operations for insertion and deletion.
• DoublyLinkedList - This is a doubly linked list that contains 0(1) and 0(n) operations for insertion and deletion.
• DoublyTailLinkedList - This is a doubly linked list which tracks a tail pointer and contains 0(1) and 0(n) operations for insertion and deletion.
• SinglyLinkedList - This is a singly linked list that contains 0(1) and 0(n) operations for insertion and deletion.
• SinglyTailLinkedList - This is a singly linked list which tracks a tail pointer and contains 0(1) and 0(n) operations for insertion and deletion.

Miscelaneous Impementations (core/misc)

• AdjacencyGraph - This contains an adjacency graph implementation that supports directed, undirected, and weighted graphs that can store arbitrary data at each node. Contains Dijkstra's shortest path algorithm, Primm's algorithm for minimum spanning trees, cycle detection, preorder, postorder, and reverse postorder depth first search, and topological sort amongst other functionality.
• AdjacencyMatrixGraph - This contains an adjacency matrix graph implementation that supports directed, undirected, and weighted graphs that can store arbitrary data at each node. In this file, breadth first search, Bellman ford, and Floyd Warshall (for negative weight paths) shortest path algorithms ,Primm's minimum spanning tree algorithms.
• ArrayQueue - Contains a queue implemented as an array containing basic enqueue, dequeue, and peek operations.
• ArrayStack - Contains an queue implemented as an array supporting basic push, pop, and peek operations.
• BinaryMinHeap - Contains a binary min heap priority queue implementation built on top of an array with 1 based indexing (for ease of swim and sink of 2*n and n/2) that supports basics insertion/removal operations.
• BinarySearchTree - Contains a binary search tree implementation which includes methods for creating a minimal Binary Search Tree, checking levels, and most notably breadth first search and iterative and recursive depth first search functionality (which uses either the call stack or an actual stack to trace position in the depth first search traversal).
• Bits - Contains core bit manipulation operations such as clearing, setting, flipping, retrieving, and clearing bit ranges.
• GenericTree - Contains a generic tree representation that could contain any number of children per node. This could be used to implement something such as a B+Tree.
• LinkedHash - Contains a linked hash table that implements basic getting and setting functionality in average case 0(1) when there are no collisions.
• LinkedHashEntry - Contains an entry in the above LinkedHash table which contains a genric key and value using Java generics.
• ListNode - Contains a list node that implements an Iterator.
• ListQueue - Contains a queue implemented via a list node.
• ListStack - Contains a stack implemented via a list node.
• QueueStack - Contains an interesting implementation of a stack implemented with two queues supporting enqueue/dequeue functionality.
• StackQueue - Contains an interesting implementation of a queue implemented with two stacks containing push/pop functionality.