InternDoor

Counting words by how they start

Mediumdesign · trie · stringsDesign a class

Reported in interviews at (where)

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.

Example 1
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.

Example 2
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 letters
  • all the words and prefixes together hold at most 200000 letters
  • erase is only called for a word the bag holds
  • at 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

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.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.