小米软件开发二面和中兴软开一面

小米二面

1. 序列化二叉树和反序列化二叉树。
   题目见链接

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {
        queue<TreeNode*> q;
        q.push(root);
        string res;
        while(!q.empty()){
            int n=q.size();
            for(int i=0;i<n;i++){
                TreeNode *cur=q.front();
                q.pop();
                if(cur==nullptr){
                    res+="#";
                    res+=",";
                    continue;
                }else{
                    res+=to_string(cur->val);
                    res+=",";
                }
                q.push(cur->left);
                q.push(cur->right);
            }
        }
        char *ret=new char[res.size()+1];
        strcpy(ret, res.c_str());
        return ret;
    }
    TreeNode* Deserialize(char *str) {
        string s=str;
        if(s[0]=='#')
            return nullptr;
        queue<TreeNode*> q;
        TreeNode* head=new TreeNode(stoi(s));
        s=s.substr(s.find_first_of(',')+1);
        q.push(head);
        while(!q.empty()){
            TreeNode* cur=q.front();
            q.pop();
            if(s[0]=='#')
                cur->left=nullptr;
            else{
                cur->left=new TreeNode(stoi(s));
                q.push(cur->left);
            }
            s=s.substr(s.find_first_of(',')+1);
            if(s[0]=='#')
                cur->right=nullptr;
            else{
                cur->right=new TreeNode(stoi(s));
                q.push(cur->right);
            }
            s=s.substr(s.find_first_of(',')+1);
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2. 内存管理上，栈和堆
   栈：是由编译器在需要时进行自动分配，不需要时自动清除的变量存储区。通常存放局部变量、函数参数等。
   堆：是由new分配的内存块，由程序员进行释放，一般一个new与一个delete对应，一个new[]和一个delete[]对应
   自由存储区：是由malloc等分配的内存块，和堆十分相似，用free来释放。
   全局/静态存储区：全局变量和静态变量被分配到同一块内存中
   常量存储区：存放常量，不允许修改。
   栈和堆有什么区别：
   1）管理方式：栈是由编译器自动管理的，无需我们手动控制；对于堆，释放工作是由程序员控制。
   2）空间大小：堆是不连续的内存区域，堆大小受限于计算机系统中有效的虚拟内存。栈是一块连续的内存区域，大小是由os预定好的。
   3）碎片问题：对于堆，频繁的new和delete会造成内存空间的不连续，从而造成大量的碎片，使得程序效率降低。对于栈，不会存在这个问题，因为是先进先出的队列
   4）生长方向：堆是由低地址向高地址，而栈是由高地址向低地址
   5）分配方式：堆都是动态分配的。栈有两种，静态分配是由编译器完成的，比如局部变量的分配；动态分配是由alloca函数进行分配。
   6）分配效率： 栈是机器系统提供的数据结构，计算机会在底层对栈提供支持，分配专门的寄存器存放栈的地址，压出栈都有专门的指令执行。堆是由C/C++函数库提供的。
3. 进入一个函数之后，栈的分配是怎么去完成的
   栈的增长方向是向低地址，因而上方意味着低地址。任何一个函数，只能使用进入函数时栈指针向上部分的栈空间。调用函数，栈指针会向低地址增长，同时为形参和函数返回地址申请连续的地址空间。
   新的函数进入后，首先做一些必须的保存的工作，然后会调整栈指针，分配出本地变量所需的空间，然后执行函数中的代码，并执行完毕之后，根据调用者压入栈的地址，返回到调用者未执行的代码中继续执行。本地变量所需的内存的就在栈上，跟函数执行所需的其他数据在一起。当函数执行完成之后，这些内存就会释放。可以看出：
   1）栈上的分配极为简单，移动一下栈指针即可
   2）站上的释放也极为简单，函数执行结束时移动一下指针即可
   3）由于后进先出的执行过程，不可能出现内存碎片
4. new和malloc有什么区别
   区别：
   1）new返回指定类型的指针，并且可以自动计算所需要的大小；而malloc只管分配内存，并不能对所得的内存进行初始化，需要手动计算大小；
   2）malloc/free是C++/C的标准库函数，new/delete是C++的运算符
   3）malloc申请空间失败时，返回的是NULL，因此使用时必须判空，new不需要，但是new需要捕获异常
   4）申请自定义类型对象时，malloc/free只会开辟空间，不会调用构造函数与析构函数，而new在申请空间 后会调用构造函数完成对象的初始化，delete在释放空间前会调用析构函数完成空间中资源的清理
5. 像常用linux、安卓、其他的操作系统，我们一般通过malloc或者new会直接向操作系统申请内存吗？
   申请的是虚拟内存
   如果分配后的虚拟内存没有被访问的话，是不会将虚拟内存映射到物理内存。只有在访问已分配的虚拟地址空间的时候，操作系统会通过查找页表，发现虚拟地址对应的页没有在屋里内存中，就会触发去缺页中断，然后操作系统就会建立虚拟内存和物理内存之间的映射关系。
   malloc 通过brk()方式申请的内存，free 释放内存的时候，并不会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用；
   malloc 通过mmap()方式申请的内存，free 释放内存的时候，会把内存归还给操作系统，内存得到真正的释放。
6. 内存分配器了解吗
   负责内存分配与管理。内存分配器是所有容器的基础。主要分为两级，第一级分配器直接调用C函数分配和释放内存。第二级分配器内存池管理内存。如果申请的内存块足够大，启动第一级分配器。否则启动第二级。这种设计的优点就是可以快速分配和释放小块内存，同时避免内存碎片；缺点是内存池的生命周期比较长，并且很难显式释放。
   第一级分配器只是简单的调用malloc()、realloc()和free()来分配、重新分配和释放内存。
   第二级分配器需要维护16个空闲块链表和一个内存池。
7. new分配内存中间是做什么事情
   new 操作符的执行过程：
   1）调用operator new分配内存 ；
   2）调用构造函数生成类对象；
   3）返回相应指针。
   要实现不同的内存分配行为，应该重载operator new，而不是new。动态建立类对象，是使用new运算符将对象建立在堆空间中。这个过程分为两步，第一步是执行operator new()函数，在堆空间中搜索合适的内存并进行分配；第二步是调用构造函数构造对象，初始化这片内存空间。

在使用new申请空间分配时，系统会有记录表记录两个信息：分配空间的地址和分配空间的大小（以字节为单位），在使用delete收回内存空间时，首先系统会在记录表中找需要delete的地址：如果找到，就收回相应大小的内存空间，并在记录表中删除该条记录；如果未找到，则delete失败，运行报错。
对于类对象的delete操作，进行delete操作时首先会调用该类的析构函数，然后再收回内存空间。如果类对象是数组，那么如果使用delete，那么就只会析构数组首地址，然后当程序运行结束后收回内存；如果使用delete []，那么就会依次调用类对象数组中的析构函数，然后收回内存空间。

9. 通过new申请的对象，直接free会怎么样？
   free去释放new开出来的对象不会走析构函数，对象里有些动态开的空间释放不了就会导致内存泄漏。
10. delete和free有什么区别
    delete用于释放new分配的空间，free用于释放malloc分配的空间。
    delete[] 用于释放new[] 分配的空间。
    delete 释放空间时会调用相应对象的析构函数。
    调用free之前需要检查需要释放的指针是否 为空。而调用delete则不需要。
11. C++中的多态
    多态时C++面向对象三大特性之一。多态分为两类：
    1）静态多态：函数重载和运算符重载属于静态多态，复用函数名
    2）动态多态：派生类和虚函数实现运行时多态
12. 虚函数怎么实现的？
    每个虚函数都会有一个与之对应的虚函数表，该虚函数表的实质是一个指针数组，存放的是每一个对象的虚函数入口地址。对于一个派生类来说，他会继承基类的虚函数表同时增加自己的虚函数入口地址，如果派生类重写了基类的虚函数的话，那么继承过来的虚函数入口地址将被派生类的重写虚函数入口地址替代。那么在程序运行时会发生动态绑定，将父类指针绑定到实例化的对象实现多态。
13. C++中的struct和class的区别
    struct的默认继承权限和默认访问权限是public，而class的默认继承权限和默认访问权限是private。另外，class还可以定义模板类形参，比如template 。
14. C++中的类型强转（几个关键字）
    详情见链接
    1）static_cast：用于基本类型间的转换，但不能用于基本类型指针间的转换；用于有继承关系类对象之间的转换和类指针之间的转换；tatic_cast是编译期进行转换的，无法在运行时检测类型，所以类类型之间的转换可能存在风险；

#include
using namespace std;
int main(){
    int i=97;
    char c='c';
    cout<<i<<" "<<c<<" ";
    c=static_cast<char>(i);
    cout<<c<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11

2）const_cast：用于去除变量的const属性；
3）ynamic_cast：主要用于类层次间的转换，还可以用于类之间的交叉转换；dynamic_cast具有类型检查的功能，比static_cast更安全；
4）reinterpret_cast（直接从二进制位进行复制，不安全的转换）：用于指针类型间的强制转换；用于整数和指针类型间的强制转换；

15. int类型指针可以转换成int类型整数吗？
    可以，但会提示：从指针转换为更小的类型“int”会丢失信息。
    
16. int类型指针可以转换成char* 吗？
    见链接
17. stl中的string是怎么实现的呢？
    见链接
18. 智能指针，怎么去设计

#include
template<class T>
class SharedPtr{
private:
 
	T* _ptr;
	int* _count;
	mutex* _mt;//防止多线程安全问题
 
private:
	void AddCount(){
		_mt->lock();
		(*_count)++;
		_mt->unlock();
	}
 
	void ReleasePtr(){
		//是否需要删除锁
		bool flag = true;
		//加锁，防止线程安全
		_mt->lock();
		(*_count)--;
		if ((*_count) == 0){
			delete _ptr;
			delete _count;
			flag = false;//锁要在外面删除，需要解锁
		}
		_mt->unlock();
		//删除锁
		if (flag == false){
			cout << "delete" << endl;
			delete _mt;
		}
	}
 
public:
	//将外面申请的资源，托管给类的成员
	SharedPtr(T* ptr = nullptr)
		:_ptr(ptr)
		, _count(new int(1))//申请一份资源，初始化为1
		, _mt(new mutex)
	{}
 
	SharedPtr(SharedPtr<T>& sp){
		_ptr = sp._ptr;
		_count = sp._count;
		_mt = sp._mt;
		AddCount();
	}
	SharedPtr<T>& operator=(SharedPtr<T>& sp){
		//防止自己给自己赋值
		if (this != &sp){
			//是否管理资源
			if (_ptr){
				ReleasePtr();
			}
 
			_ptr = sp._ptr;
			_count = sp._count;
			_mt = sp._mt;
 
			AddCount();
 
		}
		return *this;
	}
 
	T& operator*(){
		return *_ptr;
	}
	T* operator->(){
		return _ptr;
	}
 
 
	//在对象析构时，自动释放资源
	~SharedPtr(){
 
		ReleasePtr();
 
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

19. 磁盘的寻道算法
    先来先服务（First-Come，First-Served，FCFS），顾名思义，先到来的请求，先被服务。
    最短寻道时间优先（Shortest Seek First，SSF）算法的工作方式是，优先选择从当前磁头位置所需寻道时间最短的请求；
    扫描算法：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向；
    循环扫描（Circular Scan, CSCAN ）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。
    LOOK 算法，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求。

中兴一面

1. 你对C++面向对象的理解
   见链接

2. 深拷贝和浅拷贝
   浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以 当继续对资源进项操作时，就会发生发生了访问违规。

3. stl中的数据结构和算法之间用什么进行连接
   迭代器

4. 迭代器你怎么理解的
   迭代器：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。每个容器都有自己专属的迭代器。

5. 一个map> val，取出第一个map中最大key中的value值

#include
#include
using namespace std;
int main(){
    map<int, map<int, int> > val;
    int Max=INT_MIN;
    map<int, int> res;
    for(map<int, map<int, int> >::iterator it=val.begin();it!=val.begin();it++){
        if(Max<it->first){
            Max=it->first;
            res=it->second;
        }
    }
    for(map<int, int>::iterator iter=res.begin();iter!=res.end();iter++){
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    return 0;
}

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

6. makefile文件里面包含什么？
   Makefile 描述的是文件编译的相关规则，它的规则主要是两个部分组成，分别是依赖的关系和执行的命令
7. 内核态和用户态了解吗？
   原因：在 CPU 的所有指令中，有些指令是非常危险的，如果错用，将导致系统崩溃，比如清内存、设置时钟等。如果允许所有的程序都可以使用这些指令，那么系统崩溃的概率将大大增加。
   当进程运行在内核空间时就处于内核态，而进程运行在用户空间时则处于用户态。
8. 内核态和用户态之间怎么通信的？
   见链接
9. 临界区了解吗？
   临界资源：一次仅允许一个进程使用的资源。例如：物理设备中的打印机、输入机和进程之间共享的变量、数据。
   临界区：每个进程中，访问临界资源的那段代码。