Skip to content

Data Structure & Algorithms

Jump to bottom
Sandesh Kota edited this page Jun 27, 2019 · 36 revisions

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)

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

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] ];
  }
}

Collection Concurrency

  • Multi-Threaded
  • Caller Synchronization
  • Monitor synchronization
  • ReaderWriterLockSlim
  • Concurrent Collections
    • ConcurrenctDictionary<TKey, TValue>
    • ConcurrentBag
    • ConcurrentQueue // Lock free - No Dequeue() - instead TryDequeue()
    • ConcurrentStack // Lock free

Sources

Clone this wiki locally