computer network

 

Basics


Q: What are the architecture of five layer protocol ? What are the protocols at each level ?

https://blog.csdn.net/cainv89/article/details/46885197
<https://blog.csdn.net/cainv89/article/details/46885197>

*
application layer
<https://www.baidu.com/s?wd=%E5%BA%94%E7%94%A8%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
, application layer
<https://www.baidu.com/s?wd=%E5%BA%94%E7%94%A8%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
Determine the nature of communication between processes to meet the needs of users . application layer
<https://www.baidu.com/s?wd=%E5%BA%94%E7%94%A8%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
Not only to provide the information exchange needed by the application process
<https://www.baidu.com/s?wd=%E4%BF%A1%E6%81%AF%E4%BA%A4%E6%8D%A2&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
And remote operation , It also acts as a user agent for interacting application processes
<https://www.baidu.com/s?wd=%E7%94%A8%E6%88%B7%E4%BB%A3%E7%90%86&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
(user agent);

*
Transport layer
<https://www.baidu.com/s?wd=%E8%BF%90%E8%BE%93%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
The task is responsible for the communication between two processes in the host ;

*
network layer
<https://www.baidu.com/s?wd=%E7%BD%91%E7%BB%9C%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
network layer
<https://www.baidu.com/s?wd=%E7%BD%91%E7%BB%9C%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
It is responsible for the packet to choose the appropriate route ;

*
data link layer
<https://www.baidu.com/s?wd=%E6%95%B0%E6%8D%AE%E9%93%BE%E8%B7%AF%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
data link layer
<https://www.baidu.com/s?wd=%E6%95%B0%E6%8D%AE%E9%93%BE%E8%B7%AF%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
Task of : Will be on the network layer
<https://www.baidu.com/s?wd=%E7%BD%91%E7%BB%9C%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
The submitted datagrams are assembled into frames (frame), The link between two adjacent nodes realizes frame transmission ;

*
Physical layer physical layer tasks : Transparently transmit bits
<https://www.baidu.com/s?wd=%E6%AF%94%E7%89%B9&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
flow . 


Q: Why MAC And the address IP address ?

http://blog.sciencenet.cn/blog-411071-1037673.html
<http://blog.sciencenet.cn/blog-411071-1037673.html>

Basically, one idea is that one is a physical address , One is a logical address .

Suppose two points are in a network . under these circumstances , It only needs MAC The address will do . For example, through the switch to form a network of multiple computers .


  however , If two points are not in a network . That's what you need IP Address . because IP The address has two parts , One is the network address , One is the host address . therefore , Through each other's IP address , It can judge whether the other party and the local machine are in the same network . If you're in a network , As mentioned above , You just need to know about each other's MAC Address can communicate .


If not in a network , The network layer of the local machine thinks that the data should be sent to the gateway . The reason is obvious , If not in a network , You have to send the data out of the network first . How to send network , To the gateway, of course , Because the gateway is the gatekeeper of the network . To send data to the gateway , Also need to know the gateway's MAC address , How to know the gateway MAC What about the address ? This involves ARP agreement .

There's one in the computer cache ARP surface , The table has two main columns : One column is IP address , The other column is MAC address . This watch is not born , It is with the network card to receive all kinds of communication data in the network , Keep learning .


And then again , If ARP There are gateways in the table IP Address corresponding MAC address , Then the problem is converted to data transmission within the network , It has been made clear . If ARP There are no gateways in the table IP Address corresponding MAC address , Start ARP agreement , Broadcast to the network , Ask about the IP Address MAC address . The result of broadcast inquiry is that the gateway receives the broadcast , Discovery is asking yourself MAC address , So I replied to the inquirer's own MAC address . Then the data is sent to the gateway , It is also converted to intra network data transmission .

 

TCP


Q:TCP and UDP The difference between ?

https://blog.csdn.net/xiaobangkuaipao/article/details/76793702
<https://blog.csdn.net/xiaobangkuaipao/article/details/76793702>

1,TCP Connection oriented ( If you make a call, you should dial to establish a connection );UDP It's disconnected , That is, there is no need to establish a connection before sending data

2,TCP Provide reliable service . in other words , adopt TCP Data transferred by connection , No mistakes , No loss , No repetition , And arrive in order ;UDP Best effort delivery , That is, reliable delivery is not guaranteed

Tcp Pass the check sum , Retransmission control , Serial number identification , sliding window , Reliable transmission of acknowledgement response . Such as the retransmission control in case of packet loss , It can also control the order of the out of order subcontracting .

3,UDP It has good real-time performance , Work efficiency ratio TCP high , It is suitable for high-speed transmission and real-time communication or broadcast communication .

4. Every one of them TCP Connections can only be point-to-point ;UDP Support one-on-one , One to many , Many to one and many to many interactive communication

5,TCP It requires more system resources ,UDP It requires less system resources .


Q: What are congestion control and flow control , The difference between the two ?

https://blog.csdn.net/ailunlee/article/details/53716367
<https://blog.csdn.net/ailunlee/article/details/53716367>


Flow control is end-to-end control , for example A Through the Internet to B Send data ,A Sent too fast B Can't receive it (B The buffer window is too small or processing is too slow ), At this time, the control is flow control , The principle is to change the size of the sliding window . 

Congestion control is A And B The network between them is blocked, resulting in slow transmission or packet loss , It's too late to transmit . Prevent too much data from being injected into the network , In this way, the router or link in the network will not be overloaded . Congestion control is a global process , All hosts are involved , Router , And all the factors associated with reducing network performance .


Q: chat TCP Why shake hands three times ? Why wave four times ?

https://blog.csdn.net/zhaobudaofangxia/article/details/55260259
<https://blog.csdn.net/zhaobudaofangxia/article/details/55260259>

https://blog.csdn.net/qq_33982721/article/details/78493967
<https://blog.csdn.net/qq_33982721/article/details/78493967>

Three handshakes :

* for the first time .A Follow B say , I'm going to make a connection .
* The second time .B Follow A say ,OK, Then I'll make a connection, too .
* third time .A Follow B say , Um. , I got it! .
Four waves :

* for the first time .A Follow B say , I'm going to disconnect .
* The second time .B Follow A say , well , I got it! , I don't receive your messages anymore .
* third time .B Follow A say , My message to you is over , You can close the connection .
* The fourth time .A Follow B say , well , I closed the connection .
 

Q: For video playback TCP still UDP? Why? ?

TCP and UDP It's a trade-off between quality and real-time .
Take video sites , You can cushion it 20s Play it again , It won't make any difference , But if there are mosaics in the picture, it is definitely not good , So use TCP.
And for video chat , If the buffer 5s, I believe that the whole chat can not be happy , At this time, some loss of image quality can also be accepted , So use UDP.

 

HTTP

 

Q:HTTP Message format ?

https://blog.csdn.net/holmofy/article/details/68492045
<https://blog.csdn.net/holmofy/article/details/68492045>


Q: What response status codes do you know ?

https://blog.csdn.net/oops_qu/article/details/75675702
<https://blog.csdn.net/oops_qu/article/details/75675702>

http Status return code 1xx( Interim response ): A status code that represents a temporary response and requires the requester to continue the operation .

http Status return code 2xx ( success ): Status code indicating that the request was successfully processed .

http Status return code 3xx ( redirect ): Indicates that you want to complete the request , Further action is required . usually , These status codes are used for redirection .

http Status return code 4xx( Request error ): These status codes indicate that the request may have failed , Hinders server processing .

http Status return code 5xx( Server error ): These status codes indicate that the server encountered an internal error while trying to process the request . These errors can be errors on the server itself , It's not a request error .


Q:get and post The difference between ?

https://www.cnblogs.com/huaxingtianxia/p/5895236.html
<https://www.cnblogs.com/huaxingtianxia/p/5895236.html>

* GET It's harmless when the browser goes back , and POST The request will be submitted again .
* GET Produced URL Address can be Bookmark, and POST may not .
* GET The request will be initiated by the browser cache, and POST can't , Unless manually set .
* GET Requests can only be made url code , and POST Support a variety of coding methods .
* GET The request parameters are fully preserved in the browser history , and POST Parameters in are not preserved .
* GET Request in URL The parameters transmitted in are limited in length , and POST Nothing .
* The data type of the parameter ,GET admit of only interpretation ASCII character , and POST There are no restrictions .
* GET than POST It's not safe , Because the parameters are directly exposed to the URL upper , So it can't be used to transmit sensitive information .
* GET Parameters pass URL transmit ,POST Put in Request body in .
GET and POST There is another big difference

In short :

GET Produce a TCP data packet ;POST There are two TCP data packet .

Long said :

about GET How to request , The browser will http header and data Send it out , Server response 200( Return data );

And for POST, Browser sends first header, Server response 100 continue, Browser resend data, Server response 200 ok( Return data ).


in other words ,GET It only took a car run to get the goods delivered , and POST I have to run twice , The first trip , Go and say hello to the server first “ hi , I'll send a lot of goods later , You open the door to meet me ”, And then we'll send it back .


because POST It takes two steps , It takes a little more time , seem GET than POST More effective . therefore Yahoo Recommended by the team GET replace POST To optimize website performance . But it's a pit ! Be careful to jump in . Why? ?

1. GET And POST Each has its own semantics , You can't mix them up .

2.
According to research , In a good network environment , The time difference between sending a packet once and sending a packet twice can be ignored . But in the case of poor network environment , Twice TCP On the verification of packet integrity , There are very big advantages .

3. Not all browsers will be in POST Send packets twice in ,Firefox Just send it once .


Q:Http1.0,Http1.1,Http2.0 The difference between ?

https://blog.csdn.net/linsongbin1/article/details/54980801/
<https://blog.csdn.net/linsongbin1/article/details/54980801/>


Q:HTTP and TCP The difference between ?


   actually , Transport layer TCP It's based on the network layer IP Agreed , And the application layer HTTP The protocol is based on the transport layer TCP Agreed , and Socket It's not an agreement in itself , It just provides a target TCP perhaps UDP Programming interface .


Q:HTTP and HTTPS The difference between ?

https://www.cnblogs.com/wqhwe/p/5407468.html
<https://www.cnblogs.com/wqhwe/p/5407468.html>


HTTP: It is the most widely used network protocol on the Internet , Is a client-side and server-side request and response standard (TCP), Used from WWW Transmission protocol of hypertext from server to local browser , It can make browsers more efficient , Reduce network transmission .

HTTPS: It's about safety HTTP passageway , In short, it is HTTP Security version of , Namely HTTP Add below SSL layer ,HTTPS Based on SSL, So the details of encryption need to be SSL.

HTTPS There are two main functions of the agreement : One is to establish an information security channel , To ensure the security of data transmission ; The other is to confirm the authenticity of the website .


Q:HTTP and Socket The difference between ?

https://blog.csdn.net/w369033345/article/details/72779553
<https://blog.csdn.net/w369033345/article/details/72779553>

https://blog.csdn.net/w369033345/article/details/72779553
<https://blog.csdn.net/w369033345/article/details/72779553>

http Short connection :
All requests sent by the client need to be sent back by the server . After the end of the request , Active release link , So it's a short connection . The usual practice is , No data is required , Also keep sending to the server at regular intervals " Stay connected " Request for . This ensures that the client is on the server side " go online " state .

Socket Is a long connection : under normal conditions Socket Connection is TCP connect , therefore Socket
Once the connection is established , Both sides of communication began to send data content to each other , Until both sides disconnect . in application , Because there are too many network nodes , During transmission , Will be disconnected by the node , So we need to poll the high-speed network , The node is active .


Q: Type in the address bar http://www.baidu.com What will happen ?


When input www.baidu.com Time , The computer will ask DNS The server , Domain name conversion , Get the server IP address , Request to server at the same time , The server responds to the request , The client browser initiates a HTTP Conversation to IP address , And then through the tcp To encapsulate the data package , Input to network layer

 

Q: Long link and short link ?

https://www.cnblogs.com/gotodsp/p/6366163.html
<https://www.cnblogs.com/gotodsp/p/6366163.html>

 

operating system

 

Q: The difference between process and thread in operating system ?

A process is an entity of program execution , Thread is CPU The minimum unit of scheduling




Q: Generation and avoidance of deadlock ?

https://www.cnblogs.com/fangrong/p/5271724.html
<https://www.cnblogs.com/fangrong/p/5271724.html>

Four necessary conditions of deadlock :
(1) mutual exclusion (Mutual exclusion): Resources cannot be shared , Can only be used by one process .
(2) Request and hold conditions (Hold and wait): Processes that have already acquired resources can request new resources again .
(3) Non deprivation conditions (No pre-emption): Allocated resources cannot be forcibly deprived from the corresponding process .
(4) Cyclic waiting condition (Circular wait): Several processes in the system form a loop , Each process in the loop is waiting for resources occupied by neighboring processes .

  Deadlock avoidance (deadlock
avoidence) It is to avoid deadlock during system operation . This requires that every time a resource is requested , The system should judge whether to approve the application according to a certain algorithm , So that in the future period of time, the system will not appear deadlock . The most famous algorithm in this area Dijkstra[1965] Proposed banker (banker) algorithm .

 

database

 

Q: Do you understand the transactions in the database ? Four characteristics of transaction ?


Database transaction is the logical unit of work in database operation , A series of operations performed by a single logical unit of work , Either it's all done , Either not . For example, bank withdrawals are divided into 2 Steps (1) Reduction of passbook (2) Cash withdrawal ,2 Steps must be completed at the same time or none .

Four characteristics of database transaction (ACID):

(1) Atomicity (Atomicity):
      The atomicity of a transaction refers to , The program contained in the transaction serves as the logical unit of work for the database , It does all the data modification operations , Or not at all . This property is called atomicity .
(2) uniformity (Consistency) :
   
Transaction consistency means that the database must be in a consistent state before and after the execution of a transaction . This feature is called transactional consistency . If the state of the database satisfies all integrity constraints , Say that the database is consistent .
(3) Separation (Isolation):
 
  Separation means that concurrent transactions are isolated from each other . That is to say, the operation inside a transaction and the data in operation must be blocked , Not seen by other transactions attempting to modify . If there is no control over the concurrent cross execution of transactions , The execution of multiple concurrent transactions that manipulate the same shared object may cause an exception .
(4) persistence (Durability):
 
  Persistence means when a system or medium fails , True 保已提交事务的更新不能丢失.即一旦一个事务提交,DBMS保证它对数据库中数据的改变应该是永久性的,即对已提交事务的更新能恢复.持久性通过数据库备份和恢复来保证.


Q:如何理解数据库的范式?

https://blog.csdn.net/zymx14/article/details/69789326
<https://blog.csdn.net/zymx14/article/details/69789326>

第一范式(1NF):确保每一列的原子性

如果每一列都是不可再分的最小数据单元,则满足第一范式.

第二范式:非键字段必须依赖于键字段

如果一个关系满足1NF,并且除了主键以外的其它列,都依赖与该主键,则满足二范式(2NF),第二范式要求每个表只描述一件事.

第三范式:在1NF基础上,除了主键以外的其它列都不传递依赖于主键列,或者说: 任何非主属性不依赖于其它非主属性

(在2NF基础上消除传递依赖)

 

数据结构与算法

 

Q:怎么理解数据结构?

带有机构的数据元素的集合


Q:什么是斐波那契数列?

斐波那契数列(Fibonacci sequence),又称黄金分割
<https://baike.baidu.com/item/%E9%BB%84%E9%87%91%E5%88%86%E5%89%B2/115896>数列,因
数学家 <https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E5%AE%B6/1210991>
列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列
<https://baike.baidu.com/item/%E5%85%94%E5%AD%90%E6%95%B0%E5%88%97/6849441>
”,指的是这样一个数列:1,1,2,3,5,8,13,21,34,……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1,
F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)


Q:迭代和递归的特点,并比较优缺点

https://blog.csdn.net/laoyang360/article/details/7855860
<https://blog.csdn.net/laoyang360/article/details/7855860>


 

定义

优点

缺点


递归

程序调用自身的编程技巧称为递归

1)大问题化为小问题,可以极大的减少代码量;

2)用有限的语句来定义对象的无限集合.;

3)代码更简洁清晰,可读性更好

1)递归调用函数,浪费空间;

2)递归太深容易造成堆栈的溢出;

 


迭代

利用变量的原值推算出变量的一个新值,迭代就是A不停的调用B.

1)迭代效率高,运行时间只因循环次数增加而增加;

2)没什么额外开销,空间上也没有什么增加,

1) 不容易理解;

2) 代码不如递归简洁;

3) 编写复杂问题时困难.


二者关系

1) 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换.

2) 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出./*相对*/


Q:了解哪些查找算法,时间复杂度都是多少?

https://blog.csdn.net/qq_23217629/article/details/52517741
<https://blog.csdn.net/qq_23217629/article/details/52517741>


查找

平均时间复杂度

查找条件

算法描述


顺序查找

O(n)

无序或有序队列

按顺序比较每个元素,直到找到关键字为止


二分查找(折半查找)

O(logn)

有序数组


查找过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. 如果在某一步骤数组为空,则代表找不到.


二叉排序树查找

O(logn)

二叉排序树

在二叉查找树b中查找x的过程为:

1. 若b是空树,则搜索失败

2. 若x等于b的根节点的数据域之值,则查找成功;

3. 若x小于b的根节点的数据域之值,则搜索左子树

4. 查找右子树.


哈希表法(散列表)

O(1)

先创建哈希表(散列表)

根据键值方式(Key value)进行查找,通过散列函数,定位数据元素.


分块查找

O(logn)

无序或有序队列

将n个数据元素"按块有序"划分为m块(m ≤ n).


每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,…….然后使用二分查找及顺序查找.


Q:了解哪些排序算法,并比较一下,以及适用场景

https://blog.csdn.net/mountain_hua/article/details/81107024
<https://blog.csdn.net/mountain_hua/article/details/81107024>


排序法

最差时间分析

平均时间复杂度

稳定度

空间复杂度


冒泡排序

O(n2)

O(n2)

稳定

O(1)


插入排序

O(n2)

O(n2)

稳定

O(1)


选择排序

O(n2)

O(n2)

稳定

O(1)


二叉树排序

O(n2)

O(n*log2n)

不一顶

O(n)


快速排序

O(n2)

O(n*log2n)

不稳定

O(log2n)~O(n)


堆排序

O(n*log2n)

O(n*log2n)

不稳定

O(1)


希尔排序

O

O

不稳定

O(1)

 


Q:快排的基本思路是什么?最差的时间复杂度是多少?如何优化?


(升序)以某个记录的关键字为划分元,将整个数据分为两组,左边的数据小于等于划分元,右边的数据大于等于划分元.对左右两组数据,再各自选择一个划分元,将两组数据划分为更小的序列,这样一直进行下去,直到整个序列有序.
public static void quickSort(int[] array, int left, int right) { if (left <
right) { int pivot = array[left]; int low = left; int high = right; while (low
< high) { while (low < high && array[high] >= pivot) { high--; } array[low] =
array[high]; while (low < high && array[low] <= pivot) { low++; } array[high] =
array[low]; } array[low] = pivot; quickSort(array, left, low - 1);
quickSort(array, low + 1, right); } }
最差时间复杂度即是但数据有序的时候,这时候退化为冒泡排序,时间复杂度为O(n2)

优化:https://blog.csdn.net/sinat_28676875/article/details/69053449
<https://blog.csdn.net/sinat_28676875/article/details/69053449>

 

Q:冒泡排序如何优化?
public static void bubbleSort(int[] array) { int len = array.length; boolean
flag = true; while (flag) { flag = false; for (int i = 0; i < len - 1; i++) {
if (array[i] > array[i + 1]) { int temp = array[i + 1]; array[i + 1] =
array[j]; array[i] = temp; flag = true; } } len--; } }

存在这样一一种情况,冒泡过程中,后面的若干记录没有发生交换,这时候再继续进行冒泡就显得多此一举了,那么我们只需要记录没有发生交换的位置,对这个位置之后的数据不进行冒泡处理,只对这个位置之前的数据进行冒泡处理,提升算法的效率.

优化后的冒泡排序:
void Bubble_Modified_Sort(int R[],int n){ int i=n; int j; int
LastExchangeIndex; while(i>1){ LastExchangeIndex=1; for(j=0,j<i,j++){
if(R[j]>R[j+1]){ int temp=R[j+1]; R[j+1]=R[j]; R[j]=temp; LastExchangeIndex=j;
} //end if } //end for i=LastExchangeIndex; } //end while }

Q:AVL树插入或删除一个节点的过程是怎样的?

https://blog.csdn.net/Ivan_zgj/article/details/51495926
<https://blog.csdn.net/Ivan_zgj/article/details/51495926>

https://blog.csdn.net/friendbkf/article/details/50160141
<https://blog.csdn.net/friendbkf/article/details/50160141>


Q:什么是红黑树?

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机
<https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA>科学中用到的一种数据结构
<https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450>
,典型的用途是实现关联数组
<https://baike.baidu.com/item/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84/3317025>.

它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees).后来,在1978年被 Leo
J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”.

红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能.

它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目.

https://blog.csdn.net/eric491179912/article/details/6179908
<https://blog.csdn.net/eric491179912/article/details/6179908>

Q:100盏灯问题
Q:老鼠和毒药问题,加个条件,必须要求第二天出结果
Q:海量数据问题
Q:(手写算法)二分查找
Q:(手写算法)反转链表
Q:(手写算法)用两个栈实现队列
Q:(手写算法)多线程轮流打印问题
Q:(手写算法)如何判断一个链有环/两条链交叉
Q:(手写算法)快速从一组无序数中找到第k大的数/前k个大的数
Q:(手写算法)最长(不)重复子串