求职札记 | YanZhirun's Blog

准备求职过程中遇到的各种问题记录在此，以防遗忘，亦是便于复习。面向的目标职位包括c++开发工程师，Linux内核工程师，分布式存储工程师等。以下内容包括但不限于OJ平台刷题的问题，对相应职位要求的知识补充，以往面经答案总结等，是对自己知识的汇总，不足之处，希望及时指出或与我交流讨论。

OJ平台输入输出转换问题

如果平台不提供输入输出，先把包含的头文件，输入输出语句写好，保证正确的输入输出

cin输入内容保存到vector容器

std::vector vec;
int num;
for (int i=0; i<10; ++i)
{
	cin>>num;
	vec.push_back(num);
}

保存n*m大小的矩阵，初始化元素为0

1	vector<vector<int> > matrix(n, vector<int>(m, 0));

使用迭代器输出vector容器内容

std::vector<int>::iterator it;
for(it=vec.begin(); it!=vec.end(); ++it)
{
	cout<<*it<<endl;
}

数字（int）字符串（string）相互转化

C 标准库提供 atoi函数

#include <sstream>
int iNum;
//int 转 string
string str = to_string(x);
//string 转 int
int iChange = itoa(str.c_str());

C++ 标准库使用stringstream 类型在各种数据类型间转换

#include <sstream> 
std::stringstream ss;
int iNum;
string str;
//可是其他类型 char tmp[100]; long long ; float
ss << iNum;
ss >> str;

C语言

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
    printf("%d\n",atoi(argv[1]));
	
	return 0;
}

string 转char*
string str;
str.c_str();
//str.data();

数字逆置（消除前导0）

给定整数X， reverse(X) 将数字按数位翻转，并消除前导0
如 X = 123；则reverse(X) = 321;
X = 100; 则reverse(X) = 1;

int rev (int m)
{
    int t=0;
    while (m>0)
    {
        t = t*10 + m%10;
        m = m/10;
    }
    return t;
}

易错

i++不是原子操作

分为三个阶段：内存到寄存器，寄存器自增，写回内存
这三个阶段中间都可以被中断分离开

erase使用

vector对象高效增长

范围for语句体内不应该改变vector容量的大小

参见 c++Primer 9.4 5.4.3

知识点补充

排序算法

稳定性：保证排序前两个相等的数据其在序列中的先后位置与排序后它们的先后位置顺序相同。
真正应用的时候可能是对负载类型（自定义）类型排序，而排序的键值仅仅是其中一个属性。如学生数组，按照年龄排序，而其中又有很多其它属性，假使原数组按照学号为主键进行排序，稳定排序会保证相同年龄的学生学号顺序不变。

冒泡排序

稳定

选择排序

给每个位置选择待排序元素中当前最小的元素
不稳定如果当前元素有重复，而该趟比较最小元素在当前元素的重复元素之后，交互后，重复元素会提前，导致交换。如5，8，5，2，9，第一遍选择第一个元素 5会和第四个元素2交互，序列中5的前后顺序被破坏。

插入排序

在一个已经有序的小序列上一次插入一个元素。从尾部最大的开始比较，如果该值大于最后一个，则直接插后面，小则向前找。相等的则直接放后面。

快速排序

选择pivot，两个方向
不稳定：发生在交换pivot元素的时候，如5，3，3，4，3，选取第一个5作为pivot，当与最后一个3交换的时候。

归并排序

把序列递归地分成短序列，出口时短序列只有一个元素（直接有序），或者只有两个（一次比较和交换），然后合并成长序列。
稳定

基数排序

低位先排序，然后收集，再按照高位排序，然后再收集；直到最高位

希尔排序

堆排序

建堆：O（n）
排序：$$O(nlog^n)$$

各类排序比较

排序方法	最好时间	平均时间	最坏时间	辅助空间	稳定性
直接插入	$$O(n)$$	$$O(n^2)$$	$$O(n^2)$$	$$O(1)$$	稳定
二分插入	$$O(n)$$	$$O(n^2)$$	$$O(n^2)$$	$$O(1)$$	稳定
希尔		$$O(n^{1.25})$$		$$O(1)$$	不稳定
冒泡	$$O(n)$$	$$O(n^2)$$	$$O(n^2)$$	$$O(1)$$	稳定
快速	$$O(nlg^n)$$	$$O(nlg^n)$$	$$O(n^2)$$	$$O(lg^n)$$	不稳定
直接选择	$$O(n^2)$$	$$O(n^2)$$	$$O(n^2)$$	$$O(1)$$	不稳定
堆	$$O(nlg^n)$$	$$O(nlg^n)$$	$$O(nlg^n)$$		不稳定
归并	$$O(nlg^n)$$	$$O(nlg^n)$$	$$O(nlg^n)$$	$$O(n)$$	稳定
基数	$$O(d(rd+n))$$	$$O(d(rd+n))$$	$$O(d(rd+n))$$	$$O(rd+n)$$	稳定

C/C++部分

一个有10个指针的数组,该指针指向一个函数,该函数有一个整形参数并返回一个整型数

int (int *p[10] )(int)
int *a[10]; //指向int类型的指针数组a[10]
int (*a)[10]; //指向有10个int类型数组的指针a

struct和class的区别

C语言中的struct只作一种复杂数据结构类型的定义，不能用于面向对象编程。
C++中：struct默认访问级别是public，class是private。
C++中：class可以用于表示模板类型（template< class T>），struct则不行。

强制类型转换

static_cast:：父子类之间转换，无类型检查

int n =6;
double d = static_cast(n); // 基本类型转换
int_pn =&n;
double_d = static_cast(&n) //无关类型指针转换，编译错误
void_p = static_cast<void_>(pn); //任意类型转换成void类型

const_cast: 消除对象的强制属性，去掉const或者 volatile关键字，const 常量变为可变的

dynamic_cast:子类转父类安全，父类转子类（返回NULL）
reinterpret_cast：暴力的转换，从一个指针到另一个指针的二进制拷贝。无安全检查。

面向对象特征

三大基本特性：封装继承多态
多态是允许将指向子类的指针赋给父类类型的指针。主要有两种实现方式覆盖和重载

覆盖，是指子类重新定义父类的虚函数的做法。在不同的类域，基类函数必须是虚函数，名称相同，参数相同。
重载，是指允许存在多个同名函数，而这些函数的返回值或者参数表不同（或许参数个数不同，或许参数类型不同，或许两者都不同），要在相同的类域。
如果派生类的函数与基类函数同名，但是参数不同，无论有无virtual都是隐藏。
如果派生类的函数与基类的函数同名，并且参数也相同，并且基类函数没有virtual关键字，此时也是隐藏。
有virtual才是多态。

五大基本原则：单一职责原则，开放封闭原则，替换原则，依赖原则，接口分离原则

引用一个已经定义过的全局变量 extern

引用头文件的方式，也可以用extern关键字.
如果用引用头文件方式来引用某个在头文件中声明的全局变量，假定你将那个变写错了，那么在编译期间会报错，如果你用extern方式引用时，会在连接期报错。
extern 标识的变量或者函数声明其定义在别的文件中，提示编译器遇到此变量和函数时在其它模块中寻找其定义。

extern “C”：一个C++程序包含其他语言编写的部分代码，为了是它们遵循统一的规则，可以使用extern指定一个编译和连接规则。
目的是为了实现混合编程。
在cpp中调用c文件中实现的函数时，要用extern “C”声明，否则cpp会按照名字改编后的函数名去找该函数。
在cpp中实现的函数，如果c文件要调用，就必须在cpp文件中用extern “C”来声明该函数，否则cpp在编译过程中就会对其进行名字改变，c文件就找不到该函数的原型。

static 修饰全局变量局部变量函数

普通全局变量：源程序由多个源文件组成时，在所有的都有效
static全局变量：只在当前文件内有效
static局部变量只被初始化一次，下一次依据上一次的结果值
static函数在内存中只有一份
普通的函数在每个调用中维持一份拷贝

初始化列表和构造函数区别

成员初始化列表：在数据定义的同时赋值
构造函数：先定义后赋值的方式
必须使用成员初始化列表：

初始化一个引用成员变量
初始化const变量
初始化一个子类对象，并且子类对象的父类有一个显示的带参数的构造函数
调用一个类类型成员的构造函数，并且它拥有一组参数

全局变量可不可以定义在可被多个.C文件包含的头文件中

可以，在不同的C文件中以static形式来声明同名全局变量。
可以在不同的C文件中声明同名的全局变量，前提是其中只能有一个C文件中对此变量赋初值，此时连接不会出错。

类成员重写、重载、隐藏

重写和重载主要有以下几点不同

范围的区别：被重写的和重写的函数在两个类中，而重载和被重载的函数在同一个类中。
参数的区别：被重写函数和重写函数的参数列表一定相同，而被重载函数和重载函数的参数列表一定不同。
virtual 的区别：重写的基类中被重写的函数必须要有 virtual 修饰，而重载函数和被重载函数可以被virtual 修饰，也可以没有。
隐藏和重写、重载有以下几点不同

与重载的范围不同：和重写一样，隐藏函数和被隐藏函数不在同一个类中
参数的区别：隐藏函数和被隐藏的函数的参数列表可以相同，也可不同，但是函数名肯定要相同。当参数不相同时，无论基类中的参数是否被 virtual 修饰，基类的函数都是被隐藏，而不是被重写

覆盖是动态绑定的多态，重写是静态绑定的。

引用和指针

引用必须被初始化，但是不分配存储空间。指针不必在声明时初始化，在初始化的时候需要分配存储空间
引用初始化以后不能被改变，指针可以改变所指的对象
不存在指向空值的引用，但是存在指向空值的指针

函数的指针参数

#include <stdio.h>  
int main(void)  
{  
    int i=0x01;  
    int *p=&i;  
    printf("&i = %x/n",&i);   //i的地址  
    printf("p = %x/n",p);  
    printf("*p = %x/n",*p);  
    printf("&p = %x/n",&p);  
    return 0;  
}

指针占4Byte，存放所指向的数据的地址；
p是一个指向int型变量i 的指针，所以p表示该指针的内容，即i的地址；
*p表示p指向的内容，即i；
&p代表指针p本身的地址。

让p指向函数f中的静态变量

#include <stdio.h>  
int f(int **p)  
{  
    static int i = 5;  
    *p=&i;  
    return 0;  
}  
int main(void)  
{  
    int i=0x01;  
    int *p=&i;  
    f(&p);  
    printf("p = %d/n",*p);  
    return 0;  
}

函数模版

#include <iostream>
#include <string>
using namespace std;
template<class T>  //定义模版标识
T Add(T a, T b)    //函数原型
{
    T result;
    result = a + b;
    return result;
}
int main()
{
    cout<<"2+3= "<<Add(2,3)<<endl;
    cout<<"sdf+123= "<<Add(string("sdf"), string("123"))<<endl;
    return 0;
}

有符号类型和无符号类型

表达式中既有无符号类型，又有有符号类型，有符号类型会转化为无符号类型，会导致计算结果异常。

const

对指针
在*左或右决定是值还是地址不可变。

//_pa不可变，pa为地址可修改
int const _pa;
//pb表示地址不可变，_pb指向的内容可变
const int _pb;
函数声明中修饰形参表示形参为不可变的输入值，在函数中不能改变。
定义常变量时必须同时初始化，不可作为左值。
作为函数返回值时，表示返回值不可做左值。
与#define区别： #define 只是字符替换，没有类型安全检查。

nullptr 和NULL

C++是强类型语言，又有模板、重载之类需要编译器“依类型随机应变”的东西；所以作为指针类型的0和整数类型的0就必须分开。
NULL是宏，具体展开为什么由编译器决定。
C++中NULL被定义为0，如果有函数重载，就容易出错。
在正常使用过程中nullptr和NULL是等价的。

二叉树最低公共祖先

typedef struct node Node;
Node *LCA(Node *root, Node *p, Node *q)
{
    if(!root)
        return NULL;
    if(root == p || root == q)
        return root;
    Note *L = LCA(root->left, p, q);
    Note *R = LCA(root->right, p, q);
	//L和R中出现了p，q，即在root的左右子树，当前root节点即为最近公共父节点
    if(L && R)
        return root;
//p，q都在L或在R
    return L?L:R;
}

二叉搜索树第k个结点

按照中序遍历递归的求解。

class Solution {
    int count = 0;
public:
    TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
    {
        if(pRoot){ 
                TreeNode *ret = KthNode(pRoot->left, k);
                if(ret) return ret;
                if(++count == k) return pRoot;
                ret = KthNode(pRoot->right,k);
                if(ret) return ret;
        }
        return nullptr;
    }
};

矩阵中全是1的最大方块大小

思路：动态规划。假设以matrix[i][j]为右下顶点的最大方块的大小为dp[i][j]。dp[i][j]的计算可以复用比其更小的子问题。
如果matrix[i][j] = 0，那么dp[i][j] = 0，当matrix[i][j] = 1，此时要考察dp[i-1][j-1] dp[i-1][j] dp[i][j-1]，因为matrix[i][j]为右下顶点的最大访客有上面三个位置决定，并且由最小值决定。考虑边界条件可得递归方程为：
$$
dp[i][j] = \begin{cases} matrix[i][j], \qquad \text{if i=0 or j=0 or matrix[i][j]=0} \\ min\{dp[i-1][j-1],dp[i-1][j], dp[i][j-1]\}+1, \qquad\text {otherwise} \end{cases}
$$

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int> > matrix(n, vector<int>(m, 0));
    int maxSIze = 0;
    for (int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            cin >> matrix[i][j];
            if (i>0 && j>0 && matrix[i][j]==1)
            {
                int min = matrix[i-1][j-1];
                if(min > matrix[i-1][j])
                {
                    min = matrix[i-1][j];
                }
                if(min > matrix[i][j-1])
                {
                    min = matrix[i][j-1];
                }
                matrix[i][j] = min + 1;
            }
            if (matrix[i][j] > maxSize)
            {
                maxSize = matrix[i][j];
            }
        }
    }
    cout << maxSize << endl;
    
    return 0;
}

sizeof() strlen()

sizeof() 是C语言提供的操作符（不是函数），返回unsigned int 的值
注意题目中32位（sizeof(p)为4）或者64位(sizeof(p)为8)
传参的时候数组退化为指针
union联合体取成员的最大长度
空类型为1，空类为1字节，单一继承和多重继承的空类都为1字节，如果有虚函数，涉及虚表，sizeof则为4字节
strlen（）是一个函数，从内存的某个位置开始直到遇到 ‘\0’ ，返回的长度大小不包括’\0’。使用的时候，最好手动写上’\0’ 。

//输出为空，i=-1 会转化为sizeof的值很多的正整数。不满足 <=NUM-2的条件，故不会输出
#include <stdio.h>
#define NUM (sizeof(arr) / sizeof(arr[0]))
int arr[] = { 1， 2， 3， 4， 5， 6， 7 };
int main()
{
    int i;
    for( i = -1; i <= ( NUM - 2 ); i++)
	   printf("%d\n",arr[i+1]);  
    return 0;  
}

//输出为i: 10 理解编译器编译原理，sizeof仅仅是操作符，最终i++并没有执行。
////warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long unsigned int’ [-Wformat=]
#include <stdio.h>  
int main()  
{
    int i;  
    i = 10;
	
    printf("i : %d\n",i);  
    printf("sizeof(i++) is: %d\n",sizeof(i++));  
    printf("i : %d\n",i);
	
    return 0;  
}

qsort() sort()

C语言标准库中，stdlib.h头文件包含qsort()算法，是快速排序的标准实现，平均复杂度为$ O(NlogN) $，但是由于可能不当的pivot选择导致最坏情况下复杂度为$ O(N^2) $
而sort()集合各种排序算法的优点：

在数据量很大时采用正常的快速排序，此时效率为O(logN)。
一旦分段后的数据量小于某个阈值，就改用插入排序，因为此时这个分段是基本有序的，这时效率可达O(N)。
在递归过程中，如果递归层次过深，分割行为有恶化倾向时，它能够自动侦测出来，使用堆排序来处理，在此情况下，使其效率维持在堆排序的O(N logN)，但这又比一开始使用堆排序好。

使用方法

默认升序排列，改为降序如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//降序排列
static bool cmp(const int &a, const int &b)
{
    return a>b;
}
int main()
{
    int arr[10]= {34, 3, 12, 45, 9, 9, 9, 9, 1};
    vector<int> vec;
    vector<int>::iterator it;
 
 for(int i=0;i<10;++i)
        vec.push_back(arr[i]);
        
	sort(vec.begin(), vec.end(), cmp);
    cout<<"sorted:"<<endl;
    for(it=vec.begin();it!=vec.end(); ++it)
        cout<<*it<<" ";
    cout<<endl;
    return 0;
}

堆栈空间

堆是共有的空间，全局堆是所有没有分配的空间，局部堆是用户分配的空间，一般有程序员分配释放，程序结束时可能有OS回收
栈时线程独有的，保存运行状态和局部自动变量。每个线程的栈相互独立。

全局变量存在静态区
动态申请存在堆中

动态分配与释放空间

malloc() 函数用来动态的分配内存空间
calloc() 函数用来动态地分配内存空间并初始化为 0
realloc() 函数用来重新分配内存空间

malloc 从堆中获得空间。
申请的实际空间要大于请求的空间。超出部分用来记录堆这块内存的管理信息
包含头文件 #include
free() 只能释放动态分配的内存空间，并不能释放任意的内存。
如果 ptr 所指向的内存空间不是由上面的三个函数所分配的，或者已被释放，那么调用 free() 会有无法预知的情况发生。
如果 ptr 为 NULL，那么 free() 不会有任何作用。

注意事项：

申请后需要检查是否分配成功
不使用的时候要释放
释放后吧指针指向NULL，防止后面的程序使用
分配与释放要配对
不能对非动态申请的内存free
只能free一次，多次会报错
free空指针等于没有做，多次释放也不会报错
分配的时候最好加上强制类型转换

char _ptr = (char _)malloc(10*sizeof(char));
{
//…
}
free(ptr);
prt = NULL;

ps：malloc 与new 区别
new 操作符， malloc是函数
new从自由存储区（free store）上分配空间，malloc 从堆上分配
new分配成功，返回的是对象类型的指针，类型严格与对象匹配，无需类型转换，是类型安全的操作符；malloc分配成功返回void_ ，需要通过强制类型转换将void_ 转换为所需要的类型。
malloc分配失败返回NULL，C习惯在分配后添加判断

int _a = (int_)malloc(sizeof(int));
if( NULL == a)
{…}
else
{…}

new不会返回NULL，应该使用异常机制。

try
{
int *a = new int();
}
catch(bad_alloc)
{…}

区别表格：

特征	new/delete	malloc/free
分配内存位置	自由存储区	堆
内存分配成功返回值	完整类型指针	void*
内存分配失败返回值	默认抛出异常	返回NULL
分配内存大小	由编译器根据类型计算得出	必须显式指定
处理数组	new[]	需要用户计算数组大小后进行内存分配
已分配内存的扩充	无法直观处理	使用realloc
分配时内存不足	指定处理函数或者重新制定分配器	无法通过用户代码进行处理
函数重载	允许	不允许
构造函数与析构函数	调用	不调用

构造函数与析构函数

构造函数：初始化对象的数据成员。
复制构造函数：默认生成的浅拷贝，当类中有指针成员，不会复制，需要手动重写写
等号运算符重载：
能否在构造函数析构函数中抛出异常：
构造函数中尽量不要抛出异常，能避免的就避免，如果必须，要考虑不要内存泄露！
c++不禁止析构函数抛出异常，但会导致程序过早结束或出现不明确行为

构造函数中抛出异常，会导致析构函数不能被调用，但对象本身已申请到的内存资源会被系统释放（已申请到资源的内部成员变量会被系统依次逆序调用其析构函数）。
因为析构函数不能被调用，所以可能会造成内存泄露或系统资源未被释放。
构造函数中可以抛出异常，但必须保证在构造函数抛出异常之前，把系统资源释放掉，防止内存泄露。（如何保证？？？使用auto_ptr？？？

是否可是虚函数
构造函数不可以，要构造一个对象，必须知道要构造什么
析构函数可以是虚函数，也可以是纯虚函数。

调用顺序
构造函数的调用顺序是：基类->成员对象->派生类；析构相反。
构造函数里初始化列表的顺序有成员变量的声明顺序决定。

class Complex 
{         
 
private :
    double m_real;
    double m_imag;
 
public:
 
    // 无参数构造函数
    // 如果创建一个类你没有写任何构造函数，
    //系统会自动生成默认的无参构造函数，函数
    //为空，什么都不做
    // 只要你写了一个下面的某一种构造函数，系
    //统就不会再自动生成这样一个默认的构造函
    //数，如果希望有一个这样的无参构造函数，
    //则需要自己显示地写出来
    Complex(void)
    {
         m_real = 0.0;
         m_imag = 0.0;
    } 
         
    // 一般构造函数（也称重载构造函数）
    // 一般构造函数可以有各种参数形式，一个
    //类可以有多个一般构造函数，前提是参数的
    //个数或者类型不同（基于c++的重载函数原理）
    // 例如：你还可以写一个 Complex( int num)的
    //构造函数出来
    // 创建对象时根据传入的参数不同调用不同的构造函数
    Complex(double real, double imag)
    {
         m_real = real;
         m_imag = imag;         
     }
     
    // 复制构造函数（也称为拷贝构造函数）
    // 复制构造函数参数为类对象本身的引用，用于
    //根据一个已存在的对象复制出一个新的该类的
    //对象，一般在函数中会将已存在对象的数据成
    //员的值复制一份到新创建的对象中
    // 若没有显示的写复制构造函数，则系统会默认
    //创建一个复制构造函数，但当类中有指针成员
    //时，由系统默认创建该复制构造函数会存在风
    //险，具体原因请查询有关 “浅拷贝” 、“深
    //拷贝”的文章论述
    Complex(const Complex & c)
    {
        // 将对象c中的数据成员值复制过来
        m_real = c.m_real;
        m_img  = c.m_img;
    }            
 
    // 类型转换构造函数，根据一个指定的类型的对
    //象创建一个本类的对象
    // 例如：下面将根据一个double类型的对象创
    //建了一个Complex对象
    Complex::Complex(double r)
    {
        m_real = r;
        m_imag = 0.0;
    }
 
    // 等号运算符重载
    // 注意，这个类似复制构造函数，将=右边的
    //本类对象的值复制给等号左边的对象，它不
    //属于构造函数，等号左右两边的对象必须已
    //经被创建
    // 若没有显示的写=运算符重载，则系统也会
    //创建一个默认的=运算符重载，只做一些基
    //本的拷贝工作
    Complex &operator=(const Complex &rhs)
    {
        // 首先检测等号右边的是否就是左边的对象
        //本，若是本对象本身,则直接返回
        if ( this == &rhs ) 
        {
            return *this;
        }
             
        // 复制等号右边的成员到左边的对象中
        this->m_real = rhs.m_real;
        this->m_imag = rhs.m_imag;
             
        // 把等号左边的对象再次传出
        // 目的是为了支持连等 eg:    a=b=c 系统
        //首先运行 b=c
        // 然后运行 a= ( b=c的返回值,这里应该是
        //复制c值后的b对象)    
        return *this;
    }
};

linux 进程

进程是资源管理的最小单位，而线程是程序执行的最小单位
子进程如果对资源只是进行读操作，那么完全和父进程共享物理地址空间。
孤儿进程的父进程在它之前退出，会被 init 进程接管，不会造成资源浪费

引起进程调度的原因： 进程执行完毕，进程I/O请求队列，进程调用阻塞原语进入睡眠等状态

实现一个string类

能像 int 类型那样定义变量，并且支持赋值、复制。
能用作函数的参数类型及返回类型。
能用作标准库容器的元素类型，即 vector/list/deque 的 value_type。

已知类String的原型为：

class String
{
public:
     String(const char *str = NULL);// 普通构造函数
     String(const String &other);    // 拷贝构造函数
     ~ String(void);    // 析构函数
     String & operate =(const String &other);// 赋值函数
private:
     char *m_data;// 用于保存字符串
};

请编写String的上述4个函数。

//普通构造函数
String::String(const char *str)
{
        if(str==NULL)
        {
                m_data = new char[1]; 
                // 得分点：对空字符串自动申请存
                //放结束标志'\0'的//加分点：对m_data加NULL 判断
                *m_data = '\0';
        }    
        else
        {
         int length = strlen(str);
         m_data = new char[length+1];
         // 若能加 NULL 判断则更好
         strcpy(m_data, str);
        }
} 
// String的析构函数
String::~String(void)
{
        delete [] m_data; 
        // 或delete m_data;
}
//拷贝构造函数
String::String(const String &other) 　　　
// 得分点：输入参数为const型
{     
        int length = strlen(other.m_data);
        m_data = new char[length+1]; 　　　　
        //加分点：对m_data加NULL 判断
        strcpy(m_data, other.m_data);    
} 
//赋值函数
String & String::operate =(const String &other)
// 得分点：输入参数为const
型
{     
        if(this == &other)                  　
        //得分点：检查自赋值
                return *this; delete [] m_data; 　　
                //得分点：释放原有的内存资源
        int length = strlen( other.m_data );      
        m_data = new char[length+1]; 　
        //加分点：对m_data加NULL 判断
        strcpy( m_data, other.m_data );   
        return *this;     　　　　　　　　
        //得分点：返回本对象的引用  
}

注意代码的几个要点：

只在构造函数里调用 new char[]，只在析构函数里调用 delete[]。
赋值操作符采用了《C++编程规范》推荐的现代写法。
每个函数都只有一两行代码，没有条件判断。
析构函数不必检查 data_ 是否为 NULL。
构造函数 String(const char* str) 没有检查 str 的合法性，这是一个永无止境的争论话题。这里在初始化列表里就用到了 str，因此在函数体内用 assert() 是无意义的。

哈希函数构造冲突处理

构造：

数字分析
平方取中
除留取余
分段叠加

处理冲突：
1.开放地址（线性探测再散列、二次探测再散列、伪随机探测再散列）
2.链地址
3.再哈希法
4.建立公共溢出区

树

B树：二叉树，每个节点只存储一个关键字，等于则命中，小于则走左节点，大于则走右节点。
B-树：多路搜索树
B+树：所有关键字在叶子节点中出现。在B- 树的基础上增加叶子节点的链表指针，到叶子节点才能命中。
B*树：非叶子节点也添加链表指针，提高命中率。

虚函数（Virtual Function）纯虚函数、虚函数表（Virtual Table）

C++“虚函数”的存在是为了实现面向对象中的“多态”，即父类指针或者引用指向其子类实例，然后通过父类指针（或引用）调用实际子类的成员函数。
一个类只需要一个虚表，同一个类的所有对象使用同一个虚表。
对象内部包含一个虚表指针指向所用的虚表
虚函数为了实现动态绑定。
纯虚函数为了引入派生接口。

逻辑地址虚拟地址物理地址

逻辑地址（Logical Address）是指由程序产生的与段相关的偏移地址部分。
线性地址（Linear Address）是逻辑地址到物理地址变换之间的中间层。

死锁

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

互斥条件：一个资源每次只能被一个进程使用。
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
不可剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。
循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

CPU调度算法

先到先服务FCFS(first-come, first-server)
最短作业优先调度SJF(shortest-job-first)
优先权调度
轮转法调度
多级队列调度(multilevel queue-scheduling algorithm)
多级反馈队列调度算法

Linux提供两种独立进程调度算法。一种是分时算法，用于在多个进程之间进行公平可抢占调度，一种是为了实时任务设计的，Linux只允许在用户模式下运行的进程被抢占

C++11 特性

右值引用

实现了转移语义和精确传递。
主要目的：

消除连个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率。
能够更简洁明确地定义泛型函数。

分布式存储

云计算分布式存储系统

Google的GFS 和Hadoop

整体架构

逻辑层是存储服务的使用方。系统由两部分组成，一部分是数据仓库所包含的模块直接提供数据存储服务的核心部分，由接入层、数据层、配置运维中心组成；另一部分是辅助系统，主要负责系统的监控、运维和运营备份系统、监控系统、运维管理系统、用户运营系统。

一致性模型

数据一致性模型包括以下三种：

弱一致性(Weak)：写入一个新值后，读操作在其他副本上不能保证读取到最新值。
最终一致性(Eventually)：写入一个新值后，在一个时间窗口后可以读出来。
强一致性：新数据写入后，在任意时刻的任意一个副本都能读到新值。

ACID特性

在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。
在数据库系统中，一个事务是指：由一系列数据库操作组成的一个完整的逻辑过程。

CAP原理

一致性（Consistence) （等同于所有节点访问同一份最新的数据副本）
可用性（Availability）（每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）
分区容错性（Network partitioning）（以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择[3]。）

NWR模型

用于控制一致性级别的策略。将CAP选择权交给用户

两阶段提交（Two Phase Commit）

第一阶段主控节点询问所有节点是否可以提交操作
第二阶段根据执行操作
第一阶段投票，第二阶段做决定是否执行的算法
2PC 协议用于保证属于多个数据分片上的操作的原子性。这些数据分片可能分布在不同的服务器上，2PC 协议保证多台服务器上的操作要么全部成功，要么全部失败。

Paxos算法

分布式选举算法
Paxos 协议用于保证同一个数据分片的多个副本之间的数据一致性。

数据分片方法

划分号段
取模
检索表
一致性哈希

虚拟化技术

从技术上讲，虚拟化是一种在软件中仿真计算机硬件，以虚拟资源为用户提供服务的计算形式。旨在合理调配计算机资源，使其更高效地提供服务。它把系统各硬件之间的物理划分打破，从而实现架构的动态化，实现物理资源的集中管理和使用。虚拟化的最大好处是增强系统的弹性和灵活性，降低成本、改进服务、提高资源利用率。
从表现形式上看，分为两种应用模式。一种是讲一台性能强大的服务器虚拟成多个独立的小服务器。二是讲多个服务器虚拟成一个强大的服务器。
CPU虚拟化技术：Intel的VT-x，AMD的AMD-V
虚拟化软件：VMWare、微软的Hyper-V、思杰的Xen、KVM、OpenVZ等

KVM（Kernel-based Virtual Machine）基于内核的虚拟机

VMM (Virtual Machine Monitor, a.k.a Hypervisor)

一致性哈希

一致性hash算法解决了分布式环境下机器增加或者减少时，简单的取模运算无法获取较高命中率的问题。通过虚拟节点的使用，一致性hash算法可以均匀分担机器的负载，使得这一算法更具现实的意义。

负载均衡与hash算法
分布式系统中，当服务增长到一定规模时，惯常的做法是集群化，引入负载均衡。好处是：高可用，解耦，透明化了集群的内部细节（外部都通过负载均衡服务器通信，然后由负载均衡服务器分发请求）
一致性Hash
当节点数量改变时，能够使失效的缓存数量尽可能少。

一致性hash环数据结构，环的起点是0，终点是$x^32-1$，并且起点和终点相连。
将对象和机器都放到hash环上，按照规则为对象选择机器。处理器增减的时候，只有部分对象被重新分配，其他对象仍在原有机器上。
基本思想：

object求hash
cache也求hash，然后把object和cache的hash值放到一个hash空间，通过一定规则决定每个object落在哪一个cache中。

虚拟节点：引入虚拟节点是为了使落在每个cache的概率接近。实质是做了两次matching。

数据库

NoSQL 非关系型数据库，用于超大规模的数据存储，不需要固定的模式，无需多余操作就可以横向扩展。需要进一步的数据挖掘和分析。

Key-Value存储（基于Redis）：

高可用系统（High Availability）

让计算环境（软硬件）做到full-time的可用性

对软硬件的冗余，以消除单点故障
对故障的检测和恢复。
需要可靠的交汇点（CrossOver）

设计原理：

要做到数据不丢，就必须持久化
要做到服务高可用，就必须要有复用，
要做到复制，就会有数据一致性问题

设计题

基本可以使用google的三大技术，GFS，MapReduce，BIgTable。
淘宝微博采用的架构：Redis/MySQL/TFS+sharding+cache
前端cache用于提高响应速度，后端数据库用于数据的永久存储，sharding用于在多台机器间分摊负载。
问题：扩展性、容错性差，维护成本高。
新架构：
GFS：可扩展的分布式文件系统，用于大型、分布式、大量数据访问的应用，运行与廉价普通机器，提供容错功能。开源界使用HDFS。
MapReduce：针对分布式并行计算的一套编程模型。接口简单自动备份，自动容错和隐藏跨机器间的通信。
BigTable：用来存储结构化数据。开源实现有Cassandra、HBase等

高并发系统设计：关键技术点：缓存、索引、数据分片、锁粒度小。
副本存放策略：大文件切分成小block，以block为单位存放到三份不同的节点，如果不考虑跨数据中心，两个副本存放在同一个机架的不同节点，另一个副本存放在另一个机架，效率和可靠性都是最优的。

读写冲突
对于一块存储空间，单进程读写是最简单的设计，没有读写冲突的问题，但是处理能力会成为瓶颈。有必要使用多进程或多线程并发的方式，就引入了读写冲突。
写进程冲突：如果多个写进程并发操作同一块存储空间，需要使用互斥锁机制，把单机的存储空间划分为多个存储单元，每个存储单元有一个写进程处理，在并发的同时也保证了互斥，这种无锁的实现性能更好。
读进程冲突：通过校验来解决，在数据中记录一个校验值，每次写入就更新校验值。为了降低读写冲突的概率，不在原来的定长块链上进行覆写，二是分配新的定长块链写入数据。
适合写少读多的场景

读写速度提高：将随机写转化为顺序写，BigTable模型，将并发写的大批数据放到一个内存表（memtable）中，当表增大到一定程度后，顺序写入磁盘表。如果读并发度极高才采用类似手段

Linux

文件类型

- 普通文件
d 目录文件
c 字符设备文件猫等串口设备等
b 块设备文件硬盘光驱等
s 套接字文件
符号链接文件

Linux 相关问题，以及个人遇到问题

dpkg 安装文件出错
可能是因为机器为64位，缺少支持32位架构

sudo dpkg –add-architecture i386
sudo apt-get -f -y install
英文版无法安装中文输入法
安装fcitx框架注销用户等
vi编辑文件无权限保存

: w ! sudo tee > /dev/null %
! ：执行外部shell命令管道
% ：扩展成当前文件名
/dev/null ：显式的丢掉标准输出的内容。

进程间通信

管道（pipe），有名管道（FIFO）
信号（signal）
消息队列
共享内存
信号量
套接字（socket）
管道是半双工的，数据仅能单向流动；只能用于父子进程或兄弟进程间

共享内存实现

1.进程首先分配内存
2.随后需要访问这个共享内存块的每一个进程都必须将这个共享内存绑定到自己的地址空间中。
3.当完成通信后，所有的进程都将脱离共享内存，并且由一个进程释放该共享内存块。

执行：

mutex对象，锁定共享区域
将要通信的数据写入（读取）共享区域
释放mutex对象

socket 编程

常见socket类型：

流式套接字（SOCK_STREAM）
面向连接，针对于面向连接的TCP服务应用
数据报套接字（SOCK_DGRAM）
无连接，面相UDP
原始套接字（SOCK_RAW）

利用socket建立网络连接

建立socket连接至少需要一对套接字，客户端ClientSocket，服务器端ServerSocket。包括三个步骤：服务器监听，客户端请求，连接确认。

服务器监听：服务器端套接字并不定位具体的客户端套接字，而是处于等待连接状态，实时监控网络状态，等待客户端的连接请求。
客户端请求：指客户端的套接字提出连接请求，要连接的目标是服务器端的套接字。
连接确认：当服务器端套接字监听到或者说接受到客户端的连接请求，就响应客户端套接字的请求，简历一个新的线程，把服务器端套接字的描述发给客户端，一旦客户端确认了此描述，双方就正式建立连接。

大端模式小端模式判断

小端（低地址存放低位）

int i = 1;   
   char *p = (char *)&i;   
   if(*p == 1)     
         printf("Little Endian"); 
   else
         printf("Big Endian");

数据存储优先顺序：

Internet数据以高位字节优先（大端模式）在网络上传输，PC通常采用小端（低位字节优先）
htons() ntohs() htonl() ntohl()
h: host
n: network
s: short（16位IP端口号）
l: long （IP地址）

I/O多路复用解决方法

非阻塞
异步处理（fcntl()）
多路复用处理（select() 或 poll()）
多线程编程

OSI网络模型

OSI（Open System Interconnection，开放系统互联）
http 协议应用层
tcp协议传输层
ip协议网络层

TCP/IP

TCP (Transmission Control Protocol)和UDP(User Datagram Protocol)协议属于传输层协议。
其中TCP提供IP环境下的数据可靠传输。
TCP提供超时重发、丢弃重复数据、检验数据、流量控制等功能。
通俗说，它是事先为所发送的数据开辟出连接好的通道，然后再进行数据发送；
而UDP则不为IP提供可靠性、流控或差错恢复功能。传输数据有大小限制。
一般来说，TCP对应的是可靠性要求高的应用，而UDP对应的则是可靠性要求低、传输经济的应用。

TCP： Telnet、FTP、SMTP
UDP： NFS、SNMP、DNS、TFTP

TCP的3次握手

（A->B）客户端A向服务器端主机B发送一个包含SYN（Synchronize）标志的TCP报文，SYN同步报文会指明客户端使用的端口以及TCP连接的初始序号；
（B->A）：主机B在收到客户端的SYN报文后，将返回一个SYN+ACK(Acknowledgement)的报文，表示接受请求，同时TCP序号加一；
（A->B）：主机A返回一个确认报文ACK给服务器端，同样TCP序号加一，完成一个TCP连接。

可靠传输的核心思想：保证数据可靠传输，又要提高传输效率
为什么需要三次握手：为了防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误
四次握手：tcp关闭链接四次握手原因在于tpc链接是全双工通道，需要双向关闭。

http常见状态码

1开头临时响应，需要继续执行其他操作
2开头重稿处理请求
3开头重定向，表示要完成请求需要进一步操作
4开头请求错误
400 服务器不理解
403 服务器拒绝请求
404 未找到网页
5开头服务器错误
500 服务器错误

内存管理

Linux内存管理的基本思想之一，是只有在真正访问一个地址的时候才建立这个地址的物理映射。

shell统计文本中单词出现次数

脚本

#！/bin/bash
if [ $# -eq 0 ]
then
echo "Usage: $0 args error"
exit 0
fi
if [ $# -ge 2 ]
then
echo "analyse the first file $1"
fi
filename = $1
grep -E -o "\b[[:alpha:]]+\b"  $filename | awk ' { count[$0]++ } END{printf("%-20s%s\n","Word","Count");
for(word in count)
{ printf ("%-20s%s\n",word,count[word] ) } }'

[[:alpha:]] 代表字母
[[:alnum:]] 代表字母和数字字符
[a-zA-Z0-9] 代表单个字母和数字字符

ps-按进程消耗内存多少排序

ps -eo rss,pmem,pcpu,vsize,args | sort -k 1 -r -n | less

解析:
-e 是显示所有进程, -o是定制显示信息的格式

rss: resident set size, 表示进程占用RAM(内存)的大小，单位是KB
pmem: %M, 占用内存的百分比
pcpu：%C，占用cpu的百分比
vsize: 表示进程占用的虚拟内存的大小，KB
args：进程名（command）

sort命令对ps结果进行排序
-k 1 :按第一个参数 rss进行排序
-r：逆序
-n：numeric，按数字来排序

概率论

条件概率：$ p(B|A)=\frac {P(AB)} {P(A)}$

贝叶斯公式：$ P(B_i|A) = \frac {P(B_i)P(A|B)} {\sum ^n_{j=1}P(B_j)P(A|B_j)}$

排列：$A^m_n=n(n-1)(n-2)\dots(n-m+1) = \frac {n!} {(n-m)!}$

组合：$C^m_n = \frac {A^m_n} {m!} = \frac {n!} {m!(n-m)!}$

德梅齐里亚克砝码问题：一位商人有一个40磅重的砝码，由于跌落在地而碎成4块，称得每块碎片的重量都是整磅数，而且可以用这4块来称出从1到40磅之间的任意整数磅的重物，请问这4块碎片分别为多重？
1，3，9，27，。。。，2M+1。

全排列(递归的思路)：

打印1到最大的n位数

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <cstring>
void Print1ToMaxRecursively(char *number, int length, int index);
void PrintNum(char *number);
void Print1ToMax(int n)
{
    if(n<=0)
        return;
    char *number = new char[n+1];
    number[n] = '\0';
    for(int i=0; i<10; ++i)
    {
        number[0] = i + '0';
        Print1ToMaxRecursively(number, n, 0);
    }
}
void Print1ToMaxRecursively(char *number, int length, int index)
{
    if (index == length - 1)
    {
        PrintNum(number);
        return;
    }
    for(int i=0; i<10; ++i)
    {
        number[index+1] = i + '0';
        Print1ToMaxRecursively(number, length, index+1);
    }
}
void PrintNum(char *number)
{
    bool isBegin0 = true;
    int nlength = strlen(number);
    for(int i=0; i<nlength; ++i)
    {
        if(isBegin0 && number[i] != '0')
            isBegin0 = false;
        if(!isBegin0)
        {
            printf("%c", number[i]);
        }
    }
    printf("\t");
}
int main()
{
    int n;
    std::cin >> n;
    Print1ToMax(n);
}

字符串的全排列

#include <iostream>
#include <vector>
using namespace std;
void Per(string str, int begin, int end, vector<string> &result)
{
    if(str.empty())
        return;
    if(begin == end)
    {
        result.push_back(str);
    }
    for(int i=begin; i<end; ++i)
    {
        if(i!=begin && str[i] == str[begin])
            continue;
        swap(str[begin], str[i]);
        Per(str, begin+1, end, result);
        swap(str[begin], str[i]);
    }
}
int main()
{
    string input;
    cin >> input;
    vector<string> result;
	
    Per(input, 0, input.size(), result);
    
	vector<string>::iterator it = result.begin();
    for(;it!=result.end();++it)
    {
        cout << *it << endl;
    }
    return 0;
}

框架名词

Redis：基于Key-Value对的NoSQL数据库，可以当作一个轻量级队列服务应用。
memcached：是一套分布式的高速缓存系统，
SQL注入：利用未过滤、未审核用户输入的攻击方法，让应用运行本不该运行的SQL代码。
缓冲区溢出：向程序输入缓冲区写入使之溢出的内容，从而破坏程序运行，趁终端之际去的程序乃至系统控制权。
Kafka：是一种分布式的，基于发布/订阅的消息系统。
数字签名（digital signature）：发送方的私钥加密原文信息使用hash函数生成的摘要，附在密文后边。
数字证书（digital certificate）：证书中心（certificate authority， CA）为公钥做认证。证书中心用自己私钥，对用户的公钥和相关信息加密，生成数字证书。接收方可以用CA的公钥解开数字证书，得到发送方的真实公钥，证明数字签名的来源正确性。

项目介绍

项目背景
项目怎么设计的
技术选型和对比
实现的细节
项目最终的效果
团队管理
技术细节
遇到困难与解决
成果
对未来规划

首先，研究生期间做的是一个关于加密文件系统的项目，目标是设计并实现一种基于linux 的透明加密文件系统。

我比较完整的参与了整个项目，包括需求分析，整体架构，代码实现，文档撰写等工作。
刚开始阶段，主要是对相关产品的调研，对同类产品的优劣进行对比。我们几个团队在不同的平台独立实现需求的功能。我负责的小组经过前期的调研，初步拟定三种可行路线，1是直接修改内核源码。又分为两种思路：一种是在普通文件系统中直接加入加密功能，考虑到不同文件系统的兼容，了解到虚拟文件系统的相关概念后，提出第二种方案是修改VFS层的读写函数vfs_read和vfs_write，屏蔽了底层具体文件系统的操作第一种方案有其固有的优势，在效率安全性上有一定的保障，因为加密操作在内核层完成，破解就相当于攻破了整个系统，但是其开发难度较大，而且使用不便不利于推广和升级。第二种是直接在应用层做，这种方法最简单，但是在稳定性，安全性和效率的存在严重问题。结合前两种的优劣，我们考虑折衷方案，将加密服务集成到文件系统这一层面来解决上面的问题。加密文件的内容一般经过对称密钥算法加密后以密文的形式存放在物理介质上。
这种加密文件系统可以看成一个加密/解密的转换层，而并不是一个真实的全功能文件系统。堆叠式加密文件系统没有相应的磁盘布局，也不实现数据在物理介质上存取的功能。它必须架构在别的普通文件系统之上，读加密文件时先通过下层普通文件系统将文件的密文读入内存，解密后再将明文返回到上层的用户进程；写加密文件时先将内存中的明文加密，然后传给下层普通文件系统，由它们真正地写入物理介质。堆叠式加密文件的优势在于实现相对容易（因为功能相对简单）且用户可以任意选择下层的普通文件系统来存放加密文件。

技术细节：

遇到问题与解决：
搭建环境问题比较low

wrapfs文件系统无法安装。根据官网说明通过打补丁的方法添加到源码树，编译即可生成对应的.ko文件，然后挂载即可使用。中间遇到两个问题，一是无法编译，原因是内核版本和补丁文件版本不一致。解决方案：修改源码树中Makefile的版本号（extraversion=-XX-generic），然后编译，生成version.h 和utsrelease.h 里面包含版本信息，在编译模块的时候需要使用。由于使用的内核源码树和当前系统ubuntu内核版本不完全一致（ubuntu有个后缀-XX-generic）。
无法装载模块。先查看出错的日志信息，发现是版本问题，但是之前已经对版本号进行了修改，对比当前系统其他可用模块的modinfo信息，在另一台手动编译内核的机器上却没有问题。为了排除是不是之前版本修改的问题，写了一个只有执行内核打印的模块，在编译后同样无法运行，同时发现生成的Module.symvers文件为空。搜索相关资料发现，Linux 对可装载模块采取了两层验证：模块的 CRC 值校验和 vermagic 的检查。 linux2.6之后的版本在加载模块的时候采用了版本校验机制，当期望加载模块的系统环境与当前环境不一样的时候，就会出现加载失败
内核调试困难。由于条件所限，无法使用kgdb等，只能使用printk打印。注释代码，来锁定问题。大部分问题出在kmalloc和对用户空间内核空间转换上。
内存泄漏，kernel oops

产品优势是：
1、透明，可以无缝升级。
2、兼容，可以适用不同的操作系统。
3、可定制化，针对企业不同需求提供不同安全等级。
4、后续可提供产品维护，容灾备份，以及数据分析等功能（作为精细化，提高用户体验的部分）。

提问：

OJ平台 输入输出转换问题