面试学习.

Tabris

求职

发布于：2018年1月29日

次浏览

记录下我针对面试的学习

算法/编程题

a

[√] 荷兰国旗问题

噗 , 被高大上的名字给吓到了，其实就是简单的 C 语言入门题。

实现一个 LRU 算法

[√]双栈实现一个队列

实现代码

[√]编程题

问题： 两个数组 A 表示一串螺丝 B 表示一串螺帽 螺丝和螺帽能够配对，但是 A 中螺丝之间不能比较大小，B 中螺帽之间也不能比较大小，螺丝和螺帽可以比较大小，返回所有螺丝和螺帽的对应关系，要求复杂度小于 O(n^2)

解： 类似快速排序，一个和另一个比较就可以了。
code

今日头条笔试真题

https://www.nowcoder.com/test/8537140/summary

基础知识

算法与数据结构

操作系统

一个进程

一个进程是 PCB 结构与程序与数据的组合

[-]产生死锁的必要条件

• 互斥条件： 即某个资源在一段时间内只能由一个进程占有，不能同事被两个或两个以上的进程占有。这种独占资源如 CD-ROM 驱动器，打印机等等，必须在占有该资源的进程主动释放它之后，其他进程才能占有该资源。这是有资源本身的属性所决定的。如独木桥就是一种独占资源，两方的人不能同时过桥。

• 不可抢占条件： 进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者中夺取资源。而只能由该资源的占有者进程自行释放。如过独木桥的人自己不能强迫对方后退，也不能非法地将对方退下桥，必须是桥上的人自己过桥后空出桥面(即主动释放占有资源)，对方的人才能过桥。

• 占有且申请条件： 进程至少已经占有一个资源，但又申请新的资源; 由于该资源已经被另外进程占有，此时该进程阻塞; 但是，它在等待新资源之时，扔继续占用已占有的资源。还以过独木桥为例，甲乙两人在桥上相遇。 甲走过一段桥面(即占有了一些资源)，还需要走其余的桥面(申请新的资源)，但那部分桥面被已占有(已走过一段桥面).甲过不去，前进不能，又不后退;乙也处于同样的状况。

• 循环等待条件： 存在一个进程等待序列{P1,P2, ... ,Pn}, 其中 P1 等待 P2 所占有的某一资源， P2 等待 P3 所占有的某一源， ...... ，而 Pn 等待 P1 所占有的某一资源形成一个进程循环等待环。就像前面的过独木桥问题，甲等待乙占有的桥面，而乙有等待甲占有的桥面， 从而彼此循环等待。

[-]死锁预防

• 打破互斥条件： 即允许进程同事访问某些资源。但是，有的资源不允许被同时访问的，像打印机等等。这是由资源本身的属性所决定的。 所以，这种办法并无实用价值

• 打破不可抢占条件： 即允许进程强行从占有者哪里夺取某些资源。 就是说， 当一个进程已占有了某些资源，他又申请新的资源，但不能立即被满足，它必须释放所占有的全部资源， 以后再重新申请。 他所释放的资源可以分配给其他进程。这就相当于该进程占有的资源被隐蔽性地强占了。 这种预防死锁的方法实现起来困难，会降低系统性能。

• 打破占有且申请条件： 可以实行资源预先分配策略。 即进程在运行前一次地向系统申请它所需要的全部资源。 如果某个进程所需的全部资源得不到满足，则不分配任何资源，此进程在不运行。只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程。 由于运行的进程已占有它所需要的全部资源所以不会发生占有资源有申请资源的现象， 因此不会发生死锁。 但是，这种策略也有如下缺点：

  • 在许多情况下，一个进程在执行之前不可能知道它所需要的全部资源。 这是由于进程在执行时是动态的，不可预测的。
  • 资源利用率低。无论所分资源何时用到，一个进程只有在占有所需要的全部资源后才能执行。即使有些资源最后才被该进程用到一次，但该进程生存期间一直占有他们，造成长期占着不用的状况。这显然是一种极大的资源浪费。
  • 降低了进程的并发性。因为资源有限，又加上存在浪费，能分配到所需全部资源的进程个数就必然少了。

• 打破循环等待条件：实行资源有序分配策略.采用这种策略，即把资源事先分类编号，按号分配，使进程在申请，占用资源是不会形成环路。所有进程对资源的请求必须严格按字元序号递增的顺序提出。进程占用了小号资源，才能申请大耗资源，就不会产生环路， 从而预防了死锁。这种策略与前面的策略相比， 资源的利用率和系统的吞吐量都有了很大的提高，但是也存在一下缺点：

  • 限制了进程对资源的请求，同事给系统中所有资源合理编号也是件困难时，并增加了系统的开销。
  • 为了遵循按编号申请的次序，在不使用的资源也需要提前申请，从而增加了进程对资源的占用时间。

死锁避免

• 银行家算法
  系统给当前进程分配资源时，先检查是否安全。
  在满足当前的进程 X 资源申请后，是否还能有足够的资源去满足下一个距最大资源需求最近的进程(如某进程最大需要 5 个单位资源，已拥有 1 个，还需 4 个)，若可以满足，则继续检查下一个距最大资源需求最近的进程，若均能满足所有进程，则表示为安全，可以允许给当前进程 X 分配其所需的资源申请，否则让该进程 X 进入等待。
• 哲学家进餐问题

[-]进程和线程的区别

定义
进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位。
线程是进程的一个实体，是 CPU 调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源(如程序计数器，一组寄存器和栈)，但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
关系
一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行。
相对进程而言，线程是一个更加接近于执行体的概念，它可以与同进程中的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。
区别
进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

简而言之，一个程序至少有一个进程，一个进程至少有一个线程。
线程的划分尺度小于进程，使得多线程程序的并发性高。
另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。
线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。
优缺点
线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源的管理和保护；而进程正相反。同时，线程适合于在 SMP 机器上运行，而进程则可以跨机器迁移。

[]进程间通信

####### 为什么需要进程间通信？？

进程是一个独立的资源分配单元，不同进程（这里所说的进程通常指的是用户进程）之间的资源是独立的，没有关联，不能在一个进程中直接访问另一个进程的资源（例如打开的文件描述符）。

但是，进程不是孤立的，不同的进程需要进行信息的交互和状态的传递等，因此需要进程间通信( IPC：Inter Processes Communication )。

进程间通信的目的：

• 数据传输：一个进程需要将它的数据发送给另一个进程。
• 通知事件：一个进程需要向另一个或一组进程发送消息，通知它（它们）发生了某种事件（如进程终止时要通知父进程）。
• 资源共享：多个进程之间共享同样的资源。为了做到这一点，需要内核提供互斥和同步机制。
• 进程控制：有些进程希望完全控制另一个进程的执行（如 Debug 进程），此时控制进程希望能够拦截另一个进程的所有陷入和异常，并能够及时知道它的状态改变。
  Linux 操作系统支持的主要进程间通信的通信机制：

进程间通信(IPC)介绍

[]进程调度

[]进程的内存分布

进程调度

• 先来先服务 （FCFS，first come first served）
  在所有调度算法中，最简单的是非抢占式的 FCFS 算法。
  算法原理：进程按照它们请求 CPU 的顺序使用 CPU.就像你买东西去排队，谁第一个排，谁就先被执行，在它执行的过程中，不会中断它。当其他人也想进入内存被执行，就要排队等着，如果在执行过程中出现一些事，他现在不想排队了，下一个排队的就补上。此时如果他又想排队了，只能站到队尾去。
  算法优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平
  算法缺点：比较有利于长进程，而不利于短进程，有利于 CPU 繁忙的进程，而不利于 I/O 繁忙的进程

• 最短作业优先（SJF, Shortest Job First）
  短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对 FCFS 算法的改进，其目标是减少平均周转时间。
  算法原理：对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。
  算法优点：相比 FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。
  算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。

• 最高响应比优先法(HRRN，Highest Response Ratio Next)
  最高响应比优先法(HRRN，Highest Response Ratio Next)是对 FCFS 方式和 SJF 方式的一种综合平衡。FCFS 方式只考虑每个作业的等待时间而未考虑执行时间的长短，而 SJF 方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN 调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。这样，即使是长作业，随着它等待时间的增加，W / T 也就随着增加，也就有机会获得调度执行。这种算法是介于 FCFS 和 SJF 之间的一种折中算法。
  算法原理：响应比 R 定义如下： R =(W+T)/T = 1+W/T
  其中 T 为该作业估计需要的执行时间，W 为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R 最大者投入执行。
  算法优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于 SJF 法，从而采用 HRRN 方式时其吞吐量将小于采用 SJF 法时的吞吐量。
  算法缺点：由于每次调度前要计算响应比，系统开销也要相应增加。

• 时间片轮转算法（RR，Round-Robin）
  该算法采用剥夺策略。时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR 调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
  算法原理：让就绪进程以 FCFS 的方式按时间片轮流使用 CPU 的调度方式，即将系统中所有的就绪进程按照 FCFS 原则，排成一个队列，每次调度时将 CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个 ms 到几百 ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让 CPU（如阻塞）。
  算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。
  算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当
  怎样确定时间片的大小：

  • 时间片大小的确定
    1.系统对响应时间的要求
    2.就绪队列中进程的数目
    3.系统的处理力

• 多级反馈队列(Multilevel Feedback Queue)
  多级反馈队列调度算法是一种 CPU 处理机调度算法，UNIX 操作系统采取的便是这种调度算法。
  多级反馈队列调度算法描述：
  　　1、进程在进入待调度的队列等待时，首先进入优先级最高的 Q1 等待。
  　　2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3 三个队列，只有在 Q1 中没有进程等待时才去调度 Q2，同理，只有 Q1,Q2 都为空时才会去调度 Q3。
  　　3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如 Q1 队列的时间片为 N，那么 Q1 中的作业在经历了 N 个时间片后若还没有完成，则进入 Q2 队列等待，若 Q2 的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
  　　4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU 马上分配给新到达的作业（抢占式）。
  　　在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能够较好的满足各种类型用户的需要。

计算机网络

[]TCP 和 UDP 区别

详细介绍,戳<<<--

TCP 与 UDP 区别总结：
TCP 面向连接（如打电话要先拨号建立连接）;UDP 是无连接的，即发送数据之前不需要建立连接
TCP 提供可靠的服务。也就是说，通过 TCP 连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP 尽最大努力交付，即不保 证可靠交付
TCP 面向字节流，实际上是 TCP 把数据看成一连串无结构的字节流;UDP 是面向报文的 UDP 没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如 IP 电话，实时视频会议等）
每一条 TCP 连接只能是点到点的;UDP 支持一对一，一对多，多对一和多对多的交互通信
TCP 首部开销 20 字节;UDP 的首部开销小，只有 8 个字节
TCP 的逻辑通信信道是全双工的可靠信道，UDP 则是不可靠信道

[-]TCP 三次握手/四次挥手

详细介绍,戳<<<---
更亲民的介绍,戳<<<---

建立连接的过程是利用客户服务器模式，假设主机 A 为客户端，主机 B 为服务端

• TCP 的三次握手过程：主机Ａ向Ｂ发送链接请求; -> 主机 B 对收到的主机 A 的报文段进行确认; -> 主机 A 再次对主机 B 的确认进行确认
• 采用三次握手是为了防止失效的链接请求报文段突然有传送到主机 B，因而产生错误。失效的链接请求报文段是指： 主机 A 出的连接请求没有收到主机 B 的确认，于是经过一段时间后，主机 A 又重新向主机 B 发送连接请求，且建立成功，顺序完成数据传输。 考虑这样一个特殊情况，主机 A 第一次发送的连接请求并没有丢失，而是因为网络节点导致延迟到达主机 B，主机 B 以为是主机又发起的新连接，于是主机 B 同意连接，并向主机 A 发回确认，但是此时主机 A 根本不会理会，主机 B 就一直在等待主机 A 发送数据，导致主机Ｂ的资源浪费．
• 采用两次握手不行， 原因就是上面说的实效的连接请求的特殊情况。

TCP 里的一些机制

OSI,TCP/IP，五层协议的体系结构，以及各层协议

OSI 分层(7 层): 物理层，数据链路层，网络层，传输层，会话层，表示层，应用层。
TCP/IP 分层(4 层): 网络接口层，网际层，运输层，应用层。
五层协议(5 层): 物理层，数据链路层，网络层，运输层，应用层。

每一层的协议如下：
物理层： RJ45,CLOCK,IEEE802.3(中继器，集线器)
数据链路： POP,FR,HDLC,VLAN,MAX(网桥，交换机)
网络层： IP,UCMP,ARP,RARP,OSPF,IPX,RIP,IGRP(路由器)
传输层： TCP,UDP,SPX
会话层： NFS,SQL,NETBIOS,RPC
表示层： JPEG,MPEG,ASII
应用层： FTP,DNS,Telnet,SMTP,HTTP,WWW,NFS

每一层的作用如下

物理层： 通过媒介传输比特，确定机械及电器规范(比特 Bit)
数据链路： 将比特组装成帧和点到点的传递(帧 Frame)
网络层： 负责数据包从源到宿的传递和网际互联(包 PackeT)
传输层： 提供端到端的可靠报文传递和错误回复(段 Segment)
会话层： 简历，管理和中智慧化(会话协议数据单元 SPDU)
表示层： 对数据进行翻译，加密和压缩(表示协议数据单元 PPDU)
应用层： 允许方位 OSI 环境的手段(应用协议数据单元 APDU)

IP 地址的分类

A 类地址： 以 0 开头， 第一个字节范围 1127(1.0.0.0127.255.255.255);
B 类地址： 以 10 开头， 第一个字节范围 128191(128.0.0.0191.255.255.255);
C 类地址： 以 110 开头， 第一个字节范围 192223(192.0.0.0223.255.255.255);
D 类地址： 以 1110 开头， 第一个字节范围 224239(224.0.0.0239.255.255.255);
E 类地址： 保留

一种 A,B,C 是基本类，D,E 类作为多播和保留使用。
以下是留用的内部私有地址：
A 类 10.0.0.0 -- 10.255.255.255
B 类 182.16.00 -- 192.31.255.255
C 类 192.168.0.0 -- 192.168.255.255

IP 地址与子网掩码相与(&)得到网络号
ip 192.168.2.110
&
submask:255.255.255.0
.---------------------------------
网络号 192.168.2.0

注： 主机号，全是 0 的网络号(例如 192.168.2.0)，主机号全为 1 的为广播地址(192.168.2.255)

ARP 是地址解析协议，简单语言解释一下工作原理。

• 首先，每个主机都会在自己的 ARP 缓冲区中建立一个 ARP 列表，以表示 IP 地址和 MAC 地址之间的对应关系。
• 当源主机要发送数据时，首先检查 ARP 列表中是否有对应 IP 地址的目的主机的 MAC 地址，如果有，则直接发送数据，如果没有，就向本网段的所有主机发送 ARP 数据包，该数据包包括的内容有： 源主机的 IP 地址，源主机的 MAC 地址，目的主机的 IP 地址。
• 当本网络中的所有主机收到该 ARP 数据包时，首先检查数据包中的 IP 地址是否是自己的 IP 地址，如果不是，则忽略该数据包，，如果是，则首先从数据包中去除源主机的 IP 和 MAC 地址写入到 ARP 列表中，如果已经存在，则覆盖，然后将自己的 MAC 地址写入 ARP 响应包中，告诉源主机自己是它想要找的 MAC 地址
• 源主机收到 ARP 响应后。将目的主机的 IP 和 MAC 地址写入 ARP 列表，并利用此信息发送数据。 如果源主机一直没有收到 ARP 相应数据包，表示 ARP 查询失败。

广播发送 ARP 请求，单播发送 ARP 相应。

RARP 协议

RARP 是逆地址解析协议，作用是完成硬件地址到 IP 地址的映射，主要用于无盘工作站，因为给无盘工作站配置的 IP 地址不能保存。
工作流畅： 在网络中配置一台 RARP 服务器，里面保存者 IP 地址和 MAC 地址的映射关系，当无盘工作站启动后，就封装一个 RARP 数据包，里面有其 MAC 地址，然后广播到网络上去，当服务器收到请求包后，就查找对应的 MAC 地址的 IP 地址装入响应报文中发回给请求者。 因为需要广播请求报文，因此 RARP 只能用于具有广播能力的网络。

各种协议的介绍

• ICMP 协议: 因特网控制报文协议。它是 TCP/IP 协议族的一个自协议，用于在 IP 主机/路由器之间传递控制消息。
• TFTP 协议: 是 TCP/IP 协议族中的一个用来在客户机与服务器之间进行简单文件传输的协议，提供不复杂，开销不大的文件传输服务。
• HTTP 协议: 超文本传输协议，是一个属于应用层的面向对象的协议，由于其简捷，快速的方式，适用于分布式超媒体信息系统
• NAT 协议: 网络地址转换属介入广域网(WAN)技术，是一种将私有(保留)地址转化为合法 IP 地址的转换技术。
• DHCP 协议: 动态主机配置协议，给用户或者内部网络管理员作为对所有计算机作中央管理的手段。

在浏览器中输入 www.baidu.com 后执行的全部过程

• 1. 客户端浏览器通过 DNS 解析到 www.baidu.com 的 IP 地址为 220.181.27.48, 通过这个 IP 地址找到客户端到服务器的路径。 客户端浏览器发起一个 HTTP 回话到 220.181.27.48, 然后通过 TCP 进行封装数据包， 输入到网络层。
• 2. 在客户端的传输层，把 HTTP 回话请求分成报文段，添加源和目的端口， 如服务器使用 80 端口监听客户端的请求， 客户端有系统随机选择一个端口如 5000, 与服务器进行交换，服务器吧相应的请求返回给客户端的 5000 端口。 然后使用 IP 层的 IP 地址查找目的端。
• 3. 客户端的网络层不用关心应用层或者传输层的东西， 主要做到的是通过查找路由表确定如何到达服务器，期间可能经过多个路由器，这些都是有路由器来完成的工作， 我不做过多的描述， 无非就是通过查找路由表决定通过哪个路径到达服务器。
• 4. 客户端的链路层， 包通过链路层发送到路由器， 通过邻居协议查找给定 IP 地址的 MAC 地址，然后发送 ARP 请求查找到目的地址， 如果得到回应后就可以使用 ARP 的请求应答交换的 IP 数据包，现在就可以传输了，然后发送 IP 数据包到达服务器的地址。

DNS 域名系统，简单描述其工作原理

当 DNS 客户机需要在程序中使用名称时， 它会查询 DNS 服务器来解析该名称。 客户机发送的每条查询信息包括三条信息： 包括： 指定的 DNS 域名，DNS 域名的指定类型。 基于 UDP 服务，端口 53. 该应用一般不直接为用户使用， 而是为其他应用服务，如 HTTP,SMTO 等在其中需要完成主机名到地址的转换。

了解交换机，路由器，网关的概念， 并知道各自的用途

• 交换机
  在计算机网络系统中，交换机是针对共享工作模式的弱点而推出的。交换机拥有一条高带宽的背部总线和内部交换矩阵。交换机的所有的端口都挂接在这条背部总线上，当控制电路收到数据包以后，处理端口会查找内存中的地址对照表以确定目的端口。目的 MAC 若不存在，交换机才广播到所有的端口， 接手端口回应后交换机会'学习'新的地址，并把它添加入内部地址表中。
  交换机工作于 OSI 参考模型的第二层，即数据链路层。 交换机内部的 CPU 会在每个端口成功连接时，通过 ARP 协议学习它的 MAC 地址，保存成一张 ARP 表。 在今后的通讯中， 发往该 MAC 地址的数据包将仅送往其对应的端口，而不是所有端口。 因此，交换机可用于划分数据链路层广播，即冲突域; 但它不能划分网络层广播， 即广播域。
  交换机被广泛应用于二层网络交换，俗称'二层交换机'.
  交换机的种类有： 二层交换机，三层交换机，四层交换机，七层交换机分别工作在 OSI 七层模型中的第二层，第三层，第四层和第七层，并因此而得名。

• 路由器
  路由器(Router)是一种计算机网络设备，提供了路由与传送两种重要机制，可以决定数据包从来源端到目的端所经过的路由路径(host 到 host 之间的传输路径)，这个过程称为路由; 将路由器输入端的数据包移送至适当的路由器输出端(在路由器内部进行)，这成为传动. 路由工作在 OSI 模型的第三层 -> 即网络层，例如网际协议。
  路由器的一个作用是连通不同的网络另一个作用是选择信息传送的线路。 路由器与交换机的差别， 路由器是属于 OSI 第三层的产品，交换机是 OSI 第二层的产品(这里至二层交换机)

• 网关
  网关(Gateway), 网关顾名思义就是连接两个网络的设备，区别与路由器(由于历史的原因，许多有关 TCP/IP 的文献曾经把网络层使用的路由器成为网关，在今天很多局域网采用的都是路由器来接入网络，因此现在通常指的网关就是路由器的 IP)，经常在家庭中或者小型企业网络中使用，用于连接局域网和 Internet. 网关也经常把一种协议转成另一种协议的设备，比如语音网关。
  在传统 TCP/IP 术语中，网络设备只分成两种，一种为网关(Gateway)，另一种称为主机(host). 网关能在网络间传递数据包，但主机不能传送数据包。在主机(又称终端系统，end system)中，数据包需经过 TCP/IP 四层协议处理，但是在网关(又称中介系统，intermediate system)只需要到达网际层(Internet layer)，决定路径之后就可以传送。 在当时，网关(Gateway)和路由(Router)还没有区别。
  在现代网络术语中，网关(Gateway)和路由(Router)的定义不同，网关(Gateway)能在不同协议间移动数据，而路由器(Router)是在不同网络间移动数据，相当于传统所说的 IP 网关(IP Gateway).
  网关是连接两个网络的设备，对于语音网关来说，它可以连接 PSTN 网络和以太网，这就相当于 VOIP，把不同电话的模拟信号通过网关而转换成数字信号，而且加入协议再去传输。 在到了接收端的时候再通过网关还原成模拟的电话信号，最后才能在电话机上听到。
  对于以太网中的网关只能转发三层以上数据包，这一点和路由是一样的。而不同的是网关中并没有路由表，他只能按照预先设定的不同网段来进行转发。网关最重要的一层就是端口映射，子网内用户在外网看来只是外网的 IP 地址对应着不同的端口，这样看来就会保护子网内的用户。

C/C++

BSS 段的功能

char *p1 = "123" 与 char p2[]="123"，其中 p1,p2 区别

答： 常量是存储在内存中的，
*p1 是指针 指向"123"中的"1"的地址
p2[] 是数组 本质是在堆栈中定义的一段内存

sizeof(struct{char c;int a;}) = ?

答： 4

内存对其，整体占得内存一定是最大数据元素的整数倍.
这里最大的是 int(4 字节)整体就是(4*n 字节)
大概是这个样子
|int|char|
△△△△|△---|

多线程编程经验

C++ 网络编程

C++11 新增了什么，了解的有哪些。

[√]const 关键字作用。

好文

[-]多态/虚函数

介绍

Java

[√]HashMap

介绍链接

Synchronze 和 Lock 的区别和用法

Ps: 在 Java1.5 中， syncchronize 是性能低效的，因为这是一个重量级操作，需要调用操作接口，导致有可能加锁消耗的系统时间比加锁以外的操作还多。 相比之下使用 Java 提供的 Lock 对象，性能更高一些。但是到了 Java1.6，发生了变化。 synchronize 在语义上很清晰，可以进行很多优化，有适应自旋，锁消除，锁粗化，轻量级锁，偏向锁等等。 导致在 Java1.6 上 synchronize 的性能并不比 Lock 差。

乐观锁，悲观锁

• 乐观锁（ Optimistic Locking ） 相对悲观锁而言，乐观锁机制采取了更加宽松的加锁机制。悲观锁大多数情况下依靠数据库的锁机制实现，以保证操作最大程度的独占性。但随之而来的就是数据库性能的大量开销，特别是对长事务而言，这样的开销往往无法承受。而乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version ）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
• 悲观锁（Pessimistic Lock），正如其名，具有强烈的独占和排他特性。它指的是对数据被外界（包括本系统当前的其他事务，以及来自外部系统的事务处理）修改持保守态度，因此，在整个数据处理过程中，将数据处于锁定状态。悲观锁的实现，往往依靠数据库提供的锁机制（也只有数据库层提供的锁机制才能真正保证数据访问的排他性，否则，即使在本系统中实现了加锁机制，也无法保证外部系统不会修改数据）。

Linux

进程的内存分布

那个命令可以常看内存使用情况

答：
top
free [-h]

touch 有什么用

答： 两个作用

• 一，用于吧已存在文件的时间标签更新为系统当前的时间(默认方式)，它们的数据将原封不动地保留下来;
• 二，用来创建新的空文件

僵尸进程，孤儿进程，守护进程

详细介绍

• 僵尸进程： 在 fork()/execve()过程中，假设子进程结束时父进程仍存在，而父进程 fork()之前既没安装 SIGCHLD 信号处理函数调用 waitpid()等待子进程结束，又没有显示忽略该信号，则子进程成为僵尸进程。

• 孤儿进程： 一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。 孤儿进程将被 init 进程(进程号为 1)所收养，并由 init 进程对他们完成状态收集工作。

• 守护进程： Linux 系统中的守护进程是一种运行在后台的进程。 而守护进程，也就是通常说的 Daemon 进程。 它通常独立于控制终端并且周期性的执行某种任务或等待处理某些发生的事件。 Linux 大多数服务器进程就是用这种守护进程实现的， 例如 Web 服务。守护进程常常在系统引导装入时启动， 在系统关闭时终止。 守护进程最大的特点是运行在后台，与终端无连接， 除非特殊情况下， 用户不能操作守护进程。

python

大数据

MongoDB vs Redis

MongoDB 和 Redis 都是 NoSQL，采用结构型数据存储。二者在使用场景中，存在一定的区别，这也主要由于二者在内存映射的处理过程，持久化的处理方法不同。

MongoDB 建议集群部署，更多的考虑到集群方案，Redis 更偏重于进程顺序写入，虽然支持集群，也仅限于主-从模式。

数据库

数据库事务的四大特性(ACID)

• 原子性(Atomicity)
  事务是数据库的逻辑工作单位，它对数据库的修改要么全部执行，要么全部不执行。
• 一致性(Consistemcy)
  事务前后，数据库的状态都满足所有的完整性约束
• 隔离性(lsolation)
  并发执行的事务是隔离的，一个不影响一个。如果有两个事务，运行在相同的时间内，执行相同的功能，事务的隔离性将确保每一事务在系统中认为只有该事物在使用系统。 这种属性有时称为串行化，为了防止事务操作间的混淆，必须串行化或序列化请求，使得在同一时间仅有 y 一个请求用于统一数据。通过设置数据库的隔离级别，可以达到不同的隔离效果。
• 持久性(Durability)
  在事务完成后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。

并发事务引起的问题

• 更新丢失
  两个事务都同时更新一行数据，但是第二个事务却中途失败退出，导致对数据的两个修改都失效了。这是因为系统没有执行任何的锁操作，因此并发事务并没有被隔离开来。

• 脏读
  脏读又称无效数据读出。一个事务读取另外一个事务还没有提交的数据叫脏读。
  例如：事务 T1 修改了一行数据，但是还没有提交，这时候事务 T2 读取了被事务 T1 修改后的数据，之后事务 T1 因为某种原因 Rollback 了，那么事务 T2 读取的数据就是脏的。

设计题/系统题

.

[]设计一个 ID 分配器

.

技术无关

.

能抗住压力么

答：作为应届生，本就应该吃苦耐劳学技术，人都是逼出来的，有压力才有动力，这点压力不算什么。

有女朋友么

答： 没有，一心向学，不找女朋友浪费时间。(TM 是找不到好不 2333)

你有什么问题吗

1. 这个岗位做的主要业务是什么
2. 岗位的技术栈
3. 招这个岗位的校招或者实习生更看重哪方面的能力

本页文档最后更新于：2021年5月16日

面试

C++

操作系统

计算机网络

大数据