Google计算机科学面试真题

职位分类
全部
数据科学
数据分析
计算机科学
人工智能
产品经理
BQ
面试题
全部(240)
Coding(163)
System Design(20)
Algorithm(30)
Ood(15)
高频题(6)
全部(240)
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
31.Find basket counts
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
77.Passwords substrings
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
182.valid contradiction
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
191.ip address validator
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.查询子序列中的单词
204.实现double linked list
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
经典dijkstra题 给一些地点和两地之前飞机票的价钱 问两点最小cost怎么走.
3. Leetcode 1273
leetcode 1273
4. Find string with prefix
给一个string array 和一个string pre,找array里所有有pre作为prefix的string.
5. Design filesystem
要求实现一个function计算directory/file的size,添加一个file entity以及给你一个entity,判断是否合法(判断sub directory or file是否存在环.
6. Build tower
给两个int m,n 代表matrix长和宽,再给两个API buildTower(), stop(). call 一次buildTower()会返回matrix上点的坐标, 表示在这个点上建塔,stop()就是停止建塔.matrix左右两侧各有一个city, 分别与matrix第一列/最后一列相连.问要call几次能使得两个city通过tower联通.
7. Number of pointer on the upper right
给一堆点,每个点x,y坐标都是整数且都不重复,求每个点的在他右上的点的数量。用segment tree或者treeset做
8. Possibility of dices
n个k面色子 输出每种和的概率数组 比如2个2面色子 输出 [0.25, 0.5, 0.25]
9. Generate similar string
生成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
处理transaction

已知有一个函数processTX([tx1, tx2, ... txn])可以处理transaction [tx1, tx2, ... txn],如果transaction中所有entries都是good entries,那么processTX返回true;否则返回false。processTX是一个black box。

要求写handleTX([tx1, tx2, ... txn])来处理任意transaction,要求为:

1. 调用完后,所有good entries都被processTX调用过一次
2. 调用processTX的次数足够少
11. Transmit signal
给一个Router List, 包含所有router的坐标x,y. 设定Router 的最大无线传播距离为k. 求Router A是否能够把信号传播到Router B
12. Leetcode 315
给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1:

输入:nums = [5,2,6,1]
输出:[2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2:

输入:nums = [-1]
输出:[0]
示例 3:

输入:nums = [-1,-1]
输出:[0,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

receive messages.

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

问:Given a list of routers' locations (their names and the corresponding 2D coordinates), tell me whether a message from

Router A can reach Router B. Write a method / function with appropriate input and output arguments.
16. Convert matrix to all zeros
给一个matrix,只包括0和1,可以不断的翻转行或者列,请问是否能让这个matrix全是0?翻转某行或者某列的意思是,此行或者此列的1会变成0,0会变成1.

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
设计一个function 随机从一个playlist 里面播放歌曲,播放过的歌曲冷却时间为k, 也就是说当前播放的一首歌,在接下来k首里面不能出现.
18. Find closest station
有很多通信基站的位置,[[lat1, long1], [lat2, long2] ... ],这些位置信息会load到手机里,手机可以随时获取到自己的位置,设计一个数据结构能够快速查找距离手机最近的基站.
手机的位置是一直在变的,所以和每个基站的距离也在变,而且查找最近基站的方法会被调用很多次.
19. Atom and bond match
有碳氢氧三种原子,每个碳原子需要有4个化学键,氧原子2个,氢原子1个,才能算是满足要求. 提供一个叫做atoms的map,key是原子的id,value是原子的元素 {1: "C", 2: "O", 3: "O"},还提供一个bonds的list,代表哪两个原子间有化学键连接,[[1, 2], [1, 2], [1, 3], [1, 3]],根据atoms和bonds,输出是否满足要求.
20. Decide order of tasks
cpu 分配task. 给一串tasks = [[id, available time, duration], ... ],available time是一个task最早可以执行的时间,可以在这之后执行. duration是执行task需要的时间。有多个available tasks的时候先执行duration最‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍短的.要求输出task的执行顺序. 用heap做的复杂度nlogn
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
设计一个复利计算mortgage的页面
25. Number of matching subsequences
Number of Matching Subsequences的变种,先写了brute force,然后又写了最优解存dictionary的pseudo code.让分析了time complexity
26. Router send message
平面里有一些routers,它们的通讯半径是k,问一个msg从某个开始传然后可以传到哪些routers.DFS无压力.很快写完以后就开始further
27. Check validity of input
写check input是不是valid, test case,改input的format,从index改成class,讨论如果要知道n个router都连了哪些,怎么快速查找啥的
28. Remove elements within distance
给一个incoming data stream, 给一个distance D,要求如果data stream中出现连续三个within the distance D的elements,就remove the three elements from the memory (aka扔掉)。

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
给一个pool = [a,b,c], 又一堆baskets: basket1 = [a,b], basket2 = [b,c], basket3 = [a,b,c],还有个m=2,要求返回pool里长度为m的所有subsequence分别在这堆baskets里的出现次数。这里subsequence有[[a,b], [a,c], [b,c]] return一个{[a,b]:2, [a,c]:1. [b,c]:2} key是subsequence,val‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍ue是分别出现了2次1次2次.
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有多少?

用map 记录statusCode 和count的就好

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
类似Employee Importance:

每个manager下面有一些员工,

给一个manager ID, 看有多少员工report给他

先后讲了dfs, bfs 实现

和 加memo的优化

Follow UP:

added one more constraint,

如果a manger could have at most K reportee

新加入一名员工分配给谁, 没要求实现,讲了可以把所有的manager按reportee个数排序,如果新加入的

员工指定的manager已经超过了K reportee, 则分配给当前最少的manager, 否则分配给原先指定的manager
34. Buid character of length L
给一个dict, 用dict里的char组成长度为L的字符串,且连续相同的字符不能超过K个

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
给一些菜,每个菜需要一些ingredient才能做好,其中包括raw ingredient和intermediate ingredient,intermediate ingredient可以是其它的菜。然后给了available的raw ingredient,问可以做出哪些菜.
36. Find max rectangle
给一个M*N的矩阵,问其中所有边长为K的正方形里的数的最大值-最小值最大可以是多少.
37. Find anagram
给一组单词,如果这个单词的anagram也在输入列表里就返回. anagram指的是旋转180度之后的新单词,比如axe的anagram还是axe,pz的anagram是zd这样的.
38. Leetcode 694
leetcode 694
39. Prepare dishes
一个餐厅经理要设置菜单,有很多recipe,和 one set of raw ingredients,问当天能上什么菜

recipe 的例子:

1)hamburger

intermediate ingredient: bread

raw ingredient: vegetable, meat

2)bread

intermediate ingrediant: none

raw ingredient: flour, water

如果有 raw ingredients:vegetable, meat, flour, wate‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍r的话,就能做 hamburger 和 bread

如果有 raw ingredients:vegetable, meat, water的话,就什么都不能做
40. Check cards
给3张卡牌,卡牌有4个属性,3张卡牌的属性全都一样或者全不一样就是一组,判断这3张卡牌是不是一组. 我用了hashmap计数. Follow up给任意张卡牌(数量大于等于2)问了时间复杂度
41. Design API for chess
OOD: 给类似5子棋的游戏设计api
42. Delete nodes for binary tree
从叶子开始任意顺序删除二叉树的所有结点,返回删除节点序列.
43. Find substring
给一个string返回这个string的子序列. 要求1.新的子串不曾出现过,如果出现过新的子串需要为一个字符和之前见过的子串的组合 2. 所有子串连在一起能拼成输入的string 3. 新的子串要尽可能的长. Ex: 输入 string “baaaaaabio”,输出[b,a,aa,aaa,bi,o].
44. All people know the story
一开始只有0知道故事. 给一个list of meetings represented by tuple。 ex:(1,2,100)代表1和2在时间100时meet.  如果1和2当中有人知道故事那么另一方在meet后也会知道故事。 要求return一个list里面是在所有事件结束后知道故事的人. 
45. Sum of digits
给定整数N,求Sum of digits; follow up是如果可以利用cache,怎样让速度快一些. 可以用int array存一些计算好的结果;
46. Check if a word is valid
提供一个lib function:is_in_dictionary可以验证一个词是否valid. 已知一个词超过两个连续重复字母一定不valid,如heeelllo。但是可以通过shrink超过两个重复‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍字母的地方而变成hello,就valid了. 要求写一个可以验证单词是否能通过shrink变成valid的function.
47. Find path
 “{fiction:[{title:...,id..}],nonfiction:{title:......}]” console.log(findPath(json), “json.book.fiction[0].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[0].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)

做完问了我complexity.

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
总问题数,和各个难度问题的比例,int totalQuestions, doube easy, double medium, double hard

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
猜词游戏,游戏有一个secret word,然后玩家每次猜一个单词,然后返回2个数字,第一个数字告诉你在猜的单词中有几个字母完全猜对(字母的位置和secret word里字母的位置一样),第二个数字告诉你猜对了几个字母,但是位置不对

举例:

// 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)

写一个function来‍‍‌‌‌‌‍‍‍‍‌‍‌‍‍‍‍‍‍‍实现. guessword(secret, guess string) -> (match, exist)
53. Convert one word from another
全大写word1,add a single character and shuffle得到word2,给你word1 word2问你word2能不能由word1得到。example:word1: 'ACT' -> add 'K' -> 'ACTK' -> shuffle -> word2 = 'TACK' example 2: word1 = 'ACT', word2 = 'TASK' -> False. character可以duplicate
54. Delete node and reconnect
给一个treenode,treenode.parent_idx: int, treenode.data: str。给一个array of treenode,类似:[(A, 0), (B, 0), (C, 0), (D, 1), (E, 2), (F, 2)] (treenode.data, treenode.parent_idx)

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
给一个binary tree, 和2个树上的节点node1, node2, 输出从node1到node2的路径。

输出的格式不是按照node输出,而是输出一个List<String>,比如说这个树:

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
左右翻转 一个bool matrix,要求in place,内存已知存不下整个matrix,输入格式uint8_t 指针
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
给 CountWords(machine_id, doc_id) 返回一个class 异步 is_done(), data()->int (会阻塞直到data available)

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: [0]

 

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: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

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
给一个二维grid,每个格子有一个颜色,[0, 0] 位置有一个机器人,机器人的移动方向由所在格子的颜色决定。有0-7八种颜色,每个颜色可以map到一个方向。终点已知,并且机器人一定能从起点(0,0)走到终点。输出每个颜色代表的方向
77. Passwords substrings
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
写出一个 id generator。不可以 3 个重复的号
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
给两个 string,看看 s1 是否可以加一个字母,然后重新排列组成 s2。

Follow up: 现在有 l‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌ist<String> s1, 和 list<string> s2。每一个 s2 看看 s1 里是否有一个符合以上条件的 string, 然后 output list<boolean>。
84. Find path between two nodes
一个binary tree,找两个node的path
85. Win rate calculation
给你一个一个数组,其中的每一个元素代表一个player。举例:[1,2,3,4] , 有4个player,player 1先和player 2比,player 3和player 4比,赢的人再互相比。直到剩下最后一个人为止。
然后再给你一个概率的matrix 比如matrix[1][2] = 0.7 就代表了player1和player2比,player1赢得概率是0.7。求最终最有可能获胜的选手。
86. Logs printer
有一个logs:[alice: ["fefefe" , "gergrege"] , bob: ["123213","43435"]],要求你尽可能的平均输出n个信息,用刚才的例子的话,比如n = 2,那就是输入一条alice的和一条bob的,如果n=3,那就是2条alice的和1条bob的,如果n=4,那就是两条alice的和两条bob,如果n=5,也是两条alice和两条bob。
87. 寻找异位词
给你一个list of string,里面的string长度都一样,要求找出里面是否存在有两个string,他们只有一个index上的char不同。比如 abcd 和 abce,他们只有最后一位不同,符合条件。
88. Add two list of string
给你n个数组,每个数组长这样 [(0,3,4), (4,6,8)]. (0,3,4)代表的意思是从index 0到index 3的高度是4‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌, 以此类推。然后让你把这n个数组的高度相加,输出一个总数组。
比如[(0,3,4), (4,5,2)] + [(0,2,1), (3,5,4)] = [(0,2,5),(3,3,8),(4,56)]
89. Cord tree
第一问,get index, 第二问, get range
90. Black box
每次只能pop出一个中位数,要求return一个sorted list
91. List of queues
pop()操作很expensive,尽量少用,让你找最短的queue,follow up找最小sum的queue。
92. Shortest path
给一个integer矩阵和两个坐标start, end. 找到在矩阵中从start 走到 end的最短距离(只能横向或纵向走)。而且矩阵中有的点是不能通过的,需要绕道。

Follow up: 如果不是给两个点,而给你一个list of 开始坐标,和一个list of 结束坐标,你可以从选择从任意开始坐标走到任意结束坐标,问怎么走可以使得每个开始坐标到结束坐标的路径和最小。
93. 餐厅排队系统
用户可以输入人数,之后就会被加入到系统里,用户和可以随时删除,餐厅也可以按照桌子大小assign最开始排队的用户。
94. Find first index after sort
给个array和num,输出这个num在array sort后的位置(有dup)
95. Find most frequently element
给个array,输出这个array里最频繁出现的num在array sort后的位置
96. Find index after sort
给个array,写出来这里所有num在sort之后的位置。
97. Max value in array
提前给个array,需要写一个function根据start index和end index找出这中间的最大值
98. String editor
给一个字符串,和一个修改列表,对原串进行修改。例如:
 
输入:"Hello World" 以及 [(1,5, "i"), (6,9,"te")]
 
结果:"Hi ted"
 
说明:Tuple里的数字是原串的位置。开始的位置是inclusive, 结束的位置是exclusive。区间会有重叠,已经重叠的部分就不‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌要再修改了。
99. Longest subsequence
找最长的subsequence, 每个数是前一个数+1
例子: [6, 2, 1, 3, 2, 4, 3, 2, 5, 4, 5] 输出 5 (1, 2, 3, 4, 5)
100. Log file
给一个log file, 每行四个column,request timestamp | url | status code | duration, 输出一串request, follow up, 输出一个数字列,element是每个request接收后有多少pending request,然后问如果log file特别大内存放不下怎么办
 
例子: 0001 /index.html 200 1
 
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" ]
 Follow up:如果想根据词出现的概率来predict,应该怎么做?比如("I""am")出现了2次,("I","like")出现了1次,那么"am"的概率就是2/3。
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.
 Follow up:现在键盘 上的key不是unique的怎么办
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
一个整数倒序(6574->4756)
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. 中序遍历二叉搜素树
给一个BST的root node,return all node values in BSTin ascending orderRecursive DFS 
Follow up: with the Iterative approach
114. 100%胜率的出牌顺序
两位玩家,氯上一共有12张卡片-3绿3白3蕙3黑。玩家每轮需要进行一次combine把两摄卡牌叠在一起,两位玩家交替操作。
 combine的两个条件:
 a.如果两卡片高度一致,可以combine
 b.如果两操卡片顶端的卡片颜色一致,可以combine
 如果当前玩家无法进行combine操作,则另一名玩家获胜
 Perfect play:100%的玩家获胜概率,即在这条路线中不存在另一名玩家获胜的结果
 需要写一个function,输入为plaver1或plaver2并默认此player是先手,输出为bool
 如果当前玩家无法进行combine操作,则另一名玩家获胜
115. 聊天记录文件
给一个聊天记录文件,每一行的格式是something(人名@)word1..word2 word3
 人名后面的东西全是message。要求parse这个文件并返回topkword count by person.
 follow up:文件很大放不进memory怎么办。
116. 实现密码锁
给定一个input string判断能不能用密码锁转出相同的string
 支持的功能:给定某一个圈的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[4]=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
给input一堆time blocks(person_id,start_day,end_day),代表一个人在这个time block里unavailable.
 第一问,求有哪些天是所有人都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
给三个quiz bucket,一个 total num of questions,和三个bucket的比例,实现不放回随机抽样生成一份考卷
 例子是
 total 13,ratio 0.5,0.3,0.2
 total 5,ratio 2,1,1
 注意ratio并不一定add up to something。
124. 实现file system
要求实现一个function get EntitySizeByEntityld(id).给了一个json格式的Entity例子,可以是folder,可以是文件,如果是folder,会有child的filed,如果是文件,会有文件大小,问如果parse这个json,有什么exception是需要考虑的,然后实现这个function,如果给定的id是文件夹的,返回这个文件夹下所有文件的大小,如果id是文件的,直接返回这个文件的大小
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[0] <= nums[1] >= nums[2] <= nums[3]....

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小时每秒的温度,其中包括两个方程
找到过去24小时的平均值
找到过去24小时的最大值"

133. Data movement
给一个list of integers,尝试以最小化移动次数(data movement)来改变这个list,保证只留下我们想要的,删掉我们不想要的(比如只留下偶数,不要奇数之类的)

134. 判断胡牌
"用川麻的规则,给14张麻将牌,设计一个算法,判断这手14张麻将牌胡了没有
比如:
11123466778899胡了
11112345678899没胡
11223344556677七小对胡了
follow up加入花色以及翻倍"

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
intermediate ingredients: Bread, Salad
raw ingredients: Beef, Oil
Course Name: Salad
intermediate ingredients:N/A
raw ingredients: veg,egg,sauce
Course Name: Bread
raw ingredients:flour ,suger ,oil
Course NAME: sandwich
intermediateingredients: N/A
raw ingredients: flour, Suger oil, beef
假设input是 【Pizza, Steak】,output是 【flour, cheese,ketchup,suger,beef,oil,
veg,egg,sauce】"

136. 找到最长递增string list
"给你一个string set,比如:(den,dent,dents,dew,det,bet,bent),找到最长的递增
string list递增的规则是前一个string尾部增加一个字母变成后一个string。
例子的output是:den->dent->dents"

137. 设计一个Word store Service
"实现两个 method: add Word(String word) requestWord()
addWord 很简单把word加到Word Store里面存储起来
requestWord()从wordStore 中pop 一个word出来
Constraint:同一人首字母开头的单词不能在1s内同时出现两次
example:
addWord(Apple)
requestWord()return apple
AddWord(Banana)
addWord(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都可以有什么利弊。
求返回步数
follow up1:返回path
follow up2:maze中间有portal
follow up3:如果使用portal如果有额外cost"

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
给一个list of城市和对应的value,和一个list of城市之间的connections,找出4个城市value 之和最大,并且4个城市之问要连在一起,比如ABCD,就至少需要A-B B-C,C-D之间有连线

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 = [1]
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
follow up:当遇到次数为0的时候,next()要返回上一个遇到的数字"

146. Graph traversal
每个graph node 分布在不同server,不能用global memory,要求写算法每个node遍历一次

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[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1
 

Follow up:

  • 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
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/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.addContentToFile("/a/b/c/d", "hello");
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
有一个forest,以数组的形式存储,-1代表根节点,然后要求是删除某
 一个结点,输出删除后的数组表示。
 比如[-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).
假设input是两个long类型的数组,
把每个数组看成一个big number。For example:12*15=>[1,2]*[1,5]."

153. 套娃问题
给一个二维数组,每个数组是由box的长和宽组成could be like this:[[10,6],[6,4],[5,3],[5,1],[3,2],[3,2],[2,1]].每个大箱子里只能套一个小箱子,箱子dimension不是unique的,可以有一样的箱子。问你最多总共能有几个箱子套娃?

154. Similar pattern
给两个2D数组,S and T,比方说S=[[2,3],[4,5]].T=[[1,2,3,4], [2,5,4,6],[4,3,2,7]],问你在T中能找个几个和S相同的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功能
给一串字符串,要求实现csv的parse功能,比如给“name,gender n/jack,male n/marry female",要求能快速返回第几列第几个。

159. Closest Cafe for everyone
"有一群好朋友要在学校里找个距离所有人最近的咖啡厅,前提是必须让所有的好朋友都能到达。
Friends array:[1,2] Cafe array:[4,5].给一个二维数组代表图里面连接的边:((1,2),(1,5),(2,4)),返回距离最近的咖啡厅。
以每个咖啡店为起点bfs,记录下距离,最后选取距离最短的咖啡店"

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. 实现快进功能
"设计一个function输入一个新时间,并用最少次数的add 来快进到新时间(时间格式是[Hour,Minute,
""AM/PM""])。
Follow up :现在add button 的数量是不定的了,要怎么写。
E.g 有两个button[23,59],[0,2]。要快进三分钟的话就是按两下第二个按钮再按一下第一个按钮。"

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

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

164. 邮箱数据导入
"要进行qmail和其他邮箱系统数据导入,其他系统的邮箱系统是用folder {id: 27,parentld: 15,name:'projects‘},表示的。
而gmail采用的是 label{displayName:‘projects’,path:'personal/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[0][0] == 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
给一个数组,数字里每个数字都是两位数,可以逆转也可以不逆转,问最后数组最后能有多少个unigue 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[0] == -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[0] == -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
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
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.
 

Follow up:

  • 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
捐款系统。
假设付款的具体操作由第三方的服务来完成。具体需要讨论api,数据怎么存,如何保证尽可能收集到更多的捐款,如果三方api挂了怎么办,如何把这人系统弄成一个可以长期使用的产品。
175. implement booking system
一个会议室 booking system,输入start time,end time,返回有没有available spot
查overlap
176. remove floor
给一个array of building height,要求把 所有building都trim一样的高度,或者把某些夷为平地,求最少需要remove多少个floor
比如: input: [1,3,5], after remove
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系统
给餐馆设计Waitlist系统,要求一群人数已知的顾客可以加入排队,也可以离开队伍。餐馆有不同大小的桌子,当有桌子空出来后,需要返回排在队伍最前面且人数符合桌子大小的顾客。Follow up:给出更高效的方法
180. 求list中第二大的数
求list中第二大的数,不要用heap。folloW-up:求第k大的数
181. timestamp + string
Input是timestamp + string,例{1,abc},{3,abc}.(9,efg},{12,abc}{24,abc}
第一小问是,如果相同的string在10s内再次出现,那么只放入result list中一次,即上面的input应该输出{1,abc}.{9,efg},{24,abc}。无论如何都更新string的timestamp。

第二小问是,如果相同的string在10S内再次出现,那么要在result list中把之前出现那次也删掉,即上面的input应该输出 {9,efg},{24,abc}。
182. valid contradiction
判断是否是contradiction,只有==,!=例如a==b, b== c ,c!=a- -> false.
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
给出一个单词数组 words ,其中每个单词都由小写英文字母组成。
 
 如果我们可以 不改变其他字符的顺序 ,在 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.

Quad-Tree format:

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,1},{b,2},{z,2}},前面字母是值,后面数字是深度(byte-depth),通过这个数组构建一个full binary tree.比如上面的例子结果就是
   *
 /   \
 e    *
     /  \
    b   z
这些点都应该是叶子节点,如果无法构建则返回空节点,比如{{e,1},{b,2},{z,2},{a,3}},{{e,1},{b,1},{z,2}}都是不行的。
另外的两个条件
1.深度最低的永远先排在左侧
2.如果深度相同则按照字母顺序小的在左侧
191. ip address validator
要求实现两个方法,add(String ip),check(String ip,int x).每次调用add的时候就记录ip被调用了一次,check返回对应ip在过去一百万次的request中是否大于等于x次。比如ip1 add了一次,此时check(ip1,1)应该是返回true,但是当add ip2一百万次后,再check(ip1,1)就应该返回false。再add ip1一次后,check(ip1,1)返回true,check(ip1,2)返回false,因为过去一百万次中只有一次
192. 计算传纸条到target坐标的概率
有个二维数组表示教室,每个位置的学生要传递纸条,但是这个传递是有概率成功的。第一排向左右传递是90%,向后传递是50%。这个概率每向后一排就减半。比如第二排
的同学,左右传递概率是45%,向前是25%,向后是12.5%.求给某个同学的坐标和方向,概率是多少input:x,y,direction output: precent(double类型)

193. 填字游戏
有如下几种情况;空白可以填任何字母,“#”不能填任何东西,另外就是已有的字母。给定一个目标字符串,着看在不在格子里。另有个条件是这个字符串如果在格子里出现不能有前后缀.
*......*
|O##|
|#C#D M|
IG LEI
|#### #|
*......*
比如可以找到GOOGLE,C,但是GOO就不行
194. 寻找二叉树中节点最多的BST
find the biggest BST in binary tree return number of nodes.
195. 设计一个翻译系统
设计一个翻译系统,支持英语和西班牙语言的相互翻译
follow up:支持多语言的相互翻译
follow up2:支持多语言的相互翻译,且语言之间的跳转不能超过一次
196. find the longest continuous "0"
给一个beach,有很多的位置,有一些位置已经被占了,有一些没有,你和你的小伙伴要找到最长的一个连续的空位
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
实现生成随机playlist
follow up:considering signers,不要让同一歌手一直出现
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
找一个subfix of string a在string b的prefix相同的部分,
例如a ="llikeyou",b =""youlovehim""
输出“you""
202. 实现integer generator
设计一个class,是生成non repeated integer,不需要随机,要求不重复,要多线程
203. 查询子序列中的单词
input: 1) 一个string, 比如""cxadxrxetw""; 2) 一个list of words, 比[“cat", "cart","drew",
"xyz","tax"]
从左向右读string,可以跳过任意字母,找出所有list里的word
output: ["cat", ""cart"", ""drew""]
explain:
cxadxrxetw->cat
cxadxrxetw->cart
cxadxrxetw->drew
"xyz"不满足,因为string中没有"y" "z"
"tax"不满足,因为要求从左向右阅读string
Follow up:
string中的字母可以多次使用
比如list of word: ["ccc","cxxa"]
output: ["ccc" "cxxa"]
c*3xadxrxetw-> ccc
cx*2adxrxetw-> cxxa
204. 实现double linked list
在doublelinkedlist里面实现function remove_first_node删除第一个match value的node,followup是实现function remove_first_nodes,会take一个list of values,然后都删除,要求optimize time complexity,所以不能直接call第一部分的function
205. employee report dictionary
给一个employee report dictionary,要求返回一个人的score,如果一个人没有report就返回1,否则返回1+所有report的score,

 follow up:如果function反复被调用,怎么避免duplicate computation
206. 设计一个review系统
设计一个公司的review系统,只需要提供create和get的功能
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.
 

Follow up:

  • 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
给a> b,b>C,,c> a这种 string,sign,string的形式,如果有矛盾点,比如这个例子里a
 和c的大小矛盾了,就要return false。
213. 设计查询机票系统
设计一个查询机票信息的系统,实现api UpdatePlanelnfo(planeID,departureTime,
 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的内容返回给多少黑灯,多少白灯。
 follow up是作为猜测者在不知道答案的情况下,知道上一轮的guess和return的结果(有几个白灯几个黑灯),判断一个新的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[0][0] == 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
设计一个model,预测实时手机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
给一个array a[ ].称满足a[i]-a[j]=i-j的(i,j)为一个good pair,找出一共有多少对
good pair:
1.(i,j)和(j,i)是否算两对
2.是否考虑i=j的情况
226. 设计歌单分享
设计歌单分享服务分享你的歌单给朋友
227. 键值更新
给一个数,返回最小的idx比如[idx,num]
[1,10],[2,10],[1,20]
现在问num=10,返回2,因为idx 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 = [1]
Output: [[1]]

 

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 = [0]
Output: [0]

 

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
给一个secret Word,给一个input Word,要求返回一个str
(1)如果input Word中的这个char没有出现在secret Word中,则返回R
(2)如果char出现在secret Word中但secret Word中对应位置不是这个char,返回Y
(3)如果char出现在secret Word中且secre tWord中对应位置是这个char,返回G
236. 拓扑排序
拓扑排序,给你一个function,call这个function会返回两个节点的,排序如a->b,b->C。但function不保证每次返回都是unigue的,即可能返复call5次,返回的都是a->b。给你总共character的个数n,要求输出character之间的顺序。
237. 设计gmail 定时删除功能
设计gmail 定时删除功能
240. 二叉树最底层宽度
给一个binary tree,问最下边那个level的width。第一个1之前的null不算,最后一个1之后的null也不算