# 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

- insert()

# 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

- Start at the root or an arbitrary node
- 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);
}
}
}
```

## Breadth-first search

- Go wide before deep
- Preferred when finding shortest path
- Uses a Queue

- Start at the root or an arbitrary node
- 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);
}
}
}
```

## Bidirectional Search

- 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

- O(k^d)
- Using 2 BFS search (bidirectional)
- O(k^(d/2))