Flashcards in InterviewCake Deck (18)

Loading flashcards...

1

## Greedy algorithms

### 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...)

2

## Bottom-Up Algorithms

### 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)

3

## Overlapping Subproblems and Memoization

### 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).

4

## Short Circuit Evaluation

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

5

## Garbage Collection

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

6

## Closures

### A closure is a function that accesses a variable "outside" itself (javascript...)

7

## Array Slicing

### 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.

8

## In-Place Algorithm

### 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.

9

## Arrays - space, lookup, append, insert, delete

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

10

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

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

11

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

###
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)

12

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

###
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)

13

## Queue - space, enqueue, dequeue, peek

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

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

14

## Stack - space, push, pop, peek

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

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

15

## Binary Tree

###
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...)

16

## Bitwise AND, OR, XOR, NOT, bitshifting

###
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.

17

## Two's complement encoding

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

18