Airbnb计算机科学面试真题

职位分类
全部
数据科学
数据分析
计算机科学
人工智能
产品经理
BQ
面试题
全部(18)
Coding(0)
System Design(1)
Algorithm(5)
Ood(0)
高频题(0)
全部(18)
Coding(0)
System Design(1)
Algorithm(5)
Ood(0)
高频题(0)
1.Max value from time interval
2.Number of nodes
3.Search ranking in Airbnb
4.Find median in a very large array
5.Leetcode 1235
6.Leetcode 641
7.Leetcode 622
8.Max intereste level from non overlapping experiences
9.Compute the cost from the graph
10.Find min path from weighted graph
11.Simplied text justification
12.Min number of donuts in unit time
13.Application build cost
14.设计群聊
15.LeetCode 864
16.LeetCode 787
17.设计数据库(kv)
18.LeetCode 28
1. Max value from time interval
给一组time interval,每个interval有个值,time interval不能重叠,算最多能拿到的值。
2. Number of nodes
一道题 60 分钟。大概就是反转一个有像图然后计算每个节点的子节点数。
3. Search ranking in Airbnb
Airbnb search ranking with personalization for maximum booking
4. Find median in a very large array
在一个large array(没法fit in memory)里面求median,比如【1,1,1,3,3,4,5,6,7.。。。】里面找median。
5. Leetcode 1235
你打算利用空闲时间来做兼职工作赚些零花钱。
 
 这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。
 
 给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。
 
 注意,时间上出现重叠的 2 份工作不能同时进行。
 
 如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。

6. Leetcode 641
设计实现双端队列。
实现MyCircularDeque类:
 
MyCircularDeque(int k):构造函数,双端队列最大为k。
 
boolean insertFront():将一个元素添加到双端队列头部。 如果操作成功返回true,否则返回 false 。
 
boolean insertLast():将一个元素添加到双端队列尾部。如果操作成功返回true,否则返回 false 。
 
boolean deleteFront():从双端队列头部删除一个元素。 如果操作成功返回true,否则返回 false 。
 
boolean deleteLast():从双端队列尾部删除一个元素。如果操作成功返回true,否则返回false。
 
int getFront():从双端队列头部获得一个元素。如果双端队列为空,返回-1。
 
int getRear():获得双端队列的最后一个元素。 如果双端队列为空,返回-1。
 
boolean isEmpty():若双端队列为空,则返回true,否则返回false。
 
boolean isFull():若双端队列满了,则返回true,否则返回false。
7. Leetcode 622
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
 
 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
 
 你的实现应该支持如下操作:
 
 MyCircularQueue(k): 构造器,设置队列长度为 k 。
 Front: 从队首获取元素。如果队列为空,返回 -1 。
 Rear: 获取队尾元素。如果队列为空,返回 -1 。
 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
 deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
 isEmpty(): 检查循环队列是否为空。
 isFull(): 检查循环队列是否已满。
8. Max intereste level from non overlapping experiences
Airbnb has an "Experiences" product where you choose activities to do with your friends.
 
Each activity has a start time, end time, and interest level.
 
If you are given a list of potential "experiences",
 
 Write a method that returns the maximum interest_level if you chose
 
 non-overlapping experiences
 
 [start_time, end_time, interest_level]
 
 experiences = [(2, 5, 5),(3, 6, 6),(5, 10, 2),(4,‍‍‌‌‌‌‍‌‍‍‍‍‍‍‍‍‍‌‌‍ 10, 8),(8, 9, 5),(13, 14, 1),(13, 17, 5),(14, 16, 8) ]
 
 the answer should be 20
 
(3, 6, 6) (8, 9, 5) (13, 14, 1) (14, 16, 8)
9. Compute the cost from the graph
给个图 算cost 第一层 cost1 第二层cost2 以此类推 最后return 每层的cost 就行
10. Find min path from weighted graph
在一个有向有权重的图上,找到从一点到另一点的最小cost 和最短路径
11. Simplied text justification
text justification simplified version
12. Min number of donuts in unit time
给定每个时间单位最多生产多少个甜甜圈 vector<int> numOfDonuts,以及最多使用多长时间吃完所有的甜甜圈 maxTime,求每个时间单位最少吃的甜甜圈个数 d。
13. Application build cost
Application Build Cost,
 Java不用自己处理输入输出,给一个List<String>, 返回一个排好序的List<String>就行
14. 设计群聊
设计群聊

15. LeetCode 864
You are given an m x n grid grid where:

  • '.' is an empty cell.
  • '#' is a wall.
  • '@' is the starting point.
  • Lowercase letters represent keys.
  • Uppercase letters represent locks.
You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.

For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

 

Example 1:

Input: grid = ["@.a..","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.

Example 2:

Input: grid = ["@..aA","..B#.","....b"]
Output: 6

Example 3:

Input: grid = ["@Aa"]
Output: -1

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 30
  • grid[i][j] is either an English letter, '.', '#', or '@'.
  • The number of keys in the grid is in the range [1, 6].
  • Each key in the grid is unique.
  • Each key in the grid has a matching lock.
16. LeetCode 787
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

 

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

 

Constraints:

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 104
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst, k < n
  • src != dst
17. 设计数据库(kv)
设计数据库(kv)
18. LeetCode 28
Implement strStr().

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

 

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

 

Constraints:

  • 1 <= haystack.length, needle.length <= 104
  • haystack and needle consist of only lowercase English characters.