Counting words by how they start
Build WordTrie, a bag of lowercase words that can say how many of its words start with a given string. The same word may be in the bag more than once, and every copy counts.
WordTrie() starts with an empty bag.
insert(word) puts one copy of word into the bag.
count(word) returns how many copies of exactly word the bag holds.
countPrefix(prefix) returns how many words in the bag start with prefix, copies included. A word starts with itself.
erase(word) takes one copy of word out of the bag. It is only called when the bag holds at least one copy.
Every call should take time in proportion to the length of the string it is given, however many words the bag holds.
- Input
["WordTrie","insert","insert","insert","count","countPrefix","erase","count","countPrefix","countPrefix"]
[[],["tree"],["tree"],["trek"],["tree"],["tre"],["tree"],["tree"],["tre"],["b"]]- Output
[null,null,null,null,2,3,null,1,2,0]
Both copies of "tree" and the one "trek" start with "tre". Erasing takes out one copy of "tree", not both.
- Input
["WordTrie","insert","count","countPrefix","countPrefix","countPrefix","erase","countPrefix"]
[[],["car"],["ca"],["ca"],["car"],["cart"],["car"],["c"]]- Output
[null,null,0,1,1,0,null,0]
"ca" was never put in as a word, so count gives 0, but "car" starts with it. "car" also starts with "car" itself.
Limits
every word and prefix is 1 to 20 lowercase lettersall the words and prefixes together hold at most 200000 letterserase is only called for a word the bag holdsat most 20000 calls after the constructor
Hints
Hint 1
Store the words letter by letter in a tree: each node is a prefix, and its children are that prefix with one more letter.
Hint 2
Keep two counts in every node: how many words pass through it, and how many end there. insert adds 1 along the path; erase takes 1 off.
Where this was reported
- PhonePe, On-campus interview, 2023 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
