How to Solve Algorithm Problems

Brainstorm list
bit trick
O(32n) - loop and check every bit

O(nlogn) - logn*n(merge sort) or n*logn(3 sum) binary search/bisection

Save space
- reuse input
- rolling array for dp

1. Clarify the question
Listen Carefully and Ask Questions
Make sure you hear the problem correctly

Ask questions about anything you're unsure about.
- do we need threadsafe?
- can we change the input?
- all positive?
Understand and list any unique/key information in the problem.

Ask yourself if you've used all the information in the problem.
Write the pertinent information on the whiteboard

Cut out all the "fluff" to this problem

Use concrete example to help clarify the problem.

Some interviewers writes down one example, but erases it later.
- if possible, keep the example in the whiteboard

Ask
Whether all numbers are unique, positive, sorted?
Whether there are duplicate numbers?
For string - character range, ascii only?
What's the expected time and space complexity?
How frequently these apis are called?

Draw an Example
-Specific, Sufficiently large, Not a special case

State a Brute Force and iterative refinement

Think about the best conceivable runtime

Before start to write code
-- make sure your algorithm works - in speical case
-- test your algorithm with examples and different cases
-- test with corner cases

-- List basic steps

When write code
-- We can start with simple case or complex case
- based on how much time left, if there is no much time left, start with complex case to show that u can solve it

Implement
Modularized code

What Good Coding Looks Like
- Correct, Efficient, Simple, Readable, Maintainable
Use Data Structures Generously
Use/Create other classes/structs where appropriate
- StartEndPair class instead of a two-dimensional array
Modular
Appropriate Code Reuse
Flexible and Robust
Good variable/function names
Error checks - add to-do comments to remind you and the interviewer

Focus on the top-level algorithm/code
--add //TODO comments

Don't Give Up! Get excited to solve hard problems

If you see something you can improve later on: either a different approach or code refactor, explain it to your interviewer.

How to test?
Start with a "conceptual"test.
Weird looking code.
Hot spots.
Small test cases.
Special cases.
Finding patterns

Optimize
X. Look for BUD
Bottlenecks
Unnecessary work/space
Duplicated work
-- Use cache

X. DIY (Do It Yourself)
Try working it through intuitively on a real example

Simplify and Generalize

Base Case and Build - Recursive

Best Conceivable Runtime (BCR)
Derive, don't guess the runtime.

Data Structure Brainstorm
- HashMap, HashSet
- Trie
- Union Find
-- Example: LeetCode [305] Number of Islands II

- Heap, PriorityQueue
- Deque(LinkedList, ArrayDeque)
LeetCode 239 - Sliding Window Maximum

- Binary tree, binary search tree
- Augmented binary tree
- TreeMap, TreeSet
LeetCode 352 - Data Stream as Disjoint Intervals
-- Sorted, O(logn) insert/delete

- Graph
Graph modeling

Algorithm Brainstorm
- BFS, DFS
-- Multi-End BFs
-- LeetCode 286 - Walls and Gates,

DFS/Recursive

Be excited about hard problems
Listen (for clues)
Draw an Example
(A) Look for BUD
Bottlenecks
Unnecessary work
Duplicated work


Cracking the Coding Interview (College) -  Gayle McDowell
Scope, Key components, identify issues, repair
Scope the Problem
Ask questions
Make appropriate assumptions
Define Key Components
Can be somewhat naïve
Identify Issues
Bottlenecks, tradeoffs
Repair & Redesign

Run through your algorithm meticulously before coding.
Modularize your code first.
Don't crowd your code.

Review your code conceptually.
Review error hot spots.
Test against a small example.
Pinpoint potential issues.
Test error cases.
Point out the mistake, and carefully analyze why the bug is occurring.

Pattern matching means to relate a problem to similar ones, and figure out if you can modify the solution to solve the new problem.

SIMPLIFY AND GENERALIZE
DATA STRUCTURE BRAINSTORM

Handle your special cases just once

- step through code and focus on dataflow and logic

- DFS/BFS + Cache - (Compared with DP)
https://www.hrwhisper.me/leetcode-longest-increasing-path-matrix/
LeetCode 329. Longest Increasing Path in a Matrix

-- Divide and conquer
-- Find subproblems

Backtrack
Recursive

-- LeetCode [267] Palindrome Permutation II
-- What info to maintain
Leetcode 124 - Binary Tree Maximum Path Su
private class maxPathResult {
    int maxSinglePath;
    int maxPath;
}

- DP
-- multiple dp relations (LeetCode 375 - Wiggle Subsequence)
-- space optimization
from O(NM) space to O(N)
X. rolling array

what is known, unknown
whether we used all known

Common Tricks

Presum

check last loop

whether we need do extra things after loop

backtrack

Don't forget to clear state

Binary tree

- usually expected runtime for tree is O(n)

Palindrome

-- Scan from center

space save

- rolling array in dp

- use/modify origin input

Graph

Eulerian path/circuit