Leetcode OA List Link
Amazon Fresh Promotion ✅
private static int isWinner(String[][] codeList,String[] shoppingCart){
//check zero length...
if(codeList == null || codeList.length == 0)
return 1;
if(shoppingCart == null || shoppingCart.length == 0)
return 0;
int i=0,j=0;
for(int k=0; k<shoppingCart.length; k++) {//when match success
if(codeList[i][j].equals(shoppingCart[k]) || codeList[i][j].equals("anything")) {
j++;
if(j == codeList[i].length) {
i++;
j=0;
}
if(i == codeList.length)
return 1;
}else {
//when match failed, k and j both go back.
k-=j;
j=0; }}return 0;
}
Copy the codeAmazon Music Pairs/ LC 1010 ✅
6time// We can simplify this problem as a Two Sum problem. For each time[i], we want to find how many time[j]
// (0<= j < i) can satisfy the requirement (time[i] + time[j]) % 60 = (time[i] % 60 + time[j] % 60) = 0.
// We can use an array/map to store the number of each time[j]%60. I use array beacause time[j]%60 <= 59
// which is small, the "get" operation should be faster considered the hash collisions of map.
// Time: O(N) -> traverse time array once
// Space: 60 -> arr size 60, will be a constant if time is large enough
public int numPairsDivisibleBy60(int[] time) {
int result = 0;
int[] remainder = new int[60];
for (int i = 0; i < time.length; i++) {
result += remainder[(60 - time[i] % 60) % 60];
remainder[time[i] % 60] + +; }return result;
}
Copy the codeItems in Containers/ AOC ✅
1 Traverse the array two times, use dp[N][3] to store numbers of item up to now, nearest left/ right gate Each interval we need O(1) time to find resultCopy the codeLargest Item Association ✅
Very similar to the island problem, create a Map<Integer, List<Integer>> store all the mappings, use a BFS queue to find all the related items and use a set to keep track of all the numbers iteratedCopy the codeTurnstile/ AOC
Use two queue to store exiting person and entering person
Copy the codeFive Star Sellers/ AOC ✅
Use Max PriorityQueue/Heap to store the index by product[0] + 1 / prodcut[1] + 1 - product[0] / product[1] O((N + R) * logN) -> time where R is the result of function, O(N) -> heap * Need to take care about int/double type problemCopy the codeBeta Testing/ Similar to LC 1335 🆕 ✅
But not all same.
// We use dynamic programming to solve this problem, dp[i][k] means the min difficulty we use to
// finish i jobs in k days. The transition is dp[j][k - 1] (min difficulty we use to finish i jobs
// in k - 1 days) + max of jobDifficulty[j + 1 to i] which is the difficulty of i-th day.
public int minDifficulty(int[] jobDifficulty, int d) {
if (jobDifficulty.length < d) return -1;
int[][] dp = new int[jobDifficulty.length + 1][d + 1];
dp[0] [0] = 0;
int maxTemp = 0;
for (int i = 1; i <= jobDifficulty.length; i++) {
maxTemp = Math.max(maxTemp, jobDifficulty[i - 1]);
dp[i][1] = maxTemp;
}
for (int i = 1; i <= jobDifficulty.length; i++) {
for (int k = 2; k <= d; k++) {
int max = 0;
int min = Integer.MAX_VALUE;
for (int j = i - 1; j >= k - 1; j--) {
max = Math.max(max, jobDifficulty[j]);
min = Math.min(min, dp[j][k - 1] + max); } dp[i][k] = min; }}return dp[jobDifficulty.length][d];
}
Copy the codeTop K Frequently Mentioned Keywords ✅
2We use max-heap to store the result,if their frequency are same, we use compareTo(a)
We use a set1 to store all keywords to achieve O(1) get time.
For each string we use another set2, word in set1 and not in set2 will be put in map.
Copy the codeTransaction Logs/ AOC ✅
- Collections.sort(list, (a, b) -> Integer.valueOf(b) – Integer.valueOf(a));
51P3A :TreeMap is convenient, note "088" and"88"No,88In front of 088. 1P3A: There are many corner cases and test cases. So don't take it lightly.public String[] processLogFile(String[] logs, int threshold) {
Map<String, Integer> map = new HashMap<>();
List<String> list = new ArrayList<>();
for (String log : logs) {
String[] words = log.split("");
map.put(words[0], map.getOrDefault(words[0].0) + 1);
if(! words[0].equals(words[1])) {
map.put(words[1], map.getOrDefault(words[1].0) + 1); }}for (String key : map.keySet()) {
if (map.get(key) >= threshold) {
list.add(key);
}
}
Collections.sort(list, (a, b) -> Integer.valueOf(b) - Integer.valueOf(a));
String[] result = new String[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
Copy the codeSubstrings of Size K with K-1 Distinct Chars ✅
Use a map and two pointer as a sliding window to determine if current string from left to right
is a length K string with K - 1 distinct char by map.size()
- substring(left, right + 1)
public static List<String> solve(String S, int k) {
List<String> list = new ArrayList<>();
if (S == null || S.length() < k || k == 0) return list;
Map<Character, Integer> map = new HashMap<>();
Set<String> result = new HashSet<>();
int left = 0;
for (int right = 0; right < S.length(); right++) {
char currChar = S.charAt(right);
map.put(currChar, map.getOrDefault(currChar, 0) + 1);
if (right - left == k - 1) { // reach the target length
if (map.size() == k - 1) { // k character with k - 1 distinct
result.add(S.substring(left, right + 1));
}
if (map.get(S.charAt(left)) == 1) {
map.remove(S.charAt(left));
} else {
map.put(S.charAt(left), map.get(S.charAt(left)) - 1); } left++; }}for (String target: result) {
list.add(target);
}
return list;
}
Copy the codeVideos Link
Number of Islands ✅
Use DFS to reach all place connected to current '1'
Copy the codeMost Common Word/ LC 819 ✅
// 1. Store lowercased paragraph into string array
// 2. Traverse array and count numbers of each word into HashMap
// 3. Traverse banned array and remove ban words from HashMap
// 4. Traverse HashMap to find Max
String[] words = paragraph.toLowerCase().split("\\W+");
Map<String, Integer> map = new HashMap<>();
int max = 0;
String res = "";
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
for (String word : banned) {
map.remove(word);
}
for (String Key : map.keySet()) {
if(map.get(Key) > max) { max = map.get(Key); res = Key; }}return res;
Copy the codeDistance Between Nodes in BST
3
K Closest Points to Origin/ LC 973 ✅
Map heap, keep K -> O(2 * K) space, O(NlogN) time 2 1p3a Map heap, keep K -> O(2 * K) space, O(NlogN) time 2 1p3a Map heap, keep K -> O(2 * K) space, O(NlogN) time 2 1p3a I should use max_value. Notice that.Copy the codeOneCode
Secret Fruit List
Find Related Products
Shopping Patterns ✅
8 // First we use a Map<Integer, List<Integer>> to store a number and all number connected to it // Build a String set to store all edges // For each Number that list.size() > 2, we go through the list and find if any couple are in set 1p3a: find trio,O(VE), Do layer 2 BFS for each point or find out if its two neighbors are connected. So worst caseO. Note that you need to do BFS only if you have two or more neighbors. Therefore, the worst case can not be achieved basically. 1P3A: Essentially a graph looking for trio. This is done by checking each node to see if the two nodes linked to it are also linked to each other.Copy the codeThree plots of land per mu
1.
The second one gives you two arrays and a target number. Select one of the two arrays, sum is less than or equal to target number, and return is the combination closest to target. I'm going to do a transformation of sum.Copy the code1
2. Friend Circle/ Gifting Group/ LC 547 ✅
6
// Traverse 0 to N people, for ith persone, if it is already connected by previous people -> we skip this person
// else we use a queue to find all direct/ indirect friends
// Time Complexity : O(N * N) -> The complete matrix of size n^2 is traversed.
// Space Complexity : O(N) -> one set and one queue with size N
public int findCircleNum(int[][] M) {
HashSet<Integer> set = new HashSet<>();
int result = 0;
for (int i = 0; i < M.length; i++) {
if (set.contains(i)) continue;
result++;
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
set.add(i);
while (queue.size() > 0) {
int row = queue.poll();
for (int j = 0; j < M.length; j++) {
if (M[row][j] == 1&&! set.contains(j)) { queue.add(j); set.add(j); }}}}return result;
}
Copy the code3. Minimum Difficulty of a Job Schedule/ LC 1335 ✅
6
4. Utility checks/ Autoscale Policy
LC Link
6 (Twitter, AutoScale Policy, even the test case is the same and changed the name) Given an initial number of Computing Instances, and an array representing CPU utilization per second, For example, [4,25,17,87] represents the utilization of 1-4 seconds, which is 4%, 25%, 17%, and 87%, respectively. Then the computing Instances corresponding to different utilization are dealt with as follows: 0-25 Computing instances in half; Computing Instances (number of instances) computing Instances (number of instances) We should directly skip the following 10s 2 and halve the odd number to take CeiL 1P3a: it seems to be simple, but there are many corner cases mentioned, and test cases are not easy. So don't take it lightly.Copy the codeLeetCode the original
Partition Labels/ LC 763 ✅
Reorder Data in Log Files/ LC 937On September 25
LC: 340, 200, 1381/414, 1339, 1381