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)

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:

  1. Empty Messages, what to do?
  2. 11 foos
  3. 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) —

GD Star Rating
loading...
602 words
Last Post: How to Check Valid Sudoku in C/C++?
Next Post: Greedy Algorithm to Compute the Largest Number

The Permanent URL is: Google Interview Question – Print Message

4 Comments

  1. Avi
  2. Anon

Leave a Reply