Stage V: Easy Questions
Trie (Prefix Tree)
Implement Trie (Prefix Tree)
Task: Build a Trie from scratch with insert, search, and startsWith methods.
Companies: Amazon, Google, Microsoft, Facebook
Search Suggestions System
Task: Given products and a search word, return suggested products as each character is typed.
Companies: Amazon
Longest Common Prefix
Task: Find the longest common prefix string amongst an array of strings.
Companies: Amazon, Adobe
Design Add and Search Words Data Structure
Task: Design a data structure that supports adding words and searching with wildcards (.).
Companies: Facebook, Amazon, Microsoft
Maximum XOR of Two Numbers in an Array
Task: Find the maximum XOR result of any two numbers in an array. (A classic problem solvable with a Trie of bits).
Companies: Google, Amazon
Disjoint Set Union (DSU) / Union-Find
Number of Provinces
Task: Given an adjacency matrix of cities, find the total number of connected groups of cities.
Companies: Amazon, Google
Number of Connected Components
Task: Given n nodes and a list of edges, count the number of connected components.
Companies: Amazon, Facebook, Google
Graph Valid Tree
Task: Determine if a given graph is a valid tree (fully connected with no cycles).
Companies: Google, Facebook, Amazon
The Earliest Moment When Everyone Become Friends
Task: Find the earliest timestamp at which all people are connected in a single friend group.
Companies: Amazon
Sentence Similarity II
Task: Determine if two sentences are similar, given that similarity is transitive.
Companies: Google
Bit Manipulation
Single Number
Task: In an array where every element appears twice except for one, find that single one.
Companies: Amazon, Google, Facebook, Apple
Number of 1 Bits
Task: Return the number of '1' bits (Hamming weight) in an integer.
Companies: Apple, Microsoft
Counting Bits
Task: For a given integer n, return an array showing the number of 1's in the binary representation of each number from 0 to n.
Companies: Facebook
Missing Number
Task: Given an array of n distinct numbers in the range [0, n], find the only number in the range that is missing.
Companies: Amazon, Microsoft, Facebook