Google Interview Question for Software Developers
- 1of 1 vote
Implement a rate-limiter-like iterator and how to improve the space complexity- sun2gz July 05, 2018 in United States
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?
| Report Duplicate | Flag | PURGE
Google Software Developer
Interview Type: Phone Interview
Open Chat in New Window