Trie With Insert, Search and Prefix Check
Updated
Problem statement
Build a trie (a prefix tree) that stores words. It starts empty, and you get the calls in order as the list of strings operations:
insert wstores the wordw. It gives no output. Inserting a word that is already stored changes nothing.search woutputstrueif the whole wordwwas inserted earlier, andfalseotherwise.startsWith poutputstrueif some stored word begins withp, andfalseotherwise. A stored word begins with itself.
Return an array with one output for each search and startsWith, in the order they ran. If there are only inserts, return an empty array.
Aim for time proportional to the length of the word in each operation.
Function
processTrie(operations: String[]) → boolean[]Examples
Example 1
operations = ["insert plan","search plan","search pla","startsWith pla","insert planet","search plane","startsWith plane"]return = [true,false,true,false,true]After insert plan the word plan is stored, so search plan is true. search pla is false, because pla was never inserted as a word. startsWith pla is true, because plan starts with pla. After insert planet, search plane is false, since plane is only the start of planet, and startsWith plane is true for the same reason. The five outputs are [true, false, true, false, true].
Example 2
operations = ["search cat","insert cat","search cat","insert cat","insert car","startsWith ca","startsWith cab"]return = [false,true,true,false]The first search cat runs before any insert, so it is false. After insert cat it is true. Inserting cat a second time changes nothing, and car is added. startsWith ca is true, and startsWith cab is false, because no stored word starts with cab. The outputs are [false, true, true, false].
Example 3
operations = ["insert go","insert gone"]return = []Both operations are inserts, and an insert gives no output, so the answer is the empty list.
Constraints
1 <= operations.length <= 20008 <= operations[i].length <= 51- Each operation is exactly
insert w,search worstartsWith w, with one space, wherewis a word of 1 to 40 lowercase English letters.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Word Dictionary with Wildcard FindAmazon · ONSITE INTERVIEW
- Implement a TrieMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- 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
- Design File SystemGoogle · PHONE SCREENGoogle interview questions
- Implement TrieOptiver · PHONE SCREENOptiver interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)