The main purpose of this lecture is to identify moments in problems that will lead us to decide on these data types/data structures as useful approaches in interviewing problems.
- Direct implementation questions (i.e. build a stack with 2 queues)
- Depth-first search/traversal (DFS) of trees/matrices/graphs
- a subset of backtracking
- Iterative implementation of recursive algorithms (i.e. instead of a callstack, using an actual stack in the function)
- Indirect implementations
- evaluation arithmetic expressions (postfix, prefix, infix)
- vague questions (online stock span, next greater element, balancing parentheses)
- These require a look at what the question needs, and how the elements rely on the previous ones closest to it.
- Direct implementation questions
- Breadth-first search/traversal (BFS) of trees/matrices/graphs
- Think: You don't want to deal with it now, but you WILL need to deal with it later.
- Think: You are waiting to complete something so you queue it up.
- Preorder Traversal
- Level Order Traversal
- Next Greater Element
- Number of Islands
- Stock Span
- Reverse Polish Notation
- Direct implementation
- implementation for stacks/queues storage
- build linked lists from scratch, or build new nodes (using constructors and classes)
- change rules for linked lists
- Manipulate an existing linked list (provided the head/root node, or any node in the list, or the list itself)