This is the technical phone interview question from Google. Google has offices in London but the call was from Google Switzerland (+41). The interview lasts for 45 minutes.
Given a list of messages and the date/time, print each message if it is not printed in the last 10 seconds. It is possible that several messages arrive roughly at the same time (within 1 second)
The engineer didn’t provide any interface (so you can come up with the function signature). We don’t need to store all the messages and the frequency for the function call could be several per second.
00:00:01 foo 00:00:02 bar 00:00:06 bar // should not print .. .. 00:00:10 foo // should not print 00:00:11 foo // print again
Using Hashmap
Using a hashmap to store the printed messages and their corresponding time is trivial but this will have a memory issue (Out-Of-Memory) if this function is running for weeks. Hashmap will grow, especially that all the messages are unique!
Using Queue+Hashmap
We can use queue to store the messages in last 10 seconds. We can use hashmap/set to store the messages printed, in order to speed up lookup. This method is the combination of both queue and hashmap/set. The following C++ code demonstrates the idea. We use the int type to represent the time type for simplification.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | // member variables unordered_set<int> cache; queue<pair<time, int>> last10; void PrintMessage(int time, string msg) { // compute the string hash as a 32-bit integer int hash = compute_hash(msg); // remove invalid entries while (!last10.empty()) { auto key = last10.front(); if (time - key.first >= 10) { last10.pop(); cache.erase(key.second); // remove from hash set } else { break; } } if (cache.count(hash)) { return; // printed in last 10 seconds } // we can print the message now cout << msg << endl; // inserting the entry cache.insert(hash); last10.push(make_pair(time, hash)); } |
// member variables unordered_set<int> cache; queue<pair<time, int>> last10; void PrintMessage(int time, string msg) { // compute the string hash as a 32-bit integer int hash = compute_hash(msg); // remove invalid entries while (!last10.empty()) { auto key = last10.front(); if (time - key.first >= 10) { last10.pop(); cache.erase(key.second); // remove from hash set } else { break; } } if (cache.count(hash)) { return; // printed in last 10 seconds } // we can print the message now cout << msg << endl; // inserting the entry cache.insert(hash); last10.push(make_pair(time, hash)); }
I did make some mistakes in writing the code on the Google Docs without an actual Programming IDE!
It would be good that someone can make testing data for this question. To adapt it for Online Judge, we can re-write the function signature to:
1 | bool PrintMessage(int time, string msg); // return whether to print this message |
bool PrintMessage(int time, string msg); // return whether to print this message
The engineer also asks me the test cases if I want to write unit tests for it. I can think of three cases:
- Empty Messages, what to do?
- 11 foos
- foo, bar, foo bar … after 6 times
Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.
Design Logger Rate Limiter
This problem is officially available on online judge. You can read the complete solution at this post: Design a Logger Rate Limiter in Java/C++.
You may also like: 去年 Google 的面试题 – 打印消息
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Check Valid Sudoku in C/C++?
Next Post: Greedy Algorithm to Compute the Largest Number
Hi,
I am getting a bit confused here . Probably I am wrong, but shouldn’t the condition be ?
time – key.first >= 10 // then remove from queue and cache.
yes, you are right,
typos, corrected.
Did you cleared the round? As after the phone interview they get back within 2 days.
Best of luck.
Thanks, unfortunately, not, I didn’t proceed to next round i.e. did a few mistakes when I came up with the solution (the pseudo code was not perfect).
The problem is now available at leetcode online judge i.e. Logger Rate Limiter – whic you are welcome to challenge yourself.