##### 0. Pinned Summary

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

##### 1. Favourate
•  Longest Substring Without Repeating Characters
•  Longest Palindromic Substring
•  4Sum => [Follow-up] extend to k-sum
• / Merge Two Sorted Lists => Merge k Sorted Lists (* big-O analysis)
•  Merge Intervals
•  Merge Sorted Array
•  Median of Two Sorted Arrays
•  Generate Parentheses
•  - Longest Valid Parentheses
•  [Hard] Remove Invalid Parentheses
• / Swap Nodes in Pairs => 25. Reverse Nodes in k Group
•  Reverse Linked List (bfs + dfs)
•  Reverse Linked List II
•  Next Permutation
• / Search in Rotated Sorted Array I/II (weird…but worth noted)
•  - Find First and Last Position of Element in Sorted Array
• /// 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
•  combinations (dfs+bfs)
•  - Trapping Rain Water (多重解法)
•  - Hard Trapping Rain Water II (2D to 3D)
•  - Wildcard Matching
•  - Rotate Image
•  Group Anagrams
•  - Maximum Subarray O(N)
•  Maximum Subarray Sum After One Operation (good dp)
• / Jump Game I/II
• // Unique Paths I/II/III ==> extend: III return the actual path instead of path-count
•  - Plus One (clean code)
•  - Text Justification (主要看modular的能力，否则代码太乱)
•  Count and Say (practical question)
•  - Edit Distance
•  - One Edit Distance
• / Search a 2D Matrix I/II (74 binary search 解法)
•  Minimum Window Substring
• / Subsets I/II
•  Partition Equal Subset Sum
•  Partition to K Equal Sum Subsets
• /// Word Search I => Implement Trie Prefix Tree => Word Search II => Add and Search Word (Data structure design)
•  Largest Rectangle in Histogram (hard…if time allows)
•  Maximal Rectangle 最大矩形
•  Binary Tree Inorder Traversal (iteration)
•  Same Tree (二叉树的四种遍历(层序，先序，中序，后序)均有各自的迭代和递归的写法)
• / Unique Binary Search Trees I/II (II 另类DP)
•  Different Ways to Add Parentheses
•  Interleaving String
•  Validate Binary Search Tree (bfs + dfs)
•  Verify Preorder Sequence in Binary Search Tree (bfs + dfs)
•  Binary Search Tree Iterator (multiple data structure)
•  Binary Search Tree Iterator II
• / Binary Tree Zigzag Level Order => Zigzag Iterator (good [Follow-up]) (extend to multi-thread design)
•  ZigZag <= bad one, skip it
•  Construct Binary Tree from Preorder and Inorder Traversal
•  Construct Binary Tree from Inorder and Postorder Traversal
•  Construct Binary Tree from Preorder and Postorder Traversal
•  Construct Binary Tree from String (start from no ‘-‘, then expand to support ‘-‘)
•  Convert Sorted Array to Binary Search Tree
•  Convert Sorted List to Binary Search Tree
•  Convert BST to Greater Tree (easy to warm up)
•  - Flatten Binary Tree to Linked List
•  - Populating Next Right Pointers in Each Node (bfs + dfs)
•  Minimum Depth of Binary Tree (bfs + dfs)
• / Populating Next Right Pointers in Each Node I/II (bfs + dfs)
•  Binary Tree Right Side View (面试简单热身题)
•  Binary Tree Vertical Order Traversal 二叉树的竖直遍历
• /// Best Time to Buy and Sell Stock I,II,III,IV
•  Best Time to Buy and Sell Stock with Cooldown => hard, can skip
•  Best Time to Buy and Sell Stock with Transaction Fee
• / Palindrome Partitioning I/II => List作为dp，不是数组[]作为dp
•  Shortest Palindrome (2 pointer)
•  Palindrome Partitioning IV (good [Follow-up])
• // Single Number I,II,III
•  Biggest-Single-Number => do it in SQL
• // Strobogrammatic Number I,II,III
• // Ugly Number I,II => Super Ugly Number
•  Additive Number => [Follow-up]: print actual value, instead of boolean
•  Add Strings (should ask before 306)
•  Count of Smaller Numbers After Self
•  Copy List with Random Pointer => no extra space solution
• skip- Linked List Random Node => math-stats “rn = rd.nextInt(idx);” 水塘抽样 Reservoir Sampling
• / Linked List Cycle I/II
• / LRU Cache / LFU Cache
•  Sort List (top down, bottom up => solution analysis)
• // Reverse Words in a String I (extra space -> in place) => II/III
• // 344 Reverse String => 541 Reverse String II => 345 Reverse Vowels of a String
•  Min Stack (easy, but good test for data structure)
•  - Max Stack
•  Design a Stack With Increment Operation
• / Longest Substring with At Most Two or K Distinct Characters
•  Longest Substring Without Repeating Characters ==> At Most One Distinct Characters
•  Longest Substring with [At Least] K [Repeating] Characters
• [MyNote] Longest Substring with [At Most] K [Repeating] Characters
•  Number of Distinct Substrings in a String ([Follow-up] o-N solution, double-hash)
•  - [Hard] Maximum Gap
•  - Repeated DNA Sequences (expand to space saving via mask encoding, data compression)
•  Rotate Array
• // Word Frequency => Top K Frequent Elements => Top K Frequent Words
•  Valid Phone Numbers (shell script)
• // House Robber I, II, III
• / Number of Islands -> extend from 2D to 3D
•  Kth Largest Element in an Array
• // Contains Duplicate I/II/III
•  [Hard] The Skyline Problem
•  Count Complete Tree Nodes
• // [Tricky-NotSoGood] Basic Calculator I/II/III
•  Implement Stack using Queues
•  Implement Queue using Stacks
•  Kth Smallest Element in a BST (multiple solutions, + good [Follow-up])
•  Kth Smallest Element in a Sorted Matrix
• / 236 Lowest Common Ancestor of a Binary Tree => 235 更好条件BST 优化 Lowest Common Ancestor of a Binary Search Tree (bfs+dfs)
• / - Lowest Common Ancestor of a Binary Tree II/III [Follow-up]
•  Find Distance in a Binary Tree (based on LCA)
•  Product of Array Except Self => [Follow-up]
•  Sliding Window Maximum
•  Sliding Window Median => hard, can skip if no time
•  Different Ways to Add Parentheses
• // Shortest Word Distance I,II,III
•  Group Shifted Strings
•  Count Univalue Subtrees (bottom up and top down)
•  Flatten 2D Vector => great hints
• // Meeting Rooms I,II => Meeting Scheduler
•  Factor Combinations
• / Palindrome Permutation I/II
•  Strobogrammatic Number II
•  Next Permutation
• / Permutations I/II
•  Permutation Sequence
•  [Hard] Alien Dictionary (dfs+bfs)
• / Closest Binary Search Tree Value I,II => optimize solution, from binary-tree to BST
•  Integer to English Words (real use case)
•  Find the Celebrity ([Follow-up] reduce api call)
• / Wiggle Sort I,II => o(N) solution with quick-sort algorithmn (< or <=)
•  Wiggle Subsequence (optimize: dp[] to single variables)
• / Word Pattern I,II
• / Flip Game I,II
•  Best Meeting Point
•  [Hard] Shortest Distance from All Buildings
•  Walls and Gates - bfs+dfs
•  Smallest Rectangle Enclosing Black Pixels
•  Additive Number => [Follow-up]: print actual value, instead of boolean
•  Range Sum Query - Immutable (这一组是各种不常见的变种树结构，有精力再看这组题)
•  Range Sum Query 2D - Immutable
•  Range Sum Query - Mutable
•  Design a Stack With Increment Operation
•  Range Addition (累加的累加, 一维的array)
•  Range Addition II 二维的matrix
•  Range Sum Query 2D - Mutable
•  Minimum Height Trees
•  Maximum Product of Word Lengths
•  Verify Preorder Serialization of a [Binary Tree]
•  Verify Preorder Sequence in Binary Search Tree
•  Serialize and Deserialize [Binary Tree]
•  Serialize and Deserialize [N-ary Tree] (297 binary to this n-nary)
•  Serialize and Deserialize BST (297 binary-tree to BST, optimization)
•  Recover [Binary Search Tree]
•  Correct a Binary Tree (new bfs level marking)
•  Coin Change
•  Number of Connected Components in an Undirected Graph (connected component search)
•  Largest BST Subtree => o(N) (dfs+bfs)
•  Increasing Triplet Subsequence => optimize: O(n) time complexity and O(1) space complexity
• / Nested List Weight Sum I,II
•  Mini Parser (dfs + bfs) => [Follow-up] add new method ‘serialize()’
•  Flatten Nested List Iterator (dfs+bfs)
•  Moving Average from Data Stream => can extend to a system design question
•  Find Median from Data Stream => [Follow-up]
•  Data Stream as Disjoint Intervals => ([Follow-up] to a design question)
•  Sliding Window Median => can skip if no time
• / Intersection of Two Arrays I/II (easy to complex) [Follow-up]
•  Russian Doll Envelopes => 1D=>2D [Follow-up]: can rotate
•  Maximum Height by Stacking Cuboids => 2D to 3D
•  Longest Increasing Subsequence => 1D [Follow-up]
•  Rearrange String k Distance Apart
•  Logger Rate Limiter (extend to throttle, load balancing, etc.)
•  Design Hit Counter (counter too much, then need rate limiter) ([Follow-up])
•  Sort Transformed Array => optimize to O(N)
•  Largest Divisible Subset
•  Sum of Two Integers
•  Find K Pairs with Smallest Sums => start from 2 to K
•  Insert Delete GetRandom O(1)
•  Insert Delete GetRandom O(1) - Duplicates allowed
•  Mini Parser
•  Encode and Decode Strings
•  Is Subsequence => [Follow-up]: large streaming input => can extend to a design question
• / Fizz Buzz => concurrency Multithreaded
• // Max Consecutive Ones I/II/III (good [Follow-up], flip k times instead 1 time, input is an infinite stream)
• / Longest Palindromic Subsequence I/II
•  Binary Tree Longest Consecutive Sequence
•  Binary Tree Longest Consecutive Sequence II
•  Minimum Time Difference (real usecase)
•  Subarray Sum Equals K => 持续优化
• / 2 Keys Keyboard / 4 Keys Keyboard (dp/recursion convert)
•  Two Sum IV - Input is a BST (bfs+dfs)
•  Subdomain Visit Count
•  Maximum Length of Repeated Subarray (extend to: longest shared view history of 2 users)
•  All Paths from Source Lead to Destination (typical graph traverse, dfs+bfs)
•  Print in Order (latch)
•  Connecting Cities With Minimum Cost (UnionFind, 两种graph处理方式)
•  Number of Ways to Arrive at Destination
• / Web Crawler / Multithreaded (with [Follow-up]) => start from single thread, then multi-thread, then multi-host
•  Synonymous Sentences (big-O analysis)
•  Print Immutable Linked List in Reverse (good [Follow-up])
•  Minimum Number of Frogs Croaking (increasing then converge)
•  Build Binary Expression Tree From Infix Expression (in-order style)
•  Design an Expression Tree With Evaluate Function (post-order, with [Follow-up])
•  Check If Two Expression Trees are Equivalent ([Follow-up] extend from + only to +/-/*)
•  Find the Most Competitive Subsequence (单调栈)
•  Maximize the Beauty of the Garden (brute force to optimize, nice way to check 2nd appearance)
##### 2. tag [SQL]
• / 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. Employees Earning More Than Their Managers => 184. Department Highest Salary =>  Department Top Three Salaries
• / Second Highest Salary => Nth Highest Salary
•  Trips and Users (xxxDate between a and b)
•  - Game Play Analysis IV (DATEDIFF)
•  Shortest Distance in a Plane (cross join)
•  Project Employees II (max record’s rest columns)
•  Sales Analysis III (date compare)
•  All People Report to the Given Manager (sql recursion)
•  Top Travellers (ifnull)
•  Sales by Day of the Week (dayofweek)
• / Bank Account Summary I/II
•  The Most Frequently Ordered Products for Each Customer (partition over)
•  common table expression (连续id)
•  Average Time of Process per Machine
•  Number of Calls Between Two Persons (WITH xxx AS)
##### 4. tag [design]
•  Two Sum III - Data structure design
•  Design Add and Search Words Data Structure
•  Design Tic-Tac-Toe
•  Design Snake Game (real life example)
•  Design Hit Counter => [Follow-up] question
•  Design Phone Directory
•  Encode and Decode TinyURL => extend from “Design TinyURL”
•  Design Compressed String Iterator
•  String Compression
•  Design Circular Queue
•  Design Circular Deque
•  Design Excel Sum Formula
•  Design Log Storage System (asked by all interviews for data positions, eg. Apple)
• link to my own resume, cloudwatch team
•  Design Search Autocomplete System (asked by Zenefits interview) (TrieNode for search)
•  Design HashSet
•  Design HashMap
•  Design Bounded Blocking Queue (multi-thread)
•  [Hard] Design Skiplist
•  Design A Leaderboard (binary search)
•  Design a Stack With Increment Operation
•  Design Underground System
•  Design Browser History
•  Design a File Sharing System ([Follow-up])
•  Design Parking System
•  Design an Expression Tree With Evaluate Function
•  Design an Ordered Stream 没什么意思的题，可以跳过
•  Design Front Middle Back Queue
•  Design Authentication Manager
•  Design Movie Rental System
##### 5. tag [Concurrency]
•  - Print in Order
•  - Print FooBar Alternately
•  - Print Zero Even Odd
•  - Building H2O
•  - Design Bounded Blocking Queue
•  - Fizz Buzz Multithreaded