去年我参加了 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++代码就是这种组合的方式:
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) { // 把消息字符串变成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
loading...
上一篇: 浅谈棋类博弃的两种实现方式: 模式化和机器学习
下一篇: 小白教程: 怎么领取 BCC (Bitcoin Cash) ?