# Expedia计算机科学面试真题

BQ

Coding（4）
System Design（4）
Algorithm（13）
Ood（7） 高频题（3）

Coding（4）
System Design（4）
Algorithm（13）
Ood（7） 高频题（3）
2.设计一个行程单class
3.Leetcode 1
4.设计景点图
5.设计map
6.Comparator 7.棋盘最短路径
8.The kth Factor of n
9.Remove unique numbers
10.String parse to Integer
11.Leetcode 1029
12.Itinerary/map
13.LeetCode 1481
14.Jump stairs 15.设计Map、实现filter
16.Device name system
17.Minimum Knight Moves
18.棋盘路径
19.设计delivery system
20.Best Time to Buy and Sell Stock
21.String Compression 22.Metro land festival
24.最短距离
25.LeetCode 33
27.Find Anagram Word
28.Missing words
29.two sum 变种
1. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:

Input: l1 = , l2 = 
Output: 
Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros
2. 设计一个行程单class

3. Leetcode 1
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.
Example 1:

```Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums + nums == 9, we return [0, 1].
```
Example 2:

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

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

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
4. 设计景点图

5. 设计map

6. Comparator Design a comparator
7. 棋盘最短路径

（1）横向2纵向1（2）横向1纵向2
8. The kth Factor of n
Find the p-th factor  可参考Leetcode 1492：

You are given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

Example 1:

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Constraints:
1 <= k <= n <= 1000
9. Remove unique numbers

10. String parse to Integer

11. Leetcode 1029
A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Example 1:

```Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
```
Example 2:

```Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859
```
Example 3:

```Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086
```

Constraints:

• 2 * n == costs.length
• 2 <= costs.length <= 100
• costs.length is even.
• 1 <= aCosti, bCosti <= 1000
12. Itinerary/map
Implement itinerary/map
13. LeetCode 1481
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

```Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
```
Example 2:
```Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.```

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length
14. Jump stairs Jump stairs
15. 设计Map、实现filter

16. Device name system
Design a device name system
17. Minimum Knight Moves
In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].
A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:
Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

Constraints:
-300 <= x, y <= 300
0 <= |x| + |y| <= 300
18. 棋盘路径

19. 设计delivery system

20. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104

21. String Compression Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:
Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:
Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints:
1 <= chars.length <= 2000
chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.
22. Metro land festival
Metro Land is a country located on a 2D Plane. They are having a summer festival for everyone in the country and would like to minimise the overall cost of travel for their citizens. Costs of travel are calculated as follows:
Determine the total cost of travel for all citizens to go to the festival at that location.

Repeat the coordinates in x points array and y points array according to the numsPoint array.

x1 = Take median of all the x axis points.
y1 = Take median of all the y axis points.

The solution is of O(n^2) time complexity.

You are given two positive integers n and k.
A factor of an integer n is defined as an integer i where n % i = 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

Example 1:
Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2:
Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

Example 3:
Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Constraints:
1 <= k <= n <= 1000

24. 最短距离

25. LeetCode 33
There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums, nums, ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

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

Example 1:

```Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```
Example 2:

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

```Input: nums = , target = 0
Output: -1
```

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104
27. Find Anagram Word

28. Missing words
given two strings, one is a subsequence if all of the elements of the first string occur in the same order within the second string. They do not have to be continuous in the second string, but the order must be maintained.
input:
string s: a sentence of space-separated words
string t: a sentence of space-separated words
output:
arr of strings that contain all words in s but not in t, in the order they occur within s
Example:
S =‘ I like apples’
t = ‘like'
output: [‘I', ‘apple’]
s =‘I use Python for programming
T =‘Python for’
output:[‘I’, ‘use’， ‘programming’]
29. two sum 变种

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

```Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums + nums == 9, we return [0, 1].
```
Example 2:

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

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

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?