2021刷题打卡

2021/06/25

Pattern: Tree Breadth First Search

• Binary Tree Level Order Traversal (easy)
• Reverse Level Order Traversal (easy)
• Zigzag Traversal (medium), worth revisit || combination of reverse order and BFS, the trick is to List.add(0, item) so to insert into the front of the list.
• Level Averages in a Binary Tree (easy)
• Minimum Depth of a Binary Tree (easy), worth revisit
• Level Order Successor (easy)
• Connect Level Order Siblings (medium)
• Problem Challenge 1: Connect All Level Order Siblings (medium), worth revist
• Problem Challenge 2: Right View of a Binary Tree (easy)
  

1. queue.offer(root);
   
2. while(!queue.isEmpty()) {
   
3. TreeNode curr = queue.poll();
   
4. if(curr.left != null) queue.offer(curr.left);
   
5. if(curr.right != null) queue.offer(curr.right);
   
6. }

复制代码

Pattern: Tree Depth First Search

• Binary Tree Path Sum (easy)
• All Paths for a Sum (medium)
• Sum of Path Numbers (medium)
• Path With Given Sequence (medium)
  

This pattern is a little hard and can revisit all the problems.

2021/06/29

Pattern: Tree Depth First Search

• Binary Tree Path Sum (easy)
• All Paths for a Sum (medium)
• Sum of Path Numbers (medium)|| not familiar with backtracking, so revisit:Leetcode #113
• Path With Given Sequence (medium)
• Count Paths for a Sum (medium), revisit || better solution inLeetcode #347 using HashMap, trick is backtracking.
• Problem Challenge 1: Tree Diameter (medium), high rate question under Facebook tag, can work on Leetcode #1245 instead to revisit the pattern.
• Problem Challenge 2: Path with Maximum Sum (hard), revisit || similar to TreeDiameter problem, use a global variable to track the maximumSum. Another trick is we need to ignore the negative pathSum.
  

Pattern: Two Heaps

• Find the Median of a Number Stream (medium)
• Sliding Window Median (hard), worth revisit to get familiar with two heaps solution
• Maximize Capital (hard), worth revisit to get familiar with two heaps solution
• Problem Challenge 1: Next Interval (hard), TreeMap? Leetcode #436
  

2021/06/30 - 2021/07/01
Pattern: Subsets

• Subsets (easy), revisit. Really good read in Leetcode 78 solution
• Subsets With Duplicates (easy). More intuitive to implement using backtracking, Time: O(N * 2^N), Space: the stack usage for recursion O(N).
• Permutations (medium). BFS, using queue. The trick is adding the permutation to result when the length matches. We know that there are a total of N! permutations of a set with ‘N’ numbers. Time: O(N * N!), Space: O(N!)
• String Permutations by changing case (medium):
• Balanced Parentheses (hard)
• Unique Generalized Abbreviations (hard), revisit. Balanced Parentheses algorithm, using recursion. O(N * 2^N)
• Problem Challenge 1: Evaluate Expression (hard), recursion
• Problem Challenge 2: Structurally Unique Binary Search Trees (hard)
• Problem Challenge 3: Count of Structurally Unique Binary Search Trees (hard), revisit. Choose a root. recursion
  

2021/07/01

Pattern: Modified Binary Search

• Order-agnostic Binary Search (easy)
• Ceiling of a Number (medium)
• Next Letter (medium), revisit
• Number Range (medium), revisit. Trick is search forward and backward.
• Search in a Sorted Infinite Array (medium), this is an interesting problem as well. The trick is to define the search range and increase the range exponentially.
• Minimum Difference Element (medium)
• Bitonic Array Maximum (easy)
• Problem Challenge 1: Search Bitonic Array (medium), revisit. Break down this problem into two sub-problems, findMaxIndex & do binary search in two halves
• Problem Challenge 2: Search in Rotated Array (medium)
• Problem Challenge 3: Rotation Count (medium) can revisit if have time.
  

2021/07/02

Pattern: Bitwise XOR

• Single Number (easy)
• Two Single Numbers (medium)
• Complement of Base 10 Number (medium)
• Problem Challenge 1: Flip and Invert Image
  

1. 
   
2. X ^ X = 0
   
3. 0 ^ X = X
   
4. 1 ^ 1 = 0
   
5. 1 ^ 0 = 1
   
6. 0 ^ 1 = 1
   
7. 0 ^ 0 = 0
   

复制代码

Pattern: Top 'K' Elements

• Top 'K' Numbers (easy), can use minHeap or maxHeap
• Kth Smallest Number (easy)
• 'K' Closest Points to the Origin (easy)
• Connect Ropes (easy)
• Top 'K' Frequent Numbers (medium)
• Frequency Sort (medium)
• Kth Largest Number in a Stream (medium), trick: reuse add(int num) method within constructor to reduce duplicated code.
• 'K' Closest Numbers (medium)
• Maximum Distinct Elements (medium), trick: if k > 0, this means we have to remove some distinct numbers
• Sum of Elements (medium)
• Rearrange String (hard)
• Problem Challenge 1: Rearrange String K Distance Apart (hard): Worth revisit Leetcode #358. A waitingList
• Problem Challenge 2: Scheduling Tasks (hard). Worth revisit. FreqMap + PriorityQueue + batch process the task by n. Leetcode #621
• Problem Challenge 3: Frequency Stack. worth revisit. More elegant way to implement is to use stack of stack. (grouping the maxFreq numbers together within a stack, FILO) Leetcode #895
  

Pattern: K-way merge

• Merge K Sorted Lists (medium) - using minHeap
• Kth Smallest Number in M Sorted Lists (Medium)
• Kth Smallest Number in a Sorted Matrix (Hard)
• Smallest Number Range (Hard)
• Problem Challenge 1: K Pairs with Largest Sums (Hard) , reivist. Can evalute in Leetcode #373
  

2021/07/03 - 2021/07/07
Pattern: 0/1 Knapsack (Dynamic Programming)

• 0/1 Knapsack (medium)
• Equal Subset Sum Partition (medium)
• Subset Sum (medium)
• Minimum Subset Sum Difference (hard)
• Problem Challenge 1: Count of Subset Sum
• Problem Challenge 2: Target Sum (hard). Revisit at Leetcode #494
  

Find the base condition, recursive, memorization (top down) and dp (bottom up)

Pattern: Topological Sort (Graph)

• Topological Sort (medium)
• Tasks Scheduling (medium)
• Tasks Scheduling Order (medium)
• All Tasks Scheduling Orders (hard)
• Alien Dictionary (hard) Revisit at Leetcode #269. How to construct the graph?
• Problem Challenge 1
• Problem Challenge 2: Minimum Height Trees (hard), Revisit at Leetcode #310. The trick is to prove there are most 2 centroids in the graph, removing leaves step by step to find the centroids.
  

2021/07/08

Designing a URL Shortening service like TinyURL
Template of Design Interview

• Requirements & Goals (Functional Requirements, Non-functional requirements)
• Capacity Estimation and Constraints (Traffic estimates, Storage estimates, Bandwidth estimates, Memory estimates) cache | memory estimates  | 20/80 rule so cache 20% requests
• System APIs (Parameters, Returns, How do we detect and prevent abuse?)
• Database Design (What kind of database should we use? SQL v.s. nonSQL)
• Basic System Design and Algorithm
• Data Partitioning and Replication
• Cache
• Load Balancer (LB)
• Purging or DB cleanup
• Telemetry
• Security and Permissions
  

知识点：
LRU (Least Recently Used) Algorithm: used Linked HashMap, whenever the item is visited, move this element to top.

• https://www.iteye.com/blog/flychao88-1977653
• https://www.jianshu.com/p/d533d8a66795
• https://www.cnblogs.com/linxiyue/p/10926944.html
  

Data Partitioning and Replication

• range-based partitioning [this can lead to unbalanaced db servers]
• hash-based partitioning [hash function randomly distribute the URL into different partitions], [this can lead to overloaded partitions, and can be solved by consistent hashing]
  

Load Balancer

• To avoid overloaded server or slow traffic, the LB should periodically query the load on servers and balance the traffic accordingly.
  

2021/07/08
Easy under FB tab
938. Range Sum of BST  
1614. Maximum Nesting Depth of the Parentheses
1213. Intersection of Three Sorted Arrays
617. Merge Two Binary Trees
905. Sort Array By Parity
346. Moving Average from Data Stream
359. Logger Rate Limiter

• memory consideration for design, we should not avoid memory increasing nonstoppable.
• Must read: https://leetcode.com/problems/logger-rate-limiter/discuss/391558/Review-of-four-different-solutions%3A-HashMap-Two-Sets-Queue-with-Set-Radix-buckets-(Java-centric)
• Things to consider: memory, thread safe
• How to build a simple LRU cache using LinkedHashMap: reference1, reference2.Note: use LRU is not a good solution, since we don't know at most how many strings would come in at the same time.
  

1460. Make Two Arrays Equal by Reversing Sub-arrays
1047. Remove All Adjacent Duplicates In String
226. Invert Binary Tree
509. Fibonacci Number

• Memo / DP
  

977. Squares of a Sorted Array
94. Binary Tree Inorder Traversal

• Stack | or Recursive
  

2021/07/09Easy under FB tab

1636. Sort Array by Increasing Frequency
463. Island Perimeter
136. Single Number
824. Goat Latin

• StringBuilder time complexity, etc.
  

206. Reverse Linked List
637. Average of Levels in Binary Tree
349. Intersection of Two Arrays

• Two pointers, HashTable
  

766. Toeplitz Matrix

• Follow up question: memory constraint: highly-voted answer
  

266. Palindrome Permutation
108. Convert Sorted Array to Binary Search Tree
1099. Two Sum Less Than K

• TreeSet.lower(Integer i) (Black/Red Tree) or Two-Pointers
  

242. Valid Anagram
283. Move Zeroes

• The trick is we need to track two pointers: one pointer is lastNonZeroNumber index, and the other is the cursor scanning through the array
  

896. Monotonic Array

• The learning here is we should always go through examples to build a solution. Submitted multiple wrong answers for this one. Esp when the items are equal.
  

13. Roman to Integer

• Keep in mind we should validate the input
  

268. Missing Number
21. Merge Two Sorted Lists
167. Two Sum II - Input array is sorted

2021/07/10

Easy under FB tab

252. Meeting Rooms
191. Number of 1 Bits

• bit manipulations (1 ^ x = x)
• Integer.bitCount(n);
• n = 00000000000000000000000000001011 represents n = 11
• https://www.geeksforgeeks.org/all-about-bit-manipulation/
  

257. Binary Tree Paths

• Backtrack + DFS
• https://leetcode.com/problems/binary-tree-paths/discuss/68258/Accepted-Java-simple-solution-in-8-lines
  

704. Binary Search
1539. Kth Missing Positive Number
387. First Unique Character in a String
235. Lowest Common Ancestor of a Binary Search Tree

• Recursive, and binary search tree (left is always smaller and right is bigger than root)