Data Structure & Algorithms

Data Structure

• Node (value | next-pointer)
• Node Chains (two/more nodes connecting with help of next-pointers)

public class Node
{
  public int Value { get; set; }
  public Node Next { get; set; }
}

Node first = new Node { Value = 3 };
Node middle = new Node { Value = 5 };
first.Next = middle;
Node last = new Node { Value = 9 };
middle.Next = last;

Linked List

• Single chain of nodes
• Head Pointer
• Tail Pointer
• Operations: Add, Remove, Find, Enumerate
  • If there is only one item in the list, then both head and tail pointers will point to single node
  • Adding: Will update the head/tail pointer and the corresponding next-pointer (in case of array there will be performance impacts ex: adding a new value at the beginning will have to shift all the other values by one step)
• Doubly Linked List: .Net's linked list is Doubly Linked List

Stack (LIFO)

• Push & Pop
• Linked List Implementation of stack
  • Pros: No hard size limit. No bounds check (as in case of array)
  • Cons: memory allocation push, per node memory overhead, performance issues
• Array Implementation of stack
• Always best to use the Stack that comes in the framework ( C# Stack - stores in array)
• Stack Usages:
  • Undo operation
  • compiler's syntax check for matching braces is implemented by using stack
  • During Function Calls because it Follows A LIFO Structure
  • Back/Forward stacks on browsers

Queue (FIFO)

• Enqueue & Dequeue
• Linked List Implementation of Queue
• Array Implementation of Queue
• Priority Queue
  • Same as Queue but an item can be added anywhere based on the priority of the item that is being added

Binary Tree

• A tree structure with only two children
• Finding an item in Binary Tree

Find(Node current, Data value){
  if(current == null) return null;
  if(current.Value == value) return current;
  if(value < current.Value) return find(current.Left, value);
  return Find(current.Right, value);
}
// starts with Find(RootNode, value)

• Traversal
  • PreOrder: Process Node -> Visit Left Node -> Visit Right Node (recurring)
  • InOrder: Visit Left Node -> Process Node -> Visit Right Node (recurring) - processed based on sorted order
  • PostOrder: Visit Left -> Visit Right -> Process Node (recurring)
  • Tree traversals (post/pre) - compliers use trees for traversal - consider tree as dependency graph and child should be processed before parent (which is not the case in In-Order)
• Binary Tree Implemenration
• Binary Tree in .Net has default Enumerator as In-Order

Hash Table

• Key/Value, key is hashed
• Performance: hashing should be efficient since it is involved in all operations get/save.
• Types if Hashing Ex: Additive, Folding, CRC32, MD5, SHA-2 etc...
• Linked List Implementation

Algorithms

Sorting

• Bubble Sort
  • Compare each array item to it's right neighbor
  • If the right neighbor is smaller then swap right and left
  • Repeat for the remaining array items
  • Perform subsequent passes until no swaps are performed
  • Results
  • for sorting "n" values n*n operations are required (worst and Average case) | "n" operations (best case)
  • Space (n) is required. No additional space since it is done on the array(data) provided
• Insertion Sort
  • Sorts each item in the array as they are encountered
  • Current item works from left to right. Everything left of the item is known to be sorted. Right is unsorted
  • The current item is "inserted" into place within the sorted section
  • Results
  • for sorting "n" values "n*n" (Big-O n square) operations are required (worst and Average case) | "n" operations (best case)
  • Space (n) is required. No additional space since it is done on the array(data) provided
• Selection Sort
• Enumerate the array from the first unsorted item to the end (for each run)
• Identify the smallest item
• Swap the smallest item with the first unsorted item
• (foreach) find smallest item in the complete array put it in the first place - repeat (keep filling second, third place)
• Results - for sorting "n" values "n*n" (Big-O n square) operations are required (worst, average & best case)
  • Typically better than Bubble sort but worse than insertion sort - Space (n) is required. No additional space since it is done on the array(data) provided
• Merge Sort
  • Array is recursively split in half
  • When the array is in groups of 1, it is reconstructed in sort order
  • Each reconstructed array is merged with the other half

    [3,8,2,1,5,4,6,7] 
    => [3,8,2,1] & [5,4,6,7] 
    => [3,8] & [2,1] & [5,4] & [6,7] 
    => [3] & [8] & [2] & [1] & [5] & [4] & [6] & [7]
    => [3,8] & [1,2] & [4,5] & [6,7] 
    => [1,2,3,8] & [4,5,6,7] 
    => [1,2,3,4,5,6,7,8]
  

  • Results
  • for sorting "n" values "n log n" (Big-O n log n) operations are required (worst & average) | "n log n" operations (best case)
    • Data splitting means that the algorithm can be made parallel
  • Space (n) is required. No additional space since it is done on the array(data) provided
    • Even though the data is split the no of items in the memory is same
• Quick Sort
  • Divide and Conquer algorithm, Pick a pivot value & partition the array
  • Put all values before the pivot to the left and above to the right
  • Perform pivot and partition algorithm on the left and right partitions
  • Repeat until sorted

  [3,4,2,1,5,8,6,7]
  => [3,4,2,1,5,8,6,7] (pivot point is 5)
  => [1,2,3,4,5,8,6,7] (pivot point is 2)
  => [1,2,3,4,5,8,6,7] (pivot point is 1)
  => [1,2,3,4,5,8,6,7] (pivot point is 3)
  => [1,2,3,4,5,6,7,8] (pivot point is 7)
  

• Results
  • for sorting "n" values "n*n" (Big-O n square) operations are required worst) | "n log n" operations (average & best case)
  • Space (n) is required. As a recursive algorithm the array space as well as the stack space must be considered

Set Collection & Algorithms

• A collection of any type of comparable object
• Set Implementation using List

AVL Tree

• Self-balancing Binary Search Tree (works based on the heights)

String Searching

• Naive Search Algorithm

var toSearch = "He Dropped his Phone";
var toFind = "Drop";
for (var startIndex = 0; startIndex <= (toSearch.Length - toFind.Length); startIndex++)
{
  var matchCount = 0;
  while ( toSearch[startIndex + matchCount] == toFind[matchCount])
  {
    matchCount++;
    if(toFind.Length == matchcount)
      return true; // match found
  }
}

• Boyer-Moore Search
• Boyer-Moore-Horspool Search
  • Create a Bad match table

public BadMatchTable(string pattern)
{
  _defaultvalue = pattern.Length;
  _distances = new Dictionary<int, int>();
  for (int i = 0; i < pattern.Length - 1; i++)
  {
    _distances[pattern[i]] = pattern.Length - i - 1;
  }
}
// ex pattern = "TRUTH"
// Table created
/*  
  Index    Value
    ?        5
    T        1
    R        3
    U        2
*/

• Search Algorithm

BadMatchTable badMatchTable = new BadMatchTable(pattern);


int currentStartIndex = 0;
while ( currentStartIndex <= toSearch.Length - pattern.Length)
{
  int charsLeftToMatch = pattern.Length - 1;
  
  while( charsLeftToMatch >= 0 &&
        Compare( pattern[charsLeftToMatch], toSearch[currentStartIndex + charsLeftToMatch]  ) == 0 )
  {
    charsLeftToMatch--;
  }

  if (charsLeftToMatch < 0)
  {
    yield return new StringSearchMatch(currentStartIndex, pattern.Length);
    currentStartIndex += pattern.Length;
  } else {
    currentStartIndex += badMatchTable[ toSearch[ currentStartIndex + pattern.Length - 1] ];
  }
}

Sources

• My Own Github