2.1.1. Reference：

笔试面试知识整理

2.1.2. the sum of subarray <==> K

1. 53 Maximum subarray (Kadane's)
2. ​ Maximum subMatrix Link01
3. ​ Maximum subarray no larger than K ( TreeSet O(nlogn)) answer 01 Answer02
4. 363 Maximum subMatrix no larger than K (c^2^rlogr)
5. 325 longest subarray equals K (HashMap, 非负 Sliding Window O(n))
6. ​ longest subarray <= K (非负，sliding window O(n)
7. 209 Minimum size subarray >=k (sliding window O(n))

8. ​ T/F, longest % k == 0 (hashmap)

9. 求长度最长的subarray, 和为k

   • HashMap

   325. Maximum Size Subarray Sum Equals k

10. 求长度最短的subarray，和大于等于k

    • sliding Window(Two Pointers)
    • Binary Search

    209. Minimum Size Subarray Sum

2.1.3. Kadane's Algorithm

Maximum Sum Subarray Problem 53

Maximum Sum Subarray no longer than K

Maximum Size Subarray Sum Equals k 325

Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane

Max Sum of Rectangle No Larger Than K 363

Largest sum subarray with at-least k numbers

扩展K pdf

2.1.3.1. isDAG + Topological Sort

• BFS
• DFS
• Stack

2.1.4. LinkedList 变换

• • 第奇数个串在一起， 第偶数个串在一起 328. Odd Even Linked List
  • 比target大的放在前面 86. Partition List
  • 翻转 206 Reverse Linked List 92 Reverse Linked List II 25 Reverse Nodes in k-Group
  • ​

2.1.5. Design URL

• new 100 million url per month

• 1 billion request/month

• 10% shortening and 90% redirection

• shortening Request per second is 40条/s , redirection request per second is 360条/s

• 6 new billion urls in 5 years

• 假设 url -> 500bytes, 6bytes -> hash (26个A-Z，26个a-z，10个数字 62 ^6^ = 56 billion )

• all url we need 3TB, 36GB hash

• encoding : 40 (500 + 6) —> 20kb/s

• decoding : 360 (506) —> 180 kb/s

2.1.6. Longest Increasing Subsequence

DP + Binary Search

300. Longest Increasing Subsequence 354. Russian Doll Envelopes

2.1.7. Resevoir Sampling

Link01

Link02