2021刷题打卡

2021/06/9

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Sliding Window

• Maximum Sum Subarray of Size K (easy)
  

Leetcode

• 206. Reverse Linked List （linkedList好久没做了，完全easy的题都做了半个小时一头雾水，过了一遍Recursive和一遍 Iterative
  

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

2021/08/03
Union Find

1.     class UnionFind {
   
2.         int[] parent;
   
3.         
   
4.         public UnionFind(int n) {
   
5.             parent = new int[n];
   
6.             for(int i = 0; i< n; i++) {
   
7.                 parent[i] = i;
   
8.             }
   
9.         }
   
10.         
    
11.         public int find(int x) {
    
12.             if(parent[x] != x) parent[x] = find(parent[x]); // path compression
    
13.             return parent[x];
    
14.         }
    
15.         
    
16.         public void union(int x, int y) {
    
17.             int rootX = find(x);
    
18.             int rootY = find(y);
    
19.             parent[rootX] = rootY;
    
20.         }
    
21.     }

复制代码

721. Accounts Merge

• merge the emails as unique set, step 1: union, step 2: find the root and add to list
  

1361. Validate Binary Tree Nodes

• Perfect example to exercise the union-find algorithm
  

Graph
200. Number of Islands

• DFS
  

778. Swim in Rising Water

• translate to a problem to find a minimum weight path, and in this path find the maximum weight.
• Use a priorityQueue to store the node, sorted by weight. + BFS
  

1102. Path With Maximum Minimum Value

• Same question as #778
  

复习
90. Subsets II






[/i]

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/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/06/10

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Sliding Window

• Smallest Subarray with a given sum (easy)
• Longest Substring with K Distinct Characters (medium)
• Fruits into Baskets (medium) ||   简化版的Longest Substring with K Distinct Characters， 但是把这个题翻译成上面那个题也是有些许难度
• No-repeat Substring (hard) || 和下面的LC题完全一样。
  

Leetcode

• 3. Longest Substring Without Repeating Characters || 刚好这道题也是一道sliding window的题，比较tricky的点是怎么efficiently find is it repeating or not. Intuitively I wanted to use a HashMap, and just like I did in `Longest Substring with K Distinct Characters`, stores the frequency of the chracter. However, it turns out to have very slow runtime. The trick is to store the character's index as the value.
  

2021/06/11

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Sliding Window

• Longest Substring with Same Letters after Replacement (hard) || 这道题真的很难想通，为什么maxcount不用update，为什么只用if不用while，但多做几遍，过几遍例子，就能理解。
• Longest Subarray with Ones after Replacement (hard)
• Problem Challenge 1: Permutation in a String (hard) || 第一道不用看solution就能做出来的 sliding window题目，果然照模板刷适合我
• Problem Challenge 2: String Anagrams (hard)
• Problem Challenge 3: Smallest Window containing Substring (hard) || 自己做有大概思路，有几个trick没顾到，所以不是one-pass
  

2021/06/12
[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Sliding Window

• Problem Challenge 4: Words Concatenation (hard) || Need to clarify the requriements during the interview: the targeted string is not deemed to constructed by the words, it can also contains random alphabet, and also use HashMap in a clever way.
  

2021/06/13 - 06/16
Failed to leetcode / educative.io due to lack of support of nanny :(

Hang on there!!

2021/06/17 - 06/18

开始follow这个帖子提到的strategy，如果遇到不会的看五分钟，还不会，就直接翻答案。看懂了之后自己再写一次。记得总结每道题的trick。

• https://www.1point3acres.com/bbs/thread-503275-2-1.html
  

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Two Pointers

• Pair with Target Sum (easy)， 又名TwoSum, LeetCode第一题。
• Remove Duplicates (easy)，这道题题面太怪了，在leetcode各种被downvote，可以不甩。
• Squaring a Sorted Array (easy)，two pointers, trick在于反方向fill in
• Triplet Sum to Zero (medium)，3Sum
• Triplet Sum Close to Target (medium)，3Sum的变体，track一个minimumDiff
• Triplets with Smaller Sum (medium)，3Sum的变体，算count的时候有trick
• Subarrays with Product Less than a Target (medium)，worth revisit，用sliding window
• Dutch National Flag Problem (medium)，in-place replacement，参考leetcode: moveZeroes
• Problem Challenge 1: Quadruple Sum to Target (medium), 4Sum, 可以想一下KSum的解法
• Problem Challenge 2: Comparing Strings containing Backspaces (medium)，用stack是很straightforward的解法。用two pointers的话，trick是scan from the end to beginning of the string
• Problem Challenge 3:Minimum Window Sort (medium) ，自己想了个O(NlogN)的解法，就是先sort，再比对，找到不重叠的subArray. 用two pointers是O(N), 但是没那么straightforward，需要有两轮的查找。
  

2021/06/19 - 06/21

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Fast & Slow pointers || this pattern is interchangable with HashTable solutions (keep finding what items has been visited in a HashTable)

• LinkedList Cycle (easy): slow = slow.next; fast = fast.next.next;
• Start of LinkedList Cycle (medium)
• Happy Number (medium), worth revisit: two sub-problems, one is to calculate next number correctly, second problem is to find the cycle.
• Middle of the LinkedList (easy), when fast node reaches null, the slow node is the middle pointer.
• Problem Challenge 1: Palindrome LinkedList
• Problem Challenge 2: Rearrange a LinkedList
• Problem Challenge 3: Cycle in a Circular Array (hard), worth revisit. Using slow & fast pointer cost O(N^2), can use DFS to have O(N) time complexity.
  

2021/06/22

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Merge Intervals

• Merge Intervals (medium) || sort by start time, then one for-loop to merge. O(NlogN)
• Insert Interval (medium) || draw the diagram will help develop the algorithm
• Intervals Intersection (medium), worth revist || diagram drawing
• Conflicting Appointments (medium), easy
• Problem Challenge 1: Minimum Meeting Rooms (hard) || sort and use minHeap since we need to track the meeting end time
• Problem Challenge 2: Maximum CPU Load (hard), worth revisit || sort and use minHeap, can be translated to minimumRoomsForMeetings
• Problem Challenge 3: Employee Free Time (hard) , worth revisit || use MinHeap will optimize the time complexity from O(NlogN) to O(NlogK)
  

2021/06/23

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions

Pattern: Cyclic Sort

• Cyclic Sort (easy), array in-place replacement
• Find the Missing Number (easy), we can use hashTable as well
• Find all Missing Numbers (easy), we can use hashTable as well
• Find the Duplicate Number (easy), array in-place replacement
• Find all Duplicate Numbers (easy), array in-place replacement
• Problem Challenge 1: Find the Corrupt Pair (easy)
• Problem Challenge 2: Find the Smallest Missing Positive Number (medium), worth revisit. This is a nice example to use cyclic sort.
• Problem Challenge 3: Find the First K Missing Positive Numbers (hard). I am using HashTable instead and it works perfectly.
  

2021/06/24

[Educative.io] Grokking the Coding Interview: Patterns for Coding Questions
Pattern: In-place Reversal of a LinkedList

• Reverse a LinkedList (easy)
• Reverse a Sub-list (medium)
• Reverse every K-element Sub-list (medium), worth revisit
• Problem Challenge 1: Reverse alternating K-element Sub-list (medium), worth revisit
• Problem Challenge 2: Rotate a LinkedList (medium)
  

1. 
   
2. 
   
3. ListNode curr = head, prev = null, next;
   
4. 
   
5. while(curr!=null) {
   
6.     next = curr.next;
   
7.     curr.next = prev;
   
8.     prev = curr;
   
9.     curr = next;
   
10. }
    

复制代码