BQ

Coding（163）
System Design（20）
Algorithm（30）
Ood（15） 高频题（6）

Coding（163）
System Design（20）
Algorithm（30）
Ood（15） 高频题（6）
1.Min range in N sorted array
2.Find min cost
3.Leetcode 1273
4.Find string with prefix
5.Design filesystem
6.Build tower
7.Number of pointer on the upper right
8.Possibility of dices
9.Generate similar string
10.Deal with transaction
11.Transmit signal
12.Leetcode 315
13.Put rings on rod
14.Join string to get palindrome
15.Broadcase message among routers
16.Convert matrix to all zeros
17.Do not play same music in k time period
18.Find closest station
19.Atom and bond match
20.Decide order of tasks
21.Break string 放到二叉树
22.Find shortest path
23.Matching words
24.Design an page to calculate mortgage
25.Number of matching subsequences
26.Router send message
27.Check validity of input
28.Remove elements within distance
29.Design a riffle shuffle
30.Pointwise sum
32.Get status and count from data stream
33.Employee importannce
34.Buid character of length L
35.Cook with ingredient 36.Find max rectangle
37.Find anagram
38.Leetcode 694
39.Prepare dishes
40.Check cards
41.Design API for chess
42.Delete nodes for binary tree
43.Find substring
44.All people know the story
45.Sum of digits
46.Check if a word is valid
47.Find path
48.Prune employee tree
49.Lumber cutting
50.Print log messages
51.Find count of each question
52.Guess word game
53.Convert one word from another
54.Delete node and reconnect
55.Generate based on probability
56.Find the setting with shortest time
57.Print path from one node to another
58.All words combination
59.Check word edit distance
60.Minimum word edit distance
61.Random shuffle song
62.In place invert a matrix
63.Write random number generator
64.Transformer one input to another
65.Count words
66.Find largest along the tree path for all leaves
67.LeetCode 210 68.LeetCode 35
69.LeetCode 139
70.LeetCode 42 71.LeetCode 274
72.LeetCode 103
73.LeetCode 45
74.LeetCode 435
75.LeetCode 547
76.Robot moving
78.Stock price board
79.Sliding window average
80.ID generator
81.Fold full path
82.Random order
83.Word match
84.Find path between two nodes
85.Win rate calculation 86.Logs printer
87.寻找异位词
88.Add two list of string
89.Cord tree
90.Black box
91.List of queues
92.Shortest path
93.餐厅排队系统 94.Find first index after sort
95.Find most frequently element
96.Find index after sort 97.Max value in array
98.String editor
99.Longest subsequence
100.Log file
101.Word counter
102.LeetCode 261
103.Predict the next word
104.Type a word in k distance
105.Determine overlapping circles
106.Minimum area rectangle
107.最短路径
108.Number of lakes
109.Shortest path in binary tree
110.LeetCode 299
111.Reverse an integer
112.LeetCode 278
113.中序遍历二叉搜素树
114.100%胜率的出牌顺序
115.聊天记录文件
116.实现密码锁
117.LeetCode 1820
118.LeetCode 1962
119.Encode and comprees string
120.Generate a sequence that adds up to a given sum.
121.LeetCode 608
122.Time blocks
123.Generate random questions
124.实现file system
125.Minimum flight cost
126.LeetCode 778
127.LeetCode 720
128.LeetCode 704
129.LeetCode 280
130.LeetCode 55
131.设计一个NumContainer Class
132.实现一个记录大气温度的class
133.Data movement
134.判断胡牌
135.Find raw ingredient
136.找到最长递增string list
137.设计一个Word store Service
138.Maze Generation Algorithm
139.最短路径
140.LeetCode 1200
141.Split BST
142.max sum of subMap
143.LeetCode 523
144.LeetCode 747
145.设计一个iterator
146.Graph traversal
147.LeetCode 73
148.LeetCode 166
149.LeetCode 588
150.LeetCode2242
151.Delete node from forest
152.Mutiplication of two big numbers
153.套娃问题
154.Similar pattern
155.design monitoring system with metrics and alerts
156.design an interactive dialogue prediction system
157.design an interactive dialogue prediction system
158.实现csv的parse功能
159.Closest Cafe for everyone
160.Design a class organization
161.实现快进功能
162.验证不等式
163.最短通行时间
164.邮箱数据导入
165.Leetcode 1293
166.file system
167.number of unique number
168.transform an integer
169.LeetCode 323
170.LeetCode 2246
171.LeetCode 2196
172.Design Steam
173.LeetCode 295
174.Design donation system
175.implement booking system
176.remove floor
177.remove leaf node
178.shortest path
179.设计WaitList系统
180.求list中第二大的数
181.timestamp + string
183.LeetCode 1048
184.LeetCode 843
185.LeetCode 427
186.LeetCode 57
187.LeetCode 161
188.LeetCode 818
189.LeetCode 393
190.构建full binary tree
192.计算传纸条到target坐标的概率
193.填字游戏
194.寻找二叉树中节点最多的BST
195.设计一个翻译系统
196.find the longest continuous "0"
197.Leetcode 269
198.Leetcode 359
199.随机playlist
200.判断是否有一半元素大于mean
201.find common subString
202.实现integer generator
203.查询子序列中的单词
205.employee report dictionary
206.设计一个review系统
207.LeetCode 20
208.LeetCode 792
209.LeetCode 289
210.LeetCode 695
211.LeetCode 279
212.valid inequality
213.设计查询机票系统
214.实现一个统计功能
215.合并前缀树
216.设计一个广告系统
217.捷豹跳跃组合
218.实现一个waitList class
219.Guess Color
220.LeetCode 1293
221.LeetCode 2190
222.LeetCode 1944
223.预测实时手机battery life time
224.generate array list
225.number of good pair
226.设计歌单分享
227.键值更新
228.LeetCode 207
229.LeetCode 46
230.Design a simple spreadsheet
231.LeetCode 21
232.LeetCode 23
233.Leetcode839
234.secret Word
235.leetcode2034
236.拓扑排序
237.设计gmail 定时删除功能
238.leetcode20
239.leetcode399
240.二叉树最底层宽度
1. Min range in N sorted array
input 给n个integer sorted array，如果从每个array取一个element那么这n个数最小的range是什么.
2. Find min cost

3. Leetcode 1273
leetcode 1273
4. Find string with prefix

5. Design filesystem

6. Build tower

7. Number of pointer on the upper right

8. Possibility of dices
n个k面色子 输出每种和的概率数组 比如2个2面色子 输出 [0.25, 0.5, 0.25]
9. Generate similar string

Input是一组字符串，例如["word", "orange", "of"]

similar string的定义：如果一个字符串w是字符串组array的similar string，那么：1. w的第一个字符必须和array中某一个string第一个字符相同；2.w的最后一个字符必须和array中某一个string最后一个字符相同；3.w的中间字符相对于前一个字符的分布，必须和array中每一个字符相对于前一个字符的分布相同。最后一个条件有点费解，拿这个input举例，如果w[i]是'o'，那么w[i+1]只能是'r'或者'f'，而且是'r'的概率是'f'概率的两倍
10. Deal with transaction

1. 调用完后，所有good entries都被processTX调用过一次
2. 调用processTX的次数足够少
11. Transmit signal

12. Leetcode 315

5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

1 <= nums.length <= 105
-104 <= nums[i] <= 104
13. Put rings on rod
You have 10 rods numbered from 0 to 9. There are three types of rings—red, green and blue—being put on the rods. You get a point for each rod that has a ring of each color on it, i.e. to get a point you need a red ring, green ring and blue ring on one rod.

A ring put on a rod is represented by two characters—the first describes the color of the ring and the second describes which number rod it is on from 0 to 9. For example "R8" means that a red ring is being put on the 8th rod.

Write a function:

class Solution { public int solution(String S); }

that, given a correct string of length 2N describing the N rings put onto rods, returns how many points you will get.

Examples:

For ""B2R5G2R2,"" the answer is 1

Given S = "R8R0B5G1B8G8", your answer should be 1. You get one point for rings put on the 8th rod (there is one red, one blue and one green ring on it). There is also a red ring on the 0th rod, green on the 1st rod and blue on the 5th rod. You don't get points for them because they don't form a full trio on one rod. There are no rings on any of the other rods.
14. Join string to get palindrome
A string is a palindrome if it reads the same backward as forwards. For example, "madam" and "racecar" are palindromes, but "milk" is not.

We are given an array of N strings in which each string consists of two lowercase English letters. We would like to join as many strings together as possible in order to obtain a palindrome.

Write a function:

class Solution { public int solution(String[] A); }

which, given an array A of length N containing two−letter strings, returns the length of the longest palindrome that can be created by joining as many strings together as possible from A.

Examples:

Given A = ["ck", "kc", "ho", "kc"], the function should return 4 since the longest palindromes that can be created from A are "ckkc" and "kcck", and their lengths are both equal to 4.

Given A = ["ab", "hu", "ba", "nn"], the function should return 6 since the longest palindromes that can be created from A are "abnnba" and "bannab", and their lengths are both equal to 6.

Given A = ["so", "oo", "kk", "od"], the function should return 2, since the only palindromes that can be created from A are "oo" and "kk", and their lengths are both equal to 2.

Given A = ["do", "go", "ok"], the function should return 0, since no palindrome can be created from A.

Write an efficient ‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍algorithm for the following assumptions:

N is an integer within the range [1, 100,000].

Each string in A consists of two English lowercase letters.
15. Broadcase message among routers
Let's define a kind of message called "Broadcast & Shut Down." When a router receives this message, it broadcasts the

same message to all other routers within its wireless range. Then, that router shuts down, and can no longer send or

For example, Router A is at (0, 0); Router B is at (0, 8); Router C is at (0, 17); Router D is at (11, 0). If the

wireless range is 10, when Router A send a message, it could first reach B; the message from Router B will further reach

Router C. But Router D will never receive this message.

A 0 0

B 0 8

C 0 17

D 11 0

Router A can reach Router B. Write a method / function with appropriate input and output arguments.
16. Convert matrix to all zeros

Initial status:

0 0 1 0 0 --> 1 1 0 1 1

0 0 1 0 0

0 0 1 0 0

1 1 0 1 1

0 0 1 0 0
17. Do not play same music in k time period

18. Find closest station

19. Atom and bond match

20. Decide order of tasks
21. Break string 放到二叉树
Break string 然后放到二叉树里 where leaf (end node) holds a string, each (internal) node further up the tree holds the sum of the lengths of all the leaves in its left subtree

Example: "Hello_my_name_is_Alex"

21

/

14

/ \

9 3

/ \ / \

6 name_ is_ Alex

/ \

Hello_ my_
22. Find shortest path
given 01maze(0: empty, 1: wall), start_point, end_point 找最短路径
23. Matching words
"TACK" true "ACT" -‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍> "CART" true "ACE" -> "TACK" false (char order not matter) followup: rule不变 given ["ACT", "SET", "FOO"] , ["TACK", "TSET", "BAR"] -> ["TACK", "TSET"]">单词matching "ACK"-> "TACK" true "ACT" -‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍> "CART" true "ACE" -> "TACK" false (char order not matter) followup: rule不变 given ["ACT", "SET", "FOO"] , ["TACK", "TSET", "BAR"] -> ["TACK", "TSET"]
24. Design an page to calculate mortgage

25. Number of matching subsequences
Number of Matching Subsequences的变种,先写了brute force,然后又写了最优解存dictionary的pseudo code.让分析了time complexity
26. Router send message

27. Check validity of input

28. Remove elements within distance

e.g.: input_stream = [0.1, 0.1, 0.3, 0.3, 0.2, 0.5, 0.5, 0.5, 0.4], D = 0.1，让return最后剩在memory里的elements
29. Design a riffle shuffle
you are supposed to simulate a riffle shuffle. First you need to split the cards from roughly in the middle. Then you have two set of cards in your two hands. Then you need to riffle shuffle them back into a single deck (randomly interleave cards with each other).
30. Pointwise sum
pointwise sum. 给两个time series (time_stamp, value) T1=[(0, 0), (3, 1), (5,2), (7,0)] T2=[(0, 0), (4,1),(10,0)] 输出结果Ts = [(0, 0), (3, 1), (4, 2), (5, 3), (7,1), (10, 0)]
31. Find basket counts

32. Get status and count from data stream
data stream进来一组request, 每个request 有[time html statuscode duration]四个信息

Time: 表示request开始的timestamp

Html: 没什么用的信息

Duration: request持续了多久

statusCode: 例如200, 202, 404等

Q1. 同一种 statusCode的request有多少？

Q2. for each timestamp, how many requests are in the processing queue?

Input: stream of [start, end] time

Output: the # of request in each start time

{[1, 5] [2, 3], [4, 9]} 则要返回 ["1" : 1] ["2" : 2], ["4" : 2]

Streaming :

[1, 5]

[2, 3] [4 9]
33. Employee importannce

added one more constraint,

34. Buid character of length L

Example:

Input dict [a, b], K = 2, L =3

Output:

a a b

b a a

a b a

invalid: a a a
35. Cook with ingredient 36. Find max rectangle

37. Find anagram

38. Leetcode 694
leetcode 694
39. Prepare dishes

recipe 的例子：

1）hamburger

raw ingredient: vegetable, meat

intermediate ingrediant: none

raw ingredient: flour, water

40. Check cards

41. Design API for chess
OOD: 给类似5子棋的游戏设计api
42. Delete nodes for binary tree

43. Find substring

44. All people know the story

45. Sum of digits

46. Check if a word is valid

47. Find path
“{fiction:[{title:...,id..}],nonfiction:{title:......}]” console.log(findPath(json), “json.book.fiction.title”) -----> “Moby Dick”">Given json, and a string path, return the resulting json

Public obj[] findPath(JSON json, String stringPath){
…… write your code here

}
Example json : {
book :{
fiction:[
{
title: "Moby Dick",
id: 11111
},
{
title: "Mob",
id: 111112311
}
],
nonfiction:[
{
title: "Dik",
id: 1111121
}
]
}
}
console.log(findPath(json), “json.book.fiction”) -----> “{fiction:[{title:...,id..}],nonfiction:{title:......}]”

console.log(findPath(json), “json.book.fiction.title”) -----> “Moby Dick”
48. Prune employee tree
Q1. Employee tree, prune the type B employee.

example:

Bob(A) Bob(A)

/ \ / \

Alice(A) Candice(B) ----------> Alice(A) \

/ \ \ / \

Jack(A) Kat(B) Seb(A) Jack(A) Seb(A)

Q2. Candy crush board, create starting board.
49. Lumber cutting
Lumber cutting, given M * N size wood plank, price list for different sizes. What is the maximum profit?

Example: price list ---> 2*2 sells 3\$, 2*3 sells 4\$.

Cutting example: Given 6 * 2 ‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍size wood, can cut into 2X2 and 4X2, which can also be cut into 2X2 2X2 2X2, so the final profit (not max) is 9\$.
50. Print log messages
Struct Log {

String file_name;

String log_message

}

Given list of Log, and max number of logs per log file, print log messages
51. Find count of each question

output: 各个问题的数量，List of integer

5, 2,2,1 => [2,2,1]

10, 2,2,1 => [4,4,2]

20, 3,3,0 => [10,10,0]

19, 3,3,0 => [9,10,0] or [10,9,0]

20, 3,2,1 => [10,7,3] or [9,7,4] or [10,6,4]
52. Guess word game

// Examples: secret / guess

// BAT / CAT -> 2 (A, T), 0 (B != C)

// BAT / TAB -> 1 (A), 2 (B, T)

// AAB / CCA -> 0, 1 (one A in the guess)

// CAC / AAB -> 1, 0 (one A in the guess)

// CCA / AAB -> 0, 1

// AABB / CCAA -> 0, 2 (two As in both words)

53. Convert one word from another

54. Delete node and reconnect

A

/ \

B C

/ / \

D E F

treenode.parent_idx是parent node在array里面的index
1) delete a node and reconnect the children to its parent node
2) delete a subtree
55. Generate based on probability
input是一个dictionary：{output : probability}，output要根据相应的probability来输出output。example：input：{a : 0.3, b : 0.4, c : 0.2, d : 0.1}，output：abacbdbabc. output也可以每次只输出一个，然后qa team可以不断的call这个function来产生output flow，但是要按probability来
56. Find the setting with shortest time
interviewer有一个微波炉，但是他很懒，想以最省力的方法去设定时间，规定cost：每摁一次cost 1，每移动手指一次cost 2，example：‘12:06’ ：摁1 - 移到2 - 摁2 - 移到0 - 摁0 - 移到6 - 摁6，总共cost 1+2+1+2+1+2+1 = 10，找到cost最少的‘时间设置方法’并输出，‘时间设置方法’指：‘12:06’ -> ‘1206’，等效于‘1166’ which is ‘12分06秒’ = ‘11分66秒’ （lz最近没用微波炉，忘了微波炉咋定时了，一开始天真的以为 12*60 + 6 = 1166，写完了跑example的时候发现surprise，给国人算术水平丢人了，对不起）所以‘1206’ cost 10，‘1166’ cost 6 (1+1+2+1+1)，最后输出output ‘1166’. 其中稍微注意一下比如‘60’ <-> ‘1:00’或者少于一分钟的情况，还有微波炉面板最大显示‘99:99’ (每天一个生活小常识get)，最最后input, output都是string
57. Print path from one node to another

1

/ \

2 4

\

5

2->5实际上是["up", "right", "right"]
58. All words combination
Given a query , output all words combinations (ignoring order)就是一个排列组合，backtracking解决，
59. Check word edit distance
GIven two queries, output true if their word edit distance is 1 (one word addition / deletion / modification)
60. Minimum word edit distance
Given two queries, return the minimum word edit distance.
61. Random shuffle song
Given a list of songs and a cooldown period K, create a playlist shuffler that randomly selects a song to play that has not been played in the last K songs（queue+array解决）要求每次rand必须是不在last K里面的
62. In place invert a matrix

63. Write random number generator
Question is to write a random sequence generator [0,N), with a known distribution. For example pdf = [0.126, 0.5, 0.25, 0.124] followup，如何test？
64. Transformer one input to another
Given two copies of an array, each in a different order, find the transformation that would take one as input and produce the second one as output. The problem ‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍coes down to finding array C, such that A[C[i]] == B[i].
65. Count words

num_of_docs 让你写 getTotalCount() machine数没限制
66. Find largest along the tree path for all leaves
Find largest along the tree path for all leaves

5

/ \

4. 2

/ /\

3 6 1{1: 5, 3:5,6:6}

Followup 建 tree on [parent,child] Paris
67. LeetCode 210 There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

```Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So the correct course order is [0,1].
```
Example 2:

```Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take.
To take course 3 you should have finished both courses 1 and 2.
Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
```
Example 3:

```Input: numCourses = 1, prerequisites = []
Output: 
```

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.
68. LeetCode 35
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

```Input: nums = [1,3,5,6], target = 5
Output: 2
```
Example 2:

```Input: nums = [1,3,5,6], target = 2
Output: 1
```
Example 3:

```Input: nums = [1,3,5,6], target = 7
Output: 4
```

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104
69. LeetCode 139
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

```Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
```
Example 2:

```Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
```
Example 3:

```Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
```

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.
70. LeetCode 42 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

```Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
In this case, 6 units of rain water (blue section) are being trapped.
```
Example 2:

```Input: height = [4,2,0,3,2,5]
Output: 9
```

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105
71. LeetCode 274
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return compute the researcher's h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index.

Example 1:

```Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
```
Example 2:

```Input: citations = [1,3,1]
Output: 1
```

Constraints:

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000
72. LeetCode 103
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

```Input: root = [3,9,20,null,null,15,7]
Output: [,[20,9],[15,7]]
```
Example 2:

```Input: root = 
Output: []
```
Example 3:

```Input: root = []
Output: []
```

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100
73. LeetCode 45
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

```Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
```
Example 2:

```Input: nums = [2,3,0,1,4]
Output: 2
```

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
74. LeetCode 435
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

```Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
```
Example 2:

```Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
```
Example 3:

```Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
```

Constraints:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104
75. LeetCode 547
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

```Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
```
Example 2:

```Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
```

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]
76. Robot moving

Find all substrings that meet: length of 6-10, at least 2 letters, at least 2 digits
78. Stock price board
Design stock price board: addPrice(time, price), updatePrice(time, price), deletePrice(time, price), min(), max(), talk with interviewer about time complecity and tradeoffs
79. Sliding window average
Sliding window average but, toss the largest 5%, how to test
80. ID generator

follow up: 如果换不能4个重复怎么改... 或是换成k..?
81. Fold full path
Given list of object folder (有 id, name, parent id)。需要 output 每一个 folder 的 full path。(大约就是 parent path/name 这样）。
Follow up 如何改正 optimize。
82. Random order
Given song list 和 int k。需要写个 function 随机选下一首歌。前提是不可以选 k last played song
83. Word match

Follow up： 现在有 l‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌ist<String> s1, 和 list<string> s2。每一个 s2 看看 s1 里是否有一个符合以上条件的 string, 然后 output list<boolean>。
84. Find path between two nodes

85. Win rate calculation 86. Logs printer

87. 寻找异位词

88. Add two list of string

89. Cord tree

90. Black box

91. List of queues
92. Shortest path

Follow up: 如果不是给两个点，而给你一个list of 开始坐标，和一个list of 结束坐标，你可以从选择从任意开始坐标走到任意结束坐标，问怎么走可以使得每个开始坐标到结束坐标的路径和最小。
93. 餐厅排队系统 94. Find first index after sort

95. Find most frequently element

96. Find index after sort 97. Max value in array

98. String editor

99. Longest subsequence

100. Log file

0002 /cost.html 404 2

follo‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌wup 输出 1，1
101. Word counter
1.写一个function来数每个字符重复的次数.

e.g. input = 'aaabbc'

output = 'a3b2c1'
102. LeetCode 261
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

Constraints:

1 <= n <= 2000

0 <= edges.length <= 5000

edges[i].length == 2

0 <= ai, bi < n

ai != bi

There are no self-loops or repeated edges.

103. Predict the next word
Given some bigrams and with an input word try to predict the best next word (criterias frequency)
［"j"，"am"，"Sam" ]
["Sam"，"am" ]
["j"， "am""Sam" ]
[ "Sam" "am" ]
[ "j"，"am""a"，"Sam""am""j"t"like" ]
104. Type a word in k distance
Given a keyboard (2d-grid each cell is a key). from a position, you can jump at most k distance (Manhatten distance) to another position. Given a word, determine whether you can type the word on the keyboard.
You can always start at the index Where the first letter is.
105. Determine overlapping circles
Given a list of circles (x, y, radius), determine whether they belong to the same group.
Two circles are in the same group if they overlap: dist <= r1 + r2.
Follow up 1: how many groups do we have -> union find已经track
Follow up 2:return the top K largest groups -> union find已经track size了
106. Minimum area rectangle
往grid里加入和删除点的坐标，每次加入和删除return.最小的能cover所有点的方形。clarify之后return左下右上两人点坐标确定方块。
107. 最短路径
一個無限大的boara，給定0的位置，其他皆為1，求出各個到1的最短距離
108. Number of lakes
給一個mxnmatrix，0代表湖泊，决定有多少個innerlake
109. Shortest path in binary tree
binary tree,找p到q的 path
110. LeetCode 299
You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

• The number of "bulls", which are digits in the guess that are in the correct position.
• The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Example 1:

```Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
|
"7810"```
Example 2:

```Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1123"        "1123"
|      or     |
"0111"        "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.
```

Constraints:

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret and guess consist of digits only.
111. Reverse an integer

112. LeetCode 278
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

```Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
```
Example 2:

```Input: n = 1, bad = 1
Output: 1
```

Constraints:

• 1 <= bad <= n <= 231 - 1
113. 中序遍历二叉搜素树

Follow up: with the Iterative approach
114. 100%胜率的出牌顺序

combine的两个条件：
a.如果两卡片高度一致，可以combine
b.如果两操卡片顶端的卡片颜色一致，可以combine
如果当前玩家无法进行combine操作，则另一名玩家获胜
Perfect play：100%的玩家获胜概率，即在这条路线中不存在另一名玩家获胜的结果
需要写一个function，输入为plaver1或plaver2并默认此player是先手，输出为bool
如果当前玩家无法进行combine操作，则另一名玩家获胜
115. 聊天记录文件

人名后面的东西全是message。要求parse这个文件并返回topkword count by person.
116. 实现密码锁

支持的功能：给定某一个圈的index以及旋转的次数如何获得对应的combination
117. LeetCode 1820
There are m boys and n girls in a class attending an upcoming party.

You are given an m x n integer matrix grid, where grid[i][j] equals 0 or 1. If grid[i][j] == 1, then that means the ith boy can invite the jth girl to the party. A boy can invite at most one girl, and a girl can accept at most one invitation from a boy.

Return the maximum possible number of accepted invitations.

Example 1:

```Input: grid = [[1,1,1],
[1,0,1],
[0,0,1]]
Output: 3
Explanation: The invitations are sent as follows:
- The 1st boy invites the 2nd girl.
- The 2nd boy invites the 1st girl.
- The 3rd boy invites the 3rd girl.```
Example 2:

```Input: grid = [[1,0,1,0],
[1,0,0,0],
[0,0,1,0],
[1,1,1,0]]
Output: 3
Explanation: The invitations are sent as follows:
-The 1st boy invites the 3rd girl.
-The 2nd boy invites the 1st girl.
-The 3rd boy invites no one.
-The 4th boy invites the 2nd girl.```

Constraints:

• grid.length == m
• grid[i].length == n
• 1 <= m, n <= 200
• grid[i][j] is either 0 or 1.
118. LeetCode 1962
You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:

• Choose any piles[i] and remove floor(piles[i] / 2) stones from it.
Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

Example 1:

```Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.
```
Example 2:

```Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.
```

Constraints:

• 1 <= piles.length <= 105
• 1 <= piles[i] <= 104
• 1 <= k <= 105
119. Encode and comprees string
Given String "abcdefffgabcde…", encode/compress it, use ".start.end" substitue the repetitve part of substring
output:"abcdefffg.0.4"(s[o]=a,s=e)
120. Generate a sequence that adds up to a given sum.
Generate a sequence that adds up to a given sum.
121. LeetCode 608
Table: Tree

```+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+
id is the primary key column for this table.
Each row of this table contains information about the id of a node and the id of its parent node in a tree.
The given structure is always a valid tree.
```

Each node in the tree can be one of three types:

• "Leaf": if the node is a leaf node.
• "Root": if the node is the root of the tree.
• "Inner": If the node is neither a leaf node nor a root node.
Write an SQL query to report the type of each node in the tree.

Return the result table ordered by id in ascending order.

The query result format is in the following example.

Example 1:

```Input:
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+
Output:
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
| 2  | Inner |
| 3  | Leaf  |
| 4  | Leaf  |
| 5  | Leaf  |
+----+-------+
Explanation:
Node 1 is the root node because its parent node is null and it has child nodes 2 and 3.
Node 2 is an inner node because it has parent node 1 and child node 4 and 5.
Nodes 3, 4, and 5 are leaf nodes because they have parent nodes and they do not have child nodes.
```
Example 2:

```Input:
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
+----+------+
Output:
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
+----+-------+
Explanation: If there is only one node on the tree, you only need to output its root attributes.```
122. Time blocks

第一问，求有哪些天是所有人都available的，return list of days。
第二问，现在非所有人而是有K个人available，return list of days for K people
第三问，现在要相同的K个人，在连续的d天里都available，return list of day ranges for a same K people.
123. Generate random questions

例子是
total 13，ratio 0.5，0.3，0.2
total 5，ratio 2，1，1
注意ratio并不一定add up to something。
124. 实现file system

125. Minimum flight cost
Flight costs, flightCosts[from][day] =c, if c!= O,we can flight, find the schedule with minimum cost that covers all cities, optimize the searching
126. LeetCode 778
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Example 1:

```Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
```
Example 2:

```Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
```

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] < n2
• Each value grid[i][j] is unique.
127. LeetCode 720
Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Example 1:

```Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
```
Example 2:

```Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary.
However, "apple" is lexicographically smaller than "apply".
```

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 30
• words[i] consists of lowercase English letters.
128. LeetCode 704
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

```Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
```
Example 2:

```Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
```

Constraints:

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.
129. LeetCode 280
Given an integer array nums, reorder it such that nums <= nums >= nums <= nums....

You may assume the input array always has a valid answer.

Example 1:

```Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.
```
Example 2:

```Input: nums = [6,6,5,6,3,8]
Output: [6,6,5,6,3,8]
```

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 104
• It is guaranteed that there will be an answer for the given input nums.

Follow up: Could you solve the problem in O(n) time complexity?

130. LeetCode 55
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

```Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
```
Example 2:

```Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
```

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105
131. 设计一个NumContainer Class
"设计一个NumContainer Class，用于保存一系列数字，其中包括两个方程：
InsertOrReplace(lndex,Number)，就是在given index的位置插入或替换数字
findMinimumlndex(Number)，找到现在container里面最小数字的位置"

132. 实现一个记录大气温度的class
"只需要记录过去24小时每秒的温度，其中包括两个方程

133. Data movement

134. 判断胡牌
"用川麻的规则，给14张麻将牌，设计一个算法，判断这手14张麻将牌胡了没有

11123466778899胡了
11112345678899没胡
11223344556677七小对胡了

135. Find raw ingredient
"假设你是chef,你要准备菜单上的几道courses ，已知每个courses 的raw ingredients和intermediate ingredients， 给你list of courses, output是list of raw ingredient

Course Name: Pizza
intermediate ingredients: N/A
raw ingredients:flour ,cheese ketchup, suger
Course Name: Steak
raw ingredients: Beef, Oil
intermediate ingredients:N/A
raw ingredients: veg,egg,sauce
raw ingredients:flour ,suger ,oil
Course NAME: sandwich
intermediateingredients: N/A
raw ingredients: flour, Suger oil, beef

veg,egg,sauce】"

136. 找到最长递增string list
"给你一个string set，比如：（den，dent，dents，dew，det，bet，bent），找到最长的递增
string list递增的规则是前一个string尾部增加一个字母变成后一个string。

137. 设计一个Word store Service
"实现两个 method: add Word(String word) requestWord（）
requestWord（）从wordStore 中pop 一个word出来
Constraint：同一人首字母开头的单词不能在1s内同时出现两次
example:
requestWord（）return apple
requestWord()return banana
requestWord()return null （已经return 过word starts with A，可以理解为前三个requestWord 是synchronized calls)
//after 1s
requestWord() return Apple"

138. Maze Generation Algorithm
"实现一个算法：Maze Generation Algorithm
Step 1:生成一个sides box length = N，每条边XO 交叉排列，每条边X的数量=N
Step2:随机选择一个有效的X
Step3：对step2选择的X随机选择一个有效的方向（4 directions)
Step4:对随机选择的X随机选择的方向延伸标记O和X
Step5:如果还有可以选择的x，那么重复Step2
example:
If N=3
Box:
XOXOX
O   O
XOX XO. O
XOXOX.
(所有的X都没有足够的空间再放置OX)算法结束"

139. 最短路径
"从一个点到另一个点的最短路径， BFS和DFS都可以有什么利弊。

140. LeetCode 1200
Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.
Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]
Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

2 <= arr.length <= 105
-106 <= arr[i] <= 106
141. Split BST
Split a binary search tree by a pivot

142. max sum of subMap

143. LeetCode 523
Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

Constraints:

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1
144. LeetCode 747
You are given an integer array nums where the largest integer is unique.

Determine whether the largest element in the array is at least twice as much as every other number in the array. If it is, return the index of the largest element, or return -1 otherwise.

Example 1:

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest integer.
For every other number in the array x, 6 is at least twice as big as x.
The index of value 6 is 1, so we return 1.
Example 2:

Input: nums = [1,2,3,4]
Output: -1
Explanation: 4 is less than twice the value of 3, so we return -1.
Example 3:

Input: nums = 
Output: 0
Explanation: 1 is trivially at least twice the value as any other number because there are no other numbers.

Constraints:

1 <= nums.length <= 50
0 <= nums[i] <= 100
The largest element in nums is unique.
145. 设计一个iterator
"input一个长度为偶数的数组，odd位置是重复次数，even位置是数字，设计一个iterator的next（） function，return 下一个应该print的数字比如[1,2,3，4]用iterator遍历完应该输出2.2.4,4,4

146. Graph traversal

147. LeetCode 73
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

```Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
```
Example 2:

```Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
```

Constraints:

• m == matrix.length
• n == matrix.length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

• A straightforward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?
148. LeetCode 166
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 104 for all the given inputs.

Example 1:

```Input: numerator = 1, denominator = 2
Output: "0.5"
```
Example 2:

```Input: numerator = 2, denominator = 1
Output: "2"
```
Example 3:

```Input: numerator = 4, denominator = 333
Output: "0.(012)"
```

Constraints:

• -231 <= numerator, denominator <= 231 - 1
• denominator != 0
149. LeetCode 588
Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

• FileSystem() Initializes the object of the system.
• List<String> ls(String path)
• If path is a file path, returns a list that only contains this file's name.
• If path is a directory path, returns the list of file and directory names in this directory.
• The answer should in lexicographic order.
• void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.
• void addContentToFile(String filePath, String content)
• If filePath does not exist, creates that file containing given content.
• If filePath already exists, appends the given content to original content.
• String readContentFromFile(String filePath) Returns the content in the file at filePath.

Example 1:

```Input
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"
```

Constraints:

• 1 <= path.length, filePath.length <= 100
• path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/".
• You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
• You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
• 1 <= content.length <= 50
• At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.
150. LeetCode2242
There is an undirected graph with n nodes, numbered from 0 to n - 1.

You are given a 0-indexed integer array scores of length n where scores[i] denotes the score of node i. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

A node sequence is valid if it meets the following conditions:

• There is an edge connecting every pair of adjacent nodes in the sequence.
• No node appears more than once in the sequence.
The score of a node sequence is defined as the sum of the scores of the nodes in the sequence.

Return the maximum score of a valid node sequence with a length of 4. If no such sequence exists, return -1.

Example 1:

```Input: scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 24
Explanation: The figure above shows the graph and the chosen node sequence [0,1,2,3].
The score of the node sequence is 5 + 2 + 9 + 8 = 24.
It can be shown that no other node sequence has a score of more than 24.
Note that the sequences [3,1,2,0] and [1,0,2,3] are also valid and have a score of 24.
The sequence [0,3,2,4] is not valid since no edge connects nodes 0 and 3.
```
Example 2:

```Input: scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
Output: -1
Explanation: The figure above shows the graph.
There are no valid node sequences of length 4, so we return -1.
```

Constraints:

• n == scores.length
• 4 <= n <= 5 * 104
• 1 <= scores[i] <= 108
• 0 <= edges.length <= 5 * 104
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• There are no duplicate edges.
151. Delete node from forest

一个结点，输出删除后的数组表示。
比如[-1,0,0,2,3,1]的是index为1和2的结点与根节点相连，index为3的结点与index为2的结点相连，总之就是数组的数值表示的是当前index的结点连接的父结点，比如删除index=3的结点，返回结果应该是[-1,0,0,1]
又比如[-1,0,0,2,2,3,4] 删除index=3的结点,返回[-1,0,0,2,3]
注意：删除所有与删除结点连接的点，同时还要注意更新index
152. Mutiplication of two big numbers
"calculate the result for the mutiplication for two big numbers (big number means the number is even larger than type long).

153. 套娃问题

154. Similar pattern

155. design monitoring system with metrics and alerts
Design monitoring system with metrics and alerts

156. design an interactive dialogue prediction system
Design an interactive dialogue prediction system

157. design an interactive dialogue prediction system
Design an interactive dialogue prediction system

158. 实现csv的parse功能

159. Closest Cafe for everyone
"有一群好朋友要在学校里找个距离所有人最近的咖啡厅，前提是必须让所有的好朋友都能到达。
Friends array:[1,2] Cafe array:[4,5].给一个二维数组代表图里面连接的边：（（1,2)，（1,5)，(2,4)），返回距离最近的咖啡厅。

160. Design a class organization
"Design a class organization
setPeer(personA，personB)=>把person A和person B设为peer，代表着这两人将有相同的上司
reportsTo(personA，personB)=》给定两个人，返回person B是否是person A的上司，注意不一定是直属上司"

161. 实现快进功能
""AM/PM""]）。
E.g 有两个button[23,59]，[0,2]。要快进三分钟的话就是按两下第二个按钮再按一下第一个按钮。"

162. 验证不等式
"给了一个array =[('d’, '>’，'e’),( 'e’，'>’，'f’)]，里面每个元素包含三个部分。这三个部分合起来表示一个不等式运算，问把这些不等运算放在一起之后，会不会形成一个valid的不等式?如果能就return true;否则false。

163. 最短通行时间
"给一个2-d列表，每个cell代表一个城市，每个城市有一个红绿灯，一开始都是红灯，每个cell的数字代表红灯变绿的时间，也说明你可以离开这个城市，红灯说明不能离开城市，返回最快从左上到右下的时间

164. 邮箱数据导入
"要进行qmail和其他邮箱系统数据导入，其他系统的邮箱系统是用folder {id: 27,parentld: 15,name:'projects‘},表示的。

Sample input:

folders=[

{id: 27,parentId: 15, name: 'projects'},

{id:81, parentId: 27, name: 'novel'},

{id:15, parentId: -1, name: 'personal'}, // a parentid of -1 means root, some of the ariant using 0 to represent root.

{id: 35， parentId:27, name: 'blog'},
]

Sample output:

labels = [

displayName: ‘projects', path: ‘personal/projects',

displayName: ‘novel',path:‘personal/projects/novel'

displayName:‘personal', path:‘personal',

displayName:‘bloe‘,path:’personal/proiects/blog‘.
]

List<Label> folderToLabels(List<Folder> folders)
{write your excellent code here}"

165. Leetcode 1293
You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

```Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6.
Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
```
Example 2:

```Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.
```

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 40
• 1 <= k <= m * n
• grid[i][j] is either 0 or 1.
• grid == grid[m - 1][n - 1] == 0
166. file system
一个类file system的Map（key:entityld,value: entityObject）。两种entity 一种directory 一种file 都有ld。directory会有children，fle会有size。
1.给定一人entityld 怎么计算他的size（包括children的）。
2.给一个List of entity, return list of entity size。
3.给 个entity id 怎么absoluteprint entity path。
167. number of unique number

168. transform an integer

95929->99529
169. LeetCode 323
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Example 1:

```Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
```
Example 2:

```Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
```

Constraints:

• 1 <= n <= 2000
• 1 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai <= bi < n
• ai != bi
• There are no repeated edges.
170. LeetCode 2246
You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Example 1:

```Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path:
0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions.
```
Example 2:

```Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path:
2 -> 0 -> 3. The length of this path is 3, so 3 is returned.
```

Constraints:

• n == parent.length == s.length
• 1 <= n <= 105
• 0 <= parent[i] <= n - 1 for all i >= 1
• parent == -1
• parent represents a valid tree.
• s consists of only lowercase English letters.
171. LeetCode 2196
You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,

• If isLefti == 1, then childi is the left child of parenti.
• If isLefti == 0, then childi is the right child of parenti.
Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

Example 1:

```Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.
```
Example 2:

```Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.
```

Constraints:

• 1 <= descriptions.length <= 104
• descriptions[i].length == 3
• 1 <= parenti, childi <= 105
• 0 <= isLefti <= 1
• The binary tree described by descriptions is valid.
172. Design Steam
Design steam的上线，隐身系统
173. LeetCode 295
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

```Input
[[], , , [], , []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = 
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
```

Constraints:

• -105 <= num <= 105
• There will be at least one element in the data structure before calling findMedian.
• At most 5 * 104 calls will be made to addNum and findMedian.

• If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
• If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
174. Design donation system

175. implement booking system

176. remove floor

1.[0,0,0]->remove 9层floor
2.[1.1,1]->remove 6层floor
3.[0,3,3]->remove 3层floor (返回这个3)
4.[0,0,5]->remove 4层floor
177. remove leaf node

178. shortest path

179. 设计WaitList系统

180. 求list中第二大的数

181. timestamp + string
Input是timestamp + string，例{1，abc}，{3,abc}.(9，efg}，{12,abc}{24,abc}

a== b, b== c, c==a- -> true

Follow up 1:operator加上了<：a== b, b ==a, b<a--> false，a< b, b== c, a<c --> true
Follw up 2:operator 加上了<=
183. LeetCode 1048

如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。

例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。

从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
184. LeetCode 843
This is an interactive problem.

You are given an array of unique strings wordlist where wordlist[i] is 6 letters long, and one word in this list is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or fewer calls to Master.guess and at least one of these guesses was secret, then you pass the test case.

Example 1:

```Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"], numguesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4, because "abcczz" has 4 matches.
We made 5 calls to master.guess and one of them was the secret, so we pass the test case.
```
Example 2:

```Input: secret = "hamada", wordlist = ["hamada","khaled"], numguesses = 10
Output: You guessed the secret word correctly.
```

Constraints:

• 1 <= wordlist.length <= 100
• wordlist[i].length == 6
• wordlist[i] consist of lowercase English letters.
• All the strings of wordlist are unique.
• secret exists in wordlist.
• numguesses == 10
185. LeetCode 427
Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

• val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
• isLeaf: True if the node is leaf node on the tree or False if the node has the four children.
```class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}```
We can construct a Quad-Tree from a two-dimensional area using the following steps:

1. If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
2. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
3. Recurse for each of the children with the proper sub-grid.
If you want to know more about the Quad-Tree, you can refer to the wiki.

The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example 1:

```Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
```
Example 2:

```Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
```

Constraints:

• n == grid.length == grid[i].length
• n == 2x where 0 <= x <= 6
186. LeetCode 57
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:

```Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
```
Example 2:

```Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
```

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 105
187. LeetCode 161
Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

Insert exactly one character into s to get t.

Delete exactly one character from s to get t.

Replace exactly one character of s with a different character to get t.

Example 1:

Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "", t = "" Output: false Explanation: We cannot get t from s by only one step.

Constraints:

0 <= s.length, t.length <= 104

s and t consist of lowercase letters, uppercase letters, and digits.
188. LeetCode 818
Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse):

• When you get an instruction 'A', your car does the following:
• position += speed
• speed *= 2
• When you get an instruction 'R', your car does the following:
• If your speed is positive then speed = -1
• otherwise speed = 1
• Your position stays the same.
For example, after commands "AAR", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.

Example 1:

```Input: target = 3
Output: 2
Explanation:
The shortest instruction sequence is "AA".
Your position goes from 0 --> 1 --> 3.
```
Example 2:

```Input: target = 6
Output: 5
Explanation:
The shortest instruction sequence is "AAARA".
Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.
```

Constraints:

• 1 <= target <= 104
189. LeetCode 393
Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

1. For a 1-byte character, the first bit is a 0, followed by its Unicode code.
2. For an n-bytes character, the first n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.
This is how the UTF-8 encoding would work:

```     Number of Bytes   |        UTF-8 Octet Sequence
|              (binary)
--------------------+-----------------------------------------
1          |   0xxxxxxx
2          |   110xxxxx 10xxxxxx
3          |   1110xxxx 10xxxxxx 10xxxxxx
4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
```
x denotes a bit in the binary form of a byte that may be either 0 or 1.

Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

```Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
```
Example 2:

```Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.
```

Constraints:

• 1 <= data.length <= 2 * 104
• 0 <= data[i] <= 255
190. 构建full binary tree

*
/   \
e    *
/  \
b   z

1.深度最低的永远先排在左侧
2.如果深度相同则按照字母顺序小的在左侧
191. ip address validator

192. 计算传纸条到target坐标的概率

193. 填字游戏

*......*
|O##|
|#C#D M|
IG LEI
|#### #|
*......*

194. 寻找二叉树中节点最多的BST
find the biggest BST in binary tree return number of nodes.
195. 设计一个翻译系统

196. find the longest continuous "0"

Example:
Taken Free Free Free Free Taken Free
[1,0.00010J
return the longest continuous 'O' in the array
197. Leetcode 269
There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Example 1:

```Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
```
Example 2:

```Input: words = ["z","x"]
Output: "zx"
```
Example 3:

```Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".
```

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of only lowercase English letters.
198. Leetcode 359
Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

• Logger() Initializes the logger object.
• bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example 1:

```Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21
```

Constraints:

• 0 <= timestamp <= 109
• Every timestamp will be passed in non-decreasing order (chronological order).
• 1 <= message.length <= 30
• At most 104 calls will be made to shouldPrintMessage.
199. 随机playlist

200. 判断是否有一半元素大于mean
input array of integer, start, end, target, check if more than half of elements in the
range equals to target
i.e [1,2,3,3,3456] start =1end =6target=3-> True 因为3出现3次>5/2

[1,2,3,3,3,4,5,6] start = 0, end = 4, target = 3 -> True 因为3出现2次 <= 4/2 (需要more than half

followup: ln real world situation, if array contains more than billions of integers, but it stays the same for every call.How do you optimize your solution?
201. find common subString

202. 实现integer generator

203. 查询子序列中的单词
input: 1) 一个string， 比如""cxadxrxetw""; 2) 一个list of words， 比[“cat", "cart","drew",
"xyz","tax"]

output: ["cat", ""cart"", ""drew""]
explain:
"xyz"不满足，因为string中没有"y" "z"
"tax"不满足，因为要求从左向右阅读string
string中的字母可以多次使用

output: ["ccc" "cxxa"]
204. 实现double linked list

205. employee report dictionary

206. 设计一个review系统

207. LeetCode 20
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

```Input: s = "()"
Output: true
```
Example 2:

```Input: s = "()[]{}"
Output: true
```
Example 3:

```Input: s = "(]"
Output: false
```

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.
208. LeetCode 792
Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1:

```Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".
```
Example 2:

```Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2
```

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.
209. LeetCode 289
According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

Example 1:

```Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
```
Example 2:

```Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]
```

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j] is 0 or 1.

• Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
• In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?
210. LeetCode 695
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

```Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
```
Example 2:

```Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
```

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.
211. LeetCode 279
Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

```Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
```
Example 2:

```Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
```

Constraints:

• 1 <= n <= 104
212. valid inequality

和c的大小矛盾了，就要return false。
213. 设计查询机票系统

departurePlace）SearchPlane(time,departurePlace)要求只返回一个距离目标时间最近的飞机id，deletePlanelnfo(planeID,departureTime)
214. 实现一个统计功能
| 设计一个data structure，需要支持两种操作
1.insert。就是插入一个integer
2.get。假设之前插入的所有数的中位数是x，那么这个get操作需要返回任意的一个数y，y必须满足x<=y<= x*2
follow-up是比如在x=y<=x*2这个等式中，如果x不是中位数而是比如10%的percentile怎么办。
215. 合并前缀树
| 合并前缀树.
例子，bat,bac
"->b->a->t:count=1
"->b->a->t:count=2
-> c: count= 1
输出："->b->a->t:count=3
-> c: count= 1
216. 设计一个广告系统
| 假设一个广告系统，每个客户都有每天投放的金额比如一千刀.每个点击1刀，设计一个系统统计广告的实际投放金额大于等于客户的投放金额就不投放广告了
217. 捷豹跳跃组合

例子，[a,b],[0,1],[m,n]=>[a,0,m],[a,0,n],[a,1,m],[a,1,n],[b,0.m],[b,0,n],[b,1.n],[b,1,m]
218. 实现一个waitList class
就是平常你去餐厅吃饭如果要等位的话排队取号，功能很简单,可以添加或者删除group，当有空位的时候还应该有个api去实现后续的操作。
219. Guess Color
| 4个slot，首先作为知道答案的人，比如知道答案是["red"，"red"，"green"，"blue”]，得到
个别人给的猜测，比如［"blue"，"red"，"green"，"red"］，两个颜色和位置都猜对，返回两
个黑色的灯，另外两个颜色对，位置不对给两个白色的灯。写一段code根据guess的内容返回给多少黑灯，多少白灯。
return false，有可能就return true。
220. LeetCode 1293
You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

```Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
```
Example 2:

```Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.
```

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 40
• 1 <= k <= m * n
• grid[i][j] is either 0 or 1.
• grid == grid[m - 1][n - 1] == 0
221. LeetCode 2190
You are given a 0-indexed integer array nums. You are also given an integer key, which is present in nums.

For every unique integer target in nums, count the number of times target immediately follows an occurrence of key in nums. In other words, count the number of indices i such that:

• 0 <= i <= nums.length - 2,
• nums[i] == key and,
• nums[i + 1] == target.
Return the target with the maximum count. The test cases will be generated such that the target with maximum count is unique.

Example 1:

```Input: nums = [1,100,200,1,100], key = 1
Output: 100
Explanation: For target = 100, there are 2 occurrences at indices 1 and 4 which follow an occurrence of key.
No other integers follow an occurrence of key, so we return 100.
```
Example 2:

```Input: nums = [2,2,2,2,3], key = 2
Output: 2
Explanation: For target = 2, there are 3 occurrences at indices 1, 2, and 3 which follow an occurrence of key.
For target = 3, there is only one occurrence at index 4 which follows an occurrence of key.
target = 2 has the maximum number of occurrences following an occurrence of key, so we return 2.
```

Constraints:

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• The test cases will be generated such that the answer is unique.
222. LeetCode 1944
There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.

Example 1:

```Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.
```
Example 2:

```Input: heights = [5,1,2,3,10]
Output: [4,1,1,1,0]
```

Constraints:

• n == heights.length
• 1 <= n <= 105
• 1 <= heights[i] <= 105
• All the values of heights are unique.
223. 预测实时手机battery life time

224. generate array list
Input: even integer i
return:array a
Requirement1: all elements in a are distinct, even and the sum of a is equal to i:
Requirement2:the length of array is maximum
225. number of good pair

good pair：
1.（i,j）和(j,i)是否算两对
2.是否考虑i=j的情况
226. 设计歌单分享

227. 键值更新

[1，10],[2,10],[1,20]

228. LeetCode 207
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

Example 1:

```Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
```
Example 2:

```Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
```

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.
229. LeetCode 46
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

```Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```
Example 2:

```Input: nums = [0,1]
Output: [[0,1],[1,0]]
```
Example 3:

```Input: nums = 
Output: []
```

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.
230. Design a simple spreadsheet
Design a simple spreadsheet with basic operations of update, lookup, and a per column and per row level operator of get_sum. How to support all other different operators eg.get_max, get_min.
231. LeetCode 21
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

```Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
```
Example 2:

```Input: list1 = [], list2 = []
Output: []
```
Example 3:

```Input: list1 = [], list2 = 
Output: 
```

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.
232. LeetCode 23
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```
Example 2:

```Input: lists = []
Output: []
```
Example 3:

```Input: lists = [[]]
Output: []
```

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.
233. Leetcode839
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}.  Notice that "tars" and "arts" are in the same group even though they are not similar.  Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

Example 1:

```Input: strs = ["tars","rats","arts","star"]
Output: 2
```
Example 2:

```Input: strs = ["omv","ovm"]
Output: 1
```

Constraints:

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] consists of lowercase letters only.
• All words in strs have the same length and are anagrams of each other.
234. secret Word

（1）如果input Word中的这个char没有出现在secret Word中，则返回R
（2）如果char出现在secret Word中但secret Word中对应位置不是这个char，返回Y
（3)如果char出现在secret Word中且secre tWord中对应位置是这个char，返回G
236. 拓扑排序

237. 设计gmail 定时删除功能

240. 二叉树最底层宽度