# Indeed计算机科学面试真题

BQ

Coding（12）
System Design（2）
Algorithm（7）
Ood（0） 高频题（2）

Coding（12）
System Design（2）
Algorithm（7）
Ood（0） 高频题（2）
1.LeetCode 79 2.LeetCode 1160 3.LeetCode 1604
4.Fuzzy search
5.Moving average
6.简化版数独Validator
7.跳格子
8.Job推送
9.Find unique word path
10.日志查询
11.Compress Binary Tree
12.LeetCode 346
13.LeetCode 1160
14.纸牌游戏
15.generate matrix
16.Web server code review
17.Design a job posting system
18.Word Processor
19.fuzzy Search 排序
20.LeetCode 200
21.LeetCode 1160
22.LeetCode 79
1. LeetCode 79 Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
```
Example 2:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
```
Example 3:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

2. LeetCode 1160 You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

```Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
```
Example 2:

```Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
```

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] and chars consist of lowercase English letters.
3. LeetCode 1604
LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person's name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format "HH:MM", such as "23:51" and "09:49".

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that "10:00" - "11:00" is considered to be within a one-hour period, while "22:51" - "23:52" is not considered to be within a one-hour period.

Example 1:

```Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").
```
Example 2:

```Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").
```

Constraints:

• 1 <= keyName.length, keyTime.length <= 105
• keyName.length == keyTime.length
• keyTime[i] is in the format "HH:MM".
• [keyName[i], keyTime[i]] is unique.
• 1 <= keyName[i].length <= 10
• keyName[i] contains only lowercase English letters.
4. Fuzzy search

5. Moving average

6. 简化版数独Validator

eg: 2*2 matrix

[1,2]
[1,2]
False

[1,2]
[2,1]
True
7. 跳格子
R只能向右跳，B只能向左跳。

R，B可以隔一个跳，但是间隔的字符一定是不同的，比如说R可以越过一个B 跳到B右边的空位置上，但是不可以隔两个以上，或者隔一个R跳。

start = ["R","_", "B","B"]

end = ["B","_", "B","R"]

-->return

moves=[

["R","_", "B","B"]

["_","R", "B","B"]

["B","R", "_","B"]

["B","R",‍‍‌‍‍‌‌‌‌‌‌‍‌‍‌‍‍‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌‌ "B","_"]

["B","_", "B","R"]

]
8. Job推送

9. Find unique word path

10. 日志查询
给定一个输入logs数组，每个数据记录对 Web 资源访问的时间(以秒为单位),用户id，和资源id。例如
Example:
logs1 = [
["58523"，"user_1"，"resource_1"],
["62314", "user_2", "resource 2"],
["54001", "user_1", "resource 3"],
["200", "user_6", "resource 5"],
["215","user_6","resource_4"],
["54060", "user_2", "resource 3"],
["53760", "user_3", "resource 3"]
["58522", "user_22", "resource 1"],
["53651", "user_5", "resource 3"],
["2", "user_6", "resource 1"],
["100" "user_6", "resource 6"],
"400""user_7","resource_2"],
["100","user_8",recource_6"],
["54359""user 1"，"resource 3"],
]
Example 2:
logs2 =[
["300", "user_1", "resource_3"],
["599", "user_1", "resource_3"],
["900","user_1" "resource_3"],
["1199","user_1" "resource_3"],
["599","user_1" "resource_3"],
[900","user_1" "resource_3"],
["1199", "user_1" "resource_3"],
[1200","user_1" "resource_3"],
[1201","user_1" "resource_3"],
["1202","user_1" "resource_3"],
]
Example 3：
logs3 =[
["300", "user_10", "resource_5"]
Q1:
["300"，"user_10","resource_5"]
给定一个log输入，返回每人用户的开始和结束的访问时间
input: logs1
“NDINO
"user1":「54001，585231],
"user 2":[54060,62314],
"user 3": ，
"user5":,
"user 6":[2,2151],
"user 3":,
”user5",
"user 6"[2,215],
"user 7":[2,400],
"user8":[2,1001],
"user22":,
]
Q2:
还是同样的背景，写一个函数，获取日志并返回任何5分钟窗口内访问次数最多的资源，以及访问次数。
Expected Output:
most_requested_resource(logs1) # => ('resource 3', 3) [resource 3 is accessed at 53760,54001,and54060]
most_requested_resource(logs2) # => ('resource 3', 4) [resource_is accessed at 1199,1200,1201,and12021]
most_requested_resource(logs3) # => ('resource 5', 1) [resource_5 is accessed at 300]
11. Compress Binary Tree

Follow up 1: 如果不是完全二叉树怎么办？
Follow up 2: 如果有一个二叉树，他开始是完全二叉树，然后从某一层开始变得十分稀疏怎么办?
12. LeetCode 346
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window size.
• double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

```Input
["MovingAverage", "next", "next", "next", "next"]
[, , , , ]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3
```

Constraints:

• 1 <= size <= 1000
• -105 <= val <= 105
• At most 104 calls will be made to next.
13. LeetCode 1160
You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

```Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
```
Example 2:

```Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
```

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] and chars consist of lowercase English letters.
14. 纸牌游戏

design一下，把这个游戏做成web based，而且规则有所改变：1）现在同场竟技的玩家会非常非

15. generate matrix

16. Web server code review
code review一个web server代码片段，大概100行，可选一个语言配上一个框架
17. Design a job posting system

18. Word Processor
/*
We are building a word preocessor and we would like to implement word wrapping functionalitu that is a bit smarter.

Some users want to have the resulting lines to be as balanced as possible for higher redability. Therefore, Our application should divide a given text into a sequence of lines so that every line spans at most some fixed width and the difference between different lines are as little as possible.

We define the balance score of a collection of string as follows: find the longest line. For each line, sum the square of the length difference between this line and the longest line.

Given a string of the text and a maximum number of characters in a line, return a list of strings which result in the lowest balance score(on a tie, return any of the valid solutions).

Note: we are using '-' instead od space between words to make testing and visual verification of the result easier.

Examples:

text1='Seven six eight thirteen four five sixteen'

balance Wraplines(text1, 15)"balance the lines of text 1 wrapping to a max 15 length"=>

［"Seven-six-eight"// 0
"thirteen-four"，// 2*2
"five-sixteen" ]//3*4=score of 13

text 2 =XXXXXX X XXXX X X XXXX";

balanceWrap lines(text2, 9) "balance the lines of text2 wrapping to a max 9 length"=>

Correct answer(each line wrapped to a different length <=9)

["XXXXXX-X", //0*0
"XXXX-X", //2*2
"X-XXXXX"] //1*1 = score of 5

Or

["XXXXXX", //0
"X-XXXX-X", //0
"X-XXXXX"] //3*3 = score of 9

All Test Cases:
test, max line length
balanceWrapLines(text1, 15)
balanceWrapLines(test2, 9)

n=number of words OR total characters
m=length of longest line
*/
19. fuzzy Search 排序

20. LeetCode 200
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

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

```Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
```

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.
21. LeetCode 1160
You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

```Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
```
Example 2:

```Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
```

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] and chars consist of lowercase English letters.
22. LeetCode 79
Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
```
Example 2:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
```
Example 3:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?