技术岗面试题小结（一）
技术岗面试题小结（一）
研发岗的面试问题可能不会局限于某个编程语言或者某个技术栈，有时候也会去问一些比较杂项的东西，所以这里单开一个系列来汇总这些杂项题目。可能会包括一些智力题和应用题
1.大量数据，寻找重复次数最高的k条数据
大量数据可能是10G以上的级别，而内存大小有限，这意味着不可能通过内存一次性完成提取，必须要有分治法的思想。
法1：将数据分成若干份，每份单独排序，然后利用堆（或优先队列）的数据结构对这些若干小数据进行多路的外部排序，将最终的排序结果保存到大文件中。遍历排序后的文件，逐条读取数据并进行计数，读取到不同数据时确定上一组数据的频数，并用大小为k的大顶堆进行储存，遍历完成后，堆内留下的k个数据就是我们需要的数据。
法2：数据类型不多、重复率高的话，可以分成多个小文件，分别逐条读取数据通过Hash统计
大数据类型的题有很多（例如排序、统计、查询等），但是无一例外都需要借助分治法的思想
2. 25匹马，5个跑道，如何在最少的比赛次数内找出最快的三匹
排除法：
首先将25匹马分为ABCDE五组，每组5匹马，分别进行一次比赛。假设A1速度大于A2速度，A1速度大于B1速度，以此类推。
五组完成后可以淘汰掉每组的最后两匹马（必定不属于前三快），剩下的马是A-E 1-3共15匹
然后将每组最快的马放在一起比赛一次，淘汰掉末两位，同时这两匹马所对应的组全部被淘汰。同时也可以确定全部马里最快的那一匹马是A1，因此可以认为B1最快也只能排第二，C1最快只能排第3，所以可以排除B3,C2,C3，最后只留下六匹马为A1,A2,A3,B1,B2,C1,因为A1已经确定是最快的了，所以只需要让剩下五匹马再比赛一次选前二快的即可。
所以最小次数为7次
3. Linux如何找10天内修改过的文件
find ./ -mtime -10
其中find指令用于在后面指定的目录下搜索文件，-mtime表示x天内被修改的文件，同样的，-mmin表示x分钟内修改过的文件
相似的，如果需要找5分钟内修改过的文件，有下列命令
find ./ -mmin -5
4. 一个圆桌，AB两个人放硬币，A先放，先放不下的人输，A如何放才能保证赢
A第一下放在中心，之后每一下都放在与B放的位置中心对称的地方。
5. 8个球，1个球比其他7个重，如何用一个天平秤2次找出重的球
选其中六个平均放在天平两边，若平衡，则说明重的球在剩余两个里面，称出即可。若不平衡，将偏重一侧的三个球取出，选择任意两个称第二次，若第二次平衡，则剩余的那个球是重球，若第二次不平衡，则直接称出。
6. 熟悉Linux版本和命令
Linux有许多常见开发版本，如Ubuntu，Solaris，Oracle，CentOS等等
常用的文件操作命令：
ls 显示目录内文件信息
cd 改变当前终端所在目录
pwd 显示所在目录
touch 创建文件
mkdir 创建文件夹
mkdir -p 递归创建文件目录
rm 删除单个文件
rm -rf 无提示地强制递归删除目录（r为递归，f强制删除，慎用）
rmdir 删除空文件夹
mv 移动、剪切粘贴、重命名
cp 复制
cat 在终端上显示文件信息
head 显示前几行
tail 显示后几行
find 查找文件
grep 根据字符串搜索文件
mount 挂载文件系统
umount 取消挂载
man 帮助文档
chmod 修改权限
chown 修改文件所有者
unzip 解压zip文件
tar -zxvf 解压tar文件
tar -czvf 压缩tar文件
nano / vim / vi 文件编辑器
常用系统管理命令
systemctl 管理系统服务
systemctl + start/stop/restart/enable/disable/status 具体操作
top 实时显示系统进程
ps 显示当前进程快照
ps aux 列出所有进程
kill PID 终止进程
killall process_name 终止所有指定名称进程
uname 显示系统信息
shutdown now 关机 -r 重启
reboot 重启
常用网络管理命令
ifconfig/ip 显示配置网络接口
ping 测试连接
netstat 显示网络连接、路由表、接口统计信息等信息
curl 使用协议传输数据
wget 从网络下载文件
7.熟悉git（使用终端，不使用IDE）
git init 初始化git仓库
git clone 克隆远程仓库
git add 增加文件到暂存区
git commit -m "" 提交修改
git status 查看工作目录和暂存区状态
git log 查看提交记录
git branch 查看分支列表 -d 删除分支
git checkout 切换分支
git merge 合并分支
git pull 拉取远程仓库更新
git push 本地提交推送到远程仓库
git remote 管理远程仓库 add 添加 -v 查看 remove 删除
git fetch 从远程仓库更新，不合并
git rebase 将当前分支修改应用到另一个分支基础
git diff 查看未缓存或未提交文件
8.死锁的四个必要条件
发生死锁必须同时满足四个必要条件：
- 互斥(Mutual Exclusion)： 资源在任意时刻只能被一个进程使用，不能同时被多个进程使用
- 持有并等待(Hold and Wati)： 一个进程已经持有至少一个资源，并且正在等待被其他进程占用的资源
- 不剥夺(No Preemption)： 资源只能由进程自主释放，不能强行剥夺
- 环路等待(Circular Wait)： 进程之间的资源等待情况形成环路
9.银行家算法
常见的操作系统避免资源占用死锁的算法 简单来说，就是分配资源前试探判断分配后的资源安全性，若不安全则取消分配，若存在一个安全序列则处于安全状态
用Process(P)表示进程，P[i]表示第i个进程 用Max表示进程最大需求资源数量 用Available表示（初始）空闲资源数量（可用于分配） 用Work表示（实时）空闲资源数量 用Allocation表示已为该进程分配资源数量，Allocation[i]对应P[i] 用Need表示该进程还需要的资源数量（即Need = Max-Allocation），Need[i]对应P[i]
注意，上述都是向量，为简单描述，比较大小为比较每一对应位上数值的大小。 例如[1,2,3,4]<[2,3,4,5]
银行家算法判断安全性的方法如下： 开始令Work=Avaiable 在进程P[i]中找到未完成的进程且Need[i]<=Work，完成该进程，将该进程占用的资源释放， 令Work+=Allocation[i] 反复寻找，直到所有进程都能完成，视为找到了安全序列 若无法找到满足条件的进程，则视为不安全，不能分配资源
10.TCP报文格式、三次握手与四次挥手
TCP报文
TCP报文有如下关键数据信息
- Source Port / Destination Port (src/dst): 各16bit, 源端口号与目的端口号
- Sequence Number (seq): 标识该段报文数据在整体数据流中的次序，保证顺序传输
- Acknowledge Number (ack): 确认序列号,接收端下次应当收到数据的序号，ACK=1时有效
- Offset: 偏移
- TCP标识:各1bit设置为0或1
- URG: 紧急指针域是否有效(保证TCP连接不中断)
- ACK: 应答域是否有效(即ack有效)
- PSH: Push操作是否有效(跳过缓冲区)
- RST: 是否连接复位请求
- SYN: 同步序号，用于握手建立连接
- Maximum Segment Life(MSL): TCP参数，一个分段在网络中的最长生存时间
三次握手
Client为客户端，Server为服务端，握手从Client开始发起
第一次握手： 客户端发送请求报文，服务端保持监听，设置SYN=1, seq=x，客户端进入SYN_SENT状态，等待下一次握手。
第二次握手： 服务端接收到报文，进行确认。发送另一条确认报文，设置SYN=1, seq=y, ack=x+1。服务端进入SYN_RCVD状态，等待下一次握手。
第三次握手： 客户端接收到确认报文，向服务端进行回复。设置ack=y+1，至此三次握手完成。双方进入ESTABLISHED状态。
数据传输
数据传输阶段Client和Server轮流向对方发送报文
Client->Server：seq=x+1, ack=y+1 Server->Client: ack=x+2
四次挥手
完成数据传输后，客户端和服务端其中一端发出断开连接的请求,假设客户端要求中断连接。
第一次挥手： 客户端发送断连请求FIN(关闭请求)报文，设置FIN=1, seq=x+2, ack=y+1(除FIN外保持数据传输格式)。客户端进入FIN_WAIT_1状态。
第二次挥手： 服务端接收到断连请求报文，发送默认的ACK回复报文，设置ack=x+3,客户端接收到后进入FIN_WAIT_2状态。
第三次挥手： 像第一次挥手一样，服务端同样发送断连请求FIN报文，设置FIN=1, seq=y+1,服务端进入LAST_ACK状态，等待关闭。
第四次挥手： 客户端接收到FIN报文后，发送默认的ACK回复报文，设置ack=y+2。服务端接收到报文后关闭连接，客户端等待2MSL(两倍的最大分段生存期)，若未收到回复则同样关闭连接。
对于HTTPS，在三次握手之后，添加了加密和用于身份认证的SSL/TLS协议，具体流程如下：
客户端发起HTTPS连接： 发送HTTPS请求，告诉服务器需要使用HTTPS协议通信 服务器发送SSL证书： 向客户端发送证书，包含公钥、域名等信息，通过证书验证服务器身份 客户端验证证书： 检查证书颁发机构、有效期、域名是否一致 客户端生成对称密钥： 随机密钥 客户端对密钥进行加密： 通过服务器的公钥对密钥进行加密，将加密后密钥发送给服务器 服务器解密： 服务器需要通过自己的私钥（不公开）对对称密钥进行解密 **传输：**传输过程双方具有相同对称密钥，通过对称加密实现数据传输