神刀安全网

Google Interview Question – Print Message

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)

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
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 usehashmap/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.

// 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 actualProgramming IDE!

It would be good that someone can make testing data for this question. The engineer also asks me the test cases if I want to write unit tests for it. I can think of three cases:

  1. Empty Messages, what to do?
  2. 11 foos
  3. foo, bar, foo bar … after 6 times

–EOF–

GD Star Rating

loading…

412 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Google Interview Question – Print Message

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址