How should I practice Implement Trie?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Roblox onsite interview problems in FastPrep.

Is Implement Trie associated with Roblox?

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

Problem · String

Implement Trie

Learn this problem

● Medium

RobloxFULLTIMEONSITE INTERVIEW

See Roblox hiring insights

Problem statement

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

A trie supports three operations:

insert(word): insert word into the trie.
search(word): return whether word was previously inserted as a complete word.
startsWith(prefix): return whether at least one previously inserted word starts with prefix.

For this FastPrep draft, operations are provided as arrays. operations[i] is one of "insert", "search", or "startsWith", and values[i] is the word or prefix for that operation. Return the boolean results for only the search and startsWith operations, in the order they occur. insert operations do not produce output.

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]

After inserting dog, search(dog) is true, search(do) is false, and startsWith(do) is true. After inserting do, search(do) becomes true.

Example 2

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

The first search happens before abc is inserted. After insertion, ab is a valid prefix and abc is a stored word.

Constraints

operations.length == values.length
operations[i] is "insert", "search", or "startsWith".
1 <= values[i].length <= 1000
values[i] contains only lowercase English letters.