Data Structure - My Coding Interview Journery

Static Arrays

The biggest limitation of static arrays is their size.
In JS or Python you usually do not have this issue since by default their array is not static array. Instead they use dynamic arrays!
You cannot de-allocate a static value meaning shrink its size

Dynamic Arrays

When you initialize it, there might be a default size for it! For example the default size of ArrayList is 10!
When using Dynamic Arrays, when you run out of memory you need to double the size of the current array. The amortized time complexity is proved to be $O (1)$ .
Basically time complexity of dynamic array is identical to static array
- Note that although the complexity is the same, static arrays are more efficient.

Linked-Lists

Usually we have a tail and head pointer.
- Adding a node to the end is $O (1)$
- Assuming you have the pointer to the previous of a target node, removing it is $O (1)$ and this is one the benefit of Liked-List versus an Array.
However, practically speaking, removing a node is $O (n)$ .
Traverse a list:

  ListNode cur = ListNode1;
  while (cur != null) {
    cur = cur.Next;
  }

Doubly-Linked-List

You will have head and tail.
Add/Remove to/from the end of the list is $O (1)$

Note: You can implement Stack using Arrays as well as Linked-List. However, it is more common to use arrays because as we mentioned before using a dynamic array you can not only easily push and pop from the end of the array, but also you'd have $O (1)$ access to each element as well.

Queue

We need $O (1)$ for insertion into the add of the queue and delete from the beginning of it.
We cannot accomplish this using Arrays since removing from the beginning of the array is $O (n)$
Linked-List is a good candidate:
- There is a head and there is a tail.
You can implement Queues with Arrays. But, it will be a lot more complicated.

Recursion

The best way to represent recursion is decision tree!
For Fibonacci example: $F (n) = F (n - 1) + F (n - 2)$ and $F (0) = 0$ and $F (1) = 1$

int factorial(int n) {
  if (n <= 1) {
    return 1;
  }
  return factorial(n-1)*n;
}

This solution is $O (n)$ time complexity and also $O (n)$ memory complexity.

Sorts

Insertion Sort

void InsertionSort(int[] nums) {
  for (int i=1; i < nums.Length; i++) {
    j = i;
    while (j>0 && nums[j] < nums[j-1]) {
      int tmp = nums[j];
      nums[j] = nums[j-1];
      nums[j-1] = tmp;
      j--;
    }
  }
}

Best case is when the array is already sorted: $O (n)$
Worst case is then the array is sorted in reverse order: $O (n^{2})$
The algorithm is stable
The algorithm is in-place

Merge Sort

We divide into maximum $lo g_{2} n$ stages
For each stage we ned $O (n)$ to merge all sub-arrays
$O (n lo g)$
We can make it stable:
- When merging sub-arrays, if the left sub-array's element is less or equal to to the right sub-array's element, it takes priority to be moved to the main array.
The algorithm is NOT in-place.

Quick Sort

First we partition the array taking the last element as the pivot
- Use two pointers
Quick Sort both partitions

public int[] QuickSorting(int[] arr, int s, int e)
{
  if (e - s + 1 <= 1)
  {
    return arr;
  }

  int pivot = arr[e];
  int left = s;       // pointer for left side

  // Partition: elements smaller than pivot on left side
  for (int i = s; i < e; i++)
  {
    if (arr[i] < pivot)
    {
      int tmp = arr[left];
      arr[left] = arr[i];
      arr[i] = tmp;
      left++;
    }
  }

  // Move pivot in-between left & right sides
  arr[e] = arr[left];
  arr[left] = pivot;

  // Quick sort left side
  QuickSorting(arr, s, left - 1);

  // Quick sort right side
  QuickSorting(arr, left + 1, e);

  return arr;
}

Worst case: $O (n^{2})$ when the array was already sorted!
It is in-place and does not require any extra memory!
It is not stable! It might be modified to make it stable!
On average it is $O (n lo g_{2} n)$

Bucket Sorat

$O (n)$
Required memory is $O ($ range of possible values $)$
It is not stable
- You can make it stable!

Trees

Binary Search Tree (BST)

They generally do not contain duplicate values
If the tree is balanced, search is $O (lo g n)$
- If it is not balanced, worst case scenario is $O (n)$
- Technically it will be $O (h)$ where h represents the height of the tree

bool Search(RootNode root, int target) {
  if (root == null) {
    return false;
  }
  if (target > root.val)
    return Search(root.right, target);
  if (target < root.val)
    return Search(root.left, target);
  return true;
}

IMPORTANT: Why do we need this considering you can use a sorted array?

Because with a sorted array, operations like insert/remove values to the array will be $O (n)$ .
For BST, insert/remove is $O (h)$ as well.

Insert into BST

Node insert(Node root, int value) {
  if (root == null) {
    return new Node(value);
  }

  if (value > root.val) {
    root.right = insert(root.right, val);
  } else if (value < root.val) {
    root.left = insert(root.left, val);
  }
  return root;
}

This way of inserting data into a BST will end up with unbalanced tree. There are data structures like AVL Trees that resolve this issue.

Remove from BST

// Return the minimum value node of the BST.
public TreeNode MinValueNode(TreeNode root) {
  TreeNode curr = root;
  while (curr != null && curr.Left != null) {
    curr = curr.Left;
  }
  return curr;
}

// Remove a node and return the root of the BST.
public TreeNode Remove(TreeNode root, int val) {
  if (root == null) {
    return null;
  }
  if (val > root.Value) {
    root.Right = Remove(root.Right, val);
  } else if (val < root.Value) {
    root.Left = Remove(root.Left, val);
  } else {
    if (root.Left == null) {
      return root.Right;
    } else if (root.Right == null) {
      return root.Left;
    } else {
      TreeNode minNode = MinValueNode(root.Right);
      root.Value = minNode.Value; 
      root.Right = Remove(root.Right, minNode.Value);
    }
  }
  return root;
}

BST Traversal

DFS

In-Order

void inorder(Node root) {
  if (root == null)
    return;
  inorder(root.left);
  print(root);
  inorder(root.right); 
}

Note: If you were given some random values, you could sort them using BST. Now you have to insert all the values into BST which for a balanced tree will be $O (n lo g n)$ and then traversing it will be $O (n)$ . The sum of the two will be $O (n lo g n)$ .

Note: All preorder, postorder and inorder traversals are Depth First Search examples.

Pre-Order

void preorder(Node root) {
  if (root == null) {
    return;
  }
  print(root.val);
  preorder(root.left);
  preorder(root.right);
}

Post-Order

void postorder(Node root) {
  if (root == null) {
    return;
  }
  postorder(root.left);
  postorder(root.right);
  print(root.val);
}

BFS (Breadth-First Search)

  void BFS(Node node)
  {
    Queue<Node> queue = new();

    int level = 0;
    while (queue.Count > 0)
    {
      Console.WriteLine($"Level = {level}");
      for (int i = 0; i < queue.Count; i++)
      {
        Node cur = queue.Dequeue();
        Console.WriteLine(cur.val);
        if (cur.left != null)
        {
          queue.Enqueue(cur.left);
        }
        if (cur.right != null)
        {
          queue.Enqueue(cur.right);
        }
      }
      level++;
    }
  }

Sets and Maps

One implementation of Sets and Maps could be a BST!
If you use BST (since BST has unique values) to implement a set, insert and remove is $O (lo g n)$ versus $O (1)$ if you use arrays.

Backtracking

Question: Determine if a path exists from the root of the tree to a leaf node. It may not contain any zeroes.

bool FindPath(Node root) {
  if (root != null || root.val == 0) {
    return false;
  }
  if (root.left != null && root.right != null) {
    return true;
  }
  if (FindPath(root.left), val) {
    return true;
  }
  if (FindPath(root.left), val) {
    return true;
  }
  return false;
}

Now we will make it a bit more complicated. At the end if there is path, we need to print the path.

bool FindPath(Node root, Stack<int> path) {
  if (root != null || root.val == 0) {
    return false;
  }
  path.Push(root.val);
  if (root.left != null && root.right != null) {
    return true;
  }
  if (FindPath(root.left), val) {
    return true;
  }
  if (FindPath(root.left), val) {
    return true;
  }
  path.Pop();
  return false;
}

Heap/Priority Queue

The purpose of using this is to find the minimum value in $O (1)$ .
Duplicate values can exist in the structure
Usually min Heap is used
The functionality is priority queue however under the hood it uses the heap data structure.
It has two properties:
- It is a complete binary tree: every single level is gonna be completely full except the last level
IMPORTANT: It uses array under the hood.
- Queue to LinkedList is like PriorityQueue to Heap (particularly binary heap)
Index 0 of array is not used

class Heap {
  private List<int> _heap;
  public Heap() {
    heap = new (){0};
  }
}

Insert into heap

push(val) {
  _heap.Add(val);
  int i = _heap.Length - 1;

  // Percolate up
  while _heap[i] < _heap[i/2] {
    tmp = _heap[i];
    _heap[i] = heap[i/2];
    heap[i/2] = tmp;
    i /= 2;
  }
}

The operation is $O (lo g n)$

Removing from a heap

We swap the first value with the last value. Then starting from root we will go down and swap with a child until both child are smaller than it.

int pop() {
  if (heap.Count == 1)
  {
    // return null;
  }
  if (heap.Count == 2)
  {
    int res = heap[heap.Count - 1];
    heap.Remove(heap.Count - 1);
    return res; // equivalent to heap.remove(1)
  }

  int res = heap[1];
  // Move last value to root
  heap[1] = heap[heap.Count - 1];
  heap.Remove(heap.Count - 1);
  int i = 1;
  // Percolate down
  while (2 * i < heap.Count)
  {
    if (2 * i + 1 < heap.Count &&
    heap[2 * i + 1] < heap[2 * i] &&
    heap[i] > heap[2 * i + 1])
    {
      // Swap right child
      int tmp = heap[i];
      heap[i] = heap[2 * i + 1];
      heap[2 * i + 1] = tmp;
      i = 2 * i + 1;
    }
    else if (heap[i] > heap[2 * i])
    {
      // Swap left child
      int tmp = heap[i];
      heap[i] = heap[2 * i];
      heap[2 * i] = tmp;
      i = 2 * i;
    }
    else
    {
      break;
    }
  }
  return res;
}

This operation is also $O (lo g n)$

Advantages of Heap over BST:

Finding min/max is $O (1)$ vs $O (lo g n)$
You can build a heap (by an array) with $O (lo g n)$ (proof will be given below)

Heapify

You will be given an array
Push the first value into the end of the array
Now from the end we will make sure every true is a heap.
- Therefore half of the tree (leaves) will be already a heap
- The first index we really need to heapify is the index $(h e a p . l e n g t h - 1) /2$
Now you need to percolate down now and repeat it for all the nodes before.
$n /4 \sum_{i = 1}^{h} \frac{k}{2 ^{k - 1}} = O (n)$
You can use heapify and then popping from the queue for $n$ times and sort an array: $O (n lo g n)$

public void Heapify(List<int> arr)
{
  // 0-th position is moved to the end
  arr.Add(arr[0]);

  heap = arr;
  int cur = (heap.Count - 1) / 2;
  while (cur > 0)
  {
    // Percolate Down
    int i = cur;
    while (2 * i < heap.Count)
    {
      if (2 * i + 1 < heap.Count &&
      heap[2 * i + 1] < heap[2 * i] &&
      heap[i] > heap[2 * i + 1])
      {
        // Swap right child
        int tmp = heap[i];
        heap[i] = heap[2 * i + 1];
        heap[2 * i + 1] = tmp;
        i = 2 * i + 1;
      }
      else if (heap[i] > heap[2 * i])
      {
        // Swap left child
        int tmp = heap[i];
        heap[i] = heap[2 * i];
        heap[2 * i] = tmp;
        i = 2 * i;
      }
      else
      {
        break;
      }
    }
    cur--;
  }
  return;
}

Heap is not suitable for search. They are NOT intended for that.

Hash Maps

TreeMap (It is ordered)	HashMap	Operation
$O (lo g n)$	$O (1)$	Insert
$O (lo g n)$	$O (1)$	Remove
$O (lo g n)$	$O (1)$	Search
$O (n)$	$O (n lo g n)$	Inorder

Actually worst case time complexity of operations Insert, Remove and Search is not $O (1)$ but $O (n)$ .
Hash map are not sorted usually!
Hashmap under the hood is an array!
Think about:
- Hashing (something like using prime numbers)
- Collision: it will happen regardless of the hashing algorithm
- Rehashing: when the size of the hashmap reaches half of the capacity
  - we need to move every element based on the rehashing
- Readdressing


public class Pair
{
  public string Key { get; set; }
  public string Val { get; set; }

  public Pair(string key, string val)
  {
    this.Key = key;
    this.Val = val;
  }
}

public class HashMap
{
  int Size { get; set; }
  int Capacity { get; set; }
  Pair[] Map { get; set; }

  public HashMap()
  {
    Size = 0;
    Capacity = 2;
    Map = new Pair[2];
  }

  public int Hash(string key)
  {
    int index = 0;
    for (int i = 0; i < key.Length; i++)
    {
      index += (int)key[i];
    }
    return index % this.Capacity;
  }

  public string Get(string key)
  {
    int index = this.Hash(key);
    while (this.Map[index] != null)
    {
      if (this.Map[index].Key == key)
      {
        return this.Map[index].Val;
      }
      index += 1;
      index %= this.Capacity;
    }
    return string.Empty;
  }

  public void Put(string key, string val)
  {
    int index = this.Hash(key);

    while (true)
    {
      if (this.Map[index] == null)
      {
        this.Map[index] = new Pair(key, val);
        this.Size += 1;
        if (this.Size >= this.Capacity / 2)
        {
          this.ReHash();
        }
        return;
      }
      else if (this.Map[index].Key == key)
      {
        this.Map[index].Val = val;
        return;
      }
      index += 1;
      index %= this.Capacity;
    }
  }

  public void Remove(string key)
  {
    if (this.Get(key) == null)
    {
      return;
    }

    int index = this.Hash(key);
    while (true)
    {
      if (this.Map[index].Key == key)
      {
        // Removing an element using open-addressing actually causes a bug,
        // because we may create a hole in the list, and our get() may
        // stop searching early when it reaches this hole.
        this.Map[index] = null;
        this.Size -= 1;
        return;
      }
      index += 1;
      index %= this.Capacity;
    }
  }

  public void ReHash()
  {
    this.Capacity = 2 * this.Capacity;
    Pair[] newMap = new Pair[this.Capacity];

    Pair[] oldMap = this.Map;
    this.Map = newMap;
    this.Size = 0;
    foreach (Pair p in oldMap)
    {
      if (p != null)
      {
        this.Put(p.Key, p.Val);
      }
    }
  }
}

Graphs

Vertex is equivalent to node
Three ways to represent them:
- Matrix
- Adjacency matrix
- Adjacency list
It's most common to use adjacency list for graph representation.
The second one is usually rare since it takes much more space.

Adjacency Matrix: In the matrix below, every 1 represent a path from Node #row to Node #col.

1	1	1	1
0	1	1	0
0	1	0	0
1	1	1	1

Adjacency List: Every node has a list of neighbors:

class GraphNode {
  int val;
  List<GraphNode> neighbors;
}

Matrix DFS

Question: Count the unique paths from the top left to the bottom right. A single path may only move along 0's and can't visit the same cell more than once.

Note: Ask your interviewer there is gonna be at least one path from the source to the destination.

int Dfs(int[][] grid, int r, int c, int[][] visit)
{
  int ROWS = grid.Length, COLS = grid[0].Length;

  if (Math.Min(r, c) < 0 || r == ROWS || c == COLS ||
      visit[r][c] == 1 || grid[r][c] == 1)
  {
    return 0;
  }
  if (r == ROWS - 1 && c == COLS - 1)
  {
    return 1;
  }
  visit[r][c] = 1;

  int count = 0;
  count += Dfs(grid, r + 1, c, visit);
  count += Dfs(grid, r - 1, c, visit);
  count += Dfs(grid, r, c + 1, visit);
  count += Dfs(grid, r, c - 1, visit);

  visit[r][c] = 0;
  return count;
}

Memory Complexity: $O (n . m)$
Time Complexity: $O (4^{n})$

Matrix BFS

Question: Find the length of the shortest path from the top left of the grid to them bottom right.

// Shortest path from top left to bottom right
public int BFS(int[][] grid)
{
  int nr = grid.Length; int nc = grid[0].Length;
  Queue<(int row, int col)> q = new Queue();
  q.Enqueue((0, 0));
  int length = 1;
  while (q.Any())
  {
    int size = q.Count();
    for (int i = 0; i < size; i++)
    {
      (int row, int col) = q.Dequeue();
      if (row < 0 || row >= nr || col < 0 || col >= nc || grid[row][col] == 1)
      {
        continue;
      }
      if (row == nr - 1 && col == nc - 1)
      {
        return length;
      }
      grid[row][col] = 1;

      q.Enqueue((row - 1, col));
      q.Enqueue((row, col + 1));
      q.Enqueue((row + 1, col));
      q.Enqueue((row, col - 1));
    }
    length++;
  }
  return -1; // This should never be called
}

Note: BFS is much more efficient than DFS.
Time Complexity is $O (m . n)$

Adjacency List

Question: Count the unique paths from the top left to the bottom right. A single path may only move along 0's and can't visit the same cell more than once.

// Count paths (backtracking)
public int DFS(String node, String target, Dictionary<String, List<String>> adjList, HashSet<String> visit)
{
  if (visit.Contains(node))
  {
    return 0;
  }
  if (node == target)
  {
    return 1;
  }
  int count = 0;
  visit = new HashSet<String>
  {
      node
  };
  foreach (String neighbor in adjList[node])
  {
    count += DFS(neighbor, target, adjList, visit);
  }
  visit.Remove(node);
  return count;
}

Like every backtracking algorithm this is exponential: $O (N^{V})$

Question: Find the length of the shortest path from the top left of the grid to them bottom right.

// Shortest path from node to target.
public int BFS(String node, String target, Dictionary<String, List<String>> adjList)
{
  int length = 0;
  HashSet<String> visit = new HashSet<String>();
  Queue<String> q = new Queue<string>();
  visit.Add(node);
  q.Enqueue(node);

  while (q.Count != 0)
  {
    int queueLength = q.Count;
    for (int i = 0; i < queueLength; i++)
    {
      String curr = q.Peek();
      q.Dequeue();
      if (curr.Equals(target))
      {
        return length;
      }
      foreach (String neighbor in adjList[curr])
      {
        if (!visit.Contains(neighbor))
        {
          visit.Add(neighbor);
          q.Enqueue(neighbor);
        }
      }
    }
    length++;
  }
  return length;
}

Time Complexity $O (V + E)$
Space Complexity $O (V)$ since we need to add every vertices into the hashmap and to the queue.

Dynamic Programming

1d Dynamic Programming

Previously we solved the Fibonacci series problem. However, it was a bruteForce solution:

// Fibonacci-> Brute Force
public static int BruteForce(int n)
{
  if (n <= 1)
  {
    return n;
  }
  return BruteForce(n - 1) + BruteForce(n - 2);
}

If you add Memoization to this, you can make it much better:

// Memoization
public static int Memoization(int n, int[] cache)
{
  if (n <= 1)
  {
    return n;
  }
  if (cache[n] != 0)
  {
    return cache[n];
  }
  cache[n] = Memoization(n - 1, cache) + Memoization(n - 2, cache);
  return cache[n];
}

Time complexity $O (n)$
This implementation of memorization is TOP-DOWN and also recursive.
Some people do not consider this implementation as dynamic programming.
True Dynamic Programming:
- It is bottom up

// Dynamic Programming
public static int Dp(int n)
{
  if (n < 2)
  {
    return n;
  }

  int[] dp = { 0, 1 };
  int i = 2;
  while (i <= n)
  {
    int tmp = dp[1];
    dp[1] = dp[0] + dp[1];
    dp[0] = tmp;
    i++;
  }
  return dp[1];
}

This solution is of $O (n)$ time complexity and with O(1) memory.

2-d Dynamic Programming

Question: Count the number of the path from source top-left of a matrix to the bottom-right. You are only allowed to move down or right.

// Brute Force - Time: O(2 ^ (n + m)), Space: O(n + m)
public static int BruteForce(int r, int c, int rows, int cols)
{
  if (r == rows || c == cols)
  {
    return 0;
  }
  
  if (r == rows - 1 && c == cols - 1)
  {
    return 1;
  }

  return (BruteForce(r + 1, c, rows, cols) +
  BruteForce(r, c + 1, rows, cols));
}

Now we can use a memoization solution:

// Memoization - Time and Space: O(n * m)
public static int Memoization(int r, int c, int rows, int cols, int[][] cache)
{
  if (r == rows || c == cols)
  {
    return 0;
  }
  if (cache[r][c] > 0)
  {
    return cache[r][c];
  }
  if (r == rows - 1 && c == cols - 1)
  {
    return 1;
  }
  cache[r][c] = (Memoization(r + 1, c, rows, cols, cache) +
    Memoization(r, c + 1, rows, cols, cache));
  return cache[r][c];
}

With Dynamic Programming:

// Dynamic Programming - Time: O(n * m), Space: O(m), where m is num of cols
public static int Dp(int rows, int cols)
{
  int[] prevRow = new int[cols];

  for (int i = rows - 1; i >= 0; i--)
  {
    int[] curRow = new int[cols];
    curRow[cols - 1] = 1;
    for (int j = cols - 2; j >= 0; j--)
    {
      curRow[j] = curRow[j + 1] + prevRow[j];
    }
    prevRow = curRow;
  }
  return prevRow[0];
}

Keyboard shortcuts

My Coding Interview Journery