Software Engineer Interview

Author: [email protected]

Table of Contents

• Interview Preparation
• Languages and Data Structures
  • Java
    • Java Overview and Features
    • Data Structures in Java
  • Python
    • Python Overview and Features
    • Data Structures in Python
  • Go
    • Go Overview and Features
    • Data Structures in Go
• Algorithms
  • Computational Complexity
  • Basic Algorithms
    • Backtracking
    • Divide and Conquer
    • Dynamic Programming
    • Greedy
    • Enumeration
  • Sort Algorithms
    • O(n^2) Solutions
    • O(nlogn) Solutions
    • O(n) Solutions
  • Search Algorithms
    • Graph Search
    • Linear List Search
    • Search Tree
  • Other Algorithms
  • More Readings
• System Design
• Coding Preparation
  • LeetCode Current Status
  • LintCode Current Status
  • Easy Questions
  • Medium Questions
  • Hard Questions

Interview Preparation

• Interview Formats
• Mindset for Interview
• Self-Introduction
• Coding Interview
• System Design Interview
• Behavioral Interview
• Questions To Ask

Languages and Data Structures

Java

Java is a general-purpose programming language that is class-based, object-oriented, and designed to have as few implementation dependencies as possible. It is intended to let application developers write once, run anywhere, meaning that compiled Java code can run on all platforms that support Java without the need for recompilation.

Java Overview and Features

• Java Introduction
• Java Virtual Machine (JVM)
• Garbage Collection
• Generics in Java
• Concurrency in Java
• Lambda Expressions in Java
• I/O in Java

Data Structures in Java

• Array
• String
• Collection
  • Set
    • Union Find (Disjoint Set)
  • List
    • ArrayList
    • LinkedList
  • Stack
  • Queue
    • PriorityQueue
    • Deque
  • Map
    • HashMap
    • HashTable
    • TreeMap
• Tree
  • Binary Search Tree
  • Segment Tree
  • Trie
• Graph
  • Breadth-First Search
  • Depth-First Search
  • Shortest Path
  • Topological Sort

Python

Python is an interpreted, high-level, general-purpose programming language. Python's design philosophy emphasizes code readability with its notable use of significant whitespace (indentation). Python is dynamically typed and garbage-collected.

Python Overview and Features

Data Structures in Python

• Array and Sequence
  • Range
  • String
  • List
  • Tuple
• Linked List
  • Singly Linked List
  • Doubly Linked List
• Stack And Queue
  • Deque
• Priority Queue
• Hash Table
• Tree
• Graph

Go

Go is a statically typed, compiled programming language designed at Google. Go is syntactically similar to C, but with memory safety, garbage collection, structural typing, and CSP-style concurrency.

Go Overview and Features

Data Structures in Go

• Basic Data Structures
  • Array
  • Slice
  • Map
  • Struct
• Linked List
• Queue
• Stack
• Set
• Tree
• Graph

Algorithms

Algorithm is one of core parts in computer science. This section covers the algorithms in tech interviews.

An algorithm must possess the following five properties:

• input: an algorithm has zero or more inputs, taken from a specified set of objects.
• output: an algorithm has one or more outputs, which have a specified relation to the inputs.
• finiteness: the algorithm must always terminate after a finite number of steps.
• definiteness: Each step must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.
• effectiveness: all operations to be performed must be sufficiently basic that they can be done exactly and in finite length.

As the restriction of whiteboard coding and the properties of algorithm, most of interview questions can be resolved in ~50 lines of code.

Computational Complexity

The computational complexity of an algorithm is the amount of resources required to run it. Particular focus is given to time and space requirements.

• Time Complexity
• Space Complexity

Basic Algorithms

• Backtracking
• Divide and Conquer
• Dynamic Programming
• Greedy
• Enumeration

Sort Algorithms

Sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

O(n^2) Solutions

• Bubble Sort
• Insertion Sort
• Selection Sort
• ShellSort

O(nlogn) Solutions

• Quicksort
• Merge Sort
• Heapsort
• Tree Sort

O(n) Solutions

• Bucket Sort
• Counting Sort
• Radix Sort

Search Algorithms

Graph Search

• Depth-First Search
• Breadth-First Search
• A-Star(A*) Search

Linear List Search

• Linear Search
• Binary Search
• Special Search Algorithms
  • Knuth–Morris–Pratt (KMP) Algorithm

Search Tree

• Binary Search Tree
• B-tree
• (a,b)-tree

Other Algorithms

It is very rare to see bit or math questions in real interviews. So we don't need to spend lots of time here.

• Bit Manipulation
• Math

More Readings

• Introduction to Algorithms
• MIT 6.006 Introduction to Algorithms

System Design

• System Design Basics
  • Distributed System
  • Cluster
  • Load Balancing
  • Message Queue
  • Cache
    • CDN
  • Database
    • SQL
    • NoSQL
  • Networking
    • Networking Basic
    • HTTP
    • RESTful API
    • WebSocket
  • Security
• Popular System Design Questions
  • Designing a URL shortening service
  • Designing Instagram
  • Designing Facebook Messenger
  • Designing Facebook Newsfeed

The purpose of a system design interview is to assess a candidate's ability to design and understand complex systems. It's a crucial part of the hiring process for roles that involve system architecture and engineering.

The general approach I'd like to suggest is,

• Requirements Gathering
  • Gather functional & non-functional requirements
    • Functional requirements
      • Users can do A, B, C, D
    • Non-functional requirements
      • Availability
      • Scalability
      • Reliability
      • Performance
        • Round-Trip Time (RTT) or Latency
        • Throughput or Bandwidth
  • Clarify restrictions and limitations
  • Estimate system resources
• Decision-making Process
  • High level design
    • System architecture
    • Service API
    • Data schema
  • Component walkthrough
  • Optimization
• Balancing Trade-offs

Coding Preparation

How to use LeetCode

LeetCode Current Status

• Total: 426
  • 📗Easy: 153
  • 📘Medium: 215
  • 📙Hard: 58

LintCode Current Status

• Total: 53
  • 📗Easy: 11
  • 📘Medium: 32
  • 📙Hard: 10

Notes

• I use LintCode as the supplement of LeetCode for the locked questions.
• I usually skip the hard math questions, since it is almost impossible to see them in a real interview.

Easy Questions

#	Name	Solution	Algorithm	Note
1	Two Sum	Java Python Go	HashMap
7	Reverse Integer	Java	Number
9	Palindrome Number	Java	Number
13	Roman to Integer	Java	Map
14	Longest Common Prefix	Java	Loop	More solutions
20	Valid Parentheses	Java Python	Stack
21	Merge Two Sorted Lists	Java	Loop
26	Remove Duplicates from Sorted Array	Java	Two-Pointer
27	Remove Element	Java	Single Pointer
28	Implement strStr()	Java	String
35	Search Insert Position	Java	String
38	Count and Say	Java	Number
53	Maximum Subarray	Java	DP
58	Length of Last Word	Java	String
66	Plus One	Java	Loop
67	Add Binary	Java	Loop
69	Sqrt(x)	Java	Math	Apply Newton's Method
70	Climbing Stairs	Java	1D DP
83	Remove Duplicates from Sorted List	Java	Two-Pointer
88	Merge Sorted Array	Java	Two-Pointer
100	Same Tree	Java	Recursion
101	Symmetric Tree	Java	Recursion
104	Maximum Depth of Binary Tree	Java	DFS
107	Binary Tree Level Order Traversal II	Java	DFS + BFS
108	Convert Sorted Array to Binary Search Tree	Java	Recursion
110	Balanced Binary Tree	Java	DFS
111	Minimum Depth of Binary Tree	Java	DFS
112	Path Sum	Java	DFS
118	Pascal's Triangle	Java	Array
119	Pascal's Triangle II	Java	1D DP
121	Best Time to Buy and Sell Stock	Java	DP
122	Best Time to Buy and Sell Stock II	Java	Greedy
125	Valid Palindrome	Java	Two-Pointer
136	Single Number	Java	Bit
141	Linked List Cycle	Java	LinkedList
155	Min Stack	Java Python	Stack
157	Read N Characters Given Read4	Java	Stream
160	Intersection of Two Linked Lists	Java Python	LinkedList
167	Two Sum II - Input array is sorted	Java	Two-Pointer
168	Excel Sheet Column Title	Java	Math
169	Majority Element	Java	Array	Moore's voting algorithm
170	Two Sum III - Data structure design	Java	HashMap
171	Excel Sheet Column Number	Java	Math
172	Factorial Trailing Zeroes	Java	Math
189	Rotate Array	Java	Array
190	Reverse Bits	Java	Bit
191	Number of 1 Bits	Java	Bit
198	House Robber	Java	1D DP
202	Happy Number	Java	Set
203	Remove Linked List Elements	Java	LinkedList
204	Count Primes	Java	Math	Sieve of Eratosthenes
205	Isomorphic Strings	Java	Map
206	Reverse Linked List	Java	LinkedList
217	Contains Duplicate	Java	Set
219	Contains Duplicate II	Java	Two-Pointer
225	Implement Stack using Queues	Java	Queue
226	Invert Binary Tree	Java	DFS
231	Power of Two	Java	Bit Manipulation
232	Implement Queue using Stacks	Java	Stack
234	Palindrome Linked List	Java	Two-Pointer	Reversing a list is not considered "O(1) space"
235	Lowest Common Ancestor of a Binary Search Tree	Java	DFS
237	Delete Node in a Linked List	Java	LinkedList	This is a stupid question
242	Valid Anagram	Java	Counting Sort
243	Shortest Word Distance	Java	Greedy	LintCode 924
246	Strobogrammatic Number	Java	Two-Pointer	LintCode 644
252	Meeting Rooms	Java	Sort	LintCode 920
256	Paint House	Java	1D DP	LintCode 515 as medium
257	Binary Tree Paths	Java	DFS
258	Add Digits	Java	Number
263	Ugly Number	Java	Math
266	Palindrome Permutation	Java	Counting sort	LintCode 916
268	Missing Number	Java	Counting	Bit manipulation solution using XOR is here
270	Closest Binary Search Tree Value	Java	DFS	LintCode 900
276	Paint Fence	Java	1D DP	LintCode 514
278	First Bad Version	Java	Binary Search
283	Move Zeroes	Java	Two-Pointer
290	Word Pattern	Java	HashMap
292	Nim Game	Java	Minimax
293	Flip Game	Java	Loop	LintCode 914
299	Bulls and Cows	Java	Counting
303	Range Sum Query - Immutable	Java	Segment Tree
326	Power of Three	Java	Math
339	Nested List Weight Sum	Java	Recursion	LintCode 551
344	Reverse String	Java	Two Pointer
346	Moving Average from Data Stream	Java	Sliding Window	LintCode 642
367	Valid Perfect Square	Java	Math
374	Guess Number Higher or Lower	Java	Binary Search
383	Ransom Note	Java	Letter Count
401	Binary Watch	Java	bit
408	Valid Word Abbreviation	Java	String	LintCode 637
409	Longest Palindrome	Java	String
422	Valid Word Square	Java	String	LintCode 888
437	Path Sum III	Java	DFS	Deserve as medium
443	String Compression	Java	Two-Pointer
459	Repeated Substring Pattern	Java	String
485	Max Consecutive Ones	Java	1D DP
530	Minimum Absolute Difference in BST	Java	In-order Traversal
541	Reverse String II	Java	Two Pointer
543	Diameter of Binary Tree	Java	DFS
551	Student Attendance Record I	Java	Array
557	Reverse Words in a String III	Java	Two Pointer
561	Array Partition I	Java	Math
572	Subtree of Another Tree	Java	Recursion	Converting to string is a brilliant idea
575	Distribute Candies	Java	Greedy
594	Longest Harmonious Subsequence	Java	HashMap
628	Maximum Product of Three Numbers	Java	Greedy?
680	Valid Palindrome II	Java	String
700	Search in a Binary Search Tree	Java	BinarySearch
703	Kth Largest Element in a Stream	Java	MinQueue
704	Binary Search	Java	BinarySearch
709	To Lower Case	Java	String
720	Longest Word in Dictionary	Java	HashSet
724	Find Pivot Index	Java	Prefix/Suffix Sum
728	Self Dividing Numbers	Java	Math
733	Flood Fill	Java	DFS
748	Shortest Completing Word	Java	String
746	Min Cost Climbing Stairs	Java	1D DP
766	Toeplitz Matrix	Java	Matrix
771	Jewels and Stones	Java	Set
783	Minimum Distance Between BST Nodes	Java	DFS
788	Rotated Digits	Java	DP	There is O(lgn) solution, but very tricky!
796	Rotate String	Java	String	The rolling hash solution is great!
821	Shortest Distance to a Character	Java	MinArray
852	Peak Index in a Mountain Array	Java	BinarySearch
844	Backspace String Compare	Java	Stack	Two pointers starting from the end is better in term of space performance
849	Maximize Distance to Closest Person	Java	DP
859	Buddy Strings	Java	StringLoop/LetterCount
860	Lemonade Change	Java	Greedy
867	Transpose Matrix	Java	Loop
872	Leaf-Similar Trees	Java	DFS
876	Middle of the Linked List	Java	LinkedList
884	Uncommon Words from Two Sentences	Java	String
905	Sort Array By Parity	Java	Array
908	Smallest Range I	Java	Math
917	Reverse Only Letters	Java	Two-Pointer
922	Sort Array By Parity II	Java	Read/Write Head
994	Rotting Oranges	Java	BFS
1022	Sum of Root To Leaf Binary Numbers	Java	DFS
1025	Divisor Game	Java	1D DP	Solution with constant time
1047	Remove All Adjacent Duplicates In String	Java	Stack
1281	Subtract the Product and Sum of Digits of an Integer	Java	Number
1337	The K Weakest Rows in a Matrix	Java	MaxQueue

Medium Questions

#	Name	Solution	Algorithm	Note
2	Add Two Numbers	Java Python	Linked List
3	Longest Substring Without Repeating Characters	Java	Two-Pointer
5	Longest Palindromic Substring	Java	2D DP	Manacher's Algorithm is the optimal solution
6	ZigZag Conversion	Java	String
8	String to Integer (atoi)	Java	String
11	Container With Most Water	Java	Two-Pointer/Greedy
12	Integer to Roman	Java	Number
15	Three Sum	Java Python	Two-Pointer
16	3Sum Closest	Java Python	Two-Pointer
17	Letter Combinations of a Phone Number	Java	Backtracking (DFS)
18	4Sum	Java	Two-Pointer
19	Remove Nth Node From End of List	Java	Two-Pointer
22	Generate Parentheses	Java Python	Backtracking (DFS)
24	Swap Nodes in Pairs	Java	Recursion
29	Divide Two Integers	Java	Bit
31	Next Permutation	Java	Math
33	Search in Rotated Sorted Array	Java	Binary Search
34	Find First and Last Position of Element in Sorted Array	Java	Binary Search
36	Valid Sudoku	Java	Matrix
39	Combination Sum	Java	Backtracking (DFS)
40	Combination Sum II	Java	Backtracking (DFS)
43	Multiply Strings	Java	Loop
46	Permutations	Java	Backtracking (BFS & DFS)
47	Permutations II	Java	Backtracking (BFS & DFS)
48	Rotate Image	Java	Matrix
49	Group Anagrams	Java	HashMap/String Signature
50	Pow(x, n)	Java	Math
54	Spiral Matrix	Java	Matrix
55	Jump Game	Java	Greedy
56	Merge Intervals	Java	Sort
59	Spiral Matrix II	Java	Matrix
60	Permutation Sequence	Java	Math
61	Rotate List	Java	LinkedList
62	Unique Paths	Java	2D DP
63	Unique Paths II	Java	2D DP
64	Minimum Path Sum	Java	2D DP
71	Simplify Path	Java	Stack
73	Set Matrix Zeros	Java	Matrix
74	Search a 2D Matrix	Java	Binary Search
75	Sort Colors	Java	Two-Pointer
77	Combinations	Java	Backtracking (DFS)
78	Subsets	Java	Backtracking (BFS & DFS)
79	Word Search	Java	Backtracking (DFS)
80	Remove Duplicates from Sorted Array II	Java	Two-Pointer
81	Search in Rotated Sorted Array II	Java	Binary Search
82	Remove Duplicates from Sorted List II	Java	LinkedList
86	Partition List	Java	LinkedList
89	Gray Code	Java	Bit
90	Subsets II	Java	Backtracking (BFS & DFS)
91	Decode Ways	Java	1D DP
92	Reverse Linked List II	Java	LinkedList
93	Restore IP Addresses	Java	Backtracking & Greedy
94	Binary Tree Inorder Traversal	Java	Tree Traversal
95	Unique Binary Search Trees II	Java	DFS
96	Unique Binary Search Trees	Java	1D DP	Optimized from 2D to 1D
98	Validate Binary Search Tree	Java	DFS
102	Binary Tree Level Order Traversal	Java Python	DFS & BFS
103	Binary Tree Zigzag Level Order Traversal	Java	DFS & BFS
105	Construct Binary Tree from Preorder and Inorder Traversal	Java	Recursion
106	Construct Binary Tree from Inorder and Postorder Traversal	Java	Recursion
109	Convert Sorted List to Binary Search Tree	Java	D&C
113	Path Sum II	Java	Backtracking (DFS)
114	Flatten Binary Tree to Linked List	Java	BFS & DFS
116	Populating Next Right Pointers in Each Node	Java	Loop
117	Populating Next Right Pointers in Each Node II	Java	Loop
120	Triangle	Java	1D DP
127	Word Ladder	Java	Backtracking (BFS & DFS)	LeetCode needs some optimization to pass TLE, which I think is an overkill
129	Sum Root to Leaf Numbers	Java	DFS
130	Surrounded Regions	Java	BFS & DFS	Union Find solution
131	Palindrome Partitioning	Java	Backtracking (DFS) + DP + Recursion
133	Clone Graph	Java	DFS + BFS
134	Gas Station	Java	Greedy
137	Single Number II	Java	Bit + Set	Great explanation of this type of questions is here
138	Copy List with Random Pointer	Java	HashMap	Space complexity can be optimized to O(1) as here
139	Word Break	Java	1D DP
142	Linked List Cycle II	Java	LinkedList
143	Reorder List	Java	LinkedList
144	Binary Tree Preorder Traversal	Java	Stack
146	LRU Cache	Java	HashMap & DoublyLinkedList	Deserve as hard
147	Insertion Sort List	Java	LinkedList
148	Sort List	Java	LinkedList
150	Evaluate Reverse Polish Notation	Java	Stack
151	Reverse Words in a String	Java	String	Should be an easy one
152	Maximum Product Subarray	Java	1D DP
153	Find Minimum in Rotated Sorted Array	Java	Binary Search
156	Binary Tree Upside Down	Java	Stack	LintCode 649
159	Longest Substring with At Most Two Distinct Characters	Java	Two-Pointer	LintCode 928 as Hard
161	One Edit Distance	Java	String	LintCode 640
162	Find Peak Element	Java	BinarySearch
163	Missing Ranges	Java	Loop	LintCode 641
165	Compare Version Numbers	Java	String
166	Fraction to Recurring Decimal	Java	HashMap	Should be as hard
173	Binary Search Tree Iterator	Java	BFS+Stack
179	Largest Number	Java	Sort
186	Reverse Words in a String II	Java	Two-Pointer	LintCode 927
187	Repeated DNA Sequences	Java	HashMap
199	Binary Tree Right Side View	Java	DFS & BFS
200	Number of Islands	Java	DFS & BFS
201	Bitwise AND of Numbers Range	Java	Bit
207	Course Schedule	Java	Topological Sort
208	Implement Trie (Prefix Tree)	Java	Trie
209	Minimum Size Subarray Sum	Java	Sliding Window
210	Course Schedule II	Java	Topological Sort
211	Add and Search Word - Data structure design	Java	Trie+Backtracking
213	House Robber II	Java	1D DP
215	Kth Largest Element in an Array	Java	Heap Sort	A better solution uses Selection algorithm with shuffling
216	Combination Sum III	Java	Backtracking (DFS)
220	Contains Duplicate III	Java	TreeMap	TLE on LeetCode OJ (it's a boring question)
221	Maximal Square	Java	DP
222	Count Complete Tree Nodes	Java	DFS
223	Rectangle Area	Java	Math
227	Basic Calculator II	Java	Deque	A better solution uses a single stack
228	Summary Ranges	Java	Two-Pointer
229	Majority Element II	Java	Boyer-Moore Majority Voting Algorithm
230	Kth Smallest Element in a BST	Java	DFS
236	Lowest Common Ancestor of a Binary Tree	Java	DFS
238	Product of Array Except Self	Java	1D DP	This solution uses O(1) space
240	Search a 2D Matrix II	Java	Divide and Conquer
241	Different Ways to Add Parentheses	Java	Recursion
247	Strobogrammatic Number II	Java	Recursion	LintCode 776
250	Count Univalue Subtrees	Java	DFS	LintCode 921
251	Flatten 2D Vector	Java	Two-Pointer	LintCode 601
253	Meeting Rooms II	Java	Greedy	LintCode 919
254	Factor Combinations	Java	Backtracking (DFS)	LintCode 1308
255	Verify Preorder Sequence in Binary Search Tree	Java	Divide and Conquer	LintCode 1307
259	3Sum Smaller	Java	Two-Pointer	LintCode 918
260	Single Number III	Java	Bit	It's a hard question to achieve Space O(1)
261	Graph Valid Tree	Java	UnionFind	LintCode 178
264	Ugly Number II	Java	1D DP
267	Palindrome Permutation II	Java	Backtracking (DFS)	LintCode 917
271	Encode and Decode Strings	Java	String	LintCode 659
274	H-Index	Java	Sort & Map
275	H-Index II	Java	BinarySearch
277	Find the Celebrity	Java	Two-Pointer & Stack & Graph	LintCode 645
279	Perfect Squares	Java	1D DP
280	Wiggle Sort	Java	Greedy	LintCode 508
281	Zigzag Iterator	Java	List	LintCode 540
284	Peeking Iterator	Java	Design
285	Inorder Successor in BST	Java	DFS	LintCode 448
286	Walls and Gates	Java	BFS	LintCode 663
287	Find the Duplicate Number	Java	Two-Pointer
288	Unique Word Abbreviation	Java	HashMap	LintCode 648
289	Game of Life	Java	Bit
294	Flip Game II	Java	Backtracking (DFS)	LintCode 913
298	Binary Tree Longest Consecutive Sequence	Java	DFS	LintCode 595
300	Longest Increasing Subsequence	Java	1D DP	Binary search solution is more optimal
304	Range Sum Query 2D - Immutable	Java	Matrix
306	Additive Number	Java	Backtracking (DFS)
307	Range Sum Query - Mutable	Java	Segment Tree
309	Best Time to Buy and Sell Stock with Cooldown	Java	1D DP
310	Minimum Height Trees	Java	BFS
311	Sparse Matrix Multiplication	Java	List	LintCode 654
314	Binary Tree Vertical Order Traversal	Java	DFS + HashMap	LintCode 651 (LintCode OJ is incorrect)
318	Maximum Product of Word Lengths	Java	Bit-Manipulation
319	Bulb Switcher	Java	Math
320	Generalized Abbreviation	Java	Backtracking (DFS)	LintCode 779
322	Coin Change	Java	1D DP
325	Maximum Size Subarray Sum Equals k	Java	HashMap	LintCode 911
328	Odd Even Linked List	Java	LinkedList
331	Verify Preorder Serialization of a Binary Tree	Java	DFS	Non-cursive solution based on graph theory
332	Reconstruct Itinerary	Java	Greedy
334	Increasing Triplet Subsequence	Java	Loop
337	House Robber III	Java	Backtracking (DFS)
338	Counting Bits	Java	Bit
341	Flatten Nested List Iterator	Java	Recursion
343	Integer Break	Java	Math
347	Top K Frequent Elements	Java	HashMap + Heap
357	Count Numbers with Unique Digits	Java	Math
361	Bomb Enemy	Java	DP	LintCode 553
366	Find Leaves of Binary Tree	Java	DFS	LintCode 650
369	Plus One Linked List	Java	Recursion	LintCode 904
370	Range Addition	Java	Array	LintCode 903
373	Find K Pairs with Smallest Sums	Java	Heap
376	Wiggle Subsequence	Java	1D DP
377	Combination Sum IV	Java	1D DP
378	Kth Smallest Element in a Sorted Matrix	Java	Min Heap
380	Insert Delete GetRandom O(1)	Java	HashMap
382	Linked List Random Node	Java	LinkedList	It's essentially a math question (Reservoir Sampling).
384	Shuffle an Array	Java	Math	Fisher–Yates shuffle
385	Mini Parser	Java	Recursion
386	Lexicographical Numbers	Java	DFS
388	Longest Absolute File Path	Java	Stack
394	Decode String	Java	Stack & DFS	Deserve as hard
397	Integer Replacement	Java	Bit
402	Remove K Digits	Java	Greedy
406	Queue Reconstruction by Height	Java	Greedy
413	Arithmetic Slices	Java	1D DP
416	Partition Equal Subset Sum	Java	DP	Knapsack Model
417	Pacific Atlantic Water Flow	Java	BFS
418	Sentence Screen Fitting	Java	Looping	LintCode 889
419	Battleships in a Board	Java	Greedy	Should be as easy
423	Reconstruct Original Digits from English	Java	Math
424	Longest Repeating Character Replacement	Java	Two-Pointer
430	Flatten a Multilevel Doubly Linked List	Java	Recursion
433	Minimum Genetic Mutation	Java	Backtracking (DFS)
435	Non-overlapping Intervals	Java	Sort + 1D DP	Greedy solution can optimize to O(nlogn)
436	Find Right Interval	Java	TreeMap & Binary Search
438	Find All Anagrams in a String	Java	Sliding Window
439	Ternary Expression Parser	Java	Backtracking (DFS)	LintCode 887
442	Find All Duplicates in an Array	Java	Array
445	Add Two Numbers II	Java	Stack
451	Sort Characters By Frequency	Java	Counting Sort
453	Minimum Moves to Equal Array Elements	Java	Math
454	4Sum II	Java	HashMap
452	Minimum Number of Arrows to Burst Balloons	Java	Greedy
474	Ones and Zeroes	Java	3D DP	Knapsack Model
477	Total Hamming Distance	Java	Bit
486	Predict the Winner	Java	2D DP
491	Increasing Subsequences	Java	Backtracking (DFS)
494	Target Sum	Java	Backtracking (DFS)	1D DP solution
495	Teemo Attacking	Java	Greedy
498	Diagonal Traverse	Java	Matrix Looping
503	Next Greater Element II	Java	Stack
513	Find Bottom Left Tree Value	Java	DFS
515	Find Largest Value in Each Tree Row	Java	DFS
516	Longest Palindromic Subsequence	Java	2D DP
523	Continuous Subarray Sum	Java	Math
539	Minimum Time Difference	Java	String
542	01 Matrix	Java	Stack
560	Subarray Sum Equals K	Java	HashMap
567	Permutation in String	Java	Sliding Window
611	Valid Triangle Number	Java	Sort
662	Maximum Width of Binary Tree	Java	DFS
670	Maximum Swap	Java	Array
678	Valid Parenthesis String	Java	Greedy + Backtracking	It can be solved by DP, greedy and backtracking!
725	Split Linked List in Parts	Java	LinkedList
739	Daily Temperatures	Java	Stack
791	Custom Sort String	Java	Bucket Sort
856	Score of Parentheses	Java	Stack
870	Advantage Shuffle	Java	Greedy + BinarySearch
881	Boats to Save People	Java	Greedy + Two-Pointer
916	Word Subsets	Java	String Signature
921	Minimum Add to Make Parentheses Valid	Java	Greedy
958	Check Completeness of a Binary Tree	Java	BFS
1048	Longest String Chain	Java	1D DP
1110	Delete Nodes And Return Forest	Java	DFS
1202	Smallest String With Swaps	Java	UnionFind + PriorityQueue	Deserve as hard
1249	Minimum Remove to Make Valid Parentheses	Java	Greedy
1302	Deepest Leaves Sum	Java	DFS
1306	Jump Game III	Java	Backtracking (DFS)
1315	Sum of Nodes with Even-Valued Grandparent	Java	DFS
1339	Maximum Product of Splitted Binary Tree	Java	DFS
1423	Maximum Points You Can Obtain from Cards	Java	DP & Sliding Window

Hard Questions

#	Name	Solution	Algorithm	Note
2	Median of Two Sorted Arrays	Java	Binary Search
10	Regular Expression Matching	Java	Backtracking
23	Merge k Sorted Lists	Java	HeapSort
25	Reverse Nodes in k-Group	Java	LinkedList
30	Substring with Concatenation of All Words	Java	HashMap
32	Longest Valid Parentheses	Java	Stack + 1D DP
37	Sudoku Solver	Java	Backtracking
41	First Missing Positive	Java	Array
42	Trapping Rain Water	Java	Greedy/Two-Pointer
44	Wildcard Matching	Java	Backtracking/Two-Pointer
45	Jump Game II	Java	1D DP/Greedy
51	N-Queens	Java	Backtracking (DFS)
52	N-Queens II	Java	Backtracking (DFS)
57	Insert Interval	Java	Sort
65	Valid Number	Java	String
68	Text Justification	Java	String
72	Edit Distance	Java	2D DP
76	Minimum Window Substring	Java	Sliding Window
84	Largest Rectangle in Histogram	Java	Stack
85	Maximal Rectangle	Java	2D DP
87	Scramble String	Java	Backtracking
97	Interleaving String	Java	2D DP
99	Recover Binary Search Tree	Java	Morris Traversal
115	Distinct Subsequences	Java	2D DP
123	Best Time to Buy and Sell Stock III	Java	DP
124	Binary Tree Maximum Path Sum	Java	DFS
126	Word Ladder II	Java	Backtracking (DFS + BFS)	Both DFS and BFS fail as TLE in OJ
128	Longest Consecutive Sequence	Java	UnionFind + HashMap
132	Palindrome Partitioning II	Java	2D DP
135	Candy	Java	Greedy
140	Word Break II	Java	1D DP + DFS
145	Binary Tree Postorder Traversal	Java	Stack & Set
149	Max Points on a Line	Java	HashMap	Using double as key in hashmap is generally not a good practice
154	Find Minimum in Rotated Sorted Array II	Java	Binary Search
164	Maximum Gap	Java	BucketSort
174	Dungeon Game	Java	Backtracking (DFS) & DP	Backtracking - TLE
212	Word Search II	Java	Backtracking (DFS) & Trie
214	Shortest Palindrome	Java	String
224	Basic Calculator	Java	Stack
239	Sliding Window Maximum	Java	Deque
265	Paint House II	Java	2D DP	LintCode 516
269	Alien Dictionary	Java	Topological Sort	LintCode 892 - OJ on LintCode is incorrect
273	Integer to English Words	Java	String
282	Expression Add Operators	Java	Backtracking (DFS)
291	Word Pattern II	Java	Backtracking (DFS)	LintCode 829
295	Find Median from Data Stream	Java	Heap	Solution for follow-ups: 1. counting sort between 0 and 100 2. count numbers, which is > 100 and < 0
296	Best Meeting Point	Java	Math	LintCode 912
297	Serialize and Deserialize Binary Tree	Java	Tree/DFS/Queue
301	Remove Invalid Parentheses	Java	Backtracking (DFS)
302	Smallest Rectangle Enclosing Black Pixels	Java	Backtracking (DFS)	LintCode 600
305	Number of Islands II	Java	UnionFind	LintCode 434
308	Range Sum Query 2D - Mutable	Java	Matrix	LintCode 817
312	Burst Balloons	Java	2D DP
315	Count of Smaller Numbers After Self	Java	Sort	OJ TLE
316	Remove Duplicate Letters	Java	Greedy
317	Shortest Distance from All Buildings	Java	BFS	LintCode 803
329	Longest Increasing Path in a Matrix	Java	Backtracking (DFS)	DFS with cache
330	Patching Array	Java	Greedy	Cannot be a real interview question
336	Palindrome Pairs	Java	Trie
340	Longest Substring with At Most K Distinct Characters	Java	Two-Pointer	LintCode 386 as medium
352	Data Stream as Disjoint Intervals	Java	Binary Search & Union Find
381	Insert Delete GetRandom O(1) - Duplicates allowed	Java	HashMap
403	Frog Jump	Java	HashMap
425	Word Squares	Java	Backtracking (DFS)	LintCode 634
432	All O`one Data Structure	Java	HashMap + DoublyLinkedList
440	K-th Smallest in Lexicographical Order	Java	Tree
460	LFU Cache	Java	HashMap + DoublyLinkedList
480	Sliding Window Median	Java	Heap
546	Remove Boxes	Java	Backtracking (DFS)	Backtracking is TLE. 3D DP solution is here
778	Swim in Rising Water	Java	Backtracking (DFS) + UnionFind
815	Bus Routes	Java	Graph Traversal (BFS + DFS)
980	Unique Paths III	Java	Backtracking (DFS)