bd、一面、1h。
自我介绍、实习内容介绍。
项目介绍（短链接服务）
生成短链接请求→获取ID→将长链接与ID写入MySQL→将ID进行base编码并返回。
访问短链接→将短链接进行base解码获得ID→从数据库查询对应长链接→响应重定向。
短链接ID生成
- 数据库自增ID：会有性能瓶颈
- redis自增序列：宕机会导致ID重复
- UUID：UUID太长，base编码后不适合短链接
- 雪花算法：依赖时钟
- TDDL：专门设计一个表用于记录当前ID值，每个服务节点一次性获取一定数量的ID，用完后再获取。利用乐观锁保证并发情况。
缓存强一致性如何实现？
参考连接
单独使用数据库会导致性能瓶颈→因此，一般使用缓存提升系统并发性能→但这可能会导致缓存与数据库数据不一致的问题
什么情况会导致数据不一致的问题？
- 单个进程操作失败。更新数据会涉及更新数据库和缓存，不管是先更新数据库还是先更新缓存，只要第二步操作失败，都会导致数据不一致。
- 多个进程并发操作。多个进程并发读写时，由于网络问题或其它原因，导致本应顺序执行的操作发生了错乱，导致数据不一致。
单个进程导致数据不一致
先更新缓存，再更新数据库
- 如果第二步更新数据库失败，等到缓存过期之后，会把数据库中的旧值写入到缓存，导致后续的请求都获取到旧值。
先更新数据库，再更新缓存
- 如果第二步更新缓存失败，那么缓存中的值还是旧值，后续的读请求都直接从缓存中读取，但读取到的是旧值，直到过期之后重新从数据库读取并更新到缓存。
总结：上面两种方式中，先更新数据库会更好（这样能保证数据库里的数据是正确的，缓存虽然不正确，但是有过期时间），因为只会导致缓存失效之前不一致。但先更新缓存会导致缓存失效之后，后续读请求都是数据库中更新到缓存的旧值。
如何保证第二步操作不会失败？
多个进程并发导致不一致
多个进程并发读写也分为先后，以先操作缓存为例，当前数据库和缓存中X=1。
- 进程A更新缓存X=2
- 进程B更新缓存X=3
- 进程B更新数据库X=3
- 进程A更新数据库X=2
可以发现，原本A应先执行的操作由于某些原因导致在B后面执行，导致当前缓存中X=3，而数据库中X=2。一个解决方案就是加分布式锁，将并行操作转为串行操作。
一致性方案
从上可知，导致数据不一致有很多情况（原因一般是操作失败，并发操作。情况分为多种，如结合先更新缓存还是先更新数据库），此处给出一致性方案。
相比更新缓存，删除缓存更好。尤其是先更新数据库，再删除缓存，这样能最大可能减少因为并发操作导致的数据不一致问题（还是会出现不一致问题，但概率相较其它情况会小很多，因此不能避免只能减少）。
除了并发导致的不一致问题，接下来需解决操作失败导致的不一致问题。
- 第二步操作失败，可以引入重试机制。（立即重试大概率也会失败，重试多久？重试次数？）
- 为了不影响正常业务，可以使用异步重试。如将重试请求写入消息队列，但这也会导致系统复杂度，并且消息队列会可能不可靠，需要针对消息队列进行可靠性涉及。
总结：先更新数据库，再删除缓存 + 异步重试。前者减缓并发操作导致的不一致问题，后者解决操作失败导致的不一致问题。
Q：redis为什么可以作为分布式锁？（应该是想问set nx的底层实现）
Q：cpp的虚函数，一个基类指针指向某个子类，调用虚函数时是如何执行到对应的子类实现的。
- 虚函数、虚函数表、虚函数指针。
Q：cpp中一个二维矩阵，按行和按列读取的区别。
cpu cache，局部性原理。按行读取时会大部分在cpu cache中都能命中，速度更快。
具体分析见我先前的一篇关于cpu cache的文章，且附带一个简单的cache大小估计实验。
算法题
单链表升序排序。没a出来，加了一道思考题。
排序：递归+归并。对应leetcode的148.排序链表
递归三步骤：
- 终止条件；
- 递归调用；
- 整合结果；
归并排序：两路归并直接比较即可，多路归并借助堆/优先队列
cpp代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head, ListNode* tail) {
// 递归终止条件
if (head == nullptr) return head;
if (head->next == tail) {
head->next = nullptr; // 作用?
return head;
}
// 递归调用
// 将[head, tail]一分为二, 各自排序再合并. 通过快慢指针找到中点
ListNode* slow = head, *fast = head;
while (fast != tail && fast->next != tail) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow;
ListNode* head1 = sortList(head, mid); // [head, mid), 各自排序
ListNode* head2 = sortList(mid, tail); // [mid, tail), 各自排序
// 整合结果: 通过归并排序将head1和head2合并
return merge(head1, head2);
}
// 两路归并排序
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* cur = dummyHead, *h1 = head1, *h2 = head2;
while (h1 != nullptr && h2 != nullptr) {
if (h1->val <= h2->val) {
cur->next = h1;
h1 = h1->next;
} else {
cur->next = h2;
h2 = h2->next;
}
cur = cur->next;
}
if (h1 != nullptr) {
cur->next = h1;
} else if (h2 != nullptr) {
cur->next = h2;
}
return dummyHead->next;
}
};
思考题：
有100个球，每次必须拿1-7个球。现两个人轮流拿，假设你首先开始，问如何拿能保证自己赢。最后一个拿走球的人算赢家，即要保证自己是最后取走剩余球的人。
反向思考：
最后一轮，即接下来是对方拿球时有多少个球，对方是必输的？
答案是8个。
- 假设对方只拿1个，剩余7个，自己可以全部拿走，获胜。
- 加黑色对方拿7个，还剩1个，自己可以全部拿走，获胜。
现在有92个球，相同规则，如何保证自己获胜。同样是最后一轮剩8个时，自己必胜。
因此，最开始，若只有8个球，且对方先拿，那么自己必定能够获胜。
现在是100个球，自己先拿，所以必须要保证拿走球后，剩余球的数量是8的倍数。也即需要拿走，最开始自己拿走4个球，剩余96个球。
接下来每一轮，假设对方拿走m个球，自己只需拿走个球即可，保证剩余球是8的倍数即可。
