Coding Interviews Flashcards
Problem-Solving Steps (CtCI)
- Listen
- Example
- Brute Forceq
- Optimize (BUD)
- Walk Through
- Implement
- Test
Data structures to consider
- Linked List
- Trees, Tries, and Graphs
- Stacks
- Queues
- Heaps
- Hash Tables
Algorithms to consider
- Breadth-first search
- Depth-first search
- Binary search
- Merge sort / quick sort
Linked List
a structure of nodes that contain a data value and a pointer to the next node
Stack
a list with last in, first out (LIFO) ordering
Queue
a list with first in, first out (FIFO) ordering
Graph
a set of nodes (vertices) and edges linking 2 vertices
Trees
a hierarchical and acyclic graph
Balanced tree
A tree where for each node, the difference between the height of the left and right subtree is <= 1
Binary tree
A tree where each node has 0-2 children
Binary search tree
A (balanced) binary tree where for each node, the value of all nodes in the left sub-tree is less than the value of the parent node, and all nodes in the right sub-tree are greater than the parent node
Trie (prefix tree)
Combination of nodes where each node represents a unique letter. Good for forming dictionaries of words, etc.
Heap
Complete binary tree where all parent nodes are greater than or equal to their child nodes
Hash Table
Structure that maps keys to values via a hashing function
Pre-order traversal (Tree)
visit root, then left, then right
