# Ⅱ.算法
数据结构
1、二叉树有哪些类型,都有什么特点
凡是每个节点都最多有两个叉的树,都叫二叉树。
查找树和排序树是一个东西。特点是中序遍历一遍的结果是单调的。这种树建出来可以用来做二分搜索。
平衡树一般是排序树的一种,并且加点条件,就是任意一个节点的两个叉的深度差不多(比如差值的绝对值小于某个常数,或者一个不能比另一个深出去一倍之类的)。这样的树可以保证二分搜索任意元素都是O(log n)的,一般还附带带有插入或者删除某个元素也是O(log n)的的性质。
2、满二叉树和完全二叉树的异同点
满二叉树(Full Binary Tree):
要么是叶子结点(结点的度为0),要么结点同时具有左右子树(结点的度为2)。
完全二叉树(Complete Binary Tree):
每层结点都完全填满,在最后一层上如果不是满的,则只缺少右边的若干结点。\
平衡二叉树(Balanced Binary Tree):
也称为AVL树,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
3、TreeMap是用的哪种类型的二叉树
JDK中的TreeMap是一种用树实现的Map,但是,它的实现是红黑树。
4、什么是树,二叉树的有点有哪些
5、是否了解哈希,二叉树和哈希的比较(优缺点)
二叉树是为了中和链表和数组的优点,得到的插入、删除、查找都是nlogn的数据结构。
6、介绍一下红黑树
红黑树。红黑树是JDK中最重要的一个树型数据结构。TreeSet, TreeMap,以及最新的Hashtable都使用了红黑树。红黑树在各种框架,开源软件,系统中十分常见。比如在linux源代码中,就有使用红黑树做为容器管理进程的代码,再比如C++的STL中,Set, Map都是使用红黑树实现的。但是红黑树不光在教材里很少出现,即使在各类博客,教程也很少出现。我觉得这可能是因为红黑树的规则太复杂所导致的。但实际上在JDK里,红黑树的代码十分简洁。我们先看原理。
定义和性质
红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用。在STL中,很多部分(目前包括set,multiset,map, multimap)应用了红黑树。它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(logn)时间内做查找,插入和删除等操作。与二叉查找树相比,红黑树的树结点多了一个颜色属性,而每个结点不是黑色即是红色。这就是红黑树名称的由来。树的每个节点是一个五元组:color(颜色),key(数据), left(左孩子),right(右孩子)和parent(父结点)。注意哦,红黑树是一种平衡树,但是结点的结构却出奇的简单,比起传统二叉树,只多了颜色而已。
红黑树具有以下性质:
根是黑色;
所有叶子都是黑色(叶子是NIL结点);
如果一个结点是红的,则它的两个儿子都是黑的;
从任一结点到其叶子的所有简单路径都包含相同数目的黑色结点;
总结起来,最重要的就是红色结点不能有红色孩子,从根到任意叶子,经过的黑色结点数目相等。
插入数据
红黑树从根本上说还是排序二叉树,因此,红黑树的查找操作与二叉排序树的查找操作是一致的。向红黑树中插入新的结点。具体做法是,将新结点的 color 赋为红色,然后以二叉排序树的插入方法插入到红黑树中去。之所以将新插入的结点的颜色赋为红色,是因为:如果设为黑色,就会导致根到叶子的路径上有一条路上,多一个额外的黑结点,这个是很难调整的。但是设为红色结点后,可能会导致出现两个连续红色结点的冲突,那么可以通过颜色调换和树旋转来调整,这样简单多了。
删除数据
如果需要删除的结点有两个孩子,我们的做法是找到这个结点的中序后继,将后继结点中的数据拷贝至待删除结点,然后删除后继结点。而后继结点必然最多只有一个子结点,这样我们就把删除两个孩子的结点转为删除一个孩子的结点。在删除的过程中,我们只关心树是否仍然保持红黑树的性质,数据是否组织正确,而不关心这个结点是最初要删除的结点还是我们从中复制出值的那个结点。具体算法有的书分为四种、也有五种、六种的分法。
7、哈希解决冲突时的机制有哪些
线性再散列:冲突直接填下一个位置。
开放定址法 :一次不行,再来一次,直到不冲突了。
再哈希法 :同时构造多个不同的哈希函数,一个不行换第二个算。
链地址法 :所有hash地址相同的做个单链表,hashmap就有这种思想。
建立公共溢出区 :将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。
8、红黑树和平衡二叉树的区别
见题6
9、是否了解数据结构,非递归方式实现二叉树的中序遍历
10、队列和栈有什么区别,分别用在什么场景
先进先出,先进后出;JVM栈区,消息队列。11、堆排序的原理
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n / 2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1, n / 2 - 2, ... 1这些个父节点选择元素时,就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了,而第n / 2 - 1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。
12、算法题:给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。(LeetCode Easy 2)
方法一:最简单的思路是遍历数组,看数组中剩下的数里是否存在nums[j]=target-nums[i];
方法二:将数组中的数插入HashMap中,再遍历数组,看(target-nums[i])是否在HashMap中。其时间复杂度和空间复杂度都是O(n),因为Hash Table的查找时间复杂度是O(1)。
13、讲一下稳定的排序算法和不稳定的排序算法
排序算法的稳定性,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。即如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。其好处是排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n - 1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。
(3)插入排序
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
(4)快速排序
快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j,交换a[i]和a[j],重复上面的过程,直到i > j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。
(5)归并排序
归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n / 2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1, n / 2 - 2, ... 1这些个父节点选择元素时,就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了,而第n / 2 - 1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。
综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法
14、讲一下快速排序的思想
快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j,交换a[i]和a[j],重复上面的过程,直到i > j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。
快排的最坏时间复杂度(O N2) 如何避免(随机寻找pivot)如何随机(基础库的随机函数,如果rand() 是 (0, 1)区间,修改区间大小和偏移)
15、Java默认的排序算法是?
首先需要区分是 Arrays.sort() 还是 Collections.sort() (底层是调用 Arrays.sort());什么数据类型;多大的数据集(太小的数据集,复杂排序是没必要的,Java 会直接进行二分插入排序)等。
对于原始数据类型,目前使用的是所谓双轴快速排序(Dual-Pivot QuickSort),是一种改进的快速排序算法,早期版本是相对传统的快速排序,你可以阅读源码。
而对于对象数据类型,目前则是使用TimSort,思想上也是一种归并和二分插入排序 (binarySort)结合的优化排序算法。TimSort 并不是 Java 的独创,简单说它的思路是查找 数据集中已经排好序的分区(这里叫 run),然后合并这些分区来达到排序的目的。
另外,Java 8 引入了并行排序算法(直接使用 parallelSort 方法),这是为了充分利用现代多 核处理器的计算能力,底层实现基于 fork-join 框架(专栏后面会对 fork-join 进行相对详细的 介绍),当处理的数据集比较小的时候,差距不明显,甚至还表现差一点;但是,当数据集增长 到数万或百万以上时,提高就非常大了,具体还是取决于处理器和系统环境。排序算法仍然在不断改进,最近双轴快速排序实现的作者提交了一个更进一步的改进,历时多年 的研究,目前正在审核和验证阶段。根据作者的性能测试对比,相比于基于归并排序的实现,新 改进可以提高随机数据排序速度提高 10%~20%,甚至在其他特征的数据集上也有几倍的提 高,有兴趣的话你可以参考具体代码和介绍:http://mail.openjdk.java.net/pipermail/corelibs-dev/2018-January/051000.html 。
在 Java 8 之中,Java 平台支持了 Lambda 和 Stream,相应的 Java 集合框架也进行了大范围 的增强,以支持类似为集合创建相应 stream 或者 parallelStream 的方法实现,我们可以非常 方便的实现函数式代码。
算法
基本:
1、手写单链表翻转,递归和非递归。
道迭代是从前往后依次处理,直到循环到链尾;而递归恰恰相反,首先一直迭代到链尾也就是递归基判断的准则,然后再逐层返回处理到开头。总结来说,链表翻转操作的顺序对于迭代来说是从链头往链尾,而对于递归是从链尾往链头。链接
2、手写单链表成环,找环节点问题。
链接
3、手写有序旋转二维数组。
4、手写前中后层序遍历二叉树,递归和非递归。
5、手写二进制中1的个数。
6、手写栈实现队列,队列实现栈。
7、手写归并排序,堆排序,快速排序。要求知道原理,即所有排序的复杂度,稳定性,为什么稳定。
进阶:动态规划
ps:不要恐惧,不难,动态规划就是模板+套路,直接带入数即可。
8、来个算法题:一个无序数组,其中一个数字出现的次数大于其他数字之和,求这个数字 (主元素)
9、答完再来一个:一个数组,有正有负,不改变顺序的情况下,求和最大的最长子序列
10、手撕算法:一棵二叉排序树,给定一个数,找到与给定数差值最小的数
11、手撕算法:两个排序的数组A和B分别含有m和n个数,找到两个排序数组的中位数,答主用的二分,时间复杂度为O(log (m+n))。结果面试官不满意,让用归并的思想做,时间复杂度其实更高了(LeetCode第四题)
[链接](leetcode中第4题 ‘找两个有序数组的中位数’的3种方式 时间复杂度分别是O(m+n) ,O(k),O(log(m+n)) "链接")
12.翻转句子中单词的顺序
13.用栈模拟队列(或用队列模拟栈)
14.对10亿个数进行排序,限制内存为1G
15.去掉(或找出)两个数组中重复的数字
16.将一颗二叉树转换成其镜像
17.确定一个字符串中的括号是否匹配
18.给定一个开始词,一个结束词,一个字典,如何找到从开始词到结束词的最短单词接龙路径
19.如何查找两个二叉树节点的最近公共祖先
Ⅲ.其他知识
Linux
1、linux进程的内存地址空间划分
程序段(Text):程序代码在内存中的映射,存放函数体的二进制代码。
初始化过的数据(Data):在程序运行初已经对变量进行初始化的数据。
未初始化过的数据(BSS):在程序运行初未对变量进行初始化的数据。
栈 (Stack):存储局部、临时变量,函数调用时,存储函数的返回指针,用于控制函数的调用和返回。在程序块开始时自动分配内存,结束时自动释放内存,其操作方式类似于数据结构中的栈。
堆 (Heap):存储动态内存分配,需要程序员手工分配,手工释放.注意它与数据结构中的堆是两回事,分配方式类似于链表。
2、linux的常用指令有哪些
Linux常用命令(这里太基础的就不放在表中,如ls、cd、mv、cp、rm、mkdir、wget、chmod、shutdown、vi、tar、touch,这些玩过Linux的都会)
命令 | 含义 | 命令 | 含义 |
---|---|---|---|
find | 用来在指定目录下查找文件。任何位于参数之前的字符串都将被视为欲查找的目录名。 | grep | 全面搜索正则表达式并把行打印出来,是一种强大的文本搜索工具,它能使用正则表达式搜索文本,并把匹配的行打印出来。 |
awk | 统计日志信息 | sed | 按行编辑文件,常用来处理配置信息 |
netstat | 控制台命令,是一个监控TCP/IP网络非常有用的工具,可以显示路由表,实际的网络连接,以及每一个网络接口设备的状态信息 | ps | 查看进程状态 |
uptime | 主要用于获取主机运行时间和查询linux系统负载等信息。 | touch | 新建文件 |
计算机网络
1、TCP的三次握手,四次挥手,为什么是三和四?三次握手传送的是一些什么数据,最后一次握手可不可以不要?四次挥手传送的是一些什么数据,为什么服务器在响应客户端释放连接请求后要继续传送数据?
首先TCP是一种面向连接的单播协议,在发送数据前,通信双方必须在彼此间建立一条连接。所谓的“连接”,其实是客户端和服务器的内存里保存的一份关于对方的信息,如ip地址、端口号等。即建立完连接才能发数据,发送完数据后一定要关闭连接。
ACK —— 确认,使得确认号有效。
RST —— 重置连接(经常看到的reset by peer)就是此字段搞的鬼。
SYN —— 用于初如化一个连接的序列号。
FIN —— 该报文段的发送方已经结束向对方发送数据。
三次握手:SYN、SYN+ACK、ACK。分别是确认客户端发包,服务器端收包;确认服务器端发包、客户端收包(客户端自己知道了);确认服务器端发包、客户端收包(让服务器端知道)。第一、二次握手后,服务端并不知道客户端的接收能力以及自己的发送能力是否正常。而在第三次握手时,服务端收到了客户端对第二次握手作的回应。从服务端的角度,我在第二次握手时的响应数据发送出去了,客户端接收到了。所以,我的发送能力是正常的。而客户端的接收能力也是正常的。每次都是接收到数据包的一方可以得到一些结论,发送的一方其实没有任何头绪。我虽然有发包的动作,但是我怎么知道我有没有发出去,而对方有没有接收到呢?
四次挥手:FIN、DATA+ACK、FIN、ACK。分别是1.客户端发FIN,告诉服务器端结束工作。2.服务器端把自己方向的数据发送完,然后发ACK确认知道要结束了。3.服务器端发FIN告诉客户端可以结束了。4.客户端发ACK说知道了。多一次是因为服务端在LISTEN状态下,收到建立连接请求的SYN报文后,把ACK和SYN放在一个报文里发送给客户端。而关闭连接时,当收到对方的FIN报文时,仅仅表示对方不再发送数据了但是还能接收数据,己方是否现在关闭发送数据通道,需要上层应用来决定,因此,己方ACK和FIN一般都会分开发送。
经历了上面的三次握手过程,客户端和服务端都确认了自己的接收、发送能力是正常的。之后就可以正常通信了。
**PS:四次挥手中为什么TIME_WAIT状态还需要等2MSL后才能返回到CLOSED状态 ** (2点:1可靠的实现TCP全双工链接的终止:大概就是说最后一次发的ACK不一定会被对方接收到,这段等待时间对方可能重发FIN。2允许老的重复的分节在网络中消逝:简单说就是俩个IP的端口建立连接后释放,又马上建立连接,这样后面建立的连接就成了前面连接的化身,等待2MSL是为了防止这种情况出现)
2、打开百度的首页大概需要多久,期间会经过哪些步骤和节点
DNS解析 用户在浏览器中输入网址,经过一连串DNS解析(从本地缓存到系统host到服务器到根域名服务器)找到IP地址。再经过网络提供商的各个路由器最后找到服务器。
在CMD中使用tracert www.baidu.com 查看经过哪些节点到达的百度,大概12次左右。
DNS 解析:将域名解析成 IP 地址
TCP 连接:TCP 三次握手
发送 HTTP 请求
服务器处理请求并返回 HTTP 报文
浏览器解析渲染页面
断开连接:TCP 四次挥手
3、CDN是怎么实现的,为什么可以访问到离请求最近的节点
CDN是将源站内容分发至最接近用户的节点,使用户可就近取得所需内容,提高用户访问的响应速度和成功率。解决因分布、带宽、服务器性能带来的访问延迟问题,适用于站点加速、点播、直播等场景。
用户点击内容URL时,经过DNS解析并不指向原来服务器,而是指向CDN专用DNS服务器。CDN的DNS服务器将CDN的全局负载均衡设备IP地址返回用户。用户对该IP地址进行访问得到结果。区域负载均衡设备作用既是为用户选择一台合适的缓存服务器提供服务,选择的依据包括:根据用户IP地址,判断哪一台服务器距用户最近;根据用户所请求的URL中携带的内容名称,判断哪一台服务器上有用户所需内容;查询各个服务器当前的负载情况,判断哪一台服务器尚有服务能力。基于以上这些条件的综合分析之后,区域负载均衡设备会向全局负载均衡设备返回一台缓存服务器的IP地址。不行网上找,再不行再往上找,实在没有,最后会找到源服务器。
4、TCP和http的区别
HTTP(Hypertext Transfer Protocol)超文本传输协议,是在互联网上进行通信时使用的一种协议。说得更形象一点: HTTP是现代互联网中使用的公共语言。它最著名的应用是用在浏览器的服务器间的通信。HTTP属于应用层协议,底层是靠TCP进行可靠地信息传输。
HTTP在传输一段报文时,会以流的形式将报文数据的内容通过一条打开的TCP连接按序传输。TCP接到上层应用交给它的数据流之后,会按序将数据流打散成一个个的分段。再交到IP层,通过网络进行传输。另一端的接收方则相反,它们将接收到的分段按序组装好,交给上层HTTP协议进行处理。
5、http的服务器端和客户端能双向通信吗
使用HTTP协议的WEB服务器不能主动推送信息给客户浏览器未来的方向是websocket协议, 目前主流浏览器的最新版都已支持该协议, 但还有大量用户使用不支持该协议的旧版浏览器, 为了兼容业界普遍使用轮询的方法, 做法就是JS每过n秒向服务器发送一个询问请求以实现伪双向.
6、什么是TCP与UDP,各有什么优缺点,各自适用于哪些场景
TCP优点:
TCP面向连接、提供可靠的服务;UDP是无连接的,即发送数据之前不需要建立连接、尽最大努力交付,即不保证可靠交付
TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的。UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)
UDP优点:
TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信
TCP首部开销20字节;UDP的首部开销小,只有8个字节
TCP 适合金融等大多数领域,UDP适合游戏和娱乐场景
7、TCP/IP结构有几层
TCP/IP是一个网络传输框架,是一套协议族,其中最为核心的为TCP、IP协议。它将网络从低到高分为物理层、链路层、网络层、传输层、应用层(ISO/OSI把应用层分为了会话层、表示层、应用层,下面四层不变)。
程序发送信息时,在应用层按规定的协议(如HTTP、FTP、STMP)打包数据,随后在传输层上加上双方的端口号,在网络层加上双方的IP地址,在链路层上加上双方的MAC地址,并将数据拆分成数据帧,经过多个路由器和网管后,到达目标机器,反向操作,得到信息。以上每一层都有不同的物理装置按不同协议进行转发,拆分、组装,链路层有IEEE、PPP协议,网络层有IP、ARP协议,传输层有TCP、UDP协议。
8、http请求流程
域名解析 (经过DNS解析)---> 与服务器建立连接 ---> 发起HTTP请求 ---> (经过TCP协议)服务器响应HTTP请求(经过HTTP协议),浏览器得到html代码 ---> 浏览器解析html代码,并请求html代码中的资源(如js、css、图片) ---> 浏览器对页面进行渲染呈现给用户
用户在浏览器中输入网址,经过一连串DNS解析(从本地缓存到系统host到服务器到根域名服务器)找到IP地址。再经过网络提供商的各个路由器最后找到服务器。HTTP请求服务器,得到回复在浏览器打开。
9、HTTP和HTTPS的异同
HTTP over SSL。简单的说就是在HTTP协议上加上SSL协议的加密能力。由于对称算法如DES的秘钥被截则信息安全就无法保证了,于是产生了非对称算法如RSA,即分公钥、密钥。一方用公钥加密,一方用本地的私钥解密即可。当然他的问题的加密解密时间过长,比较适合对少量数据进行处理。
具体过程是先用HTTPS加密的握手建立一个加密的通道,然后用对称加密传输。CA作为最具HTTP方面公信力的组织,颁发HTTPS数字证书给各个网站来进行HTTPS服务。
10、解释一下长连接
**短连接连接->传输数据->关闭连接 **
比如HTTP是无状态的的短链接,浏览器和服务器每进行一次HTTP操作,就建立一次连接,但任务结束就中断连接。 具体就是 浏览器client发起并建立TCP连接 -> client发送HttpRequest报文 -> server接收到报文->server handle并发送HttpResponse报文给前端,发送完毕之后立即调用socket.close方法->client接收response报文->client最终会收到server端断开TCP连接的信号->client 端断开TCP连接,具体就是调用close方法。也可以这样说:短连接是指SOCKET连接后,发送接收完数据后马上断开连接。 因为连接后接收了数据就断开了,所以每次数据接受处理不会有联系。 这也是HTTP协议无状态的原因之一。
长连接连接->传输数据->保持连接 -> 传输数据-> ...........->直到一方关闭连接,多是客户端关闭连接。
长连接指建立SOCKET连接后不管是否使用都保持连接,但安全性较差。
http 1.0一般就指短连接,smtp,pop3,telnet这种就可以认为是长连接。一般的网络游戏应用都是长连接
11、分布式服务器会出现哪些问题
服务不好拆分,业务的原子性操作跨服务,两个服务分开;
如何保证各个服务器的负载均衡;
如何保证数据库的性能和高可用。
12、介绍网络编程
网络编程是指编写运行在多个设备(计算机)的程序,这些设备都通过网络连接起来。java.net 包中 J2SE 的 API 包含有类和接口,它们提供低层次的通信细节。你可以直接使用这些类和接口,来专注于解决问题,而不用关注通信细节。java.net 包中提供了两种常见的网络协议的支持:TCP、UDP。
如java.net.Socket 类代表一个套接字,并且 java.net.ServerSocket 类为服务器程序提供了一种来监听客户端,并与他们建立连接的机制。
13、Tcp怎么保证可靠传输(中间穿插了好多小问题)
三次握手,建立通道。连接建立后,客户端和服务器就开始进行安全可靠的数据传输了。
其他的还有差错检验、快速重传、接受缓存(滑动窗口)。
14、Tcp的拥塞控制
TCP的拥塞控制由4个核心的算法组成:慢启动(从1开始指数增大)、拥塞避免(增大到阈值线性增大)、快速重传(收到3个重复确认立即重传)和快速恢复(快速重传后,把门限/2,并开始拥塞避免)。
拥塞控制,在发送方维持着一个拥塞窗口cwmd(congestion window)的状态量。拥塞窗口的大小取决于网络的拥塞程度,并且动态的变化。发送方让自己的发送窗口等于拥塞窗口,另外考虑到接收方的接收能力,发送窗口可能小于拥塞窗口。
15.TCP的time_wait了解吗?说说
16.TCP的close_wait了解吗?close_wait占据了太多的接口应该怎么办?
17.为什么TCP关闭链接时需要TIME_WAIT状态,为什么要等2MSL?
18.HTTP2和HTTP的区别有哪些?
http状态码
304状态码前前后后的具体流程
Git
git是一种分布式代码管理工具,git通过树的形式记录文件的更改历史。Git无论在本地还是远端都可以不用自己搭建服务器;每次commit之后会产生一个号,由此可以利用快照签名回溯历史版本;由于Git是分布式管理的版本控制,故我们在git上,可以很多个用户维护一个repository。
常用的Git操作有
操作 | 含义 | 操作 | 含义 |
---|---|---|---|
add | 将当前工作目录中更改或者新增的文件加入到Git的索引中,加入到Git的索引中就表示记入了版本历史中,这也是提交之前所需要执行的一步。 | push | 将本地commit的代码更新到远程版本库中,例如 “git push origin”就会将本地的代码更新到名为orgin的远程版本库中 |
fetch | 从服务器的仓库中下载代码。(与服务器交互,从服务器上下载最新代码) | mv | 重命名一个文件、目录或者链接。 |
merge | 把服务器上下载下来的代码和本地代码合并。或者进行分支合并。 | tag | 创建、列出、删除或者验证一个标签对象(使用GPG签名的)。 |
chekout | git checkout feature 从当前分支hotfix 切换到分支 feature | rebase | git rebase master 将feature 分支衍合(变基)到 master 分支(不考虑文件冲突) |
加密解密
1、加密解密了解么?几种算法,讲一下你了解的
对称加密:DES加密算法(仅对密钥进行保密,但是由于算法公开。破译DES加密算法实际上就是搜索密钥的编码。对于56位长度的密钥来说,如果用穷举法来进行搜索的话,其运算次数为256。)
非对称加密:RSA加密算法(RSA是第一个能同时用于加密和数宇签名的算法,它能够抵抗到目前为止已知的所有密码攻击,已被ISO推荐为公钥数据加密标准。)
Base64加密算法Base64加密算法是网络上最常见的用于传输8bit字节代码的编码方式之一,Base64编码可用于在HTTP环境下传递较长的标识信息。
MD5加密算法,MD5用的是哈希函数,它的典型应用是对一段信息产生信息摘要,以防止被篡改。MD5的典型应用是对一段Message产生fingerprin指纹,以防止被“篡改”。如果再有—个第三方的认证机构,用MD5还可以防止文件作者的“抵赖”,这就是所谓的数字签名应用。
Comments | NOTHING