去年 Google 的面试题: 打印消息

去年我参加了 Google 的初面(电话面试), 可惜没有通过. Google 瑞士的一个软件工程师打电话面试, 电话面试就考了一道算法题, 虽然我也准备了近一个月的时间, 但是我回答的并不完美.

虽然和我联系的Google 是在伦敦, 但是面试的时候手机上显示的是 +41 电话来自 Google 瑞士, 整个面试大约45分钟.

题目是:

给了一些消息和对应的日期和时间, 如果消息并不在最近10秒钟内打印过那么就打印. 同时有可能多条消息到达(1秒之内).

就这么一个题目并没有指定接口, 而我们也不需要把所有消息都保存起来, 并且我们知道这个打印函数可能一秒内被调用多次:

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

我的第一个想法就是使用哈希表 HashMap, 但是这里有一个问题就是: 如果这个系统运行了好久好久, 这么一来, 内存就会不够了, 特别是到达的消息都是唯一的话.

面试官在我给出上面这个初步的答案后并不满意, 当然他会给提示指出问题(out of memory), 我在思考后给出了一个用队列+哈希表的方案:

我的方案是: 用队列来保存最近10秒打印过的消息, 并且我们用哈希表来加速查找. 以下C++代码就是这种组合的方式:

// member variables
unordered_set<int> cache;
queue<pair<time, int>> last10;
 
void PrintMessage(int time, string msg) {
    // 把消息字符串变成32位的哈希值
    int hash = compute_hash(msg);
    // 去除超过10秒的记录
    while (!last10.empty()) {
        auto key = last10.front();
        if (time - key.first >= 10) {
            last10.pop();
            cache.erase(key.second); 
        } else {
            break;
        }
    }   
    if (cache.count(hash)) {
        return; //  已经在过去10秒钟打印过了
    }
    // 打印消息
    cout << msg << endl;
    // 插入消息
    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) {
	// 把消息字符串变成32位的哈希值
	int hash = compute_hash(msg);
	// 去除超过10秒的记录
	while (!last10.empty()) {
		auto key = last10.front();
		if (time - key.first >= 10) {
			last10.pop();
			cache.erase(key.second); 
		} else {
			break;
		}
	}	
	if (cache.count(hash)) {
		return; //  已经在过去10秒钟打印过了
	}
	// 打印消息
	cout << msg << endl;
	// 插入消息
	cache.insert(hash);
	last10.push(make_pair(time, hash));
}

我并不是一下子就把代码写对, 有一些小细节的错误. 虽然没再进入下一轮面试, 但是还是体验了一把.

第二阶段就是问了单元测试相关知识, 比如上面的方法可以定义接口为:

1	bool PrintMessage(int time, string msg); // 返回是否打印

bool PrintMessage(int time, string msg); // 返回是否打印

那么测试用例(Test Cases) 可以是:

空字符串
11 个 foo
6 次 foo, bar, foo bar

您还有什么比较刁钻的测试用例么? 在下面评论吧.

更新: , 这题后来被分享到leetcode 上了(Logger Rate Limiter), 我写了Java/C++的解题报告: Design a Logger Rate Limiter in C/Java/

英文: Google’s Interview: Print Message

面试经历

面试题

面试技巧

面试其它

GD Star Rating
loading...

本文一共 602 个汉字, 你数一下对不对.

去年 Google 的面试题: 打印消息. (AMP 移动加速版本)
上一篇: 浅谈棋类博弃的两种实现方式: 模式化和机器学习
下一篇: 小白教程: 怎么领取 BCC (Bitcoin Cash) ?

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

面试经历

面试题

面试技巧

面试其它

相关文章：

评论