AirBnB Interview Questions
Disclaim
All questions below are collected from Internet, which include but not limit to:
From what I know:
- AirBnB is not hiring during this coronavirus pandemic time.
- airBnB likely will change all interview questions after they start to hire on 2021. This repository is no longer updated.
List of Questions
1 Collatz Conjecture
- If a number is odd, the next transform is 3*n+1
- If a number is even, the next transform is n/2
- The number is finally transformed into 1.
- The step is how many transforms needed for a number turned into 1.
Given an integer n, output the max steps of transform number in [1, n] into 1.
2 Implement Queue with Limited Size of Array
Implement a queue with a number of arrays, in which each array has fixed size.
3 List of List Iterator
Given an array of arrays, implement an iterator class to allow the client to traverse and remove elements in the array list.
This iterator should provide three public class member functions:
- boolean hasNext() return true if there is another element in the set
- int next() return the value of the next element in the array
- void remove() remove the last element returned by the iterator. That is, remove the element that the previous next() returned. This method can be called only once per call to next(), otherwise an exception will be thrown.
4 Display Page (Pagination)
Given an array of CSV strings representing search results, output results sorted by a score initially. A given host may have several listings that show up in these results. Suppose we want to show 12 results per page, but we don’t want the same host to dominate the results.
Write a function that will reorder the list so that a host shows up at most once on a page if possible, but otherwise preserves the ordering. Your program should return the new array and print out the results in blocks representing the pages.
Given an array of csv strings, output results separated by a blank line.
5 Travel Buddy
I have a wish list of cities that I want to visit to, my friends also have city wish lists that they want to visit to. If one of my friends share more than 50% (over his city count in his wish list), he is my buddy.
Given a list of city wish list, output buddy list sorting by similarity.
6 File System
Write a file system class, which has two functions: create, and get
- create("/a",1)
- get("/a") //get 1
- create("/a/b",2)
- get("/a/b") //get 2
- create("/c/d",1) //Error, because "/c" is not existed
- get("/c") //Error, because "/c" is not existed
7 Palindrome Pairs
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
8 Find Median in Large Integer File of Integers
Find the median from a large file of integers. You can not access the numbers by index, can only access it sequentially. And the numbers cannot fit in memory.
9 IP Range to CIDR
Given an IPv4 IP address p and an integer n, return a list of CIDR strings that most succinctly represents the range of IP addresses from p to (p + n).
10 CSV Parser
Write a method to parse input string in CSV format.
11 Text Justification
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
12 Regular Expression
Implement a simple regex parser which, given a string and a pattern, returns a boolean indicating whether the input matches the pattern.
By simple, we mean that the regex can only contain special character:
- * (star) The star means what you'd expect, that there will be zero or more of previous character in that place in the pattern.
- . (dot) The dot means any character for that position.
- + (plus). The plus means one or more of previous character in that place in the pattern.
13 Water Drop/Water Land/Pour Water
Input is a array represent how the height of water is at each position, the number of water will be poured, and the pour position. Print the land after all water are poured.
Example: input land height int[]{5,4,2,1,3,2,2,1,0,1,4,3} The land is looks ike:
+
++ +
++ + ++
+++ +++ ++
++++++++ +++
++++++++++++
012345678901
water quantity is 8 and pour at position 5. The land becomes:
+
++ +
++www+ ++
+++w+++www++
++++++++w+++
++++++++++++
012345678901
14 Hilbert Curve
Given (x, y, iter), in which (x, y) is position at x-axis and y-axis, and iter is how many iterations will be. Output is in iteration iter, how many steps are required to move from (0, 0) to (x, y) in iteration iter.
15 Simulate Diplomacy
Input (army_name, location, action())
action() could be:
- move(new_location) then army_name to new_location, If there is an army at new_location, then company strength of two aramy:
- The army have higher strength stay at new_location, the lower army is disappeared.
- If two army have the same strength, both are disppeared.
- hold() stay at the same location
- support(army_name) supoort another army. The supported army have one more strength.
The army's strength are intialized as the same.
16 Meeting Time
Input is a number of meetings (start_time, end_time)。 Output is a number of time intervals (start_time, end_time), where there is no meetings.
For exmaple, input is [[1, 3], [6, 7]], [[2, 4]], [[2, 3], [9, 12]] ]
output [[4, 6], [7, 9]]
17 Round Prices
Given an array of numbers A = [x1, x2, ..., xn] and T = Round(x1+x2+... +xn). We want to find a way to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1+y2+...+yn = T where yi = Floor(xi) or Ceil(xi), ceiling or floor of xi.
We also want to minimize sum |x_i-y_i|
18 Sliding Game
You're given a 3x3 board of a tile puzzle, with 8 tiles numbered 1 to 8, and an empty spot. You can move any tile adjacent to the empty spot, to the empty spot, creating an empty spot where the tile originally was. The goal is to find a series of moves that will solve the board, i.e. get [ [1, 2, 3], [4, 5, 6], [7, 8, - ]…
19 Maximum Number of Nights You Can Accommodate
Given a set of numbers in an array which represent number of consecutive nights of AirBnB reservation requested, as a host, pick the sequence which maximizes the number of days of occupancy, at the same time, leaving at least 1 day gap in between bookings for cleaning. Problem reduces to finding max-sum of non-consecutive array elements.
20 Find Case Combinations of a String
Find all the combinations of a string in lowercase and uppercase. For example, string "ab" >>> "ab", "Ab", "aB", "AB". So, you will have 2^n (n = number of chars in the string) output strings. The goal is for you to test each of these strings and see if it matchs a hidden string.
21 Menu Combination Sum
Given a menu (list of items prices), find all possible combinations of items that sum a particular value K. (A variation of the typical 2sum/Nsum questions).
22 K Edit Distance
Find all words from a dictionary that are k edit distance away.
23 Boggle Game
Given 2d matrix of letters, and a word dictionary, find a path which has largest number of words (existed inside the dictionary).
24 Minimum Cost with At Most K Stops
Given a flight itinerary consisting of starting city, destination city, and ticket price (2d list) - find the optimal price flight path to get from start to destination. (A variation of Dynamic Programming Shortest Path)
25 String Pyramids Transition Matrix
Given a list of leaf nodes in a pyramid, and a map which indicates what's the possible parent node given a left and right node. Return true if the one of leaf node could turn into the root node, Otherwise, return false. For example:
root
/ \
X X
/\ /\
X X X
/ \/ \/ \
A B C D
Map:
left: A | B | C | D
right---------------------------------
A B |A or C| D | A
B D |B or C| A |
C B
D
Note:1. If left child is B, right child is A, the parent node could be B or C
Given leaf input of "ABCD", output true.
26 Finding Ocean
Given: An array of strings where L indicates land and W indicates water, and a coordinate marking a starting point in the middle of the ocean.
Challenge: Find and mark the ocean in the map by changing appropriate Ws to Os.
- An ocean coordinate is defined to be the initial coordinate if a W, and
- any coordinate directly adjacent to any other ocean coordinate.
void findOcean(String[] map, int row, int column);
String[] map = new String[]{
"WWWLLLW",
"WWLLLWW",
"WLLLLWW"
};
printMap(map);
STDOUT:
WWWLLLW
WWLLLWW
WLLLLWW
findOcean(map, 0, 1);
printMap(map);
STDOUT:
OOOLLLW
OOLLLWW
OLLLLWW
27 Preference List
Given a list of everyone's preferred city list, output the city list following the order of everyone's preference order.
For example, input is [[3, 5, 7, 9], [2, 3, 8], [5, 8]]. One of possible output is [2, 3, 5, 8, 7, 9].
28 Minimum Vertices to Traverse Directed Graph
Given a directed grapjh, represented in a two dimension array, output a list of points that can be used to travese every points with the least number of visited vertices.
29 10 Wizards
There are 10 wizards, 0-9, you are given a list that each entry is a list of wizards known by wizard. Define the cost between wizards and wizard as square of different of i and j. To find the min cost between 0 and 9.
For example:
wizard[0] list: 1, 4, 5
wizard[4] list: 9
wizard 0 to 9 min distance is (0-4)^2+(4-9)^2=41 (wizard[0]->wizard[4]->wizard[9])
30 Number of Intersected Rectangles
Given lots of rectangles, output how many of them intersect.
31 Guess Number
The system has a secret four digits number, in which each digit is in range of one to 6 [1, 6].
Given a four digital number, the system also provide a API that returns the number of correct matched digits.
Design a method to guess this secret number.
Requirements
- Java >= 1.11.106
- Gradle >= 5.6.3
Run Unit Tests
If you write some unit tests, you can use the following command to run them.
# run all tests
gradle test
# run Palindrome Pairs test only
gradle -Dtest.single=PalindromePairs test
# run Palindrome Pairs test only with some informnation
gradle -Dtest.single=PalindromePairs test --infoUpdate Logs
v1.0 11/25/2017
- Update almost all questions with unit tests
v1.1 8/26/2020
- Update build.gradle to be compatible with Java 11 and gradle 5.6