##### 0. Pinned Summary

My time machine, please go back to 2006-09-01 damn hot Hangzhou.

##### 1. Favourate

- [3] Longest Substring Without Repeating Characters
- [5] Longest Palindromic Substring
- [18] 4Sum =>
`[Follow-up]`

extend to k-sum- [454] 4Sum II

- [21]/[23] Merge Two Sorted Lists => Merge k Sorted Lists (* big-O analysis)
- [22] Generate Parentheses
- [24]/[25] Swap Nodes in Pairs => 25. Reverse Nodes in k Group
- [31] Next Permutation
- [33]/[81] Search in Rotated Sorted Array I/II (weird…but worth noted)
- [34] - Find First and Last Position of Element in Sorted Array
- [39]/[40]/[216]/[377] Combination Sum I/II/III/IV (DP solution, not typical dp[]) -> 377 with followup, 377 can also extend to return actual lists instead of just total-count
- [77] combinations (dfs+bfs)

- [42] - Trapping Rain Water (多重解法)
- [407] - Hard Trapping Rain Water II (2D to 3D)

- [44] - Wildcard Matching
- [48] - Rotate Image
- [49] Group Anagrams
- [53] - Maximum Subarray O(N)
- [1746] Maximum Subarray Sum After One Operation (good dp)

- [55]/[45] Jump Game I/II
- [1345] Jump Game IV

- [62]/[63]/[980] Unique Paths I/II/III ==> extend: III return the actual path instead of path-count
- [66] - Plus One (clean code)
- [68] - Text Justification (主要看modular的能力，否则代码太乱)
- [72] - Edit Distance
- [161] - One Edit Distance

- [74]/[240] Search a 2D Matrix I/II (74 binary search 解法)
- [76] Minimum Window Substring
- [78]/[90] Subsets I/II
- [79]/[208]/[212]/[211] Word Search I => Implement Trie Prefix Tree => Word Search II => Add and Search Word (Data structure design)
- [84] Largest Rectangle in Histogram (hard…if time allows)
- [94] Binary Tree Inorder Traversal (iteration)
- [100] Same Tree (二叉树的四种遍历(层序，先序，中序，后序)均有各自的迭代和递归的写法)

- [96]/[95] Unique Binary Search Trees I/II (II 另类DP)
- [241] Different Ways to Add Parentheses

- [97] Interleaving String
- [98] Validate Binary Search Tree (bfs + dfs)
- [103]/[281] Binary Tree Zigzag Level Order => Zigzag Iterator (good
`[Follow-up]`

) (extend to multi-thread design)- [6] ZigZag <= bad one, skip it

- [105] Construct Binary Tree from Preorder and Inorder Traversal
- [106] Construct Binary Tree from Inorder and Postorder Traversal
- [889] Construct Binary Tree from Preorder and Postorder Traversal
- [536] Construct Binary Tree from String (start from no ‘-‘, then expand to support ‘-‘)
- [108] Convert Sorted Array to Binary Search Tree
- [109] Convert Sorted List to Binary Search Tree
- [538] Convert BST to Greater Tree (easy to warm up)
- [114] - Flatten Binary Tree to Linked List
- [116] - Populating Next Right Pointers in Each Node (bfs + dfs)

- [111] Minimum Depth of Binary Tree (bfs + dfs)
- [116]/[117] Populating Next Right Pointers in Each Node I/II (bfs + dfs)
- [121]/[122]/[123]/[188] Best Time to Buy and Sell Stock I,II,III,IV
- [127]/[126] Word Ladder I/II
- [131]/[132] Palindrome Partitioning I/II => List作为dp，不是数组[]作为dp
- [136]/[137]/[260] Single Number I,II,III
- [619] Biggest-Single-Number => do it in SQL
- [246]/[247]/[248] Strobogrammatic Number I,II,III
- [263]/[264]/[313] Ugly Number I,II => Super Ugly Number
- [306] Additive Number =>
`[Follow-up]`

: print actual value, instead of boolean- [415] Add Strings (should ask
`before 306`

)

- [415] Add Strings (should ask
- [315] Count of Smaller Numbers After Self

- [138] Copy List with Random Pointer => no extra space solution
- skip-[382] Linked List Random Node => math-stats “rn = rd.nextInt(idx);” 水塘抽样 Reservoir Sampling

- [141]/[142] Linked List Cycle I/II
- [146]/[460] LRU Cache / LFU Cache
- [148] Sort List (top down, bottom up => solution analysis)
- [151]/[186]/[557] Reverse Words in a String I (extra space -> in place) => II/III
- [155] Min Stack (easy, but good test for data structure)
- [159]/[340] Longest Substring with At Most
`Two or K`

Distinct Characters- [3] Longest Substring Without Repeating Characters ==> At Most
`One`

Distinct Characters - [395] Longest Substring with [At Least] K [Repeating] Characters
- [MyNote] Longest Substring with [At Most] K [Repeating] Characters
- [1698] Number of Distinct Substrings in a String (
`[Follow-up]`

o-N solution)

- [3] Longest Substring Without Repeating Characters ==> At Most
- [164] - [Hard] Maximum Gap
- [187] - Repeated DNA Sequences (expand to space saving via mask encoding, data compression)
- [189] Rotate Array
- [396] Rotate Function

- [192]/[347]/[692] Word Frequency => Top K Frequent Elements => Top K Frequent Words
- [193] Valid Phone Numbers (shell script)

- [198]/[213]/[337] House Robber I, II, III
- [200]/[305] Number of Islands -> extend from 2D to 3D
- [215] Kth Largest Element in an Array
- [217]/[219]/[220] Contains Duplicate I/II/III
- [218] [Hard] The Skyline Problem
- [222] Count Complete Tree Nodes
- [224]/[227]/[772] [Tricky-NotSoGood] Basic Calculator I/II/III
- [225] Implement Stack using Queues
- [232] Implement Queue using Stacks

- [230] Kth Smallest Element in a BST (multiple solutions, + good
`[Follow-up]`

)- [378] Kth Smallest Element in a Sorted Matrix

- [235]/[236] 236 Lowest Common Ancestor of a Binary Tree => 235 更好条件BST 优化 Lowest Common Ancestor of a Binary Search Tree (bfs+dfs)
- [238] Product of Array Except Self =>
`[Follow-up]`

- [239] Sliding Window Maximum
- [241] Different Ways to Add Parentheses
- [243]/[244]/[245] Shortest Word Distance I,II,III
- [249] Group Shifted Strings
- [250] Count Univalue Subtrees (bottom up and top down)
- [251] Flatten 2D Vector => great hints
- [252]/[253]/[1229] Meeting Rooms I,II => Meeting Scheduler
- [254] Factor Combinations
- [266]/[267] Palindrome Permutation I/II
- [269] [Hard] Alien Dictionary (dfs+bfs)
- [270]/[272] Closest Binary Search Tree Value I,II => optimize solution, from binary-tree to BST
- [273] Integer to English Words (real use case)
- [277] Find the Celebrity (
`[Follow-up]`

reduce api call) - [280]/[324] Wiggle Sort I,II => o(N) solution with quick-sort algorithmn (< or <=)
- [376] Wiggle Subsequence (optimize: dp[] to single variables)

- [282] Expression Add Operators
- [290]/[291] Word Pattern I,II
- [293]/[294] Flip Game I,II
- [296] Best Meeting Point
- [302] Smallest Rectangle Enclosing Black Pixels
- [303] Range Sum Query - Immutable (这一组是各种不常见的变种树结构，有精力再看这组题)
- [310] Minimum Height Trees
- [318] Maximum Product of Word Lengths
- [331] Verify Preorder Serialization of a [Binary Tree]
- [297] Serialize and Deserialize [Binary Tree]
- [255] Verify Preorder Sequence in Binary Search Tree
- [428] Serialize and Deserialize [N-ary Tree] (297 binary to this n-nary)
- [449] Serialize and Deserialize BST (297 binary-tree to BST, optimization)
- [99] Recover [Binary Search Tree]
- [1660] Correct a Binary Tree (new bfs level marking)

- [322] Coin Change
- [323] Number of Connected Components in an Undirected Graph (connected component search)
- [333] Largest BST Subtree => o(N) (dfs+bfs)
- [334] Increasing Triplet Subsequence => optimize: O(n) time complexity and O(1) space complexity
- [339]/[364] Nested List Weight Sum I,II
- [385] Mini Parser (dfs + bfs) =>
`[Follow-up]`

add new method ‘serialize()’

- [385] Mini Parser (dfs + bfs) =>
- [341] Flatten Nested List Iterator (dfs+bfs)
- [346] Moving Average from Data Stream => can extend to a system design question
- [349]/[350] Intersection of Two Arrays I/II (easy to complex)
`[Follow-up]`

- [354] Russian Doll Envelopes => 1D=>2D
`[Follow-up]`

: can rotate - [358] Rearrange String k Distance Apart
- [359] Logger Rate Limiter (extend to throttle, load balancing, etc.)
- [362] Design Hit Counter (counter too much, then need rate limiter) (
`[Follow-up]`

)

- [362] Design Hit Counter (counter too much, then need rate limiter) (
- [360] Sort Transformed Array => optimize to O(N)
- [368] Largest Divisible Subset
- [371] Sum of Two Integers
- [373] Find K Pairs with Smallest Sums => start from 2 to K
- [380] Insert Delete GetRandom O(1)
- [381] Insert Delete GetRandom O(1) - Duplicates allowed

- [385] Mini Parser
- [392] Is Subsequence =>
`[Follow-up]`

: large streaming input => can extend to a design question - [412]/[1195] Fizz Buzz => concurrency Multithreaded
- [485]/[487]/[1004] Max Consecutive Ones I/II/III (good
`[Follow-up]`

, flip k times instead 1 time, input is an infinite stream) - [516]/[1682] Longest Palindromic Subsequence I/II
- [539] Minimum Time Difference (real usecase)
- [560] Subarray Sum Equals K => 持续优化
- [650]/[651] 2 Keys Keyboard / 4 Keys Keyboard (dp/recursion convert)
- [653] Two Sum IV - Input is a BST (bfs+dfs)
- [811] Subdomain Visit Count
- [718] Maximum Length of Repeated Subarray (extend to: longest shared view history of 2 users)

- [1059] All Paths from Source Lead to Destination (typical graph traverse, dfs+bfs)
- [1114] Print in Order (latch)
- [1135] Connecting Cities With Minimum Cost (UnionFind, 两种graph处理方式)
- [1976] Number of Ways to Arrive at Destination

- [1236]/[1242] Web Crawler / Multithreaded (with
`[Follow-up]`

) => start from single thread, then multi-thread, then multi-host - [1258] Synonymous Sentences (big-O analysis)
- [1265] Print Immutable Linked List in Reverse (good
`[Follow-up]`

) - [1419] Minimum Number of Frogs Croaking (increasing then converge)
- [1597] Build Binary Expression Tree From Infix Expression (in-order style)
- [1673] Find the Most Competitive Subsequence (单调栈)
- [1788] Maximize the Beauty of the Garden (brute force to optimize, nice way to check 2nd appearance)

##### 2. tag [SQL]

- [182]/[196] Duplicate Emails => Delete Duplicate Emails (delete clause)
- insert clause: INSERT INTO table_name (column1, column2, column3, …) VALUES (value1, value2, value3, …)
- update clause: update table set a=1 where b=2

- [181]/[184]/[185] 181. Employees Earning More Than Their Managers => 184. Department Highest Salary => [185] Department Top Three Salaries
- [262] Trips and Users (xxxDate between a and b)
- [550] - Game Play Analysis IV (DATEDIFF)
- [612] Shortest Distance in a Plane (cross join)
- [1076] Project Employees II (max record’s rest columns)
- [1084] Sales Analysis III (date compare)
- [1270] All People Report to the Given Manager (sql recursion)
- [1407] Top Travellers (ifnull)
- [1479] Sales by Day of the Week (dayofweek)
- [1555]/[1587] Bank Account Summary I/II
- [1596] The Most Frequently Ordered Products for Each Customer (partition over)
- [1613] common table expression (连续id)
- [1661] Average Time of Process per Machine
- [1699] Number of Calls Between Two Persons (WITH xxx AS)

##### 3. tag [top-100]

##### 4. tag [design]

- [170] Two Sum III - Data structure design
- [211] Design Add and Search Words Data Structure
- [348] Design Tic-Tac-Toe
- [353] Design Snake Game (real life example)
- [355] Design Twitter
- [362] Design Hit Counter =>
`[Follow-up]`

question - [379] Design Phone Directory
- [535] Encode and Decode TinyURL => extend from “Design TinyURL”
- [588] Design In-Memory File System
- [1166] Design File System

- [604] Design Compressed String Iterator
- [443] String Compression

- [622] Design Circular Queue
- [641] Design Circular Deque

- [631] Design Excel Sum Formula
- [635] Design Log Storage System (asked by all interviews for data positions, eg. Apple)
- link to my own resume, cloudwatch team

- [642] Design Search Autocomplete System (asked by Zenefits interview) (TrieNode for search)
- [705] Design HashSet
- [706] Design HashMap
- [707] Design Linked List
- [1188] Design Bounded Blocking Queue (multi-thread)
- [1206] [Hard] Design Skiplist
- [1244] Design A Leaderboard (binary search)
- [1381] Design a Stack With Increment Operation
- [370] Range Addition

- [1396] Design Underground System
- [1472] Design Browser History
- [1500] Design a File Sharing System (
`[Follow-up]`

) - [1603] Design Parking System
- [1628] Design an Expression Tree With Evaluate Function
- [1656] Design an Ordered Stream 没什么意思的题，可以跳过
- [1670] Design Front Middle Back Queue
- [1797] Design Authentication Manager
- [1912] Design Movie Rental System

##### 5. tag [Concurrency]

- [1114] - Print in Order
- [1115] - Print FooBar Alternately
- [1116] - Print Zero Even Odd
- [1117] - Building H2O
- [1188] - Design Bounded Blocking Queue
- [1195] - Fizz Buzz Multithreaded