# awesome_interview **Repository Path**: fengdingwen/awesome_interview ## Basic Information - **Project Name**: awesome_interview - **Description**: Key points in interviews - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-09-19 - **Last Updated**: 2021-09-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README - 自我介绍 - 项目介绍 - 项目中碰到过什么问题？ - 北洋荣科的项目中： - 项目整体的流程： - 用户需求混乱，不明确：小组分工，将整个系统按照不同的目标划分成不同的子模块，再根据每个模块分别细化其功能，并列出需求说明；而后根据需求说明可以初步画出实体关系图。 - 数据库是否要使用外键进行约束：刚开始数据库设计和编码时按照学习过程中的习惯性使用外键来进行约束，导致大量表格之间存在着拓扑排序的关系；同时也导致服务器端在进行插入、更新、删除等操作时需要进行额外的数据检验工作，增加了服务器的负担；*解决方法：* 与领导及公司工程师进行协商后，确定不采用外键的方案，改为程序手动进行检查；可将大部分检查工作放在客户端进行，同时涉及到依赖关系的部分数据则采用触发器进行约束。 - 三维人脸表情合成研究 - 语言基础 - C/C++ - 指针和引用的区别 - 指针：指针是一个变量，存储的是某个内存块的地址，如int *p = \&a里面p存储的就是a这个变量的地址； - 引用：给某个变量取一个别名；必须使用需要初始化的对象or变量来进行初始化，一旦初始化后不可修改；常用于形式参数。 ``` int a = 1; int &b = a; ``` b是一个引用变量，底层保存的是a的指针，当我们使用b的时候自动解引用，可以理解为使用b的地方被替代为*（&a）,所以引用变量一旦经过初始胡我们就无法访问到b实际的内存，因而也无法改变b的指向（引用）。 - std::move()移动语义操作； - unique_ptr类型的智能指针不能直接进行赋值操作，应当使用std::move()来进行移动赋值： ``` unique_ptr ptest(new Test("123")); unique_ptr ptest2(new Test("456")); ptest2 = std::move(ptest); // ptest2 = ptest => this is totally wrong! ``` - 移动构造函数 - 当函数的返回值为unique_ptr的时候，会自动调用移动构造函数： ``` unique_ptr fun() { return unique_ptr(new Test("789")); } unique_ptr ptest = fun(); //这里可以直接用=，会自动调用移动构造函数 ``` - [智能指针](https://www.cnblogs.com/TenosDoIt/p/3456704.html) - 智能指针在C++11版本之后提供，包含在头文件中，shared_ptr、unique_ptr、weak_ptr - 基于RAII（获取即初始化）技术 - shared_ptr：多个指针指向相同的对象。使用引用计数，每一个shared_ptr的拷贝都指向相同的内存。每使用（如赋值）他一次，内部的引用计数加1，每析构一次，内部的引用计数减1，减为0时，自动删除所指向的堆内存。shared_ptr内部的引用计数是线程安全的，但是对象的读取需要加锁。 - 赋值=>引用计数+1 - reset()释放（析构）=>引用计数-1 - use_count()=>获取当前引用计数 - unique_ptr：用于替代auto_ptr，避免在auto_ptr在被当作参数传入函数的时候丢失控制权的问题，且unique_ptr对数组支持偏特化重载，并作了相应的优化，支持[]操作符。 - 独享所有权 - 无法进行复制构造，无法进行复制赋值操作。但是可以进行移动构造和移动赋值操作（调用std::move()函数）。 - 当unique_ptr本身被释放删除的时候，会调用对应的删除器(deleter)释放其指向的对象。 - weak_ptr：若两个shared_ptr相互引用，则他们的引用计数永远都不可能降为0，从而导致无法释放的死锁；因此可以将其中一个设置为weak_ptr类型，即可解决这个问题；weak_ptr本身不可以直接访问其引用的对象的内部，但可以和shared_ptr进行转换，从而实现对引用对象的内部访问。 - 函数指针： - 函数具有可赋值给指针的物理内存地址，一个函数的函数名就是一个指针，它指向函数的代码。 - 函数的调用可以通过函数名，也可以通过指向函数的指针来调用。 - 定义形式：类型（*指针变量名）（参数列表）；如 int (*p)(int i,int j); - static 两个作用：限定作用域；保持变量静态化持久化；静态变量位于静态存储区，全局静态变量在定义后在当前文件中可用；局部静态变量则在局部作用域内可用（如在函数内部，则函数结束后不可访问，下次再运行函数时可访问且内容不变）；静态变量都默认初始化为0；类中的静态标量属于类的所有实例共有，且不需要实例化即可访问。静态函数也只在当前文件中可见；类中的静态函数则不需要实例化即可调用，但只可访问类内的静态成员或函数。 - inline 内联函数，修饰简单的函数，可以在调用的时候直接替换成函数内容；限制：函数本身不能复杂，不能包含if for等结构控制语句，同时也不能是递归函数即使使用了inline也不一定有用，这得看编译器的意思，编译器认为函数比较复杂，则不会进行内联展开；即*inline只是一个建议* - extern 两种作用：表示变量或函数的定义在其他的文件中；用于进行链接指定；第一、extern "C" fun(int a)表示函数fun在编译时函数名翻译按照C的规则来翻译，而避免C++编译器将函数换名，但这种方式会导致函数重载失效；第二、extern后直接跟变量或函数时，表明该变量或函数的定义可能位于别的文件中，需要编译器在编译阶段查找其他文件（即该变量在别的地方有过定义，这个地方的变量应使用那个地方的变量来替换）。 - volatile volatile 关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改，比如：操作系统、硬件或者其它线程等。遇到这个关键字声明的变量，编译器对访问该变量的代码就不再进行优化，从而可以提供对特殊地址的稳定访问。声明时语法：int volatile vInt; 当要求使用 volatile 声明的变量的值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指令刚刚从该处读取过数据。而且读取的数据立刻被保存。 - public 公开 protected 子类、自己、友元类 private 自己、友元类 - 多态（使用virtual函数）接口的多种不同实现方式即为多态；父类中以virtual修饰的函数，在子类中存在同名同参的函数时，调用父类指针指向的子类实例，则调用的函数是子类的。如A为父类，A中fun()为虚函数，B继承A，B中也有一个fun()，那么A* a = new B()时，a->fun()调用的是子类B中的函数。原理：编译器在编译期间会为含有虚函数的类生成一张虚函数表，表中存有各个虚函数的函数指针；这张虚函数表为这个类的所有实例所共有，且位于进程的静态数据段，类中实际上存储的是虚函数表的指针，位于所有成员变量的前面（大小就是指针的大小）。而继承了父类的子类中也会拷贝父类的虚函数表，且与父类中虚函数相同的函数会将虚函数表中的相应指针位置覆盖，因而就会出现调用子类的函数的现象。 - 虚基类（解决钻石继承、菱形继承问题）如果某个子孙类通过各种方式继承下来（有多条继承的路径）发现最后多次继承了某个基类，那么就会发现这个基类会被多次实例化，用虚基类就可以解决这个问题。虚基类的构造函数由最远的子类来确定 - const 根据const右边的东西来确定是什么不变。 const int* a表示a指向的地址的内容不可变；int* const a表示a的内容不变（a存储的是地址，故地址不变，但地址指向的地方的内容可以变）； const修饰函数时，当const在函数名前面时表示函数返回的内容不可修改（如函数访问public的变量，但是又不想让别人修改这个变量，可以将函数修饰为const函数）；当const在函数名后面（如fun() const这种）则表示该函数体内的所有操作均不可修改类的成员变量，也不可调用非const的函数（只可调用有const在后的）。 - 宏定义在编译阶段会直接被替换 - STL - vector（如何扩容）动态分配，在堆中分配内存；元素连续存放，且保留大小（数组大小减少也不会释放内存，因此vector占用的内存只增加不减少，只有在析构的时候才会被系统收回）；扩容：当占有的内存不够时，会向系统申请当前大小的双倍内存，再调用拷贝构造函数将已有的数据复制过去。之所以扩容是双倍，是为了方便内存收缩后，前面如果是以2的内存来进行分配的话到一定程度后就可以将前面分配过但已经不用的内存重新利用起来。 https://blog.csdn.net/dengheCSDN/article/details/78985684 - map——红黑树内部元素按照key自动排序（因此对于key为自定义类的情况需要重载操作符<） map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。因此按照中序遍历会产生有序序列。 - unordered_map 内部元素不会按照key自动排序 - set - 重载、重写（覆盖）和隐藏（重定义） ![重载、重写和隐藏](https://wx3.sinaimg.cn/mw690/7c9c3ec6ly1fv5n0346i9j20nn09a0x0.jpg) - 继承中的构造函数、析构函数调用顺序构造函数调用顺序： - 在子类指针指向子类时，会先调用父类构造函数后调用子类构造函数；析构函数调用顺序：先子后父； - 在父类指针指向子类时，会先调用父类构造函数后调用子类构造函数；但*析构函数则仅调用父类析构函数*； - 继承方式 - public继承： A: public B - protected继承：A: protected B - private继承：A: private B - 三种继承方式对于父类中不同权限的成员变量的访问权限是不一样的： ``` 基类中 & 继承方式 => 子类中 public ＆ public继承 => public public ＆ protected继承 => protected public ＆ private继承 = > private protected ＆ public继承 => protected protected ＆ protected继承 => protected protected ＆ private继承 = > private private ＆ public继承 => 子类无权访问 private ＆ protected继承 => 子类无权访问 private ＆ private继承 = > 子类无权访问 ``` - C++中struct和class的区别 C++中的struct继承于C，但在C++中，struct中不仅可以包含成员变量，并且还可以有成员函数，且在struct中，成员变量和成员函数默认是public访问权限的；且在C++中class可以继承struct，struct也可以继承class。 - 函数参数入栈方式从右往左，为了保证可变长度的变量顺利入栈 - 各种类型的变量内存分配方式分为五个部分： - 栈：存储局部变量、函数参数等编译器才知道什么时候需要分配内存的变量 - 堆：程序员自己控制分配，也由程序员自己回收（容易导致运行中的内存泄漏，但程序结束操作系统会自动收回）；存储的都是由malloc分配的内存。 - 自由存储区：C++中独有的区域，存储的是用new分配的内存块，和堆相似；在C中不存在； - 静态存储区：全局变量和静态变量； - 常量存储区：存储常量，不允许修改。 - 程序代码区：存放程序、函数体的二进制代码。 - 友元在C++之中，类的友元函数是定义在类外部，但它有权访问类的所有私有（private）成员和保护（protected）成员。尽管友元函数的原型有在类的定义中出现过，但是友元函数并不是成员函数。友元可以是一个函数，该函数被称为友元函数；友元也可以是一个类，该类被称为友元类。 - Python - import路径查询先搜索当前路径以及从当前目录指定的sys.path，然后是PYTHONPATH环境变量的路径，然后是python安装的时候设置的某些默认路径。因此当需要的包不在当前路径也不在路径内的时候，在import之前先把这个包的路径加到sys.path即可： import sys sys.path.append("login文件夹的绝对路径") import login_main - \_\_init\_\_.py 可以声明目录为package - \_\_all\_\_ 用于模糊导入（“from xxx import *”） - if \_\_name\_\_==\_\_main\_\_ 定义程序入口，若当前文件被执行则为入口，若被当作模块导入则不执行 - 数据结构 - 堆满足两个性质：其一：总是一棵完全二叉树；其二：某节点的值总是不大于或不小于其父节点的值。 - 大顶堆——根节点最大的堆叫做大顶堆 - 小顶堆——根节点最小的堆叫做小顶堆 - 栈后进先出 - B+树——数据库索引 - B-树 - AVL树 - 红黑树——stl map - 每个结点要么是红的，要么是黑的。 - 根结点是黑的。 - 每个叶结点，即空结点（NIL）是黑的。 - 如果一个结点是红的，那么它的俩个儿子都是黑的。 - 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。 ![红黑树](https://wx2.sinaimg.cn/mw690/7c9c3ec6ly1fv5k9uxkn3j20ik0dyn5g.jpg) - 哈希表——数组+链表 - 算法 - 排序 - 冒泡（稳定）、选择（不稳定）、插入（稳定） O(n^2) 选择排序：每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止插入排序：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。冒泡排序：冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序 - 快速排序——不稳定每一趟取一个中枢元素，设置两个哨兵，一个左哨兵一个右哨兵，右哨兵往左遍历找到一个比中枢元素小的，左哨兵向右找到一个比中枢大的，交换这两个元素；重复上述行为，直至左右哨兵相遇，此时相遇的点即为中枢元素应该待的位置；而后以中枢元素为分解，左右两半重复上述过程。因此，*每一趟排序下来都有一个中枢元素归位*。平均O(nlog)，最差O(n^2) - 归并排序——稳定最好最坏平均都为O(nlogn) - 堆排序——使用堆来进行排序，不稳定将无序序列构造成堆，而后按照升序或降序选择大顶堆还是小顶堆，将堆构造成想要的堆，然后交换顶点元素与末尾元素（最后一个叶子节点）；而后针对剩下部分的子树继续调整成大顶堆or小顶堆重复上述过程；最好、最坏、平均都为O(nlogn) - 桶排序——类似于用位向量排序适用于数据量大，且数据较为集中并且需要保留重复数据的数据集。如游戏中胜场数排名； O(n) - 基数排序——不稳定分配的时间复杂度为O（n）收集的的时间复杂度为O（radix）分配和收集共需要distance趟所以基数排序的时间复杂度为O(d(n+r)) - 超大规模数据的排序（多次归并、位向量、有关联数据的情况） - 广度优先——队列 - 深度优先——栈 - 最短路 - 迪杰斯特拉 - 普里姆 - 1）单字符串压缩：输入：ABBBCCD ，输出AB3C2D - 2）多字符串压缩输入：AABCABCD，输出A(ABC)2D - 计算机网络 - 网络分层结构 - 应用层：HTTP、SMTP、DNS（域名解析协议） - 传输层：TCP（传输控制协议）、UDP、ICMP（互联网控制报文协议） - 网络层：IP、ARP协议（地址解析协议，ip=>MAC地址） - 数据链路层：MAC地址（media access control媒体访问控制，硬件唯一） - 物理层 - DNS协议，客户端发起请求使用UDP协议，域名服务器之间进行域传输使用TCP协议 - 第一步：发起http请求时，系统会首先查询本地DNS缓存和hosts文件信息，若能查询到则返回域名对应的ip地址； - 第二步：若本地DNS缓存和hosts均未查询到，则系统会发送查询请求给系统设置中的本地DNS服务器，若本地DNS服务器的DNS缓存中有相应的记录，则返回； - 第三步：若本地DNS服务器的DNS缓存中也无记录，则向根域名服务器发起查询请求； - 第四步：根域名服务器返回待查询域名对应的主域名服务器（gTLD）给本地DNS； - 第五步：本地DNS服务器根据上一步返回的gTLD地址向其发起查询请求； - 第六步：gTLD服务器返回对应域名注册的服务器地址； - 第七步：本地DNS缓存起来，并将服务器地址返回给客户端。 ![DNS解析过程](https://wx2.sinaimg.cn/mw690/7c9c3ec6ly1fw4cheyk0mj20j10e6gp2.jpg) - TCP——可靠的、面向连接、全双工、点对点 - 三次握手客户端发送请求，SYN 服务端收到请求，发送SYN和ACK 客户端收到ACK，发送确认ACK 举个打电话的例子： A : 你好我是A，你听得到我在说话吗（SYN） B : 听到了（ACK），我是B，你听到我在说话吗（SYN） A : 嗯，听到了（ACK）之所以要三次，是因为客户端发送第一次SYN的时候可能服务端蛮久没收到，客户端等不及就再发送了一个SYN，此时服务端可能会收到两个SYN，因而认为客户端需要两个TCP连接，容易造成服务端资源浪费；因此客户端收到服务端的ACK后再发送一次ACK给服务端用于确认。 - 四次挥手客户端发送FIN给服务端，请求断开连接服务端收到FIN，发送ACK给客户端服务端传送任务完成后断开与客户端的连接，并发送FIN给客户端客户端收到FIN后发送ACK报文给服务端举个例子： A：你好，我没有东西要发给你了，我要的东西的清单也已经全发给你了（FIN），你发完了就断开连接吧。 B：知道了（ACK），我还没准备好，你再等我消息。（一段时间后） B：你好，你要的东西我都发完了（FIN），断开连接了啊。 A：知道了（ACK）。（再等一小段时间看有没有回复，没有则证明断开连接了）之所以要四次握手，B需要确保自己发送给A的东西都发送完了，而A也需要保证B知道可以断开连接。 - UDP——不可靠、无连接的应用层可以更好地控制要发送的数据和发送的时间无需建立连接，没有建立连接的延时无需维护连接状态分组首部开销小（TCP20字节首部，UDP8字节首部） - HTTP 无状态协议——服务端不保存任何客户端的相关信息使用TCP作为运输协议。分为持久连接和非持久连接： - 持久连接：完整的页面框架及其中包含的各对象都是用一个TCP连接来完成传送 - 非持久连接：网页框架的传送使用一个TCP连接，而后断开后依次建立连接传送其中包含的各个对象。 HTTP1.0和HTTP1.1的区别：其一、HTTP1.0需要keep-alive参数才可支持长连接，而HTTP1.1默认支持长连接；其二、HTTP1.1更节省带宽（支持发送只有头部的报文，用于测试是否有权限访问，无权限则后续直接可以不进行连接，从而节省带宽资源），同时支持断点续传（客户端已有资源不进行传送，只传送需要更新的部分）。 HTTP1.1和HTTP2.0的区别：其一、HTTP2.0支持多路复用，同一个连接并发处理多个请求；其二、HTTP2.0支持对头部信息进行压缩，HTTP1.1则不支持；其三、HTTP2.0支持服务器推送，即客户端发起web server请求时，服务端主动将一些客户端需要的资源发送给客户端，避免客户端再次创建连接获取资源。 - HTTPS ![HTTPS](https://wx4.sinaimg.cn/mw690/7c9c3ec6ly1fw4js6x06zj20ya0q67wh.jpg) - ARP协议 - SYN洪泛攻击 TCP建立连接的三次握手过程中，服务器收到客户端发送的SYN后会将其加入到待处理队列中，这就导致SYN的到达必定会消耗服务端资源；因此，若到达的SYN过多，则容易导致服务器因内存消耗过大而耗尽资源。解决办法：SYN缓存、SYN Cookies验证等（未涉猎） - 中间人攻击在正常的通信过程中，第三者欺骗客户端说自己是服务端，欺骗服务端说自己是客户端，从而实现劫持通信数据包。实际上网络抓包的软件即基于此。 - DDOS 通过大量的合法请求霸占服务器资源从而造成服务器瘫痪。实际上SYN洪泛攻击、ACK洪泛攻击、ICMP洪泛攻击都属于此 - ARP攻击（地址解析协议） ARP攻击就是通过伪造IP地址和MAC地址实现ARP欺骗，能够在网络中产生大量的ARP通信量使网络阻塞，攻击者只要持续不断的发出伪造的ARP响应包就能更改目标主机ARP缓存中的IP-MAC条目，造成网络中断或中间人攻击。 ARP攻击常位于局域网中，局域网内有一台计算机感染该病毒即可。 - traceroute：分为traceroute和tcptraceroute两种实现方式，都属于应用层协议； - 原理： - 发送一个TTL(Time-To-Live)相当小的包，TTL经过每一跳时会递减。当它减为0时，数据包就被丢弃。 - 当TTL失效后，看哪个路由器返回一个带有表明的ICMP “time exceeded” - 如果返回的路由器就是最终的目的地，停止trace；否则，TTL加1并返回到步骤1 - traceroute：基于UDP和ICMP协议实现，使用的是UDP或ICMP协议的“ECHO”包，这两种包均会被防火墙拦截； - tcptraceroute：基于TCP实现，使用TCP建立连接所使用的“SYN”包来携带TTL信息，不会被防火墙拦截，较可靠。 - GET和POST的原理区别 - GET方式只产生一个TCP数据包，其中包含了HTTP header和data两部分，发送至服务端后服务端返回状态号200 （ok的意思）。 - POST方式产生两个TCP数据包，第一个数据包中只包含了HTTP header，服务端收到后返回状态号100（continue的意思），第二个数据包中包含data，发送至服务端后服务端返回200（ok）。 - 操作系统 - CPU调度算法 - 先来先服务（FCFS） - 最短作业优先（shortest process next，SPN）:选择就绪队列中执行时间最短的进程执行——可能导致饥饿现象 - 最短剩余时间优先（shortest remaining time,SRT）：最短作业优先的改进版，可解决饥饿问题； - 最高响应比有限（Highest Response Ratio Next，HRRN）：选择就绪队列中响应比最高的进程执行——不会导致饥饿现象；响应比：（等待时间+执行时间）/执行时间 - 32位与64位的区别 - 一次性处理数据不同——32位一次性处理32位的数据，64位则一次处理64位数据（64位系统加64位软件）；CPU的位数通常指内部寄存器的位数，32位CPU内部寄存器都只有32位长，64位CPU内部则为64位长的寄存器。 - CPU地址总线根数不同（32位CPU有32根，64位CPU通常为40根）; - 32位、64位下长度相同的类型：bool(1)、char(1)、short(2)、int(4)、float(4)、double(8)、longlong(8) - 32位、64位下长度不同的类型：long-4-8、unsignedlong-4-8、指针类型-4-8 - 内存对齐问题：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小（只要该成员有子成员，比如说是数组，结构体等）的*整数倍*开始，同时，结构体、类或联合本身的大小需要补齐到4or8的倍数（32位默认4，64位默认8） - 进程定义进程包含代码段、数据段和栈；文本区域存储处理器执行的代码；数据区域存储变量和进程执行期间使用的动态分配的内存；堆栈区域存储着活动过程调用的指令和本地变量。进程是一个实例化的程序。进程的状态： - 就绪：进程获取了除CPU以外的所有资源，随时可以准备运行； - 运行：进程获得了CPU时间分配开始执行; - 阻塞：进程等待其余资源就绪时，如等待I/O操作的时候； - 阻塞态不可直接转为运行态，因为即使阻塞态等待的操作完成了，也还需要等待CPU分配，因此会进入就绪态； - 进程的内存管理 - 代码段.text：存放执行代码，只读，*也包含只读的常量* - 全局（静态）区：包含以下两个分区： - 数据区.data：存放已初始化的全局变量和静态变量。 - .bss：存放未经初始化的全局变量。 - 栈stack：用于存放程序临时创建的局部变量和函数参数，对程序员透明，不可控；由高地址向低地址生长。 - 堆heap：用于存放程序员手动调用new分配的内存，也应当由程序员手动释放；由低地址向高地址生长。 - 给4MB空间，每次请求分配1K/2K或4K空间，怎么分配比较好 - 注意内存对齐 - 可以考虑用位图结构 - 线程定义通常在一个进程中可以包含若干个线程，一个进程中至少有一个线程。线程可以利用进程所拥有的资源，在操作系统中，进程作为分配资源的基本单位，线程作为独立运行和独立调度的基本单位；由于线程比进程更小，基本上不拥有系统资源，故对它的调度所付出的开销就会小得多，能更高效的提高系统多个程序间并发执行的程度。线程拥有独立的堆栈空间，但是*共享数据段*，它们彼此之间使用相同的地址空间，共享大部分数据，比进程更节俭，开销比较小，切换速度也比进程快，效率高，但也因此不如进程安全。 - 死锁两个进程或线程因为互相等待对方完成特定操作而都进入阻塞态。避免死锁的方式： - 设置加锁顺序：为所有线程设置加锁的顺序，按照先后顺序排队加锁；因此需要事先知道所有可能会用到的锁，并知道锁的获取顺序。 - 线程请求加锁时会记录相应信息，因此当请求加锁时，可以检测是否存在对方向自己申请的加锁，从而避免死锁。 - 设置线程优先级（随机or其他） - 进程与线程对比 ![进程与线程对比](https://wx2.sinaimg.cn/mw690/7c9c3ec6ly1fv5k7w3ysvj20to0ab0t6.jpg) - 互斥、同步 - 临界区（只可用于同一进程下的线程）:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。临界区实际上是一段代码，任意时刻都只有一个线程执行此段代码；当一个线程处于临界区中时，其余线程试图访问临界区代码时会被挂起，一直等到处于临界区的线程离开。 - 互斥量、互斥锁（可用于线程也可以用于进程）:为协调共同对一个共享资源的单独访问而设计的。只有拥有互斥对象的线程（进程）才可访问共享资源。 - 信号量（可用于线程也可以用于进程）:为控制一个具有有限数量用户资源而设计。信号量指出了同时访问共享资源的线程（or进程）最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。P操作（申请资源）信号量减1，若信号量仍大于等于0则继续执行，否则挂起进入调度程序；V操作（释放资源）信号量加1，若信号量大于0则继续执行，小于0则唤醒等待队列中的一个进程（线程）。 - 事件:用来通知线程有一些事件已发生，从而启动后继任务的开始。 - 字符串压缩（霍夫曼编码之类的方法）霍夫曼编码：出现频率高的编码短，频率低的编码长；且字符之间的编码互相不能为前缀。 - 错误校验（奇偶校验、CRC校验） - 奇偶校验：实现约定好什么校验方式，检测二进制数据中1的个数是奇数还是偶数； - CRC校验： - 数据库 - CAST和CONVERT的用法 - CAST('111' AS SIGNED) - CONVERT('111', SIGNED) - 只能对以下类型的数据使用： - 二进制，同带binary前缀的效果 : BINARY - 字符型，可带参数 : CHAR() - 日期 : DATE - 时间: TIME - 日期时间型 : DATETIME - 浮点数 : DECIMAL - 整数 : SIGNED - 无符号整数 : UNSIGNED - sql查询优化 - 保证不查询多余的行与列 - 避免select * - 多使用where具体限定数据 - 多使用top，查询字段少的情况下多使用distinct - 查询字段较多的情况下谨慎使用distinct - 慎用union关键字 - 对大批量的操作进行分批处理 - 内连接、左连接、右连接、完全连接、交叉连接 - 内连接 - 左连接 - 右连接 - 完全连接 - 交叉连接 - 索引原理基于*B+树*的数据结构； - 事务 - 原子性：事务要么完全执行，要么全部失败回滚 - 一致性：事务的执行应当使数据库保持一致，即从一个一致的状态转到另一个一致的状态； - 隔离性：当多个用户并发访问数据库时，比如操作同一张表时，数据库为每一个用户开启的事务，不能被其他事务的操作所干扰，多个并发事务之间要相互隔离，即对于任意两个并发的事务T1和T2，在事务T1看来，T2要么在T1开始之前就已经结束，要么在T1结束之后才开始，这样每个事务都感觉不到有其他事务在并发地执行。 - 不考虑隔离性会发生的问题 - 脏读：脏读是指在一个事务处理过程里读取了另一个未提交的事务中的数据。当一个事务正在多次修改某个数据，而在这个事务中这多次的修改都还未提交，这时一个并发的事务来访问该数据，就会造成两个事务得到的数据不一致。 - 不可重复读：对于数据库中的某个数据，一个事务范围内多次查询却返回了不同的数据值，这是由于在查询间隔，被另一个事务修改并提交了。 - 幻读（虚读）：幻读是事务非独立执行时发生的一种现象。例如事务T1对一个表中所有的行的某个数据项做了从“1”修改为“2”的操作，这时事务T2又对这个表中插入了一行数据项，而这个数据项的数值还是为“1”并且提交给数据库。而操作事务T1的用户如果再查看刚刚修改的数据，会发现还有一行没有修改，其实这行是从事务T2中添加的，就好像产生幻觉一样，这就是发生了幻读。 - 幻读和不可重复读都是读取了另一条已经提交的事务（这点就脏读不同），所不同的是不可重复读查询的都是同一个数据项，而幻读针对的是一批数据整体（比如数据的个数）。 - MySQL的四种隔离级别 - 串行化(serializable)：最高级别，可以避免脏读、不可重复读、幻读的发生； - 可重复度(repeatable read)：可避免脏读、不可重复读的发生； - 读已提交(read committed)：可避免脏读的发生； - 读未提交(read uncommitted)：最低级别，无法保证任何情况； - 持久性：持久性是指一个事务一旦被提交了，那么对数据库中的数据的改变就是永久性的，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。 - 日志 - redo日志 *事务commit位于数据持久化（写入到磁盘）之前，数据持久化之前一定要先确保日志写入到磁盘。*一旦系统中确认有事务的commit，则任务已经完成，且数据已写入数据库。因而当出现问题时，将所有commit的事务全部重新执行。 - undo日志 *没有commit的事务一律回滚到之前的状态，已经commit的日志则不处理。*因此，undo日志要确保事务commit之前先将数据持久化（写入到硬盘）。 - SQL注入，如何防范当程序使用用户输入的内容来动态构造sql语句时，若未对用户输入的内容进行限制和筛选（对于存储过程也适用），则容易发生sql注入攻击。如何防止sql注入： - 不相信用户的输入，主动对用户的输入进行限制、筛选； - 不使用动态构造sql语句，尽量使用参数化的sql或使用ORM框架； - 不适用管理员权限连接数据库，为每个应用或用户单独设置账号密码； - Linux - GDB - CAT：打印文件内容 - TAC：按照行，倒序打印文件内容，第一行内容最后打印，最后一行内容最先打印。 - VIM :s /old /new /将把当前中模式old的第一次出现修改为new。 /（斜杆）是命令不同部分之间的分隔符（当斜杆为该行的最后一个字符时，可不写）下面这种形式的替换命令： s / old / new / g 把当前行old的每次出现改为new，而不只是该行的第一个old。 - grep 查找、匹配特定字符串、正则表达式 - sed 编辑、替换等 sed 's/原字符串/替换字符串/' filename sed 's/原字符串/替换字符串/g' filename 每一行中的所有匹配都替换 - awk 以行为单位处理文本文件 awk '{print $1}' 打印每一行的第一个字段 - find 在指定目录下查找符合指定表达式的文件or目录find /home -name "*.txt" - locate 查找目录or文件，但是查找的是mlocate.db的数据库文件，这个数据库每一天更新一次；故速度快，但有可能数据不一致，如被删除的文件也可以查找到，或者新建的文件查找不到等；可以通过updatedb命令更新数据库。 - whereis whereis命令只能用于搜索程序名，而且只搜索二进制文件（参数-b）、man说明文件（参数-m）和源代码文件（参数-s） - which which命令是查找命令是否存在，以及命令的存放位置在哪儿。 - type type命令用来区分某个命令到底是由shell自带的，还是由shell外部的独立二进制文件提供的。如果一个命令是外部命令，那么使用-p参数，会显示该命令的路径，相当于which命令。 - tail tail命令默认在屏幕上显示指定文件的末尾10行。如果给定的文件不止一个，则在显示的每个文件前面加一个文件名标题。如果没有指定文件或者文件名为“-”，则读取标准输入。 tail file （显示文件file的最后10行） tail +20 file （显示文件file的内容，从第20行至文件末尾） tail -c 10 file （显示文件file的最后10个字符） - head命令用于显示文件的开头的内容。在默认情况下，head命令显示文件的头10行内容。 -n<数字>：指定显示头部内容的行数； -c<字符数>：指定显示头部内容的字符数； -v：总是显示文件名的头信息； -q：不显示文件名的头信息。 - 内核态、用户态 - I/O模型 - 同步阻塞IO模型：用户空间的应用程序执行一个系统调用（如recv或recvform），这会导致应用程序阻塞，什么也不干，直到数据准备好，并且将数据从内核复制到用户进程，最后进程再处理数据，在等待数据到处理数据的两个阶段，整个进程都被阻塞; - 非阻塞IO模型：非阻塞的recvform系统调用调用之后，进程并没有被阻塞，内核马上返回给进程，如果数据还没准备好，此时会返回一个error。进程在返回之后，可以干点别的事情，然后再发起recvform系统调用。重复上面的过程，循环往复的进行recvform系统调用。这个过程通常被称之为轮询。轮询检查内核数据，直到数据准备好，再拷贝数据到进程，进行数据处理。 - IO多路复用：可以同时“轮询”多个文件描述符orsocket，基本原理就是select，poll，epoll这个function会不断的轮询所负责的所有socket，当某个socket有数据到达了，就通知用户进程。 - select:select本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理 - 缺点：单个进程可监视的fd数量被限制，即能监听端口的大小有限; 对socket进行扫描时是线性扫描，即采用轮询的方法，效率较低;需要维护一个用来存放大量fd的数据结构； - poll:poll系统调用的原理与原型和select基本类似，也是在指定时间内轮询一定数量的文件描述符，以测试其中是否有就绪者。 - epoll: - 1 首先要调用epoll_create建立一个epoll对象。参数size是内核保证能够正确处理的最大句柄数，多于这个最大数时内核可不保证效果。 - 2 epoll_ctl可以操作上面建立的epoll，例如，将刚建立的socket加入到epoll中让其监控，或者把 epoll正在监控的某个socket句柄移出epoll，不再监控它等等。 - 3 epoll_wait在调用时，在给定的timeout时间内，当在监控的所有句柄中有事件发生时，就返回用户态的进程。 - 在调用epoll_create时，内核除了帮我们在epoll文件系统里建了个file结点，在内核cache里建了个红黑树用于存储以后epoll_ctl传来的socket外，还会再建立一个list链表，用于存储准备就绪的事件，当epoll_wait调用时，仅仅观察这个list链表里有没有数据即可。这样就保证可以高效返回； - 设计模式 - 单例模式 - 利用static成员对象和static成员函数 - 构造函数为private，防止多次实例化 - 判断是否存在，存在则返回，否则实例化； ``` public class Singleton { private static Singleton Instance; private Singleton() { } public static Singleton GetInstance() { if (Instance == null) { Instance = new Singleton(); } return Instance; } } ``` - - 题 - 下楼梯，一个小人从屏幕顶下楼梯(类似于真男人下一百层，只不过楼梯不变)，只能在楼梯上左右移动，落在空中的时候不能动，掉落距离超过一定长度就摔死，空中掉落和左右移动都是1 m/s，问下到屏幕底所需的最短时间(第一想法，用dfs，bfs实现？)，动态规划先从屏幕低到顶遍历一遍，确认好每个高度的楼梯对应的左边和右边楼梯，然而动态规划的方程dp[h] = min\[dp\[h->左\](左边的楼梯)+(左边楼梯移动的时间)+空中掉落的时间，dp\[h->右\](右边的楼梯)+(右边楼梯移动的时间)+空中掉落的时间）,边界条件就是底部dp[0]=0 - 给定一个地图，分割为多块，怎么把建筑物的高度压缩到0-1.0的高度实际上类似于数据处理中的标准化，去建筑物的最高最低值，然后得出建筑物的范围，再用每个建筑物的高度减去最小值后除以范围即可。 - 射击游戏，怎么判断开枪后命中的目标(子弹可穿透)，目标如果有体积怎么检测第一反应，类似图像处理中的直线段检测？实际上就是检测物体上是否存在多个点共着一条线，如果是这样的话就可以使用霍夫变换将直线空间转化为极坐标下的点集合？；另外是不是也可以从直线与面相交来入手。。。 - 100层楼丢鸡蛋的问题：两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。假设我们要求最多k次测试完成，那么，第一次我们肯定只能在第k层进行测试，因为只有这样我们才能利用接下来的k-1次机会继续完成测试。如果第一次测试鸡蛋碎了，那么从低层开始一层一层利用第二个鸡蛋往上试探，最终在最多k-1次测试的时候可以找出想要的最高层数。如果第一次测试鸡蛋没有碎，则移动至k+k-1层处测试；若碎了，则从k层开始往上一层一层试探，若没碎，则向上移动k-2层（即移至k+k-1+k-2层）。以此类推；因此有 k+(k-1)+(k-2)+……+1>=100 解出k>=14，因此第一次测试最好从14层开始测试，因而最多需要14次测试即可完成。 - 整数快速幂如x^19，19的二进制位10011 下列代码中，N&1其实就是判断N的二进制码最后一位是否为1 ``` int QuickPow(int x,int N) { int res = x; int ans = 1; while(N) { if(N&1) { ans = ans * res; } res = res*res; N = N>>1; } return ans; } ``` - 100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？ - ip区间问题 ipstart ipend 所属运营商 10.1.1.1 10.2.2.50 西安电信 100.1.1.5 100.5.5.30 江苏移动问：给定一个ip，如何快速求出其所属运营商？答：区间树？？