美文网首页
不会的题

不会的题

作者: 吃掉夏天的怪物 | 来源:发表于2021-09-10 16:52 被阅读0次
image.png
image.png
操作系统如何处理段错误 image.png image.png

find查找文件信息
grep查找文件内容
-R递归 -n显示行信息


image.png image.png image.png

1 3 3 3
文件类型 | (rwx)文件所有者 | 文件所有者所有组 | 其它

image.png

UDP报文有四个信息,①源端口号、②目的端口号、③数据报长度、④检验和

image.png

假设快指针是慢指针的2倍

image.png image.png

正常情况就可以用①Hash表存储这个值,如果有重复就说明有环。
②用快慢指针的形式

image.png

os如何处理段错

无论是Windows还是Linux,在用户模式下访问一个指针时,拿到的只是一个虚拟地址,CPU将这个地址(也就是一个32位或者6 4位的地址)传递给CPU中的内存管理单元(MMU),MM将查询进程的页表,从页表中找到对应的物理地址。
所以说,如果一个地址是非法的,那么它可能是没有对应的物理地址,也可能是它所在的这一页是不可读的,有权限冲突。如果是没有物理地址,那么程序回通知操作系统有一个页错误(Page fault),操作系统来进行换页。如果是出现了页的权限错误,或者是操作系统发现并没有页面可以换入(未分配的),那么它会触发一个"软中断"。
在Linux中,所谓的软中断其实就是一个信号(signal),由于访问非法

完全二叉树的高度 稳定排序 时间复杂度

什么是爬虫,请列举五种反爬机制

1.IP,当一个IP访问次数过多会把你IP封禁
2.验证码
3.模拟点击(selenium)
4.JS
5.user-agent

零拷贝技术

零拷贝主要的任务就是避免CPU将数据从一块存储拷贝到另外一块存储。


image.png

C++ STL sort

内部实现是快排,(快排最不擅长基本有序,如果有序就退化成O(N^2))


1
2

递归到小区间大小为16就不继续下去了,区间块有序,区间内部无序
depth_limit 递归层次的限制(2*logn),当超过这个层次就进行partial_sort堆排序,时间复杂度非常稳定不管是什么样的数据都是nlogn


3

插入排序最坏 O(n^2) 但是最好时间复杂度O(n)

递归排序最好的层次是logn , (假设每次都能选择最中间的那个值)


image.png

进入快排陷阱的时候就立刻切换为堆排序来做这个事情

image.png

(单边递归法、无监督快排)
单边递归法: 减少递归层数,递归栈空间的开辟
无监督(通用的一种方法)就是通过一种方法判断会不会死循环,从而避免了每次函数调用时判断是否会死循环

快排+堆排来保证进行一次排序后,整体接近有序
然后利用插入排序,加速排序
内省排序

排序1 排序2 二分次数
scanf 进制 linux 过滤器
awk、seed、grep Linux下文本三剑客 磁盘空间

根据CPU可寻址范围来确定虚拟空间大小

进程传递信息

Linux软中断 (还是不太了解)

中断会打断进程的正常调度与执行,来处理响应设备的请求。
(中断分为两部分, 1.快速处理这个中断, 2.延迟处理上半部分未完成的事情)
硬中断,特点就是快
软中断,特点就是延迟执行。

tcp三次握手 CPU层级

CPU缓存在计算机中的分布,CPU有三级缓存。三级缓存比一级二级大很多倍。
为什么三级缓存比一二级缓存加起来还要大那么多呢?
因为现在我们CPU都是多核的,每个核都有自己的一二级缓存,但是所有的核公用一个三级缓存。

数据离CPU越近执行越快,因为电子信号传输需要时间的,电信号的传输会影响CPU的时间。CPU的空间很狭小大小是有限制的。
CPU的缓存比内存快的多得多。

CPU访问一次内存通常需要100个时钟周期以上,而访问一个一级缓存只需要4-5个时钟周期,2级缓存12个,3级缓存30个。跟直接访问内存差别很多。
一个时钟周期0.几几纳秒。

如何在CPU层面提升缓存命中率?

说说CPU层级的代码优化

CPU层级

横着读不能很好利用CPU缓存,7-8倍性能上的差距。
场景:
①Hash表的桶大小,它这个大小就是默认是cpu的cache一次预读出来的这些值。从而更好的利用cpu的缓存。
②提升缓存命中率:
遍历一位数组是不是小于某个值,乱序和有序。有序比乱序快上1/3。因为CPU中有分支预测器。
发现循环中有大量的If、switch语句的时候,分支预测器可以预测出来接下来程序执行那个代码块的概率更大。

排序算法可以让CPU处于更加稳定的状态。


人为的分支预测器

如何提升TCP三次握手的性能

(全双工,三次才能双方都比较可靠)
HTTP建立在TCP之上的,TCP所占的时间10%~30%,时间占用还是挺长。
更改TCP还挺难,服务端更改客户端不一定更改。
双方 客户端、服务端
服务端监听端口(比较被动),存储一些状态,优化起来比较复杂

客户端优化

根据网络状态和服务器的繁忙程度,更改尝试次数和时间。(比如返回一个错误)

服务端优化

队列保存半连接状态下的一些信息

TCP_fastopen

连接过一次后(第一次客户端syn明确说开启tfo功能),网络出现一些状况,客户端再发送syn请求的时候就把cookie这个包给带上去。

MySQL为什么选择B+树

(思考往往比结论更重要)
主要是两个方便①查询效率(尽可能快)②存储空间(尽可能小)

Hash表查询时间复杂度O(1),

Hash这种存储结构不适合区间的查找

MySQL中Innodb引擎默认B+树,并不是只有B+树。
二叉树/跳表...

TCP vs UDP

TCP面向连接(传输数据前先建立连接),UDP面向无连接

UDP继承IP包的特性,不能保证不丢失也不能保证按序到达

TCP面向字节流
UDP面向包的协议基于数据报

TCP有流量控制拥塞控制,有状态的服务。
UDP无状态的服务

UDP三大特点 UDP三大使用场景

为什么需要实时性的东西的时候不可以用TCP呢?因为TCP在网络不好的情况下,会出现严重的丢包。严重丢包时拥塞控制+流量控制还会再降低速度。

HTTP3.0及之后采用UDP的协议,之前采用TCP。

TCP是服务端客户端双方的行为,所以改起来特别麻烦。

(拓展:①QUIC协议②什么是基于HTTP3.0的新的协议 )
[HTTP3.0](https://baijiahao.baidu.com/s?id=1677802258258817086&wfr=spider&for=pc

外部排序的简单应用


image.png

C++为什么不像JAVA一样有垃圾回收机制

RAII资源获取即初始化
结合栈和析构函数做的小技巧,通过栈和析构函数来对所有资源包括堆内存在内的资源进行管理。
RAII是导致垃圾回收机制没有在C++中正式使用的原因之一。
也可以说RAII是C++区别于其它语言的特性。
所有主流语言中只有C++是用RAII来做内存回收机制管理。

栈空间:函数本地变量存放位置,函数执行完后,函数所依赖的栈空间的东西就会自动被释放掉。C++所有东西窦应该放在栈空间上,放在栈空间上有优点也有缺点,比如当我们对象很大的时候或者在编译期间不能确定大小的时候,就不大适合放在栈空间里。


很危险的代码

new和delete之间不知道会进行什么样的操作,也许有一个return?或者有一个异常?
什么才是真正的一个RAII的东西,RAII就是说我们要用我们的一个栈空间的一个类来对我们new出来的堆空间里的东西做一个管理。栈空间来管理堆空间。


RAII
循环队列满
HashMap的数据结构

什么是内存池(太浅了)

在我们想要使用内存之前,我们要先申请一块内存当作备用,以备不时之需。
内存块大多数情况都不能刚好满足所需大小,可能会造成内存碎片。

map和unordered_map的区别?

map底层基于红黑树(整体平衡)来实现,unordered_map就是哈希表(类似vector + 开链法8以下,8以上就转化为红黑树)。

map:①有序②增删改查平均logn的时间复杂度

unordered_map不一定比map快,如果有很多冲突。

(拓展: unordered_set与set)

什么是HTTPS的SSL认证

对称加密(效率高很多)

非对称加密

数字证书

信息 -- > hash

各大CA的公钥是默认安装在我们的操作系统里的

TCP四次挥手的过程

image.png

提升四次挥手的性能

互联网中往往主动关闭的不是客户端而是服务器端,因为HTTP的消息传输是个单向传输协议。
服务器一般接收完请求过后才能生成一个响应,发送完响应过后很大概率会去关闭这个TCP连接,来去即时释放一个资源,为更多用户来提供一个服务。
①主动方的优化过程
1)更改TCP的tcp_orphan_retries值(一般8次)
2)当受到攻击FIN报文发送不出去(比如把接收窗口设置为0),可以发送REST复位报文来强制关闭TCP连接而绕过四次挥手。
②被动方的优化过程
控制close_wait的持续时间

虚拟内存

什么是虚拟内存,我们为什么要用虚拟内存这个东西?虚拟内存是怎么实现的?单级页表、多级页表,反制页表?以及它们的优缺点。❓❓❓

在刚刚有进程这个东西的时候,人们就意识到我一个程序在运行的时候,可能并不需要把我们全部的程序和全部的数据都放在内存中让CPU去运行。可以把目前已经在运行的那些程序啊或者已经在跑的那些需要的数据放在内存里面去,暂时不需要的放在硬盘里面去,到时候需要的时候再进行置换,这样的话可以节约很多内存空间。因为os跑起来的时候可能挂着好几百个进程,我们没有办法把所有东西都放在内存里的。这个时候就诞生了虚拟内存这个东西。虚拟内存的意思就是,进一步扩大进程地址空间,将我们地址空间的一部分存储到我们的磁盘上,只将运行到的部分的数据放在物理我们的内存当中。这个想法,就允许一个进程拥有与物理内存相同的甚至大于物理内存的地址空间。
虚拟内存是怎么转换成物理内存的?
首先想要把虚拟内存地址映射到物理内存地址,最直观的办法就是建一张映射表,那么这张映射表就是能实现我虚拟内存中的页面对应着物理内存中的页,做一个一一映射(页表)。
页表,把内存地址分为页号和偏移量两个部分。



image.png
image.png

mysql中普通索引和唯一索引的区别?

显而易见的区别:唯一索引不能有重复,普通可以有。
???索引数据结构的区别,MySQL innodb中默认的索引结构是

C++中右值(C++11)解决了什么问题?

右值引用的最终目的是实现移动语义。移动语义的意义是减少程序运行里的开销。


image.png

返回值优化(一种常见的C++编程错误,在函数里面返回一个对本地变量(栈空间,会被销毁不正确)的引用)(C++11后就可以直接移动出去)、完美转发(自动判断是左值还是右值,保持传入时左值与右值)

引用折叠 有时候& = &&

C++为什么要有智能指针


(所有人都用不到的情况下进行安全的销毁)

C++中有哪些智能指针,使用场景是什么

解决:
①空指针野指针的问题
②对象重复释放的问题
③内存泄漏
④不匹配的new和delete问题


unique_ptr

对于一个未初始化的unique_ptr进行操作,就像对一个空指针进行操作。
make_unique C++14
表示唯一的指针,禁止了拷贝复制

shared_ptr

如果不考虑应用场合,过多使用会降低程序运行的效率
析构函数不应该 非常复杂
循环引用

weak_ptr

作用就是打破循环引用

❓❓❓shared_ptr和unique_ptr是线程安全的指针吗?

实现一个线程安全的栈

STL里面的栈啊队列啊都不是线程安全的东西。因此必须手动封装一下。

#include<bits/stdc++.h>
using namespace std;

template<typename T>
class threadsafe_stack {
private:
    stack<T> m_data;
    mutable mutex m_lock;//???
public:
    threadsafe_stack() {}
    void push(T new_value){
        lock_guard<mutex> lock(m_lock);//RAII的方式拿到锁进行控制
        m_data.push(move(new_value));
    }
    /**
    void pop(){ //pop和top 有锁竞争的陷阱

    }
    T top(){

    }**/
//top & pop
    void pop(T &value) {
         lock_guard<mutex> lock(m_lock);
         if(m_data.empty()){
             return -1;
         }
         value = std::move(m_data.top());//没有进行复制
         m_data.pop();
    }
    bool empty()  const{
        lock_guard<mutex> lock(m_lock);
        return m_data.empty();
    }
};
int main()
{

}

RAII的最常见的常见:锁、智能指针

进程间通信方式⭐

最好了解接口啊参数啊实现啊,很容易考到。


进程间通信方式

注意: 信号和信号量不是一个东西
(管道以文件的形式存在)
消息队列模型经常在生产者消费者模型出现。
共享内存通常是与信号量在一起使用的。(信号量,就是解决进程访问内存避免竞争,更类似于互斥量。同一共享资源在同一刻)

信号:123都是对于常规情况下的通信方式,但是对于一些异常情况比如线上故障啊等突发情况锁之类流程都来不及了。告警系统

socket:经常用于网络之前的进程和进程

实现auto_ptr

(已经被淘汰,符合RAII)

#include<bits/stdc++.h>
using namespace std;

template <typename T>
class smart_ptr {
public:
    explicit smart_ptr(T* ptr =nullptr):m_ptr(ptr) {}
    ~smart_ptr(){
        delete m_ptr;
    }
    // smart_ptr(const smart_ptr&) = delete;
    // smart_ptr& operator=(const smart_ptr&) = delete;
    smart_ptr(smart_ptr&& other){
        m_ptr = other.released();
    }
    smart_ptr& operator=(smart_ptr rhs){
        rhs.swap(*this);
        return *this;
    }
    T* release() {
        T* ptr = m_ptr;
        m_ptr = nullptr;
        return ptr;
    }
    void swap(smart_ptr& rhs){
        swap(m_ptr.rhs.m_ptr);
    }


    T* get() const {return m_ptr;}
    T& operator*() const { return *m_ptr;}
    T* operator->() const {return m_ptr;}
    operator bool() const {return m_ptr;}
private: 
    T* m_ptr;
};

class shape {
public:
    virtual ~shape(){
        cout<<"~shape()"<<endl;
    }
};

class  circle: public shape
{
    public:
        ~circle(){
            cout<<"~circle()"<<endl;
        }
};


int main(){
    smart_ptr<circle> ptr(new circle);
    smart_ptr<circle> ptr2;
    ptr2 = move(ptr1);
    return 0;
}

相关文章

  • 不会的题

    今天我有很多的不会的题,小姨讲给我听,但是小姨怎么讲我都不会。那些题太难了 ,小姨讲来讲去,我都快迷糊了。

  • 不会的题

    find查找文件信息grep查找文件内容-R递归 -n显示行信息 1 3 3 3文件类型 | (rwx)文件所有者...

  • 不会做的题

    指着空白处, 你问我它空白的原因。 我同你讲, 它考的不等式, 是我唯一不会的三角不等式。 看懂你满眼的疑惑, 我...

  • 暂时不会的题

    为了养成不看题解的习惯,不会的题单独列出来。 ZOJ1008(UVA1302一直PE,最好不在UVA提交)HDU2...

  • 对于高中生来说,什么是假装努力?

    01 刷大量的题,碰到不会的就跳。 不会动脑思考,只做自己会的题。 你和你的同桌一起刷题,他一直纠结于某道题,你火...

  • 无标题文章

    思考着去做题 很多学生都有这样的困惑,做了很多题但不会的题还是很多,最可气的就是很多题明明做过,但是再遇到还是不会...

  • 面试的几个不会的题

    对mysql的什么ml和什么ml的看法 对package的理解

  • 这道题我不会

    俗话说:“兵来将挡水来土掩”。但是,面对爱情我才知道自己束手无策,毫无办法。 遇见她,喜欢她,却不敢告诉她。感觉自...

  • 【这题不会做】

    海上,船长进行着交易:一头500美元。 犀牛的种群得到了拯救。 海上,船长进行着交易,一个500美元 黑人的种群受...

  • 不会做“活题”

    早晨起来,就看到好友亚红校长的微信信息,于是赶忙拉起电话拨打过去。 亚红校长告诉我,这次六年级调研之后反映出来不少...

网友评论

      本文标题:不会的题

      本文链接:https://www.haomeiwen.com/subject/ykkpwltx.html