Airbnb Interview Questions

This is primarily a simulation problem rather than an algorithmic one: you greedily pack as many words as fit into each line without exceeding the max width, then distribute the remaining spaces evenly across the gaps (extra spaces go to the leftmost gaps first), with special handling for single-word lines and the final line, which is left-justified instead of fully justified. There's no clever data structure here — it tests whether a candidate can translate a fussy, ambiguous spec into clean, bug-free code and enumerate edge cases (empty lines, one word filling a whole line) without missing any. It's a good signal of implementation discipline under a wordy problem statement, which is why it shows up as a rigorous string-manipulation check.

This is a weighted interval scheduling problem: sort jobs by end time, then use dynamic programming where each state answers 'what's the best profit using jobs up to index i,' combined with binary search to quickly find the latest job that doesn't overlap with the current one. It tests whether a candidate can recognize a scheduling problem as DP-with-binary-search rather than reaching for a greedy or brute-force solution, and it's a natural extension of simpler interval-merging problems into an optimization setting.

Given a list of words, the task is to find all index pairs whose concatenation forms a palindrome. The efficient solution builds a hash map of reversed words and checks, for every word, whether its remaining prefix or suffix (after accounting for a potential palindromic split) exists in that map — avoiding the O(n^2 * k) brute force of checking every pair directly. It's a strong test of combining hashing with palindrome-checking logic, and the edge cases (empty strings, words that are palindromes themselves) trip up candidates who don't think through the split carefully.

This is an iterator-design problem: implement `next()` and `hasNext()` over a vector of vectors, correctly skipping empty inner vectors and never over- or under-reporting whether more elements remain. It has no deep algorithmic content, but it tests whether a candidate can manage internal pointer/index state cleanly across a two-level structure, a common pattern for 'design an iterator' style interview questions.

A classic backtracking problem: given a set of candidate numbers (each reusable an unlimited number of times) and a target, find every unique combination that sums to the target. It tests standard DFS-with-backtracking technique, including pruning branches once the running sum exceeds the target and avoiding duplicate combinations by only considering candidates from the current index forward. It's often used as a foundational check of whether a candidate can structure recursive search correctly before moving to harder combinatorial variants.

Given a hierarchy of regions described as parent-to-children lists of strings (rather than an explicit tree structure), the task is to find the smallest region containing two given regions. The standard approach builds a child-to-parent map from the input, then walks up the ancestor chain of one region into a set and walks up the other until it hits a region already in that set — essentially the lowest-common-ancestor pattern applied to a tree that isn't given as literal node objects. It tests whether a candidate can recognize an LCA problem underneath an unfamiliar input format.

This is a graph/BFS traversal problem with dependent state: boxes may be locked or unlocked, and opening one can yield candies, keys to other boxes, and additional boxes you don't yet have. The typical solution uses a queue and keeps reprocessing boxes that were found but were locked at the time, since a key for them might arrive later. It tests careful handling of circular and out-of-order dependencies in a simulation/traversal setting, which is more about bookkeeping discipline than a named algorithm.

A terrain-simulation problem: water droplets are poured one at a time onto an array representing heights, and each droplet flows left or right toward the lowest reachable point before settling (with left preferred as a tiebreak). It requires careful, step-by-step array simulation rather than a shortcut formula, and Google/Airbnb use it as a check of whether a candidate can correctly implement a stateful physical process with several interacting edge cases (flat ground, walls, no valid drop point).

Given a list of words sorted according to an unknown alphabet's ordering, the task is to reconstruct a valid character ordering: build a directed graph of precedence constraints from adjacent word comparisons, then topologically sort it (Kahn's algorithm or DFS-based), detecting cycles as an invalid/impossible ordering. The task is conceptually similar to inferring a token ordering from partial, pairwise evidence, which is plausibly why it resonates with companies doing tokenizer/vocabulary-adjacent ML work. It's a solid test of translating a word-comparison problem into a graph and correctly handling topological sort edge cases (cycles, ties, unreachable characters).

A shortest-path problem with an added constraint on the number of edges (stops) used: the standard approaches are a bounded Bellman-Ford (relax all edges K+1 times) or a modified Dijkstra/BFS that tracks both cost and stop count as part of the search state. It tests whether a candidate understands why plain Dijkstra can fail here (it doesn't account for the stop limit) and can adapt a shortest-path algorithm to a secondary constraint — a pattern that generalizes to real routing and logistics problems.

This problem asks for the minimum number of moves to solve a 2x3 sliding puzzle, and the key insight is treating each board configuration as a node in an implicit graph, with moves of the blank tile as edges, then running BFS from the start state to the solved state. It tests whether a candidate can recognize a puzzle as a graph/state-space search problem, encode board states compactly (usually as a string) for a visited set, and enumerate valid moves correctly for each blank-tile position.

A design problem simulating a simplified spreadsheet: cells can hold direct values or sum formulas over ranges of other cells, and setting a cell must correctly propagate to any cells that depend on it. The natural model is a dependency graph between cells, recomputing affected cells (often via DFS/topological order) whenever an upstream value changes. It tests whether a candidate can design a stateful class with correct invalidation/recomputation logic rather than just solving a single-pass algorithmic question.

Given an elevation map, compute how much water it can trap after rain — the water trapped at each index equals the shorter of the tallest bars to its left and right, minus its own height. It's solvable with two pointers in O(1) extra space, with a monotonic stack, or with two precomputed max-prefix/max-suffix arrays, making it a great vehicle for comparing multiple valid techniques in one interview. Its breadth of companies asking it reflects that it's one of the most widely used checks of two-pointer/array reasoning in the entire interview circuit.

Given a starting IP address and a count of addresses to cover, the task is to output the minimum number of CIDR blocks that exactly cover that range. The approach converts the IP to a 32-bit integer, then repeatedly takes the largest power-of-two-aligned block starting at the current address that doesn't overshoot the remaining count, subtracting it and continuing. It's a bit-manipulation problem dressed in networking terminology, testing comfort with binary representations and address alignment rather than networking domain knowledge itself.

Given each employee's schedule as a list of busy intervals, find the intervals of time that are free for every employee. The standard approach merges all employees' intervals together (often via a heap-based k-way merge or a simple sort-then-merge), then reports the gaps between consecutive merged intervals. It's an extension of basic interval-merging into a multi-list setting, testing whether a candidate can generalize a familiar single-list technique.

A class-design problem: implement a bank system supporting transfer, deposit, and withdraw operations across a fixed array of accounts, validating account indices and sufficient balance before each operation. There's minimal algorithmic depth — it mainly tests whether a candidate writes a correct, well-validated state machine with clean method boundaries and handles invalid-input edge cases without crashing or silently corrupting state.

Given a grid of letters and a list of target words, find every word that can be traced as a path of adjacent cells. The efficient solution builds a Trie from all target words, then does a DFS/backtracking search from every cell, using the Trie to prune paths that can't possibly extend into any remaining word. It's a strong signal problem because it requires combining two separate techniques — Trie construction and grid backtracking — rather than applying either in isolation.

The task is to parse a string representing a nested list of integers (e.g. `"[123,[456,[789]]]"`) into a nested integer structure. It's typically solved with a stack that tracks the currently-open nested lists, pushing a new list on `[`, popping and attaching on `]`, and parsing multi-digit and negative numbers along the way. It tests careful string parsing and stack-based state management rather than any well-known algorithm.

Implement regular expression matching supporting `.` (any single character) and `*` (zero or more of the preceding element) against a full string. The standard solution is a 2D dynamic program over (string index, pattern index), where the transition for `*` requires considering both 'match zero occurrences' and 'match one more occurrence' cases. It's widely regarded as one of the trickier string DP problems because the `*` transitions are easy to get subtly wrong, making it a good test of precise DP formulation under pressure.