2021刷题打卡

2021/07/11
Easy under FB tab

1275. Find Winner on a Tic Tac Toe Game
993. Cousins in Binary Tree

• The tick is to determine if sibling at parent level. Using BFS would be convenient.
• Binary Search Tree is different from Binary Tree.
• Solution inspired by Java-BFS-time-and-space-beat-100
  

121. Best Time to Buy and Sell Stock

• Kadane's Algorithm
• keep how many variables? draw the diagram will help define the problem.
  

953. Verifying an Alien Dictionary
270. Closest Binary Search Tree Value

• Use binary search to optimize to O(H)
  

543. Diameter of Binary Tree
303. Range Sum Query - Immutable

• Prefix Sum Algorithm
  

2021/07/12

FB Easy Tab

415. Add Strings

• StringBuilder.insert(0, x);
• test all kinds of use cases is important! Missed carryOver != 0 use case
  

70. Climbing Stairs
53. Maximum Subarray

• Another example of Kadane's Algorithm  + Prefix Sum
• https://iq.opengenus.org/prefix-sum-array/
• https://zhuanlan.zhihu.com/p/96014673
  

67. Add Binary

• The ticky part is how to calculate without using addition operator
• Bit manipulation
  

1. 1 ^ 0 = 1
   
2. 1 ^ 1 = 0
   
3. 0 ^ 0 = 0
   
4. 0 ^ 1 = 1
   
5. 1 & 1 = 1
   
6. 1 & 0 = 0
   
7. 1 | 0 = 1
   
8. 1 | 1 = 1
   
9. 0 | 0 = 0

复制代码

724. Find Pivot Index

• Ask clarify question, define the algorithm first, then start coding.
  

26. Remove Duplicates from Sorted Array
1. Two Sum

• Interesting,failed to solve it with optimal solution (HashTable)
  

2021/07/12

FB Easy Tab

844. Backspace String Compare

• Need to revisit to use two pointer solution so that space complexity is O(1)
  

246. Strobogrammatic Number

• Map<Character, Character> dict = Map.of(K1, V1, K2, V2,...);
  

674. Longest Continuous Increasing Subsequence

• Identify the local & global variables
  

160. Intersection of Two Linked Lists (two pointers solution)
345. Reverse Vowels of a String

• Choose the data structure purposefully. For example the dictionary should contain both lower case and upper case so that we don't need call Characters.toLowerCase() multiple times.
  

110. Balanced Binary Tree

今天开始按照类型在LC刷题。问了比较多的朋友，平时刷题按类型刷，临面试再刷相应公司的高频题。

刷题大纲
✅ Prefix Sum
⏹ HashTable
⭕ Dynamic Programming
⭕ Union Find
⭕ Backtracking
⭕ Divide and Conquer
⭕ Breadth-First Search
⭕ Depth-First Search
⭕ Stack
⭕ Queue
⭕ Heap (Priority Queue)
⭕ Graph
⭕ Two Pointers

2021/07/13

HashTable
217. Contains Duplicate
350. Intersection of Two Arrays II
169. Majority Element

• The basic implementation is hashTable, but if we need to optimize for space complexity to O(1), it will become complicated.
• Approach 6: Boyer-Moore Voting Algorithm
  

202. Happy Number
3. Longest Substring Without Repeating Characters

• Sliding Window
  

Prefix Sum

238. Product of Array Except Self

• forward, backward
  

528. Random Pick with Weight

• translate this question into a prefixsum + binary search problem. (Find a insertion point)
• Be mindful prefixsum = prefixsum[i-1] + num[i];[/i]
  

523. Continuous Subarray Sum

• to get a O(N) solution instead of O(N^2) solution, the trick is if(a % k == b % k), (a - b) % k == 0
  

974. Subarray Sums Divisible by K

• a similar problem as the above question, one trick is that if the mod of two indexes are the same, then we can choose those two indexes as the subarray's start and end index. How many choices do we have if there are 3 same mods? It's (n-1)*n / 2 = 3. Don't forget to add the count for mod == 0
  

Miscellaneous
205. Isomorphic Strings
1423. Maximum Points You Can Obtain from Cards (Sliding window)

工作今天有点多，又开了会儿小差，刷了两道easy Dp

2021/07/14

122. Best Time to Buy and Sell Stock II
118. Pascal's Triangle

想了想 还是按照FB的题刷好了，这样刷起来比较有序，而且FB下面都刷完都会做的话，其他公司也不在话下了。

有个策略是在FB下面的题目也按tag刷，说干就干

2021/07/15

1762. Buildings With an Ocean View
How to convert ArrayList<Integer> to int[]

1. res.stream()
   
2.   .mapToInt(i->i)
   
3.   .toArray();

复制代码

HashTable
791. Custom Sort String
734. Sentence Similarity
1650. Lowest Common Ancestor of a Binary Tree III

• This problem can be solved as two pointers Exactly the same problem as Leetcode #160
  

451. Sort Characters By Frequency

• Initially I build a solution with O(N^2), insert the characters into maxHeap and update the frequency map at the same time: so I need to remove the existing character before inserting the new character, which take O(N) in the priorityQueue data structure.
• Looking at the other posts, I realized I should break this operation into two smaller steps: 1) build the freqency map, 2)maxHeap.addAll(). Then I'll be able to acheive O(N) time complexity.
  

49. Group Anagrams

• The main problem is how to construct the key
  

249. Group Shifted Strings

• corner case: ["za", "ab"] is grouped together
  

348. Design Tic-Tac-Toe
138. Copy List with Random Pointer

• I hit TLE exception in the first round since the random pointer can generate a loop. The trick is to store the node early to the Map
• O(1) space solution is to weave and unweave from the original list.
  

146. LRU Cache

• Mention java LinkedHashMap has such built-in function to create a LRU cache.
• The proper way to implement is double linked list: a class to enable O(1) operation to remove node, add node to head, remove node from tail. The cache should store the key and the node. Another trick is to have pesudo head and tail so we don't need to have multiple null checks.
  

Some interesting read for this topic

• https://www.jianshu.com/p/d533d8a66795
• https://www.cnblogs.com/linxiyue/p/10926944.html
  

2021/07/16
HashTable

460. LFU Cache (hard)

• 不愧是Hard，debug了半天才发现错在哪里。
• Similar to build a LRU Cache, need to leverage a DoubleLinkedList to record the user count sequence when there is clash of frequency. Still need a hash map to store key, and the node; then use another map store count to the doublelinkedlist. we need to update both map for any operations (put and get).
  

442. Find All Duplicates in an Array

• This is a question that I almost answered correctly without hint. Use in-place replacement. However, did not build the loops properly.
• One take-away is to add each comment for each scenarios properly so can build the correct logic. And go through all the examples ruthlessly. and the third tip is to have proper variable naming.
  

398. Random Pick Index

• Similar to 528. Random Pick with Weight
  

41. First Missing Positive

• cyclic sort, similar to #442
  

2021/07/17

System Design Prep

https://www.youtube.com/watch?v= ... 7RItdiB&index=1

Chapter 1. Distributed system introduction
Chapter 2. Models of distributed systems