#algorithm #engineering

idea

Determine type of algorithm

Try several if hard to find the right one.

• Searching:
  • Binary search (aka. dichotomy). $O(log(n))$ search complexity in sorted array. Find first and last, find two integers whose arrangement in a certain way is $x$.
• Sort:
  • Merge sort. $O(n.log(n))$ sort complexity, in place, maintains order
  • Heap sort.
• Traversing/searching:
  • sub tree by subtree Depth First Search,
  • level by level: Breadth first search
• Recursion vs. iteration
  • Dynamics Programming, when optimal substructure and overlapping sub-problems. E.g. Fibo, rob houses,
    • top-down or bottom-up. Start from the end and walk backwards.
• Use a Sliding window search to find continguous elements in an array with a certain property

Optimizations

• Use memos (cache)
• Check for edge cases: MaxInt, MinInt, ...
  • Pre-emptively catch overflow by dividing MaxInt and comparing what will be multiplied before multiplying.

Data structures

• Heap
  • Highest, nth highest
  • Priority queues (each element in the queue has a priority)
• Stack
  • Check balancing (e.g. balanced parenthesis)
  • Reversing
    • Reverse string
    • Backtracking (being able to go back, e.g. undo, finding a path, etc.)
    • Reverse state (e.g. memory after function call)
  • Process expressions
• Queue
  • Limit processing concurrency
  • Async processing
  • BFS
• HashTable
  • Fast access based on keys
  • Memo

references

• Master Leetcode Style Interviews (github.com/jeffzh4ng)