Katkat
Back

Implement Trie Insert and Exact-Word Search

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

operations = [insert("apple"), search("apple"), search("app"), insert("app"), search("app")]
output = [true, false, true]

Hints

Hints

Hint 1

Represent prefixes: Each edge consumes one character and each node represents the prefix along its path.

Hint 2

Mark complete words: Reaching the final character is not enough unless the terminal node records an insertion.