Stage V: Hard Questions
Trie (Prefix Tree)
Word Search II
Task: Given a 2D board of characters and a list of words, find all words from the list that exist in the board.
Companies: Amazon, Microsoft, Google, Facebook
Palindrome Pairs
Task: Given a list of unique words, find all pairs of indices (i, j) so that words[i] + words[j] is a palindrome.
Companies: Google, Amazon, Airbnb
Concatenated Words
Task: Find all words that are made of a sequence of at least two other words from the list.
Companies: Amazon
Word Squares
Task: Given a set of words, find all "word squares" you can build from them.
Companies: Google
Maximum XOR With an Element From Array
Task: An offline query problem where you find the maximum XOR for a given number against elements in an array that are less than a certain value.
Companies: Google
Disjoint Set Union (DSU) / Union-Find
Accounts Merge
Task: Merge user accounts that share a common email address.
Companies: Google, Facebook, Amazon
Redundant Connection II
Task: In a directed graph that is a tree with one extra edge, find the redundant edge.
Companies: Google, Amazon
Number of Islands II
Task: After each addLand operation on a grid of water, count the number of islands.
Companies: Google, Amazon
Couples Holding Hands
Task: Find the minimum number of swaps required so that every couple is sitting side-by-side.
Companies: Google
Optimize Water Distribution in a Village
Task: Find the minimum cost to supply water to all houses by either building wells or laying pipes.
Companies: Amazon
Bit Manipulation
Single Number II
Task: In an array where every element appears three times except for one, find that single one.
Companies: Google, Amazon
Single Number III
Task: In an array where exactly two elements appear only once and all others appear twice, find the two elements.
Companies: Google
Bitwise AND of Numbers Range
Task: Given a range [left, right], return the bitwise AND of all numbers in this range.
Companies: Google
Maximum Product of Word Lengths
Task: Find the maximum product of the lengths of two words from a list that do not share any common letters.
Companies: Google
Smallest Sufficient Team
Task: Find the smallest team of people that covers all required skills.
Companies: Google