Quick Overview

Implement trie insertion and exact-word search for up to a million total characters, distinguishing terminal words from mere prefixes and returning search results in operation order.

Implement Trie Insert and Exact-Word Search

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Implement a trie that supports `insert(word)` and `search(word)`. Insert adds a lowercase word. Search returns true only when the complete word was previously inserted; a stored word merely sharing the requested prefix is not a match. Process a sequence of operations and return the results of all searches. ### Constraints & Assumptions - There are at most 200,000 operations. - Every word has length between 1 and 1,000. - The total number of characters across all operations is at most 1,000,000. - Words contain lowercase English letters. ### Clarifications - Inserting the same word repeatedly is allowed and has no additional effect. - A node must distinguish an inserted word ending there from a prefix only. - Return booleans in the same order as search operations appear. ### Examples ```text operations = [insert("apple"), search("apple"), search("app"), insert("app"), search("app")] output = [true, false, true] ``` ### Hints ```hint Represent prefixes Each edge consumes one character and each node represents the prefix along its path. ``` ```hint Mark complete words Reaching the final character is not enough unless the terminal node records an insertion. ```

Overview: Implement trie insertion and exact-word search for up to a million total characters, distinguishing terminal words from mere prefixes and returning search results in operation order.

Read the full Google Software Engineer interview experience this question came from

Process a fresh trie through operations ["insert", word] and ["search", word]. Insert adds a lowercase word and may be repeated without additional effect. Search returns true only if that complete word was previously inserted; reaching a prefix node is insufficient. Return booleans only for search operations, preserving their order.

Constraints

  • operations contains at most 200000 encoded insert or search lists.
  • Every word has length between 1 and 1000.
  • The total number of characters across all operations is at most 1000000.
  • Words contain only lowercase English letters.
  • Duplicate insertion has no additional effect.
  • Only search operations contribute returned booleans.

Examples

Input: ([['insert', 'apple'], ['search', 'apple'], ['search', 'app'], ['insert', 'app'], ['search', 'app']],)

Expected Output: [True, False, True]

Explanation: This is the source example; app is only a prefix until it is explicitly inserted.

Input: ([],)

Expected Output: []

Explanation: No search operations produce an empty result.

Hints

  1. Let every trie node represent one consumed prefix.
  2. Mark a node separately when an inserted word ends there.

Loading coding console...

Show the approach

Approach

Each trie node represents the prefix spelled by the path from the root and stores one child per next lowercase character plus a terminal flag. Insert follows or creates the word's edges and marks only its final node terminal. Search follows the requested edges; a missing edge proves the word was never inserted, while reaching all characters succeeds only when the final node is terminal. Therefore shared prefixes reuse nodes without confusing a prefix with an exact stored word.

Time complexity:
O(C), where C is the total number of characters across all operations
Space complexity:
O(I + r), where I is the number of distinct inserted-prefix characters and r is the number of searches