记录下我针对面试的学习

算法/编程题

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 操作系统支持的主要进程间通信的通信机制:

进程间通信-1

进程间通信(IPC)介绍

[]进程调度

[]进程的内存分布

代码段全局常量(const)、字符串常量、函数以及编译时可决定的某些东西
数据段存储初始化的全局变量 和 初始化的静态变量(全局和局部)
BSS段存储未初始化的全局变量 和 未初始化的静态变量(全局和局部)
动态分配的区域(malloc、new等)
l临时声明的局部变量(初始化以及未初始化的,但不包含静态变量),局部常量(const)
命令行参数和环境变量顾名思义

进程调度

  • 先来先服务 (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区别

TCPUDP
传输提供面向连接的、可靠地数据流传输提供的是非面向连接的、不可靠的数据流传输
传输单位TCP报文段用户数据报
安全性TCP注重数据安全性UDP数据传输快,因为不需要链接等待,少了许多操作,但是起安全性却一般
协议FTP:定义了文件传输协议,使用21端口;DNS: 用于域名解析服务,将域名地址转换成IP地址.DNS用的是53号端口.
协议Telnet: 一种用于远程登录的端口,使用23端口,用户可以以自己的身份远程连接到计算机上,可提供基于DOS模式下的通信服务SNMP: 简单网络管理协议,使用161端口,是用来管理网络十倍的.由于网络设备很多,无连接的服务就体现出其优势.
协议SMTP: 邮件传送协议,用于发送邮件.服务端开放的是25号端口TFTP(Trival File Transfer Protocal): 简单文件传输协议,该协议在熟知端口69上使用UDP服务
协议POP3: 它是和SMTP对应,POP3用于接收邮件.POP3协议所用的是110端口
协议HTTP: 是从Web服务器传输超文本到本地浏览器的传送协议

详细介绍,戳<<<–

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

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

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

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

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

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开头, 第一个字节范围1~127(1.0.0.0~127.255.255.255);
B类地址: 以10开头, 第一个字节范围128~191(128.0.0.0~191.255.255.255);
C类地址: 以110开头, 第一个字节范围192~223(192.0.0.0~223.255.255.255);
D类地址: 以1110开头, 第一个字节范围224~239(224.0.0.0~239.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进行封装数据包, 输入到网络层.
    1. 在客户端的传输层,把HTTP回话请求分成报文段,添加源和目的端口, 如服务器使用80端口监听客户端的请求, 客户端有系统随机选择一个端口如5000, 与服务器进行交换,服务器吧相应的请求返回给客户端的5000端口. 然后使用IP层的IP地址查找目的端.
    1. 客户端的网络层不用关心应用层或者传输层的东西, 主要做到的是通过查找路由表确定如何到达服务器,期间可能经过多个路由器,这些都是有路由器来完成的工作, 我不做过多的描述, 无非就是通过查找路由表决定通过哪个路径到达服务器.
    1. 客户端的链路层, 包通过链路层发送到路由器, 通过邻居协议查找给定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的区别和用法

Synchronze(隐式锁)Lock(显示锁)
在需要同步的对象中加入此控制,synchronize可以加在方法上,也可以加在特定代码块中,括号中表示需要所得对象需要显示指定起始位置和终止位置.一般使用ReentrantLock类作为锁,多个线程中必须要使用一个ReentrantLock类作为对象才能保证锁的生效.且在加锁和解锁处需要通过lock()和unlock()显示指出.所以一般会在finally块中写unlock()以防死锁
托管给JVM执行的java写的控制锁代码
采用的的CPU的悲观锁机制,即线程获得的是独占锁.独占锁意味着其他线程只能依靠阻塞来等待线程释放锁乐观锁方式,每次不加锁而是假设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止.乐观锁实现的机制就是CAS操作(Compare and Swap)

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

乐观锁,悲观锁

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

Linux

进程的内存分布

名称内容
代码段可执行代码
数据段已初始化全局变量,已初始化全局静态变量,局部静态变量,常量数据
BSS段未初始化全局变量,未初始化全局静态变量
局部变量,函数参数
动态内存分配

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

答:
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更偏重于进程顺序写入,虽然支持集群,也仅限于主-从模式。

比较指标MongoDB(v2.4.9)Redis(v2.4.17)比较说明
实现语言c++c/c++-
协议BSON,自定义二进制类telnet-
性能依赖内存,TPS{(transaction per second)代表每秒执行的事务数量}较高依赖内存,TPS非常高Redis优于MongoDB
可操作性丰富的数据表达,索引;最类似于关系型数据库,支持丰富的查询语句数据丰富,较少的IOMongoDB优于Redis
内存及存储适合大数据量存储,依赖系统虚拟内存,采用镜像文件存储;内存占用率比较高,官方建议独立部署在64位系统Redis2.0后支持虚拟内存特性(VM) 突破物理内存限制;数据可以设置时效性,类似于memcache不同的应用场景,各有千秋
可用性支持master-slave,replicatset(内部采用paxos选举算法,自动故障恢复),auto sharding机制,对客户端屏蔽了故障转移和切片机制依赖客户端来实现分布式读写;主从复制时,每次从节点重新连接主节点都要依赖整个快照,无增量复制;不支持auto sharding,需要依赖程序设定一致性hash机制MongoDB优于Redis;单点问题上,MongoDB应用简单,相对用户透明,Redis比较复杂,需要客户端主动解决.(MongoDB一般使用replicasets和sharding相结合,replicasets侧重高可用性以及高可靠,sharding侧重性能,水平扩展)
可靠性从1.8版本后,采用binlog方式(类似Mysql) 支持持久化依赖快照进行持久化;AOF增强可靠性;增强性的同时,影响访问性能-
一致性不支持事务,靠客户端保证支持事务,比较脆,仅能保证事务中的操作按顺序执行Redis优于MongoDB
数据分析内置数据分析功能(mapreduce)不支持MongoDB优于Redis
应用场景海量数据的访问效率提升较小数据量的性能和运算MongoDB优于Redis

数据库

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

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

并发事务引起的问题

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

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

设计题/系统题

.

[]设计一个ID分配器

.

技术无关

.

能抗住压力么

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

有女朋友么

答: 没有,一心向学,不找女朋友浪费时间.(TM是找不到好不2333)

你有什么问题吗

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