Array & String

Hashtables

  • Compute key’s hash code -> Int/long
    • keys can share the same hash
  • Find index of the array
    • hash % array_length
  • Use linkedlist to store key and value at this index

ArrayList & Resizable Arrays

  • Resizing ArrayList takes O(1)
    • Doubling takes O(n) but very rare so its amortized insertion time is still O(1)

StringBuilder

  • Creates a resizable array and copies strings over only when necessary

Stack

Type

  • LIFO (last in first out)\

Functions

  • pop()
    • Remove the top item from the stack
  • push(item)
    • Add an item to the top of the stack
  • peek()/top()
    • Return the top of a stack
  • isEmpty()
    • Return true iff the stack is empty

Runtimes

  • O(1) add/remove
  • O(n) access

Implementation


class Stack {
  constructor(items) {
    this.items = items == null ? [] : items;
  }

  push(data) {
    this.items[this.items.length] = data;
  }

  pop() {
    if (this.items.length === 0) return undefined;

    var removed = this.items[this.items.length - 1];
    // Cannot do
    // delete this.items[this.items.length - 1]
    // Because that will leave the index as undefined instead of removing the index altogether
    this.items.splice(this.items.length - 1, this.items.length);
    return removed;
  }

  peek() {
    if (this.items.length === 0) return undefined;
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

}

Usage

  • Good for certain recursive algorithms
  • Can be used to implement a recursive algorithm iteratively

 

Queue

Type

  • FIFO (first in first out)

Functions

  • add(item)
    • Add an item to the end of the list
  • remove()
    • Remove the first item in the list
  • peek()/top()
    • Return the top of the stack
  • isEmpty()
    • Return true iff the stack is empty

Implementation


class Queue {
  constructor(items) {
    this.items = items == null ? [] : items;
  }

  enqueue(data) {
    return this.items.push(data);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length == 0;
  }
}

Usage

  • BFS
  • Implementing cache

 

Linked Lists

  • Sequence of nodes, each points to the next and previous nodes in the list
  • Can add or remove from the beginnning of the list in constant time

Deleting a node

  • Single
    • Set prev.next = n.prev
  • Double
    • Set prev.next = n.prev
    • Set n.next.prev = n.prev

Implementation


class LinkedList {
  constructor(head) {
    this.head = head;
  }

  push(data) {
    var node = new LinkedListNode(data, null);
    var current;
    if (!this.head) {
      this.head = node;
    } else {
      var current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
  }

  remove(data) {
    var current = this.head;

    // Remove the only node in the LinkedList
    if (current.data == data) {
      this.head = current.next;
    } else {
      var prev = current;

      while (current.next) {
        // Remove the node in between the nodes
        if (current.data == data) {
          prev.next = current.next;
          break;
        }
        prev = current;
        current = current.next;
      }

      // Remove last no9de
      if (current.data == data) {
        prev.next == null;
      }
    }
  }
}

class LinkedListNode {
  constructor(data, next) {
    this.data = data;
    this.next = next;
  }

  toString() {
    var node = this;
    var output = String(node.data);
    while (node.next) {
      output = output + " -> " + String(node.next.data);
      node = node.next;
    }

    return output;
  }

}

The “Runner” Technique

  • Have 2 pointers for a linked list that has an even number of length
  • Iterate 1 pointer one by one and iterate the other every other
  • By the time the faster pointer reaches the end, the first pointer will be at the midpoint
  • Iterate backwards and connect these nodes alternatively

Recursive Strategy

  • Takes at least O(n) space
  • All recursive methods can be done iteratively

Trees

Fundamentals

  • Each tree has a root node
  • Has zero or more child nodes
  • Each child node has zero or more child nodes
  • Node is called leaf node if no children

class Node {
  public String name;
  public Node[] children;
}

class Tree {
  public Node root;
}

Trees vs Binary Trees

Tree Binary Tree
No limit on # of children nodes Up to 2 children

Binary Tree vs Binary Search Tree

  • Binary Search Tree follows the rule:
    • all left descendents <= n < all right descendents

Balanced vs Unbalanced

  • Balanced tree implies
    • O(log n) insert
    • O(log n) find
  • Balance tree types
    • red-black tree
    • AVL tree

Complete Binary Tree

  • Every level of the tree is fully filled except for the very last one on the right
  • Trees are filled from left to right

Full Binary Tree

  • Binary tree in which every node has zero or two children
  • No nodes have only one child

Perfect Binary Tree

  • Filled and complete
  • All leaf nodes will be at the same level, and has max number of nodes
  • have 2^k – 1 node (where k is the number of levels)

Binary Tree Traversal

In-Order Traversal

  • visit the left branch, then the current node, then right branch

void inOrderTraversal(TreeNode node) {
  if (node != null) {
    inOrderTraversa(node.left);
    visit(node);
    inOrderTraversal(node.right);
  }
}

Pre-Order Traversal

  • visit the current node before child nodes

void preOrderTraversal(TreeNode node) {
  if (node != null) {
    visit(node);
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

Post-Order Traversal

  • visit curren node after its child nodes

void postOrderTraversal(TreeNode node) {
  if (node != null) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    visit(node);
  }
}

Binary Heaps (Min-Heaps and Max-Heaps)

  • Complete binary tree where each node is smaller than its children
  • The root is the smallest node
  • functions
    • insert()
      • Start by inserting the element at the bottom at the rightmost spot
      • Then swap the new element with its parent until it’s bigger than the parent node (bubble up)
      • O(log n)
    • extract_min()
      • Min is always the root of the tree
      • Swap the min element with the last node in the heap (bottommost rightmost element)
      • Then swap the node with the smallest between the left or right node
      • Continue until the children nodes are bigger than the node

Tries (Prefix Trees)

  • Prefix tree
  • Variant of an n-ary tree which characters are stored at each node, each path down the tree may represent a word
  • The * nodes (null nodes) indicates complete words.
  • Can have 0 to ALPHABET_SIZE + 1 children
  • Can tell if a string is a prefix of any words very quickly
    • O(K) time – K = length of the string

Graphs

  • Tree is a type of graph
  • tree is a connected graph without cycles

What are graphs

  • Collection of nodes with edges between (some of) them
  • Can be directed or undirected, and can have directed or undirected edges
  • may consist of multiple isolated subgraphs
  • Called connected graph if there’s a path between every pair of vertices
  • Can have cycles
  • Acyclic graph = graph with no cycles

Adjacency List

  • Most common way to rep graphs
  • Every vertex stores a list of adjacent vertices
  • List is stored twice in an undirected graph

class Graph {
  public Node[] nodes;
}

class Node {
  public String name;
  public Node[] children;
}

Adjacency Matrices

  • NxN boolean matric (N = number of nodes)]
  • True at matrix[i][j] indicates an edge from node i to node j
  • Adjacency matrix is symmetric in an undirected graph

Depth-first search (DFS)

  • Go deep before wide
  • Preferred when we want to visit every node in the graph
  • Recursive
  1. Start at the root or an arbitrary node
  2. Expore each branch completely before moving on to the next branch

void search(Node root) {
  if (root == null) return;
  visit(root);
  root.visited = true;
  foreach (Node n in root.adjacent) {
    if (n.visited == false) {
      search(n);
    }
  }
}
  • Go wide before deep
  • Preferred when finding shortest path
  • Uses a Queue
  1. Start at the root or an arbitrary node
  2. Explore each neighbor before going to another node

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true;
  queue.enqueue(root);
  
  while (!queue.isEmpty()) {
    Node r = queue.dequeue();
    visit(r);
    foreach(Node n in r.adjacent) {
      n.marked = true;
      queue.enqueue(n);
    }
  }
}
  • Used to find the shortest path between a source and destination node
  • Runs two simultaneous BFS
  • When their searches collide, the path is found
  • Using 1 BFS search
    • O(k^d)
      • k = number of nodes
      • d = number of times
  • Using 2 BFS search (bidirectional)
    • O(k^(d/2))

Leave a Reply

Your email address will not be published. Required fields are marked *