Airbnb Software Engineer Interview Questions and Answers

Given a 2D matrix with doors and walls, fill distance matrix with minimum distance to the nearest door.

• Iterate through the matrix and find the doors

• Use Breadth-First Search (BFS) to calculate the minimum distance from each cell to the nearest door

• Update the distance matrix with the minimum distances

Find kth smallest element in unordered array with O(1) space

• Use the QuickSelect algorithm to partition the array and find the kth smallest element

• Choose a pivot element and partition the array into two subarrays

• Recursively partition the subarray that contains the kth smallest element

• Repeat until the pivot element is the kth smallest element

• Time complexity: O(n) average case, O(n^2) worst case

To find friends of friends who are not already friends with you, we can first find your friends and then their friends excluding yourself and your friends.

• Get your list of friends

• For each friend, get their list of friends

• Exclude yourself and your friends from the final list of friends of friends

Boundary traversal of a tree is the process of visiting the nodes on the boundary of a tree in a specific order.

• The boundary traversal can be done in three steps: left boundary, leaf nodes, and right boundary.

• For the left boundary, start from the root and traverse down the left side of the tree until reaching a leaf node.

• For the leaf nodes, perform an inorder traversal to visit all the leaf nodes of the tree.

• For the ri...read more

Find the nearest greater value of a given value in a Binary Search Tree (BST).

• Start from the root node and compare the given value with the current node's value.

• If the given value is less than the current node's value, move to the left subtree.

• If the given value is greater than the current node's value, move to the right subtree.

• Keep track of the closest greater value encountered while traversing the tree.

• Return the cl

Given an infinite staircase with a broken kth step, find the maximum height we can reach in n rounds of jumping i steps.

• We can start by jumping the maximum number of steps in each round until we reach the broken step.

• After reaching the broken step, we can discard the i steps that would land us on the broken step and jump the remaining steps.

• We can continue this pattern until we reach the maximum height we can reach wit