Google Interview QuestionSoftware Developers
- 0of 0 votes
Implement a rate-limiter-like iterator and how to improve the space complexity
Given a <Word, TimeStamp> pair data type iterator as input. Implement an iterator based on it which can ignore the item if the same word has occurred in the past 10 seconds.
My implementation is to use a HashMap to memorize the word and its latest timestamp + 10s. For each new item, it will be checked against the HashMap to see if it has duplicated word occurred in the past 10s.
The interviewer asked me how to improve the space complexity if the string value varieties are infinite. He mentioned some boundary stuff.
Could anyone share some thoughts?
Country: United States
Interview Type: Phone Interview