字节面试第二次一面挂_字节 算法 一面挂

进步很多了，问的深度比以前要难了。
但是还是有点不会，所以继续加油吧——挂了好难受。

1G的长度16的字符串，只能用1M，找出前100多的字符串

分治法：
将1G文件分成5000个文件，每个文件大致是200k。
然后把所有数据哈希映射到每个文件中，每次只进行1M的操作。

对于每个文件，再不超过1M内存的情况下，对每个字符串进行计数。
计数用哈希表进行计数，每次遇到一个新的哈希值就增加index，然后把计数信息加入，或者在原来的基础上进行修改；计数信息保存到文件中。

最后能得到每个文件中的字符串计数信息。
然后建立一个top 100堆，找到每个文件前100大，和上面同理，如果超内存了就把数据保存到文件中下一次继续进行操作。

维护一个top 5000，top 5000保存前5000个数，然后按顺序取最大的，每取完一个，把对应文件再弹出一个新的，直到100个。

建议：面试的时候假定冲突较少，每个文件里面的数量较少。

哈希表实现，开链过长

STL的哈希表：
负载系数：元素$/$表格大小
线性探测：重复了就线性往下找，存在主集团问题，找的时间比负载系数增长的快
二次探测：$f(t)=t+i^2$，这样解决了主集团问题，但会引起次集团问题，每次探测的位置是相同的。
开链法：每个键值有个列表，表格是vector的，这种就是STL实现了。
如果元素总数超过表格大小，就进行重建，找一个适合的质数作为表格大小(STL预存了28个质数)，用一个新的vector装新加入的元素，然后逐步把所有键值的起始节点加入进新的vector，每个键值内的直接修改链表节点指向就行了。
最后交换vector的指针，并且释放原来的内存。
java中hashmap某个键值对应链表较长会转红黑树。

操作系统的内存管理

https://editor.csdn.net/md/?articleId=108157222

B树、B+树优点，适用于

(1)B树的树内存储数据，因此查询单条数据的时候，B树的查询效率不固定，最好的情况是O(1)。我们可以认为在做单一数据查询的时候，使用B树平均性能更好。但是，由于B树中各节点之间没有指针相邻，因此B树不适合做一些数据遍历操作。
(2)B+树的数据只出现在叶子节点上，因此在查询单条数据的时候，查询速度非常稳定。因此，在做单一数据的查询上，其平均性能并不如B树。但是，B+树的叶子节点上有指针进行相连，因此在做数据遍历的时候，只需要对叶子节点进行遍历即可，这个特性使得B+树非常适合做范围查询。
因此，我们可以做一个推论:没准是Mysql中数据遍历操作比较多，所以用B+树作为索引结构。而Mongodb是做单一查询比较多，数据遍历操作比较少，所以用B树作为索引结构。

堆栈

见这

数据库的ACID特性

事务是一个操作序列
原子性： 原子性是指事务是一个不可再分割的工作单位，事务中的操作要么都发生，要么都不发生。
一致性： 一致性是指在事务开始之前和事务结束以后，数据库的完整性约束没有被破坏。这是说数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性。
隔离性： 多个事务并发访问时，事务之间是隔离的，一个事务不应该影响其它事务运行效果。
持久性： 在事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。

AVL和红黑树

红黑树是不够严格的$AVL$，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，插入和删除的影响较小，较快。
但查找的效率红黑树较慢，因为他至多不平衡$n$层，最大查询复杂度是$2logn$的。
红黑树最多旋转3次，AVL是log次。

进程/线程通信方式

管道：半双工的通信方式，数据只能单向流动，且只能在有亲缘关系（父子进程或兄弟进程）的进程间使用；
命名管道：FIFO，半双工的通信方式，但允许在无亲缘关系的进程间通信；
消息队列：消息的链表，存放在内核中，并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点；
信号量：是一个计数器，用于控制多个进程间对共享资源的访问；
共享内存：映射一段能被其他进程访问的内存，这段内存由一个进程创建，但多个进程都可以访问；
套接字

线程通信：锁机制和信号量机制。

共享内存

共享内存允许两个或更多进程访问同一块内存，就如同malloc()函数向不同进程返回了指向同一个物理内存区域的指针。当一个进程改变了这块地址中的内容的时候，其它进程都会察觉到这个更改。
特点：
1、很快，立马就看到修改
2、需要同步，不允许同时修改。(信号量实现)
具体模型：
要想使用一块共享内存，一个进程首先要分配它，随后需要访问这个共享内存块的每一个进程都必须将这个共享内存绑定到自己的地址空间，完成通信之后，所有进程将脱离共享内存，然后由一个进程释放。

计算机网络，如果客户端发送的SYN丢失，如何？

服务端超时重发。

IO复用机制

$select$

$select$缺点

1、单个进程能够监视的文件描述符的数量存在最大限制，通常是1024，当然可以更改数量，但由于select采用轮询的方式扫描文件描述符，文件描述符数量越多，性能越差；(在linux内核头文件中，有这样的定义：#define __FD_SETSIZE 1024)
2、内核 / 用户空间内存拷贝问题，select需要复制大量的句柄数据结构，产生巨大的开销；
3、select返回的是含有整个句柄的数组，应用程序需要遍历整个数组才能发现哪些句柄发生了事件，并且扫描的过程中也是轮询的方式。
4、select的触发方式是水平触发，应用程序如果没有完成对一个已经就绪的文件描述符进行IO操作，那么之后每次select调用还是会将这些文件描述符通知进程。

$epoll$

Linux epoll机制是通过红黑树和双向链表实现的。 首先通过epoll_create()系统调用在内核中创建一个eventpoll类型的句柄，其中包括红黑树根节点和双向链表头节点。然后通过epoll_ctl()系统调用，向epoll对象的红黑树结构中添加、删除、修改感兴趣的事件，返回0标识成功，返回-1表示失败。最后通过epoll_wait()系统调用判断双向链表是否为空，如果为空则阻塞。当文件描述符状态改变，fd上的回调函数被调用，该函数将fd加入到双向链表中，此时epoll_wait函数被唤醒，返回就绪好的事件。

epoll优点

事件驱动——不需要轮询
需要监听的文件描述符都存在了内核，用红黑树，不需要每次从用户空间复制。

cookie和session等登录方式

它们都是用来标记用户状态的。

cookie

cookie是K-V形式的，存储在浏览器中一种数据。它有大小限制，以及使用字符串类型作为value值，分为内存和硬盘(非持久和持久)。

1、监测到浏览器客户端没有标识用户的 cookie，跳转到登陆界面
2、用户账号密码登陆，后端验证，成功后，在Set-cookie中设置标识用户的 cookie
3、登陆成功，保存用户标识的 cookie
4、购买商品，自动携带用户身份的 cookie，后端验证无误后，购买成功
缺点：
a. cookie会被附加在每个HTTP请求中，所以无形中增加了流量。
b. 由于在HTTP请求中的cookie是明文传递的，所以安全性成问题。（除非用HTTPS）
c. Cookie的大小限制在4KB左右。对于复杂的存储需求来说是不够用的。[2]

session

Session 机制准确来说，也是通过 K-V 数据格式来保存状态。其中：

Key：也称 SessionID，保存在客户端浏览器。
Value：也称Session，保存在服务端。

可以看到，客户端只需要存储 SessionID。具体映射的数据结构放在了服务端，因此跳出了仅仅浏览器cookie只可以存储 string类型的限制。而客户端存储 SessionID，还是需要借助 cookie 来实现，如果不支持就加到URL上。

Token

session的不足：服务器是有状态的。分布式系统的多台后端服务器无法共享 session。解决方法是，专门准备一台 session服务器，关于 session 的所有操作都交给它来调用（Memcached），为了避免单点故障，又得搞出session集群。

Token的解决思路是，不在服务端保存sessionid，而是通过加密的token令牌来验证，token中包含的数据：用户信息+签名（用于加密，可能是hmac-sha256的加密串），这样就解除了服务器需要存储sessionid的负担，也方便了分布式系统中用户的跟踪，验证token时只需要cpu通过密钥计算来完成。

1、用户尝试登陆
2、登陆成功后，后端依靠加密算法，将凭证生成 token，返回给客户端
3、客户端保存 token，每次发送请求时，在http的header中携带token
4、后端再接收到带有 token 的请求时，通过密钥来验证 token 的有效性

cookie和session 的区别

1、cookie数据存放在客户的浏览器上，session数据放在服务器上。
2、cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗
考虑到安全应当使用session。
3、cookie 是一种发送到客户浏览器的文本串句柄，并保存在客户机硬盘上，可以用来在某个WEB站点会话间持久的保持数据。
4、session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能考虑到减轻服务器性能方面，应当使用COOKIE。
5、单个cookie保存的数据不能超过4K，很多浏览器都限制一个站点最多保存20个cookie。
6、session其实指的就是访问者从到达某个特定主页到离开为止的那段时间。 Session其实是利用Cookie进行信息处理的，当用户首先进行了请求后，服务端就在用户浏览器上创建了一个Cookie，当这个Session结束时，其实就是意味着这个Cookie就过期了。
注：为这个用户创建的Cookie的名称是aspsessionid。这个Cookie的唯一目的就是为每一个用户提供不同的身份认证。
7、cookie和session的共同之处在于：cookie和session都是用来跟踪浏览器用户身份的会话方式。
详细

同源策略

A的cookie，B不能打开，除非同源。
同源：协议、端口、域名相同。

http://www.example.com/dir/page.html这个网址，协议是http://，域名是www.example.com，端口是80（默认端口可以省略）。
Cookie有两个很重要的属性:Domain(域名归属)和Path(路径归属)，用来指示此

特点

Cookie的作用域需要满足以下两点： 1.当前域名或者父域名下的Cookie；2.当前路径或父路径下的Cookie。要满足以上两个条件的Cookie才会被提交。举个例子：有4个Cookie:

9个球，一个天平，有一个较大的球，找几次找到最大的球，一次可以放多个球

二分

12个球，有一个坏球，找出来是大是小

首先，如果有3个球，已知每个球可能是大还是可能小。
选两个球比较(相同可能的)，如果相同则是另一个球，否则这两个球中，比如$a<b$，且$a、b$可能较小，那么答案是$a$。

所以我们分成三组，前两组比较，相同的话，就是在后面一组。
9 10 11 12，9 10 11和1 2 3(一定是对的)，如果相同，答案是12，12和1比较就知道大小了。
如果9 10 11 < 1 2 3，有一个较小的，9和10比较，相同的时候就是11，不同的时候就是较小的。

如果1 2 3 4 < 5 6 7 8，根据这种三个为组的特质，我们需要在一次划分之后：
得到多个三个一组即可。
123<567可以吗？显然不可以，因为123较小，567较大，无法确定。
125<346可以吗，首先只有可能是12较小或6大，因为34较小不可能使右边变大，5较大不可能使得左边变小，得到126两个较小和一个较大，根据最开始的特质判断即可。
125>346答案就是34较小或5较大，同理。
125=346那么只剩下78了。

1234>5678同理。

上面的问题，13个球呢？

首先如果1234 5678不相同的时候，还是一样的。
如果相同了，答案在9 10 11 12 13中，9 10 11可以直接判断，然后继续比较，12 < 1或12 > 1，答案就是12且知道大小，但12 = 1的时候确定了13但是不知道大小。