How should I practice Implement Trie?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Bloomberg LP phone screen and onsite interview problems in FastPrep.

Is Implement Trie associated with Bloomberg LP?

FastPrep tags this as a Bloomberg LP phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Implement Trie

Bloomberg LP● MediumNEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

Implement the behavior of a prefix tree, also known as a trie.

Process the paired arrays operations and values from left to right:

insert: store the word.
search: report whether the value is a previously inserted complete word.
startsWith: report whether at least one inserted word begins with the value.

Return the boolean results produced by search and startsWith, in operation order. Insert operations produce no result. Repeated insertion of the same word does not change behavior.

Function

trieOperations(operations: String[], values: String[]) → boolean[]

Examples

Example 1

operations = ["insert","search","search","startsWith","insert","search"]values = ["dog","dog","do","do","do","do"]return = [true,false,true,true]

dog is a complete word, do is initially only a prefix, and inserting do makes its later search succeed.

Example 2

operations = ["search","insert","startsWith","search"]values = ["a","abc","ab","abc"]return = [false,true,true]

The first search happens before insertion. Afterward, ab is a prefix and abc is a complete word.

Example 3

operations = ["insert","insert","search","startsWith"]values = ["cat","cat","cat","ca"]return = [true,true]

Inserting the same word twice preserves ordinary set semantics.

Constraints

1 <= operations.length == values.length <= 100000.
Each operation is insert, search, or startsWith.
1 <= values[i].length <= 1000.
The total length of all values is at most 500000.
Every value contains only lowercase English letters.