字节跳动，提前批一面问题

1. 介绍你最看重的一个项目

   华为的未完成项目

2. 说一下哈希及其优化，哈希函数怎样设计？

一种O(1)时间复杂的键值数据结构。优化思想有将链表改为红黑树，重哈希，提高哈希函数随机分布性，有Java中的哈希表设计（数组+链表或者红黑树，当装载因子超过0.75进行重哈希，数组大小翻倍,无收缩操作），redis的哈希表设计（数组+链表，哈希函数为MurmurHash3，渐进哈希保证服务器的响应性）。哈希函数设计最主要的目的是使得不同键尽量不会冲突，Java通过hash = hashCode^(hashCode>>16)，在hash&(tbSize-1)来散列到具体哪个bin。保证了很好地利用了键hashCode中的每个字符。

1. 讲一下redis的rehash过程
   有两个hashTable,ht[0]在没有开始rehash时保存数据。如果开始rehash，每一次修改或者查询就将一个在ht[0]中的键值对转移到ht[1]中，在put数据时就直接put到第二个ht中，get数据时先从第一个找，找不到再从第二个找,delete亦然。
2. 做一个算法题，p = "abcdfg", q = "abcd"，找出p中包含q所有字符的最短子序列
3. 一致性哈希算法，如何避免数据倾斜
   分布式系统中机器增加删除能够快速重新哈希。通过对键值加后缀1，2，..
4. 数据库索引，给定一个表"id student_id course_type score"
   要选出每门课程的top10，如何建索引，sql语句怎么写？

   select * from student A 
   where id in
   (select id from student B 
   where B.course_type==A.course_type 
   order by score DSC limit 0,10) 
   order by course_type, score DSC

   应该建立course_type,socre的联合索引吧？
5. LRU缓存设计，如和优化(队列+哈希)
6. TCP的四次挥手以及TIME_WAIT作用
   四次挥手保证当客户端发出断开连接报文时，服务端仍然可以向客户端发送数据。
   TIME_WAIT作用一是保证客户端ACK报文没有被服务端收到，服务端重发FIN+ACK后还能够确认，二是客户端发送完最后一个确认报文后，在这个2MSL时间中，就可以使本连接持续的时间内所产生的所有报文段都从网络中消失。这样新的连接中不会出现旧连接的请求报文。