interview.md

Algorithm Arsenal

• sort
  • merge sort n log n
  • insertion sort
  • heap sort (n log n)
  • bubble sort n log n
• graph search
  • DFS
  • BFS
  • shortest path - Djikstra's algorithm
• binary search (keep halving problem)
• map reduce

Data Structures Arsenal

• array
• linked lists
• set
  • hash
  • less than - stored as binary trees
• map
  • hash - if there is a collision, insertion can be as worse as O(n)
  • less than - stored as binary trees
• stacks
• queues
• trees
  • binary search tree
  • trie
• graph !!!! UNDERSTAND HOW THESE STRUCTURES WORK !!!!

Design questions (for self)

• concurrency
• recursion & induction
• dynamic programming
• scalability & memory limits

OOP

• inheritance - allows child class to inherit props of parent (minus private)
• abstract
  • can only be extended, not instantiated
  • can have implemented methods and abstract methods
• polymorphism - allows subclass to act like superclass
  • overriding - runtime
  • overloading - compile time
• encapsulation - hide methods and attributes inside class (black box)
• templates (done at compile time)