Skip to content

Latest commit

 

History

History
466 lines (360 loc) · 18.7 KB

data_structures_and_algorithms.md

File metadata and controls

466 lines (360 loc) · 18.7 KB

Data structures and algorithms

I highly recommend creating a free account on Leetcode so you can can submit solutions to real problems.

Big O analysis

Big O characterizes (1) how long a function takes to run, or (2) how much memory/space the function uses, as the size of its input increases.

To make things concrete, let's analyze the big O of a solution to the Valid Anagram problem. First, let's consider a solution where we sort the strings:

function isAnagram(source, target) {
  if (source.length !== target.length) {
    return false;
  }

  const sourceArr = source.split('');
  sourceArr.sort();

  const targetArr = target.split('');
  targetArr.sort();

  // If the two sorted strings are the same, then they're anagrams of each other.
  return sourceArr.join('')  === targetArr.join('');
}

The big O runtime is O(n log n), because sorting an array generally takes O(n log n) time (and we call it twice with .sort()). What is "n"? It's the length in characters of both source and target strings.

The leetcode submission runtime is 100ms, faster than 34% of other JS solutions. Can we do better? With the right insight - that two anagrams have the same character count - we can. We also rely on the fact that in a hash table, setting a value and retrieving a value are O(1) operations.

function isAnagram(source, target) {
  if (source.length !== target.length) {
    return false;
  }
  const sourceArr = source.split('');
  const targetArr = target.split('');
  const charCounts = {};

  // Count how many times each character occurs in source str
  sourceArr.forEach((char) => {
    charCounts[char] = charCounts[char] || 0;
    charCounts[char] += 1;
  });

  // Iterate through target str, decrementing the counts for
  // each char seen.
  targetArr.forEach((char) => {
    charCounts[char] = charCounts[char] || 0;
    charCounts[char] -= 1;
  });

  // If all characters' counts are now 0, then each string has the
  // same number of each character, and are therefore anagrams.
  return Object.keys(charCounts).every((key) => {
    return charCounts[key] === 0;
  });
}

The big O runtime is O(n) because we make 5 sets of O(n) computations. If we submit it in Leetcode, we can see that the runtime has been improved from the previous solution.

Let's group up into pairs and work together to solve Contains duplicate, and try to get a solution that passes the Leetcode online judge.

Concepts:

  • Applies to both runtime and space
  • Can involve "amortization", e.g. with hash tables implemented with dynamic arrays
  • Binary search is log(n)
  • Not always "n": can have multiple input sizes (e.g. two arrays, array of strings of different lengths)
  • Space usage with recursion is O(number of stack frames).
  • Sorting in general is O(n log n), but can be faster with specific inputs.

References:

Data structures

I've highlighted some relevant Leetcode questions for each type of data structure.

Essential:

  • Arrays and Strings
    • Big O: random access, append, delete TODO
    • Leetcode questions: arrays, strings
    • References:
      • Cracking the Coding Interview, Ch. 1
  • Hash tables
    • Big O: O(1) lookup, O(1) insert amortized
    • In javascript, objects act like hash tables ({ key: value })
  • Linked lists
  • Stacks and Queues
    • Big O: TODO
      • Stacks: push/pop
      • Queues: enqueue/dequeue
    • In javascript, stacks can be implemented with arrays (const stack = []; stack.push(item); stack.pop();)
    • Concepts:
      • Know how to write a Stack or Queue with a linked list
      • Know how to use a stack to implement recursive algorithms iteratively
    • References:
      • Cracking the Coding Interview, Ch. 3
    • Leetcode questions:
  • Trees
    • Big O: find, insert, delete TODO
    • Concepts: binary tree traversal (in-order, pre-order, post-order), binary search
    • Can implement as class TreeNode { value: any, children: TreeNode[] }, or class TreeNode { value: any, left: TreeNode | null, right: TreeNode | null } for binary trees. Can also implement as an array.
    • References:
    • Leetcode questions:
  • Graphs
    • Depth-first search (DFS): explore a branch fully before going to other neighbors. Simpler than BFS. Can be implemented recursively, or with a stack.
    • Breadth-first search (BFS): visit all neighbors before going to any deeper neighbors. Can be used to find shortest path. Uses a queue.
    • Detecting cycles
    • There are many ways to represent a graph in code. It's good to develop intuition on what can be abstractly translated into a graph problem (e.g. a maze).
      • Adjacency list (most common): can simply use a hash table that maps nodes (keys) to neighbors (value array): { 0: [1, 2], 2: [3, 5], ... }
      • List of edges (undirected graph): [(0, 1), (0, 3), (1, 5), ...]
      • 2D matrixes
    • References:
    • Leetcode questions:

Less common:

  • Tries
    • A type of tree, can appear in string search and prefix search problems. Improves efficiency of searching for a length-k string among n strings from O(n) to O(k).
    • Leetcode questions
    • References:
  • Heaps
    • Big O: insert, extract min/max TODO

Problem solving techniques

Applying concepts to real problems

Greedy algorithms

Let's go through Best time to buy and sell stock.

There's a brute force O(n^2) solution where you compare every 2 elements and record the price difference. We get O(n^2) because we iterate through n + (n - 1) + (n - 2) + ... + 1 pairs, which sums to (n + 1) * (n / 2) = (n^2 + n) / 2, which is proportional to n^2.

function maxProfit(prices) {
  let maxProfitValue = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const profit = prices[j] - prices[i];
      maxProfitValue = Math.max(maxProfitValue, profit);
    }
  }
  return maxProfitValue;
}

How can we do better?

Well, let's take a look at each time we see a new minimum stock value. Going forward, we no longer need to consider any values to the left of this new minimum - because any price difference to the right will strictly be better starting from this new minimum. This is a trademark of greedy algorithms - we don't need to "backtrack" and we can discard parts of the input. We should keep track of what the biggest price difference had been, though, in case it was higher.

Let's illustrate this by simulating what happens with some test cases:

[5, 20, 4, 10, 3, 10]  // Biggest diff at beginning
[5, 20, 4, 10, 3, 20]  // Biggest diff at end

At this point, we can also ask the interviewer more details about the question:

  • Will the price array have negative numbers? (let's assume no)
  • Should we report a negative profit if prices keep descending? (let's assume no)

Okay, now let's code it up:

function maxProfit(prices) {
  let maxProfitValue = 0;
  let minPrice = prices[0];

  prices.forEach((price) => {
    if (price < minPrice) {
      // Set new minimum
      minPrice = price;
    } else {
      // Track whether profit increases against current minimum
      maxProfitValue = Math.max(maxProfit, price - minPrice);
    }
  });

  return maxProfit;
}

Let's also think about some more edge cases to test:

[]
[5, 4, 3, 2, 1]

You can run node solutions/best_time_to_buy_and_sell_stock.js to see how I set up testing this function out locally. We can also now submit the solution on Leetcode.

Big O analysis: we do an O(n) pass. We keep track of two variables, so O(1) storage.

This demonstrates a "greedy algorithm", where we can go from O(n^2) to O(n) runtime by having an insight that allows us to make a single pass through the input. Note that a greedy approach doesn't always work. If we change the problem slightly and ask for the Longest increasing subsequence, we can no longer discard earlier inputs when we see new minimums, because they can still factor in going forward. It's important to recognize when you can use a greedy approach, and when you can't.

Recursion and trees

Trees are represented by "nodes" which can have "children", which are other nodes.

In code, this tree could be represented as:

{
  // Root node: 2
  value: 2,
  left: {
    // Node with value 7
    value: 7,
    left: {
      // Node with value 2, a "leaf" node
      value: 2,
      left: null,
      right: null,
    },
    right: {
      // Node with value 6
      value: 6,
      // ...children 5 and 11...
    },
  },
  right: {
    // Node with value 5
    value: 5,
    left: null,
    right: {
      // Node with value 9
      value: 9,
      left: {
        // Leaf node with value 4
        value: 4,
        left: null,
        right: null,
      },
      right: null,
    }
  }
}

Why do we even care about trees? They're actually a very useful way to represent a lot of things - some of which you use every day. Programs that you write are also represented as trees under the hood, using abstract syntax trees (ASTs). When you write a webpage with HTML, the DOM is a tree:

<div>
  <p>My homepage</p>
  <ul>
    <li>Item 1</li>
  </ul>
</div>

Let's solve Maximum depth of binary tree. With a tree problem, always consider: if we solve the problem for the children of the root node, could we answer the question for the whole tree?

Suppose we know that the left child of a tree has max depth 5, and right child has max depth 7. What's the max depth of the tree?

Let's code it up:

// Leetcode's definition of a tree node. Just like a plain object,
// but implemented as a class instead.
function TreeNode(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

function maxDepth(node) {
  // Base case
  if (!node) {
    return 0;
  }

  // Use recursion - call the same function on the two child nodes.
  // Recursion will eventually end because we're calling on successively smaller inputs.
  const leftDepth = maxDepth(node.left);
  const rightDepth = maxDepth(node.right);

  return Math.max(leftDepth, rightDepth) + 1;  // Add 1 to the max child depth
}

Let's try testing this. Take a look at solutions/maximum_depth_of_binary_tree.js.

After doing this, you can try implementing Same tree on your own.

Tree traversal

How do we list out all the nodes in a tree?

Let's think about it recursively. Assume we can list out the left and right subtrees - now what would we need to do to list the whole tree?

Let's solve Binary tree inorder traversal, without worrying about the "binary tree" or "inorder" parts of it yet.

function inorderTraversal(root) {
  const visited = [];
  traverse(root, visited);
  return visited;
};

function traverse(node, visited) {
  // Handle base case - nodes with no children.
  if (!node) {
    return;
  }
  traverse(node.left, visited);
  visited.push(node.val);
  traverse(node.right, visited);
}

We can simulate this code on some example trees, and keep track of what visited looks like at each step.

This is an example of depth-first traversal, which is an important concept in both trees and graphs.

Binary search trees (BSTs)

Let's try solving Search in a binary search tree.

Binary search trees are a special type of binary tree, where all the values in a node's left subtree are lower than the node's value, and all the values in the right are higher.

This allows us to do binary search. Let's simulate this on a tree, e.g. [4, 2, 7, 1, 3].

What's the big-O runtime of binary search? We can always find a value in the tree with a number of comparisons equal to the "depth" of the tree. If we have n nodes in the tree, how many comparisons is that?

To figure this out, let's look at how many nodes we can fill at each possible tree depth.

| Depth | Max nodes | 1 | 1 2 | 3 3 | 7 4 | 15 5 | 31 6 | 63

Can you see a pattern? nodes = 2^depth - 1. So you can also say depth = log2(nodes + 1). The number of comparisons to find a node, or the depth, is therefore O(log n).

Graphs and depth-first search

Suppose we have a graph, represented by a hash table mapping from nodes to neighbors:

const testGraph = {
  1: [2, 3],
  2: [4],
  4: [1, 6],
  6: [],
}

Let's do a depth-first search of this graph and look for the node "6":

function dfs(graph, node, targetNode, visitedNodes) {
  if (node == null) {
    return false;
  }

  // Don't revisit a node that has already been visited
  if (visitedNodes.includes(node)) {
    return false;
  }

  // Mark node as visited
  visitedNodes.push(node);

  // Check if targetNode is found
  if (node === targetNode) {
    return true;
  }

  // Get the neighbors of the node
  const neighbors = graph[node] || [];

  // Recursively do depth-first search on each of the node's neighbors.
  // If any of the neighbors finds the node, then return true (using .some)
  for (let i = 0; i < neighbors.length; i++) {
    const found = dfs(graph, neighbors[i], targetNode, visitedNodes);
    if (found) {
      return true;
    }
  }
  return false;
}

Let's try it out. Run node algorithms/depth_first_search.js.

Graph applications

Graphs can be represented in a wide number of ways (adjacency lists, list of edges, and 2D matrixes), and can also appear in very abstract representations. If a set of items relate to each other, it can probably be represented as a graph (e.g. plane tickets from various cities).

Let's solve a real problem using graphs and depth-first search: Course schedule. Most DFS problems aren't actually as simple as looking for a value in the graph, though - DFS is simply a way to traverse the graph and solve problems.

See solution at solutions/course_schedule.js.

Breadth-first search with level-order traversal on a tree

We can illustrate how breadth first search works on a tree, by solving Binary tree level order traversal.

References

14 patterns to ace any coding interview question

  • kdn251/interviews - overview of algorithms and data structures, prep resources, and problem solutions in Java
  • yangshun/lago - data structures and algorithms in JS

Next section

Next: Technical phone screen and whiteboarding practice