FastPrepImplement a Trie
Problems/Implement a Trie

Implement a Trie

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Two reviews of Microsoft software engineering internship interviews, mention building a trie. In one, a trie was the main task of the algorithm interview. The other names it next to a second coding question.

Neither report says which operations the trie needs or gives any limits. Here it stores lowercase words and supports insert, search for a whole word, and startsWith for a prefix. The calls come as two lists of the same length, and you return the true or false answers of search and startsWith in order. Insert gives no answer.

Our version is about 85% the same as the reported questions.

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: answer true if this exact word was inserted earlier, otherwise false.
  • startsWith: answer true if some word inserted earlier begins with this string (a word counts as beginning with itself), otherwise false.

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 <= 5000
  • words.length == operations.length
  • Each operations[i] is "insert", "search", or "startsWith".
  • 1 <= words[i].length <= 30, and every words[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

Interview reports that mention this question

  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public boolean[] processTrie(String[] operations, String[] words) {
        // Write your code here.
    }
}
Checking account…