Algorithms

Question 1

time complexity

Answer 1

the number of elementary instructions a program executes

Question 2

Big O

Answer 2

upper bound on time (asymptotic performance)

Question 3

Big Ω

Answer 3

lower bound

Question 4

Big θ

Answer 4

both O and Ω

Question 5

3 ways to describe runtime of an algorithm

Answer 5

best case
worst case
expected case

Question 6

space complexity

Answer 6

amount of memory or space required by an algorithm

Question 7

data structures

Answer 7

Linked List
Tree, Trie and Graph
Stack and Queue
Heap
Vector/ArrayList
HashTable

Question 8

search and sort algorithms

Answer 8

breadth-first search
depth-first search
binary search
merge sort
quick sort

Question 9

steps to handle a technical question

Answer 9

1. Listen carefully
2. Draw an example
3. State a brute force
4. Optimize
5. Walk through
6. Implement
7. Test

Look for bottlenecks, unnecessary work and duplicated work.

Question 10

Linked List

Answer 10

runner technique: two pointers, one runs ahead

many linked list problems rely on recursion

Question 11

Stack

Answer 11

LIFO: most recent item added is the first to be removed. E.g. stack of dinner plates

Used in some recursive algorithms and to implement a recursive algorithm iteratively.

pop()
push(item)
peek()
isEmpty()

Question 12

Queue

Answer 12

FIFO: first-in, first-out. E.g. ticket line
Often used in breadth-first search or caches.

add(item)
remove()
peek()
isEmpty()

Question 13

Tree

Answer 13

data structure comprised of nodes. Has a root node with zero or more child nodes. Each child node has zero or more child nodes. Cannot contain cycles.

Question 14

Binary Tree

Answer 14

a tree in which each node has up to two children

Question 15

Binary Search Tree

Answer 15

a binary tree in which every node has a specific ordering property:
all left descendants <= n < all right descendants

Question 16

Balanced Tree

Answer 16

a tree that is “not terribly imbalanced”. Left and right subtrees do not have to be exactly the same size.

Question 17

Complete Binary Tree

Answer 17

a binary tree in which every level of the tree is fully filled except for perhaps the last level. The last level is filled left to right.

Question 18

Full Binary Tree

Answer 18

a binary tree in which every node has either zero or two children. No node has only one child.

Question 19

Perfect Binary Tree

Answer 19

a binary tree that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.

Question 20

In-Order Traversal

Answer 20

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

Question 21

Pre-Order Traversal

Answer 21

visit the current node before its child nodes.

Question 22

Post-Order Traversal

Answer 22

visit the current node after its child nodes

Question 23

Min-Heap

Answer 23

complete binary tree where each node is smaller than its children. The root is the minimum element in the tree.

Question 24

Max-Heap

Answer 24

complete binary tree where each node is larger than its children. The root is the maximum element in the tree.

Question 25

Trie

Answer 25

variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word. Also known as Prefix Tree.

Question 26

Graph

Answer 26

a collection of nodes with edges between some of them. Can be directed or undirected.

Question 27

Adjacency List

Answer 27

most common way to represent a graph. Every node stores a list of adjacent vertices.

Question 28

Depth-First Search

Answer 28

search that starts at the root (or other node) and explores each branch completely before moving on to the next branch. Go deep before going wide. Preferred if we want to visit every node in the graph.

Question 29

Breadth-First Search

Answer 29

search that starts at the root (or other node) and explores each neighbor before going on to any of their children. Go wide before going deep. Generally better than DFS for finding a path.

Question 30

DFS steps

Answer 30

1. Push the root node on to the stack
2. Loop until the stack is empty
3. Peek the stack
4. If the node has unvisited child nodes, get the unvisited child node, mark it as visited, and push it on the stack
5. If the node does not have any unvisited child nodes, pop the node from the stack

Question 31

DFS algorithm

Answer 31

public void dfs() {
    Stack s = new Stack()
    s.push(rootNode)
    rootNode.visited = true
    print(rootNode)
    while (!s.isEmpty()) {
        Node n = s.peek()
        Node child = getUnvisitedChildNode(n)
        if (child != null) {
            child.visited = true
            print(child)
            s.push(child)
        } else {
            s.pop()
        }
    }
}

Question 32

BFS steps

Answer 32

1. Push the root node on to the queue
2. Loop until the queue is empty
3. Remove the node from the queue
4. If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in the queue

Question 33

BFS algorithm

Answer 33

public void bfs() {
    Queue q = new Queue()
    q.add(root)
    print(root)
    root.visited = true
    while (!q.isEmpty()) {
        Node n - q.remove()
        Node child = null
        while (child = getUnvisitedChildNode(n) != null) {
            child.visited = true
            print(child)
            q.add(child)
        }
    }
}

Question 34

Bottom-Up Approach for recursion

Answer 34

start by knowing how to solve for a simple case. Build the solution for a case off the previous one.

Question 35

Top-Down Approach for recursion

Answer 35

think about how to divide a problem for a case into subproblems.

Question 36

Half and Half Approach for recursion

Answer 36

divide the data set in half. Examples are binary search and merge sort.

Question 37

Dynamic Programming

Answer 37

taking a recursive algorithm, finding the repeated calls and caching the results for future recursive calls.

Question 38

Bubble Sort

Answer 38

Runtime: O(n²) average and worst case
Memory: O(1)

BubbleSort(A) {
    for (i=0; i A[i+1] {
            swap(A[i], A[i+1])
        }
    }
}

Question 39

Selection Sort

Answer 39

Runtime: O(n²) average and worst case
Memory: O(1)

void selection_sort (int A[ ], int n) {

int minimum; 

for (int i = 0; i < n-1 ; i++) {
    minimum = i ;
}

    for (int j = i+1; j < n ; j++ ) {
        if (A[ j ] < A[ minimum ]) { 
        minimum = j ;
    }
}

swap ( A[ minimum ], A[ i ]) {
}

Question 40

Merge Sort

Answer 40

Runtime: O(n log (n)) average and worst case
Memory: Depends

Divides the array in half, sorts each half and merges them back together.

MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)

Question 41

Quick Sort

Answer 41

Runtime: O(n log (n)) average worst case O(n²)
Memory: O(n log (n))

quickSort(arr[], low, high) {
    if (low < high) {
        pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    }
}