InterviewCake

Question 1

Greedy algorithms

Answer 1

A greedy algorithm builds up a solution by choosing the option that looks the best at every step. Sometimes a greedy algorithm doesn’t give you an optimal solution! (eg Give money back, biggest coin first…)

Question 2

Bottom-Up Algorithms

Answer 2

Avoid recursion (top-down), saving the memory cost that recursion incurs when it builds up the call stack as well as the risk of stack overflow error. (eg product from 1 to n)

Question 3

Overlapping Subproblems and Memoization

Answer 3

A problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times. (eg Fibonacci) Memoization ensures that a function doesn’t run for the same inputs more than once by keeping a record of the results for the given inputs (usually in a dictionary).

Question 4

Short Circuit Evaluation

Answer 4

Avoid unnecessary work (don’t evaluate a part of the condition). We can use this to our advantage.

Question 5

Garbage Collection

Answer 5

A garbage collector automatically frees up memory that a program isn’t using anymore. tracing garbage collection VS reference counting VS manual memory management

Question 6

Closures

Answer 6

A closure is a function that accesses a variable “outside” itself (javascript…)

Question 7

Array Slicing

Answer 7

Careful: you are allocating a new list and copying the elements from the original list to the new list O(n) time and O(n) space, where n is the number of elements in the resulting list. Even if the variable is not saved.

Question 8

In-Place Algorithm

Answer 8

Operates directly on its input and changes it (destructive). Working in-place is a good way to save space. An in-place algorithm will generally have O(1) space cost.

Question 9

Arrays - space, lookup, append, insert, delete

Answer 9

O(n), O(1), O(1), O(n), O(n). Fixed size, one after another in memory.

Question 10

Dynamic Array - space, lookup, append, insert, delete

Answer 10

O(n), O(1), O(1) - amortized, O(n), O(n)

Question 11

Hash Tables - space, lookup, append, insert, delete

Answer 11

O(n), O(1) - amortized, O(1) - amortized, O(1) - amortized
Flexible keys (any datatype), Fast lookups but Unordered, Single-directional lookups (O(n) to get the key of a value), Not cache-friendly (uses linked-lists, data not next to each other in memory)

Question 12

Linked List - space, prepend, append, lookup, insert, delete

Answer 12

O(n), O(1), O(1), O(n), O(n), O(n)
An item in a linked list is called a node. The first node is called the head. The last node is called the tail.
Fast operations on the ends, Flexible size but Costly lookups (used for stacks and queues)

Question 13

Queue - space, enqueue, dequeue, peek

Answer 13

O(n), O(1), O(1), O(1)

A queue stores items in a first-in, first-out (FIFO) order. Fast operations (BFS, processes…)

Question 14

Stack - space, push, pop, peek

Answer 14

O(n), O(1), O(1), O(1)

A stack stores items in a last-in, first-out (LIFO) order. Fast operations (DFS…)

Question 15

Binary Tree

Answer 15

class BinaryTreeNode(object):
    def \_\_init\_\_(self, value):
        self.value = value
        self.left  = None
        self.right = None

perfect: every level of the tree is completely full (half of our nodes are on the last level)
n = 2^h + 1
log2(n - 1) = h
(level starts at 0 with 2^0 node…)

Question 16

Bitwise AND, OR, XOR, NOT, bitshifting

Answer 16

5 & 6 → 4
5 | 6 → 7
5 ^ 6 → 3
~ 5 → -6
0010 << 1  →  0100
1011010 >> 3  →  0001011

Shifting left multiplies by 2. Shifting right divides by 2, throwing out any remainders.

Question 17

Two’s complement encoding

Answer 17

The leftmost digit is negative, and the rest of the digits are positive. ex: 101 = -3

Question 18

Binary heap - space, get min, insert, remove min

Answer 18

O(n), O(1), O(lg(n)), O(lg(n))
A binary heap is a binary tree where the nodes are organized to so that the smallest value is always at the top. Quickly access the smallest item, Space efficient. One way to efficiently sort items is to insert them all into a heap and then remove them one at a time.