Dynamic Prefix Query Counts
Google● MediumINTERNONSITE INTERVIEWProblem statement
Maintain a collection of search queries and answer how many stored query occurrences begin with a given prefix. Duplicate queries count separately.
The collection is initially empty. You are given arrays operations and values of equal length. Process entry i in order:
insert: add one occurrence of the queryvalues[i].delete: remove one occurrence of the exact queryvalues[i]. If it is absent, leave the collection unchanged.count: count all stored query occurrences that start with the prefixvalues[i].
Return only the results of the count operations, in their original order. Mutations do not produce output. An empty prefix matches every stored query occurrence. If there are no count operations, return an empty integer array.
Examples
Example 1
operations = ["insert","insert","insert","count","delete","count","count"]values = ["app","apple","app","app","app","app",""]return = [3,2,2]The first prefix count includes both copies of app and apple. Deleting one app leaves two matching occurrences. The empty prefix then counts the same two stored occurrences.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.