技术类面试要点梳理

未完待续==

一、数据结构与算法

1. 排序

排序

• 插入排序
  N-1趟排序组成。从P=1到P=N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。
  反着比较，若比当前元素大依次向后移位，否则插入。

void InsertSort(int *a, int n)
{
    int temp;

    for(int i=1; i<n; i++)
    {
        temp = a[i];   //即将新插入的值
        for (int j=i; j>0 && a[j-1]>temp; j--)
            a[j] = a[j-1]; //元素依次向后移动
        a[j] = temp;  //插入空挡
    }
}

• 选择排序
  每次选择最小的元素，交换到相应位置。

void SelectSort(int *a, int n)
{
    for(int i=0; i<n; i++)
    {
        int min = i;    //先赋值每趟的开始位置为最小
        for (int j=i+1; j<n; j++)
        {
            if(a[j]<a[min])
                min = j;       //时刻更新最小位置
        }
        if(i!=min)
            swap(a[i], a[min]);   
    }
}

• 冒泡排序

void BubbleSort(int *a, int n)
{
    for (int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(a[i]>a[j])
                swap(a[i], a[j]);
        }
    }       
}

• 归并排序
  分治思想。
  合并两个已排序的表。两个输入数组A和B，一个输出数组C，三个计数器Aptr， Bptr， Cptr， A[Aptr]和B[Bptr]中较小者放入C的下一个位置。当其中一个表没有剩余时，将其余元素全部拷贝到C中。
• 堆排序
• 快速排序

//partition函数
int partition(int *a, int left, int right)
{
    int temp = a[left];   //为方便起见，最左边元素为枢纽。其实是不科学的

    while(left<right)
    {
        while(left<right && a[right]>temp)
            -- right;    //若右侧元素比枢纽元素值大，则继续向左查找
        a[left] = a[right];    //一旦查找到比枢纽元素小的值，则交换到左边（枢纽）位置

        while(left<right && a[left]<=temp)
            ++ left;
        a[right] = a[left];
    }

    a[left] = temp;  //将枢纽插入空位
    return left； //返回枢纽位置
}
//quicksort函数
void QuickSort(int *a, int left, int right)
{
    int pivot;

    if(left>=right) return;
    
    pivot = partition(a, left, right);
    QuickSort(a, left, pivot-1);
    QuickSort(a, pivot+1, right);
}

2. 二分查找

//不使用递归
int binarySearch(int arry[], int len, int value)
{
    if(arry==NULL||len<=0)
        return -1;

    int start=0;
    int end=len-1;

    while(start<=end)
    {
        int mid=start+(end-start)/2;
        if(arry[mid]==value)
            return mid;
        else if(value<arry[mid])
            end=mid-1;
        else
            start=mid+1;
    }
    return -1;
}
//不要传参，传引用调用，减少垃圾。
int binarySearchRecursion(int arry[], int value, int start, int end)
{
    if(start>end)
        return -1;

    int mid=start+(end-start)/2;
    if(arry[mid]==value)
        return mid;
    else if(value<arry[mid])
        return binarySearchRecursion(arry,value,start,mid-1);
    else
        return binarySearchRecursion(arry,value,mid+1,end);
}

---

二、操作系统

高效面试之操作系统常考题

1. 进程和线程的区别

• 一个进程至少有一个主线程。线程是进程内的一个执行单元，也是进程内的可调度实体。
• 进程是资源分配的基本单位，线程是CPU调度和分派的基本单位。
• 进程有自己独立的地址空间，线程共享进程的地址空间，没有单独的地址空间，线程可以有自己的寄存器和堆栈。
• 线程更加灵活，进程更加稳定。一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，需要用多线程。

2. 进程的状态
   进程的三种状态及转换
   运行状态，阻塞状态，就绪状态。
   进程状态转换图
   创建和退出不是进程的状态。阻塞和就绪的区别：阻塞是等待除CPU以外的资源，而就绪等待的是CPU资源。

• 进程三种状态间的转换
  一个进程在运行期间，不断地从一种状态转换到另一种状态，它可以多次处于就绪状态和执行状态，也可以多次处于阻塞状态。
  (1) 就绪→执行处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
  (2) 执行→就绪处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。
  (3) 执行→阻塞正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
  (4) 阻塞→就绪处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。

3. 进程通信的几种方式
   linux系统下：

• 管道（pipe）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
• 命名管道（named pipe）：命名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
• 信号量（semophore）：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列（message queue）：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 信号（signal）：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存（shared memory）：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
• 套接字（socket）：套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

4. 线程同步几种方式。(一定要会写生产者、消费者问题，完全消化理解)

5. 线程的实现方式。 (也就是用户线程与内核线程的区别)

• 内核线程：由操作系统内核创建和撤销。内核维护进程及线程的上下文信息以及线程切换。一个内核线程由于I/O操作而阻塞，不会影响其它线程的运行。Windows NT和2000/XP支持内核线程
• 用户线程：由应用进程利用线程库创建和管理，不以来于操作系统核心。不需要用户态/核心态切换，速度快。操作系统内核不知道多线程的存在，因此一个线程阻塞将使得整个进程（包括它的所有线程）阻塞。由于这里的处理器时间片分配是以进程为基本单位，所以每个线程执行的时间相对减少。

6. 死锁
   是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

• 产生原因：
  资源竞争引起进程死锁。
  进程推进顺序不当。
• 导致死锁四个必要条件：
  简洁版：
  互斥条件 : 任一时刻只允许一个进程使用资源。
  非剥夺条件: 进程已经占用的资源, 不会被强制剥夺。
  占用并请求条件: 进程占有部分资源 , 申请更多的资源 , 且不会释放已经占有的资源。
  循环等待 : 请求资源的进程形成了循环。
  复杂版：
  1、互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
  2、请求和保持：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
  3、不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  4、环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
• 处理死锁的四个方式：
  1、撤消陷于死锁的全部进程；
  2、逐个撤消陷于死锁的进程，直到死锁不存在；
  3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失；
  4、从另外一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。
• 预防死锁的方法、避免死锁的方法：
  采用资源静态分配，破坏“部分分配”条件；
  允许进程剥夺使用其他进程占用的资源，破坏“不可剥夺”条件；
  采用资源有序分配法，破坏“环路”条件；
  互斥条件无法破坏。

---

c++基础知识

C++面试题——基础概念篇
C++面试出现频率最高的30道题目（一）
C++面试出现频率最高的30道题目（二）
C++面试出现频率最高的30道题目（三）

1. static

• 隐藏。未加static前缀的全局变量和函数都具有全局可见性；使用static在不同文件中定义同名函数和同名变量，不必担心命名冲突。
• 保持变量内容持久。全局变量和static变量存储在静态存储区，存储在静态存储区的变量会在程序刚开始运行就完成初始化，也是唯一一次初始化。
• 默认初始化为0。（全局变量也是）。

2. const
   修饰的内容不可改变，包括const数据成员，const参数，const返回值，const成员函数。被修饰的东西会被强制保护，可以预防意外变动，提高程序的健壮性。
3. 宏#define和const关键字的区别

• const是有数据类型的常量，而宏常量没有，编译器可以对前者进行静态类型安全检查，而后者只是字符串替换，没有类型安全检查，在字符替换时可能会发生意想不到的错误。
• 有些编译器可以对const常量进行调试，不能进行宏调试。
• const无法代替宏作为卫哨来防止文件的重复包含。

4. C++中引用和指针的区别
   引用是对象的别名， 操作引用就是操作这个对象， 必须在创建的同时有效得初始化（引用一个有效的对象， 不可为NULL）， 初始化完毕就再也不可改变， 引用具有指针的效率， 又具有变量使用的方便性和直观性， 在语言层面上引用和对象的用法一样， 在二进制层面上引用一般都是通过指针来实现的， 只是编译器帮我们完成了转换。 之所以使用引用是为了用适当的工具做恰如其分的事， 体现了最小特权原则。
5. C与C++的内存分配方式

• 静态存储区域分配。内存在程序编译时就已经分配好，这块内存在程序的整个运行期间都存在，如全局变量，static变量。
• 在栈上创建。在执行函数时，函数内部局部变量的存储单元可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
• 从堆上分配（动态内存分配）。程序在运行的时候用malloc或new申请任意多少的内存，程序员负责在何时用free或delete释放内存。动态内存的生存期自己决定，使用非常灵活。

6. 面向对象程序设计的优点
   开发时间短， 效率高， 可靠性高。面向对象编程的编码具有高可重用性，可以在应用程序中大量采用成熟的类库（如STL），从而虽短了开发时间，软件易于维护和升级。

---

数据库

https://www.zhihu.com/question/19552975/answer/123523074
数据库基础知识复习

索引：帮助MySQL高效获取数据的数据结构。 B-Tree和B+Tree。

计算机网络