Data Structures for Interviews

class: center, middle

# Data Structures for Interviews

2013-11-19

Zack Newman, ADI

adicu.com

---

# Expectations for this talk

I assume familiarity with Java (if you know some other language, you can probably
figure it out). I didn't check all of my code.

The is **not** a replacement for 3134. It should be a good preview that gets you
ready for some basic interviews.

PLEASE stop me if I say something that doesn't make sense.

> He who asks is a fool for five minutes, but he who does not ask remains a fool forever.
> .right[*Chinese Proverb*]

---

# Review of Big O

* "Big O" is the "asymptotic runtime"

* Expressed as function of the size of the inputs

* Consider best, worst, and average cases

![Big O](http://i.stack.imgur.com/WcBRI.png)

---

# Review of Big O

/**
     * Return the index of the minimum element in an integer array.
     */
    public static int findMin(int[] array) {
        int minIndex = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] < array[minIndex]) {
                minIndex = i;
            }
        }
    }

---

# Review of Big O

/**
     * Return the index of the minimum element in an integer array.
     */
    public static int findMin(int[] array) {
        int minIndex = 0; // O(1)
        for (int i = 0; i < array.length; i++) { // n times
            if (array[i] < array[minIndex]) { // O(1)
                minIndex = i; // O(1)
            }
        }
    } // O(1) + n (O(1) + O(1)) = O(1) + n O(1) = O(1) + O(n) = O(n)

---

# Review of Big O

/**
     * Return the index of array (which must be sorted) at which value can be
     * found, or -1 if it is absent.
     */
    public static int find(int[] array, int value) {
        return findHelper(array, 0, array.length - 1, value);
    } // O(lg n)

private static int findHelper(int[] array, int minIndex, int maxIndex,
            int value) {
        if (maxIndex < minIndex) {
            return -1;
        }

int index = (maxIndex + minIndex) / 2;
        if (value < array[index]) {
            return findHelper(array, minIndex, index, value);
        } else if (value > array[index]) {
            return findHelper(array, index + 1, maxIndex, value);
        } else {
            return index;
        }
    }

---

# Abstract Data Type

* What is a "data structure" anyway? We define ADTs first

* An interface for interacting with data

* list, stack, set, queue, map

* Defines operations and results, but not how they're implemented

---

# Data Structures

* A method of representing data on a computer (including the implementation)

* For example, an "ArrayList" or "HashMap"

---

# Data Structure Primitives

## Arrays

int[] array = {1, 3, 5, 2, 6, 9};

/*
       * Index: 0 1 2 3 4 5
       * Value: 1 3 5 2 6 9
       */

---

# Data Structure Primitives

## Linked lists

![Linked List](http://upload.wikimedia.org/wikipedia/commons/1/1b/C_language_linked_list.png)

---

# Data Structure Primitives

## Linked lists

public class Node {
          public int value;
          public Node next;

public Node(int value, Node next) {
              this.value = value;
              this.next = next;
          }
      }

---

# Let's make lists!

// This should be documented
    public interface MyList {
        public int get(int index);

public void update(int index, int value);

public void append(int value);

public String toString();
    }

---

# Let's make lists!

public class MyArrayList implements MyList {
        private int[] data;
        private int length = 0;

public MyArrayList() {
            data = new int[100];
        }

---

# Let's make lists!

public int get(int index) {
            if (index >= length) {
                throw new ArrayIndexOutOfBoundsException();
            }
            return data[index];
        }

---

# Let's make lists!

public void update(int index, int value) {
            if (index >= length) {
                throw new ArrayIndexOutOfBoundsException();
            }
            data[index] = value;
        }

---

# Let's make lists!

public void append(int value) {
            if (data.length > length) {
                data[length++] = value;
            } else {
                int newData[data.length + 100];
                for(int i = 0; i < data.length; i++) {
                    newData[i] = data[i];
                }
                newData[data.length] = value;
                data = newData;
                length++;
            }
        }

---

# Let's make lists!

public String toString() {
            String repr = "[ ";
            for (int i = 0; i < length; i++) {
                repr += data[i] + " ";
            }
            return repr + "]";
        }
    }

---

# Let's make lists!

public class MyLinkedList implements MyList {
         private Node head = null;
         private Node tail = null;

---

# Let's make lists!

public int get(int index) {
             Node curr = head;
             for (int i = 0; i < index; i++) {
                 curr = curr.next;
             }
             return curr.value;
         }

---

# Let's make lists!

public void update(int index, int value) {
             Node curr = head;
             for (int i = 0; i < index; i++) {
                 curr = curr.next;
             }
             curr.value = value;
         }

---

# Let's make lists!

public void append(int index; int value) {
             if (head == null || tail == null) {
                 head = tail = new Node(null, value);
             } else {
                 tail.next = new Node(null, value);
                 tail = tail.next;
             }
         }

---

# Let's make lists!

public String toString() {
             Node curr = head;
             String repr = "[ ";
             while (curr != null) {
                 repr += curr.value + " ";
                 curr = curr.next;
             }
             return repr + "]";
         }
     }

---

# Let's make lists!

<table>
  <th>
    <td>Array</td> <td>List</td>
  </th>
  <tr>
    <td>Access</td>    <td>O(1)</td>  <td>O(n)</td>
  </tr>
  <tr>
    <td>Update</td>    <td>O(1)</td>  <td>O(n)</td>
  </tr>
  <tr>
    <td>Append</td>    <td>O(1)/O(n)</td>  <td>O(1)</td>
  </tr>
  <tr>
    <td>Traversal</td> <td>O(n)</td>  <td>O(n)</td>
  </tr>
</table>

---

# Lists: Standard Library

import java.util.LinkedList;
        import java.util.ArrayList;
        import java.util.List;

// ...

List<Integer> a = new ArrayList<Integer>();
        List<Integer> b = new LinkedList<Integer>();

for (int i = 0; i < 10; i++) {
            a.add(i);
            b.add(i);
        }
        a.set(5, 0);
        b.remove(5);
        System.out.println(a); // [0, 1, 2, 3, 4, 0, 6, 7, 8, 9]
        System.out.println(b); // [0, 1, 2, 3, 4, 6, 7, 8, 9]

---

# Linked list: example

How do you reverse a linked list?

---

# Linked list: example

public static Node reverse(Node head) {
          Node prev = null;
          Node curr = head;
          Node next;

while (curr != null ) {
              next = curr.next;
              curr.next = prev;
              prev = curr;
              curr = next;
          }
          return prev;
      }

---

# Stacks

![Stack](http://www.cs.cmu.edu/~mrmiller/15-121/Homework/hw8/stack.png)

---

# Stacks

// Last-in first-out data structure
    public interface MyStack {
        // Add a value to the stack
        public void push(int value);

// Remove a value from the stack
        public int pop();

// See the value on the "top" of the stack (next to be removed)
        public int peek();
    }

MyStack a = ...; // [ ]
    a.push(1); // [ 1 ]
    a.push(2); // [ 2 1 ]
    a.peek(); // returns 2
    a.push(3); // [ 3 2 1 ]
    a.pop(); // [ 2 1 ], returns 3
    a.push(4); // [ 4 2 1 ]
    a.peek(); // returns 4

---

# Stacks

public class MyArrayStack implements MyStack {
          private int[] data;
          private int length = 0;

public MyArrayStack() {
              data = new int[100];
          }

---

# Stacks

public void push(int value) {
             if (data.length > length) {
                 data[length++] = value;
             } else {
                 int newData[data.length + 1];
                 for(int i = 0; i < data.length; i++) {
                     newData[i] = data[i];
                 }
                 newData[data.length] = value;
                 data = newData;
             }
         }

---

# Stacks

public int pop() {
            if (length == 0) {
                throw new ArrayIndexOutOfBoundsException();
            }
            length--;
            return data[length]; // lazy deletion
        }

---

# Stacks

public int peek() {
            if (length == 0) {
                throw new ArrayIndexOutOfBoundsException();
            }
            return data[length - 1];
        }
    }

---

# Stacks

public class MyLinkedListStack implements MyStack {
        private Node top = null;

public void push(int value) {
            Node newTop = new Node(value, top);
            top = newTop;
        }

public void pop() {
            int value = top.value;
            top = top.next;
            return value;
        }

public void peek() {
            return top.value;
        }
    }

---

# Stacks

<table>
  <th>
    <td>Array</td> <td>List</td>
  </th>
  <tr>
    <td>Push</td>      <td>O(1)/O(n)</td>  <td>O(1)</td>
  </tr>
  <tr>
    <td>Pop</td>       <td>O(1)</td>  <td>O(1)</td>
  </tr>
  <tr>
    <td>Peek</td>      <td>O(1)</td>  <td>O(1)</td>
  </tr>
</table>

---

# Stacks: Standard Library

Stack<Integer> a = new Stack<Integer>();

a.push(1);
        a.push(2);
        System.out.println(a.pop()); // 2
        a.push(3);
        System.out.println(a); // [1, 3]

---

# Stack: Question

Write a function to determine if a string consisting of the characters '{', '}',
'[', and ']' is balanced.

For example, "{[]}" is balanced, and "{[}]" is not.

---

# Stack: Question

public static boolean isBalanced(String braces) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < braces.length(); i++) {
            switch (braces.charAt(i)) {
                case '{': stack.push('{');
                    break;
                case '[': stack.push('[');
                    break;
                case '}': if (stack.pop() != '{') { return false; }
                    break;
                case ']': if (stack.pop() != '[') { return false; }
                    break;
            }
        }
        return stack.isEmpty();
    }

---

# Queues

![Queue](http://www.mmrelearning.ca/pluginfile.php/8007/mod_page/content/1/Unit_7_Linked_Lists/queue.jpg)

---

# Queues

// First-in first-out data structure
    public interface MyQueue {
        // Add a value to the back of the queue
        public void enqueue(int value);

// Remove a value from front of the queue
        public int dequeue();

// See the value on the "front" of the queue (next to be removed)
        public int peek();
    }

MyStack a = ...; // [ ]
    a.enqueue(1); // [ 1 ]
    a.enqueue(2); // [ 1 2 ]
    a.peek(); // returns 1
    a.enqueue(3); // [ 1 2 3 ]
    a.dequeue(); // [ 2 3 ], returns 1
    a.enqueue(4); // [ 2 3 4 ]
    a.peek(); // returns 2

---

# Queues

<table>
  <th>
    <td>Array</td> <td>List</td>
  </th>
  <tr>
    <td>Enqueue</td>   <td>O(1)/O(n)</td>  <td>O(1)</td>
  </tr>
  <tr>
    <td>Dequeue</td>   <td>O(1)</td>  <td>O(1)</td>
  </tr>
  <tr>
    <td>Peek</td>      <td>O(1)</td>  <td>O(1)</td>
  </tr>
</table>

I'm not going to write out the implementations this time. Ask me later (or
Google).

---

# Queues: Standard Library

import java.util.Queue;
      import java.util.ArrayDeque;

Queue<String> stack = new ArrayDeque<String>();

---

# Queue Question

Given one queue and one stack, how do you reverse the stack?

---

# Queue Question

Stack<Integer> stack = new Stack<Integer>();
        Queue<Integer> queue = new ArrayDeque<Integer>();

stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack); // [1, 2, 3]
        while (!stack.isEmpty()) {
            queue.add(stack.pop());
        }
        while (!queue.isEmpty()) {
            stack.push(queue.remove());
        }
        System.out.println(stack); // [3, 2, 1]

---

# Sorting arrays

The problem: given an array containing many values, permute the array so that
those values are in order.

You'll definitely be expected to have a high-level understanding of these and
know the runtimes. Maybe you'll have to implement one.

---

# Sorting arrays

private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

---

# Sorting arrays: selection sort

public static void selectionSort(int array[]) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

---

# Sorting arrays: selection sort

![Selection Numbers](http://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif)

---

# Sorting arrays: bubble sort

public static void bubbleSort(int array[]) {
         for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
         }
     }

---

# Sorting arrays: bubble sort

![Bubble Numbers](http://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif)

---

# Sorting arrays: Merge sort

Here's where I'm going to stop implementing things and just explain them.
Wikipedia is great.

Merge sort is recursive.

function mergeSort(A):
        split A into A_beginning and A_end at the middle
        mergeSort(A_beginning)
        mergeSort(A_end)
        return merge(A_beginning, A_end)

---

# Sorting arrays: Merge sort

![Merge Numbers](http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif)

---

# Sorting arrays: Quicksort

function quickSort(A):
        pick a "pivot" element in A
        move all elements less than the pivot to the beginning of A
        move all elements greater than the pivot to the end of A
        put the pivot in the middle
        quicksort the beginning of A recursively
        quicksort the end of A recursively

---

# Sorting arrays: Quicksort

![Quicksort Numbers](http://upload.wikimedia.org/wikipedia/commons/9/9c/Quicksort-example.gif)

---

# Sorting arrays: Counting sort

Comparison-based sorts can't be faster than n * log(n). BUT non-comparison based
ones can. There are catches, though.

public void countingSort(int[] array, int max) {
        int[] counts = new int[max];
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - 1]++;
        }
        int i = 0;
        for (int j = 0; j < max; j++) {
            while (counts[j] > 0) {
                array[i++] = j + 1;
            }
        }
    }

---

# Recursion

public int fib(int n) {
          if (n < 2) {
              return 1;
          } else {
              return fib(n - 1) + fib(n - 2);
          }
      }

---

# Trees

![Tree](http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg)

---

# Trees

public class Node {
        public int value;
        public Node left;
        public Node right;

public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

public Node(int value) {
            this(value, null, null);
        }
    }

---

# Trees

These are **mad** useful. Can represent hierarchical data: parse trees in NLP,
database indexes, etc.

---

# Trees: Ordered

**Binary Search Tree**: every value in the left subtree of a node with a value
is less than that value; every value in the right subtree of a node with a value
is greater than that value.

This gives us O(log(n)) retrieval (in the average but not worst case; more on
that later).

---

# Trees: Ordered

![BST](http://upload.wikimedia.org/wikipedia/commons/d/da/Binary_search_tree.svg)

---

# Trees: Ordered

public boolean find(Node root, int value) {
        if (root == null) {
            return false;
        }
        if (value < root.value) {
            return find(root.left, value);
        } else if (value > root.value) {
            return find(root.right, value);
        } else {
            return true;
        }
    }

---

# Trees: Ordered

![BST worst](https://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_fig33.gif)

---

# Trees: Ordered

We can traverse the tree in one of a few ways.

## Pre-Order (XLR)

![preorder](http://www.sqa.org.uk/e-learning/LinkedDS04CD/images/pic011.jpg)

---

# Trees: Ordered

We can traverse the tree in one of a few ways.

## In-Order (LXR)

![inorder](http://www.sqa.org.uk/e-learning/LinkedDS04CD/images/pic013.jpg)

---

# Trees: Ordered

We can traverse the tree in one of a few ways.

## Post-Order (LRX)

![postorder](http://www.sqa.org.uk/e-learning/LinkedDS04CD/images/pic012.jpg)

---

# Trees: Question

How do we do a level-order traversal of a tree?

![levelorder](http://upload.wikimedia.org/wikipedia/commons/d/d1/Sorted_binary_tree_breadth-first_traversal.svg)

---

# Trees: Question

public void levelOrder(Node root) {
        Queue<Node> queue = new Queue<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.remove();
            System.out.println(curr.value);
            if (curr.left != null) {
                queue.add(curr.left);
            }
            if (curr.right != null) {
                queue.add(curr.right);
            }
        }
    }

---

# Hash tables

Imagine that we have a list of integers and we want to determine if there are any duplicates?

We could sort, but that takes O(n * log(n)) time. Can we do better?

---

# Hash tables

Imagine that we have a list of integers and we want to determine if there are any duplicates?

We could sort, but that takes O(n * log(n)) time. Can we do better?

What if we applied the ideas from counting sort?

---

# Hash tables

Imagine that we have a list of integers and we want to determine if there are any duplicates?

We could sort, but that takes O(n * log(n)) time. Can we do better?

What if we applied the ideas from counting sort?

This works great, **unless** the numbers are large and sparse (because then we need more space).

---

# Hash tables

Imagine that we have a list of integers and we want to determine if there are any duplicates?

We could sort, but that takes O(n * log(n)) time. Can we do better?

What if we applied the ideas from counting sort?

This works great, **unless** the numbers are large and sparse (because then we need more space).

What if we have a smaller number of buckets, and assign the larger numbers buckets using the modulus?

---

# Hash sets

public interface MySet {

// Add a member to the set if it does not exist
        public void add(int member);

// Remove a member from the set
        public void remove(int member);

// Test if a member is present from the set
        public boolean isPresent(int member);
    }

---

# Hash sets

// this is bad for a lot of reasons, but illustrates the point
    public class MyHashSet {
        int table[37];

---

# Hash sets

public void add(int member) {
            int hashVal = member % table.length;
            // "linear probing"
            while (table[hashVal] != 0) {
                hashVal = (hashVal + 1) % table.length;
            }
            table[hashVal] = member;
        }

---

# Hash sets

public void remove(int member) {
            int hashVal = member % table.length;
            while (table[hashVal] != 0 &&
                    table[hashVal] != -1 && table[hashVal] != member) {
                hashVal = (hashVal + 1) % table.length;
            }
            if (table[hashVal] == member) {
               table[hashVal] = -1; // lazy deletion
            } else {
                // not found; should probably throw exception
            }
        }

---

# Hash sets

public boolean isPresent(int member) {
            int hashVal = member % table.length;
            while (table[hashVal] != 0 &&
                    table[hashVal] != -1 && table[hashVal] != member) {
                hashVal = hashVal + 1 % table.length;
            }
            if (table[hashVal] == member) {
               return true;
            } else {
                return false;
            }
        }
    }

---

# Hash tables

**Hash function**: maps an object (of some type) to an integer.

Example:

public int hash(String s) {
        int hashVal = 0;
        for (int i = 0; i < s.length(); i++) {
            hashVal = s.charAt(i) + hashVal * 37;
        }
        return hashVal;
    }

---

# Hash maps

Maps are the same idea, but instead of just storing the key, you store a key-value pair.

// int keys and string values
    public interface MyHashMap {
        public String get(int key);

public void put(int key, String value);
    }

---

# Hash Maps: Standard library

import java.util.HashSet;
    import java.util.HashMap;

// ...

HashSet<String> set = new HashSet<String>();
    set.add("dog");
    set.add("cat");
    set.add("fish");
    System.out.println(set.contains("dog")); // true
    System.out.println(set.contains("horse")); // false

HashMap<String, String> map = new HashMap<String, String>();
    map.put("Jenny", "867-5309");
    System.out.println(map.get("Jenny")); // 867-5309

---

# Hash maps: example

Implement a word counter (not case sensitive, and ignoring special characters).

Example: "Gabba gabba hey, gabba gabba hey!" -> { "gabba": 4, "hey": 2 }

---

# Hash maps: example

import java.util.HashMap;

public static HashMap<String, Integer> countWords(String document) {
        HashMap<String, Integer> counts = new HashMap<String, Integer>();
        for (String word : document.split(" ")) {
            String key = word.toLowerCase().replaceAll("[^a-zA-Z]", "");
            if (counts.containsKey(key)) {
                counts.put(key, counts.get(key) + 1);
            } else {
                counts.put(key, 1);
            }
        }
        return counts;
    }

---

# Other things to know:

* Priority queues (implemented using heaps)

* Graphs

* Depth/Breadth-first search

* Balanced binary tree

* How to code in your interview language

* How to use Unix (scripting, regexes)

* How a computer works (bits and bytes)

* Object-oriented programming

---

# Other resources

* https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions

* http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

* Cracking the Coding Interview

* Google

* ICPC

* CLRS

![ADI](http://adicu.com/img/logo.png)