Expedia计算机科学面试真题

职位分类
全部
数据科学
数据分析
计算机科学
人工智能
产品经理
BQ
面试题
全部(29)
Coding(4)
System Design(4)
Algorithm(13)
Ood(7)
高频题(3)
全部(29)
Coding(4)
System Design(4)
Algorithm(13)
Ood(7)
高频题(3)
1.Add Two Numbers
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
23.设计notepad
24.最短距离
25.LeetCode 33
26.Design Instagram
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 = [0], l2 = [0]
Output: [0]
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
设计一个行程单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[0] + nums[1] == 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. 设计景点图
给定一个amount,和list of prices设计一个function可以visit最多多少景点
5. 设计map
设计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
给了个array有很多数字和一个可以remove数字的次数m,问最后可以剩下的最少的unique number个数是多少?
 
比如[1,1,1,2,3,2], m = 2 结果是2 因为比如把两个2remove掉,剩下[1,1,1,3] 刚好‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌只有2个unique nums
10. String parse to Integer
字串处理,把给定的字串数组中的数字parse出来
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
设计Map、实现filter的design
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. 棋盘路径
给你一个棋盘,问一颗棋子从指定起‍‍‌‍‍‌‍‌&成的最小步数,移动方向只能(1)横向2纵向1(2)横向1纵向2。
19. 设计delivery system
设计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
23. 设计notepad
设计notepad
24. 最短距离
给平面上一些点,输入一个点求离这个点最近的一个点。最近点需要和输入点共x or共y
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[0], nums[1], ..., 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 = [1], 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
26. Design Instagram
Design Instagram
27. Find Anagram Word
给一个长 sentence,找出里面没有 anagram的词
比如Came lAde Edal,返回的就是 came。需要注意忽略大小写,duplicates,单个字母(单个字母不算anagram)
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 变种
变种:public static int twoSum(List<Integer> numbers, int k).a+k=b.要求返回disticnt a,b的pair个数。O(n)秒,follow up :a+k*n=b 怎么办。


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[0] + nums[1] == 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?