2020年字节跳动秋招C++精选面试题及答案(上)

tech2023-05-21  91

1. C++智能指针如何解决内存泄露问题

1.shared_ptr共享的智能指针

std::shared_ptr使用引用计数,每一个shared_ptr的拷贝都指向相同的内存。在最后一个shared_ptr析构的时候,内存才会被释放。

可以通过构造函数、std_make_shared辅助函数和reset方法来初始化shared_ptr:

// 构造函数初始化

std::shared_ptrp ( new int(1) ) ;

std::shared_ptrp2 = p ;

// 对于一个未初始化的智能指针,可以通过reset方法来初始化。

std::shared_ptrptr; ptr.reset ( new int (1) ) ;

if (ptr) {cout << “ptr is not null.\n” ; }

不能将一个原始指针直接赋值给一个智能指针:

std::shared_ptrp = new int(1) ;// 编译报错,不允许直接赋值

获取原始指针:

通过get方法来返回原始指针

std::shared_ptrptr ( new int(1) ) ;

int * p =ptr.get () ;

指针删除器:

智能指针初始化可以指定删除器

void DeleteIntPtr ( int * p ) {

delete p ;

}

std::shared_ptrp ( new int , DeleteIntPtr ) ;

当p的引用技术为0时,自动调用删除器来释放对象的内存。删除器也可以是一个lambda表达式,例如

std::shared_ptrp ( new int , [](int * p){delete p} ) ;

注意事项:

(1).不要用一个原始指针初始化多个shared_ptr。

(2).不要再函数实参中创建shared_ptr,在调用函数之前先定义以及初始化它。

(3).不要将this指针作为shared_ptr返回出来。

(4).要避免循环引用。

2.unique_ptr 独占的智能指针

unique_ptr是一个独占的智能指针,他不允许其他的智能指针共享其内部的指针,不允许通过赋值将一个unique_ptr赋值给另外一个unique_ptr。

unique_ptr不允许复制,但可以通过函数返回给其他的unique_ptr,还可以通过std::move来转移到其他的unique_ptr,这样它本身就不再拥有原来指针的所有权了。

如果希望只有一个智能指针管理资源或管理数组就用unique_ptr,如果希望多个智能指针管理同一个资源就用shared_ptr。

3.weak_ptr弱引用的智能指针

弱引用的智能指针weak_ptr是用来监视shared_ptr的,不会使引用计数加一,它不管理shared_ptr内部的指针,主要是为了监视shared_ptr的生命周期,更像是shared_ptr的一个助手。

weak_ptr没有重载运算符*和->,因为它不共享指针,不能操作资源,主要是为了通过shared_ptr获得资源的监测权,它的构造不会增加引用计数,它的析构不会减少引用计数,纯粹只是作为一个旁观者来监视shared_ptr中关离得资源是否存在。

weak_ptr还可以用来返回this指针和解决循环引用的问题。

需要完整面试题集与各大一线互联网面试题公众号关注零声学院免费领取!

2. linux中软连接和硬链接的区别

原理上,硬链接和源文件的inode节点号相同,两者互为硬链接。软连接和源文件的inode节点号不同,进而指向的block也不同,软连接block中存放了源文件的路径名。

实际上,硬链接和源文件是同一份文件,而软连接是独立的文件,类似于快捷方式,存储着源文件的位置信息便于指向。

使用限制上,不能对目录创建硬链接,不能对不同文件系统创建硬链接,不能对不存在的文件创建硬链接;可以对目录创建软连接,可以跨文件系统创建软连接,可以

对不存在的文件创建软连接。

3. TCP的拥塞控制机制是什么?请简单说说

我们知道TCP通过一个定时器(timer)采样了RTT并计算RTO,但是,如果网络上的延时突然增加,那么,TCP对这个事做出的应对只有重传数据,然而重传会导致网络的负担更重,于是会导致更大的延迟以及更多的丢包,这就导致了恶性循环,最终形成“网络风暴” —— TCP的拥塞控制机制就是用于应对这种情况。

首先需要了解一个概念,为了在发送端调节所要发送的数据量,定义了一个“拥塞窗口”(Congestion Window),在发送数据时,将拥塞窗口的大小与接收端ack的窗口大小做比较,取较小者作为发送数据量的上限。

拥塞控制主要是四个算法:

1.慢启动:意思是刚刚加入网络的连接,一点一点地提速,不要一上来就把路占满。

连接建好的开始先初始化cwnd = 1,表明可以传一个MSS大小的数据。

每当收到一个ACK,cwnd++; 呈线性上升

每当过了一个RTT,cwnd = cwnd*2; 呈指数让升

阈值ssthresh(slow start threshold),是一个上限,当cwnd >= ssthresh时,就会进入“拥塞避免算法”

2.拥塞避免:当拥塞窗口 cwnd 达到一个阈值时,窗口大小不再呈指数上升,而是以线性上升,避免增长过快导致网络拥塞。

每当收到一个ACK,cwnd = cwnd + 1/cwnd

每当过了一个RTT,cwnd = cwnd + 1

拥塞发生:当发生丢包进行数据包重传时,表示网络已经拥塞。分两种情况进行处理:

等到RTO超时,重传数据包

sshthresh = cwnd /2

cwnd 重置为 1

3.进入慢启动过程

在收到3个duplicate ACK时就开启重传,而不用等到RTO超时

sshthresh = cwnd = cwnd /2

进入快速恢复算法——Fast Recovery

4.快速恢复:至少收到了3个Duplicated Acks,说明网络也不那么糟糕,可以快速恢复。

cwnd = sshthresh + 3 * MSS (3的意思是确认有3个数据包被收到了)

重传Duplicated ACKs指定的数据包

如果再收到 duplicated Acks,那么cwnd = cwnd +1

如果收到了新的Ack,那么,cwnd = sshthresh ,然后就进入了拥塞避免的算法了。

4. 利用快速排序对单链表进行排序

#include<iostream> #include<ctime> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *sortList(ListNode *head) { if (head == NULL) return head; ListNode* tail=head; ListNode* end = tail; while (tail->next != NULL) { //if (tail->next->next == NULL) // end = tail; tail = tail->next; } qSortList(head, tail); return head; } ListNode* Partition(ListNode* head, ListNode* tail) { ListNode* newHead = new ListNode(0); newHead->next = head; ListNode* ipt = newHead, *jpt = head; int ar = tail->val; while (jpt != tail) { if (jpt->val < ar) { ipt = ipt->next; swap(ipt->val, jpt->val); } jpt = jpt->next; } ipt = ipt->next; swap(ipt->val, tail->val); return ipt; } void qSortList(ListNode*head, ListNode*tail) { if (head == NULL) return; if (tail == NULL) return; if (tail->next!=NULL && tail->next == head) return; else if (tail->next!=NULL && tail->next->next!=NULL && tail->next->next== head) return; if (head == tail) return; if (head->next == tail) { if (head->val > tail->val) swap(head->val,tail->val); return; } ListNode* mid = Partition(head, tail); ListNode*tail1 = head; if (tail1!=mid) while (tail1->next != mid) tail1 = tail1->next; ListNode*head2 = mid->next; qSortList(head, tail1); qSortList(head2, tail); } }; int main() { ListNode* head0 = new ListNode(200); ListNode* head = head0; srand(time(NULL)); for (int i = 0; i < 10000; i++) { ListNode* mNode = new ListNode(rand() % 4); head0->next = mNode; head0 = head0->next; } Solution sln; ListNode*res=sln.sortList(head); while (res->next != NULL) { cout << res->val << " "; res = res->next; } return 0; }

5.计算机为什么能识别二进制机器码?

1、计算机的理论基础

布尔代数是计算机的理论基础,

Boolean(布尔运算)通过对两个以上的物体进行并集、差集、交集的运算,从而得到新的物体形态。系统提供了4种布尔运算方式:Union(并集)、Intersection(交集)和Subtraction(差集,包括A-B和B-A两种)。

1)与逻辑和乘法

乘法原理中自变量是因变量成立的必要条件,与逻辑的定义正好和乘法原理的描述一致,所以与逻辑和乘法对应。

2)或逻辑和加法

加法原理中自变量是因变量成立的充分条件,或逻辑的定义正好和加法原理的描述一致,所以或逻辑和加法对应。

乘法就是广义的与逻辑运算,加法就是广义的或逻辑运算。与逻辑运算可以看作是乘法的特例。或逻辑运算可以看作是加法的特例。

总之,乘法原理、加法原理可以看作是与逻辑和或逻辑的定量表述;与逻辑和或逻辑可以看作是乘法原理、加法原理的定性表述。

通俗来讲:这是一门运用”与“”或“”“非”“假”“真”来描述任意两个量(可以是任何具体事物的或者抽象概念)的逻辑关系。

2、逻辑代数与计算机电路

应用于逻辑中,解释 0 为假,1 为真,∧ 为与,∨ 为或,¬为非。涉及变量和布尔运算的表达式代表了陈述形式,两个这样的表达式可以使用上面的公理证实为等价的,当且仅当对应的陈述形式是逻辑等价的。由于逻辑代数小的逻辑单元与二进制高度契合,再加上电路最为简单的开和关恰好也对应0和1,于是就有了依据逻辑代数理论创建一系列的电路在表达基础的逻辑理论,这就是计算机具有判断、计算能力的基础。

3、二进制机器识别过程

根据前面两点可以知道,如果选用二进制原理作为计算机的判断计算依据,将会使得电路制造的实现成为可能,但是自然界是不存在二进制的,为了处理这个问题,统一人为规定将其他非二进制数据表示成二进制机器码,供计算机读取。然而。随着对数据的处理能力要求越来越高,处理数据也越来越大,为了解决这个问题,汇编器出现,替代了将非二进制数据转化为二进制数据,但是这远远不足,为了更好处理,直接将硬件与汇编器组合,单独发展更高级汇编器(实质就是现在熟知的各类程序),这样,硬件与软件彻底分开。实质上就是将数据转化与判断和数据的录入、存储、输出彻底分开,使计算机的使用者可以完全不必再关注计算机的具体运算。

也就是说,计算机为什么能够识别二进制机器码,是因为有以逻辑代数原理制造的数字电路,为什么选用二进制已经解释过了。同时,也应该明白,为何程序会出现假,1为真,∧ 为与,∨ 为或,¬为非这五个元素,算法为何而来,指的就是优化数据之间的逻辑代数关系。

6.对于一颗二叉树,如何对此进行层次遍历,并且按行输出。

解法1: class Solution { public: vector<vector<int>> levelOrder(Node* root) { BFS(root, 0); return res; } public: void BFS(Node* node, int level) { if(node == nullptr) return; if(level == res.size()) res.push_back(vector<int> ()); res[level].push_back(node->val); for(auto n:node->children) BFS(n, level+1); } private: vector<vector<int>> res; }; 解法2: class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> output; if (!root) return output; queue<Node*> treeTemp; treeTemp.push(root); auto treeNum = treeTemp.size(); while (treeNum) { vector<int> valTemp; for (auto i=0; i<treeNum; ++i) { root = treeTemp.front(); valTemp.push_back(root->val); treeTemp.pop(); for (auto childTemp:root->children) treeTemp.push(childTemp); } output.push_back(valTemp); treeNum = treeTemp.size(); } return output; } };
最新回复(0)