**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;

}

-- multiple dp relations (LeetCode 375 - Wiggle Subsequence)

-- space optimization

from O(NM) space to O(N)

X. rolling array

-- 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