时间：2015-08-11 11:30 ~ 12:30
地点：知春路甲48号盈都大厦B座11层今日头条
1. 先对着简历的项目问了许多。
2. 算法题：一个按顺序排好的数组，从某一个位置开始将后面的数移动到前面。例如，"123456789" -> 从第7个元素开始移动到最前面，"789123456", 在这种情况下查找一个数。
int search(int A[], int left, int right, int target) { if (left < right) return -1; int middle = (left + right) / 2; if (A[middle] == target) return middle; else if (A[right] < target) return search(A, left, middle - 1, target); else if (A[middle] < target) return search(A, middle + 1, right, target); else return search(A, left, middle - 1, target); }
3. 算法设计题：
实现一个方法 bool visit(const string &ip); 该方法满足以下需求，限制每一个IP地址一个小时内最多访问5w次，如果超过5w次，那么返回false，否则返回true。注意：这一小时是滑动的。也就是随着时间一直在移动的范围。
类似题目：
http://intgraph.wizmann.tk/System%20Design/ratelimit-system.html
struct IPInfo { int count[3600]; // 存储每一秒的访问次数 int index; // count的index int total_visits; // 这一小时内的访问次数 int last_time; // 上一次访问的时间，以秒为单位 int cnt_visits; // 当前这一秒访问次数 }; map<string, IPInfo> ip_info; bool visit(const string &ip) { const int cnt_time = get_cnt_time(); // 获得当前时间，以秒为单位 if (ip_info.find(ip) == ip_info.end()) { // 该IP地址第一次访问 IPInfo ipf; ipf.index = 0; ipf.total_visits = 0; ipf.last_time = cnt_time; ipf.cnt_visits = 1; ip_info[ip] = ipf; return true; } IPInfo &ipf = ip_info[ip]; int cnt_total_visits, old; if (ipf.last_time == cnt_time) { // 跟上一次是同一秒访问的 ipf.cnt_visits++; cnt_total_visits = ipf.total_visits - ipf.count[ipf.index] + ipf.cnt_visits; if (cnt_total_visits > 50000) return false; return true; } else { // 跟上一次 不是 同一秒访问的 // 写入last_time的访问量到count[index] ipf.total_visits -= ipf.count[ipf.index]; ipf.count[ipf.index] = ipf.cnt_visits; ipf.total_visits += ipf.cnt_visits; ipf.index++; ipf.index %= 3600; if (cnt_time > ipf.last_time + 1) { // last_time = 3s // cnt_time = 5s // 那么需要将index移动2次，并且total_visits要减去那些旧的访问量 int i = cnt_time - ipf.last_time - 1; while (i--) { ipf.total_visits -= ipf.count[ipf.index]; ipf.count[ipf.index] = 0; ipf.index++; ipf.index %= 3600; } } ipf.cnt_visits = 1; ipf.last_time = cnt_time; if (ipf.total_visits + 1 > 50000) return false; return true; } }
4. 看过什么书
《C++Primer》
《C++程序设计语言》
《Effective C++》
5. 做过什么项目
1. 看过chrome源码。大概一个月。
2. ALG 算法相关的项目。https://github.com/loverszhaokai/ALG
6. 总结
应该是面试失败了。我感觉不是2面失败了，而是因为1面。最后一题，与面试官的沟通出现了很大问题。彼此感觉都不好。还好这是2015年的第一次面试，注意跟面试官进行沟通。冷静，当然遇到某些面试官。。。