FastPrepTrie With Insert, Search and Prefix Check
Problems/Trie With Insert, Search and Prefix Check

Trie With Insert, Search and Prefix Check

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: One post, published on September 8, 2018 by a student from an Expedia campus internship drive, lists this task in an interview after the online test.

The post names fast dictionary lookup and a trie written from scratch with insert and search, and links a separate article for the code. It gives no input form, no limits and no examples. Here, the input is a list of text operations answered in order: insert, search for a whole word, and startsWith. The prefix operation is our addition, since it is what a trie offers beyond a hash set. Words are 1 to 40 lowercase letters and there are up to 2000 operations. Only the answers are checked, not the time or the use of a trie. A hash set also passes the search calls, and scanning every stored word passes the prefix calls.

Our version is about 70% the same as the reported question.

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 w stores the word w. It gives no output. Inserting a word that is already stored changes nothing.
  • search w outputs true if the whole word w was inserted earlier, and false otherwise.
  • startsWith p outputs true if some stored word begins with p, and false otherwise. 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 <= 2000
  • 8 <= operations[i].length <= 51
  • Each operation is exactly insert w, search w or startsWith w, with one space, where w is 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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public boolean[] processTrie(String[] operations) {
        // Write your code here.
    }
}
Checking account…