##### 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
• [21]/[23] Merge Two Sorted Lists => Merge k Sorted Lists (* big-O analysis)
• [56] Merge Intervals
• [88] Merge Sorted Array
• [4] Median of Two Sorted Arrays
• [22] Generate Parentheses
• [32] - Longest Valid Parentheses
• [301] [Hard] Remove Invalid Parentheses
• [24]/[25] Swap Nodes in Pairs => 25. Reverse Nodes in k Group
• [206] Reverse Linked List (bfs + dfs)
• [92] Reverse Linked List II
• [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
• [62]/[63]/[980] Unique Paths I/II/III ==> extend: III return the actual path instead of path-count dfs(*start, 0) => def dfs(i, j, k)
• [66] - Plus One (clean code)
• [68] - Text Justification (主要看modular的能力，否则代码太乱)
• [38] Count and Say (practical question)
• [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
• [416] Partition Equal Subset Sum
• [698] Partition to K Equal Sum Subsets
• [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)
• [85] Maximal Rectangle 最大矩形
• [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)
• [255] Verify Preorder Sequence in Binary Search Tree (bfs + dfs)
• [173] Binary Search Tree Iterator (multiple data structure)
• [1586] Binary Search Tree Iterator II
• [103]/[281] Binary Tree Zigzag Level Order => Zigzag Iterator (good [Follow-up]) (extend to multi-thread design)
• [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 ‘-‘)
• [538] Convert BST to Greater Tree (easy to warm up)
• [114] - Flatten Binary Tree to Linked List
• [108] Convert Sorted Array to Binary Search Tree
• [109] Convert Sorted List to Binary Search Tree
• [111] Minimum Depth of Binary Tree (bfs + dfs)
• [116]/[117] Populating Next Right Pointers in Each Node I/II (bfs + dfs)
• [199] Binary Tree Right Side View (面试简单热身题)
• [314] Binary Tree Vertical Order Traversal 二叉树的竖直遍历
• [121]/[122]/[123]/[188] Best Time to Buy and Sell Stock I,II,III,IV
• [309] Best Time to Buy and Sell Stock with Cooldown => hard, can skip
• [714] Best Time to Buy and Sell Stock with Transaction Fee
• [131]/[132] Palindrome Partitioning I/II => List作为dp，不是数组[]作为dp
• [214] Shortest Palindrome (2 pointer)
• [1745] Palindrome Partitioning IV (good [Follow-up])
• [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)
• [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] 146 LRU Cache / 460 LFU Cache
• [148] Sort List (top down, bottom up => solution analysis)
• [151]/[186]/[557] 151 Reverse Words in a String I (extra space -> in place) => II/III
• [344]/[541]/[345] 344 Reverse String => 541 Reverse String II => 345 Reverse Vowels of a String
• [155] Min Stack (easy, but good test for data structure)
• [716] - Max Stack
• [1381] Design a Stack With Increment Operation
• [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, double-hash)
• [164] - [Hard] Maximum Gap
• [187] - Repeated DNA Sequences (expand to space saving via mask encoding, data compression)
• [189] Rotate Array
• [192]/[347]/[692] 192 Word Frequency (shell script) => 347 Top K Frequent Elements => 692 Top K Frequent Words
• [193] Valid Phone Numbers (shell script)
• [198]/[213]/[337] House Robber I, II, III
• [200]/[305] 200 Number of Islands -> 305 Number of Islands II (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 => 更好条件BST 235 Lowest Common Ancestor of a Binary Search Tree (bfs+dfs)
• [1644]/[1650] - Lowest Common Ancestor of a Binary Tree II/III [Follow-up]
• [1740] Find Distance in a Binary Tree (based on LCA)
• [238] Product of Array Except Self => [Follow-up]
• [239] Sliding Window Maximum
• [480] Sliding Window Median => hard, can skip if no time
• [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 => 1229 Meeting Scheduler
• [254] Factor Combinations
• [266]/[267] Palindrome Permutation I/II
• [247] Strobogrammatic Number II
• [31] Next Permutation
• [46]/[47] Permutations I/II
• [60] Permutation Sequence
• [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 (no duplication, then with duplication) => o(N) solution with quick-sort algorithmn (< or <=)
• [376] Wiggle Subsequence (optimize: dp[] to single variables)
• [290]/[291] Word Pattern I,II
• [293]/[294] Flip Game I,II
• [296] Best Meeting Point
• [317] Shortest Distance from All Buildings [Hard]
• [286] Walls and Gates - bfs+dfs
• [302] Smallest Rectangle Enclosing Black Pixels
• [306] Additive Number => [Follow-up]: print actual value, instead of boolean
• [303] Range Sum Query - Immutable (这一组是各种不常见的变种树结构，有精力再看这组题)
• [304] Range Sum Query 2D - Immutable
• [307] Range Sum Query - Mutable (Binary Indexed Tree)
• [1381] Design a Stack With Increment Operation
• [370] Range Addition (累加的累加, 一维的array)
• [598] Range Addition II 二维的matrix
• [308] Range Sum Query 2D - Mutable (Binary Indexed Tree)
• [310] Minimum Height Trees
• [318] Maximum Product of Word Lengths
• [331] Verify Preorder Serialization of a [Binary Tree]
• [255] Verify Preorder Sequence in Binary Search Tree (no “#” in input)
• [297] Serialize and Deserialize [Binary 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()’
• [341] Flatten Nested List Iterator (dfs+bfs)
• [346] Moving Average from Data Stream => can extend to a system design question
• [295] Find Median from Data Stream => [Follow-up]
• [352] Data Stream as Disjoint Intervals => ([Follow-up] to a design question)
• [480] Sliding Window Median => can skip if no time
• [349]/[350] Intersection of Two Arrays I/II (easy to complex) [Follow-up]
• [1213] Intersection of Three Sorted Arrays
• [2248] Intersection of Multiple Arrays
• [354] Russian Doll Envelopes => 1D=>2D [Follow-up]: can rotate
• [1691] Maximum Height by Stacking Cuboids => 2D to 3D
• [300] Longest Increasing Subsequence => 1D [Follow-up]
• [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])
• [360] Sort Transformed Array => optimize to O(N)
• also callable, [302] Smallest-Rectangle-Enclosing-Black-Pixels
• [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
• [271] Encode and Decode Strings
• [392] Is Subsequence => [Follow-up]: large streaming input => can extend to a design question
• [412]/[1195] 412 Fizz Buzz => 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
• [298] Binary Tree Longest Consecutive Sequence
• [549] Binary Tree Longest Consecutive Sequence II
• [539] Minimum Time Difference (real usecase)
• [560] Subarray Sum Equals K => 持续优化
• [650]/[651] 650. 2 Keys Keyboard / 651. 4 Keys Keyboard (dp/recursion convert)
• [653] Two Sum IV - Input is a BST (bfs+dfs)
• [170] Two Sum III - Data structure design
• [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 (all threading tools)
• [1135] Connecting Cities With Minimum Cost (UnionFind, 两种graph处理方式)
• [1976] Number of Ways to Arrive at Destination
• [1236]/[1242] 1236 Web Crawler / 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], and big-O analytis)
• [1419] Minimum Number of Frogs Croaking (increasing then converge)
• [1597] Build Binary Expression Tree From Infix Expression (in-order style)
• [1628] Design an Expression Tree With Evaluate Function (post-order, with [Follow-up], and abc inheritance)
• [1612] Check If Two Expression Trees are Equivalent ([Follow-up] extend from + only to +/-/*)
• [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
• [176]/[177] Second Highest Salary => Nth Highest Salary
• [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)
##### 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)
• [362] Design Hit Counter => [Follow-up] question
• [379] Design Phone Directory
• [535] Encode and Decode TinyURL => extend from “Design TinyURL”
• [622] Design Circular Queue
• [641] Design Circular Deque
• [635] Design Log Storage System (asked by all interviews for data positions, eg. Apple)
• [642] Design Search Autocomplete System (asked by Zenefits interview) (TrieNode for search)
• [705] Design HashSet
• [706] Design HashMap
• [707] Design Linked List (highly related to [146] 146-LRU-Cache )
• [1188] Design Bounded Blocking Queue (multi-thread)
• [1244] Design A Leaderboard (binary search)
• [1381] Design a Stack With Increment Operation
• [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
• [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 (self.semaphore._value and acquire(2) )
• [1188] - Design Bounded Blocking Queue
• [1195] - Fizz Buzz Multithreaded