子非鱼的技术博客

面试题汇总

C++

基础知识

C 和 CPP 区别是什么

C++编译过程

预处理：展开include和define

编译：转化为汇编代码

汇编：转化为二进制机器码

链接：将目标和其需要的库链接成可执行文件

设计原则

依赖倒置原则（DIP）

高层模块（稳定）不应该依赖于低层模块（变化），二者都应该依赖 于抽象（稳定）

抽象（稳定）不应该依赖于实现细节（变化），实现细节应该依赖于 抽象（稳定）

开放封闭原则（OCP）

对扩展开放，对更改封闭

类模块应该是可扩展的，但是不可修改

模版方法（Template Method）

模式动机

一些功能在底层开发模块时不知具体实现，而需要在高层模块实现

1. 选择合适的模型

对于回归或分类问题使用合适的模型，在本文中对于回归问题使用线形回归模型，对于分类问题使用Logistic回归模型

2. 如何判定当前模型及参数是符合现实要求的（Cost Function）

$$
J(w,b) = \frac{1}{2m} \sum\limits_{i = 0}^{m-1} (f_{w,b}(x^{(i)}) - y^{(i)})^2
$$

$$
f_{w,b}(x^{(i)}) = wx^{(i)} + b \tag{2}
$$

计算预测值与现实值的均方误差后取平均（除以2是为了在求导时与平方的2约去）

3. 数据预处理

特征缩放（Feature Scaling）

如果不同属性的取值返回相差过大则会导致模型收敛得很慢，所以要对属性值做映射。

常用缩放方法：
均值标准化
$$
x_i := \dfrac{x_i - \mu_i}{max - min}\tag{Mean normalization}
$$

图的建立

邻接表

1
2
3
4
5
6
7

vector<vector<int>> build_tree_with_table(int node_count,vector<vector<int>> prerequisites)
{
    vector<vector<int>> graph(node_count);
    for (int i=0;i<prerequisites.size();i++)
        graph[prerequisites[i][0]].push_back(prerequisites[i][1]);
    return graph;
}

邻接矩阵

1
2
3
4
5
6
7

vector<vector<int>> build_tree_with_martix(int node_count,vector<vector<int>> prerequisites)
{
    vector<vector<int>> graph(node_count,vector<int>(node_count,0));
    for (int i=0;i<prerequisites.size();i++)
        graph[prerequisites[i][0]][prerequisites[i][1]] = 1;
    return graph;
}

图的遍历（获取所有路径）

DFS

使用on_path判断当前访问的结点是否在当前访问列表中，如果在则表示有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<vector<int>> path_lists;
vector<int> path;
vector<bool> on_path;
void traverse_dfs(vector<vector<int>> graph,int start)
{
if (src < 0 || src >= graph.size()) return;
    if (on_path[start] == true)
        return;
    path.push_back(start);
    on_path[start] = true;
    path_lists.push_back(path);
    
    for (int i=0;i<graph[start].size();i++)
        traverse_dfs(graph, graph[start][i]);
    path.pop_back();
    on_path[start] = false;
}

判断图是否有环

基础

竖向堆叠起来的输入特征被称作神经网络的输入层（the input layer）。

神经网络的隐藏层（a hidden layer）。“隐藏”的含义是在训练集中，这些中间节点的真正数值是无法看到的。

输出层（the output layer）负责输出预测值。

正向传播（推理）

概念

通过线性回归对不同的输入x计算，之后通过激活函数（Activation Function）映射后输出到下一层

激活函数

第五章 面向对象编程（二）

引用的其他用法

引用作为成员变量

函数返回引用，可以将返回值做左值

拷贝构造

通过类的其他对象初始化当前对象（有默认拷贝构造方法，成员对成员的拷贝，可能发生对象的嵌套拷贝）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//During call by value
void roster(Person){};
Person child("Ruby");
roster(child); // call copy ctors

// During initialization, call copy ctor
Person baby_a("Fred");
Person baby_b = baby_a;
Person baby_c(baby_a); // same as above

//During function return
Person captain(){
  Person player("George");
  return player;
}

T::T(const T&)

建议每个类提供默认构造函数，拷贝构造函数，虚函数

其他

类不是实体，对象是实体

成员变量（filed）属于对象

成员函数（member function）属于类

Big Three（构造函数，拷贝构造，拷贝赋值）

构造函数

初始化列表

列表初始化（initialize list）仅对成员变量初始化。

在构造函数里对成员变量初始化则为先初始化（默认）后赋值，故所有成员变量必须要有默认的初始化方法（成员变量包含其他类但该类没有默认构造函数则会报错）。构造函数无法主动调用。

尽量使用列表初始化

1
2
3
4
5
6

class A{
  public:
  	int a;
    A(int i):a(i){};  //initialize list
  	// A(int i):{a=i;} 
};

当执行throw时，throw后的语句都不执行，控制权转移到与之对应的catch模块

退出catch后，catch模块中的局部变量将会销毁

当异常处理完毕后，异常对象将被销毁

1
2
3
4
5
6
7

try{
  //...
}catch (exception_a){
  //...
}catch (exception_b){
  //...
}

捕捉catch（对于每个catch执行下述步骤）

1. 判断是否是精确匹配
2. 派生类向基类转换（仅引用和指针类型）
3. （…）匹配所有

其中一个被捕捉，跳过下面的catch

重新抛出

一条catch语句通过重新抛出的稻作将异常传递给另一个catch语句

1

throw;

static全局变量

static变量只能在当前文件访问，其他文件不能通过extern访问

static局部变量

定义时创建，程序结束时销毁，修改了生命周期，作用域不变

static类

static对象的构造在main函数前执行，析构在main函数结束后

static成员变量

存在于所有对象且保持一致，可在其他文件访问

不能在初始化列表初始化

需在类外定义，因为class内语句都是声明

第二章 C++基础——指针

指针是一个变量，其存储的是值的地址，而不是值本身

使用常规变量时，值是指定的量，而地址是派生量，而指针相反

OOP强调的是在运行阶段（而不是编译阶段）进行决策，提供了灵活性，对于内存管理也更加高效

初始化指针

1
2

int* ptr_a;
double* ptr_b;

初始化时必须指定所指元素类型，因为对所有指针来说其都是代表一个初始地址，但从该初始地址读多少字节则由指针类型判断

指针也是作为变量存储，只不过其内存空间存的是地址。指针p1,p2有各自的地址&p1,&p2。长度为4B（32位）或8B（64位）。p1,p2表示存储的所指向元素的地址。*p1表示指向元素的值。

指针注意事项

在C++中创建指针时，计算机将分配用来存储地址的内存，但不会分配用来存储指针所指向的数据的内存（指向不确定）。另外，一定要在对指针提取（*）之前，将指针初始化为一个确定的、适当的地址。