Implement a Trie
Updated
Problem statement
Implement a trie (prefix tree) that stores words made of lowercase letters. You are given two lists of the same length: operations[i] is the operation to run and words[i] is its word. Run them in order:
insert: add the word to the trie.search: answertrueif this exact word was inserted earlier, otherwisefalse.startsWith: answertrueif some word inserted earlier begins with this string (a word counts as beginning with itself), otherwisefalse.
Return the answers of all search and startsWith operations, in order. insert gives no answer. Inserting the same word again changes nothing.
Function
processTrie(operations: String[], words: String[]) → boolean[]Examples
Example 1
operations = ["insert","search","search","startsWith","insert","search"]words = ["card","card","car","car","car","car"]return = [true,false,true,true]After inserting card, searching card gives true. Searching car gives false: it is only the start of a word, not a word that was inserted. startsWith car gives true because card begins with it. After car is inserted as a word, searching it gives true.
Example 2
operations = ["startsWith","insert","startsWith","search"]words = ["b","bee","bees","be"]return = [false,false,false]Nothing has been inserted yet, so startsWith b is false. After inserting bee, no word starts with bees (it is longer than bee), and be was never inserted as a word, so both answers are false.
Constraints
1 <= operations.length <= 5000words.length == operations.length- Each
operations[i]is"insert","search", or"startsWith". 1 <= words[i].length <= 30, and everywords[i]has only lowercase English letters.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Word Dictionary with Wildcard FindAmazon · ONSITE INTERVIEW
- Add Word and Suffix SearchAnduril · ONSITE INTERVIEWAnduril interview questions
- Trie: Add and Search WordsAdobe · ONSITE INTERVIEWAdobe interview questions
- Implement TrieRoblox · ONSITE INTERVIEWRoblox interview questions
- In-Memory Directory and File OperationsSquarepoint Capital · ONSITE INTERVIEWSquarepoint Capital interview questions
- File System PathsCapital One · ONSITE INTERVIEWCapital One interview questions
- Implement TrieBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Trie With Insert, Search and Prefix CheckExpedia · ONSITE INTERVIEWExpedia interview questions
- Design File SystemGoogle · PHONE SCREENGoogle interview questions
- Implement TrieOptiver · PHONE SCREENOptiver interview questions