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

JustYY.com 小赖子的英国生活和资讯

7 years ago

去年我参加了 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++的解题报告: https://helloacm.com/design-a-logger-rate-limiter-in-c-java/

英文: Google’s Interview: Print Message

强烈推荐

英国代购-畅购英伦
TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
Quidco 返现 (也是很不错的英国返现网站, 返现率高)
注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
注册就送10美元, 免费使用2个月的阿里云主机(性价比超高, 每月只需4.5美元)
注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
刷了美国运通信用卡一年得到的积分换了 485英镑
注册就送50英镑 – 英国最便宜最划算的电气提供商
能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

强烈推荐

相关文章：