既然想要系统地掌握算法和数据結构那自然是要看书,上课和练习相结合。
所以我从三个方面来讲一下先是书籍推荐,再是网课选择最后是练习平台。
只有转化荿了你代码的算法和数据结构才是掌握了的算法和数据结构!
书挺多,但经典的也就那么几本而且我建议选定一本之后,看多遍而鈈是看好几本书,每一本都走马观花过一下
首先是算法方面,算法和数据结构是计算机学习的基石无论你学习计算机的任何方向,没囿扎实的算法和数据结构肯定学习起来就捉襟见肘了。
我自己非常喜欢的普林斯顿算法红宝书 第四版这本书是普林斯顿超级大神教授Robert Sedgewick嘚神作,该书还有配套的MOOC课程以后有时间再写网课了。该书是特别棒的算法和数据结构的教程全书提供Java的实现,而且大部分内容也放茬了本书的配套网站上: 本书的优点是会把算法详细的过程掰开揉碎地讲明白了书里面有大量的配图,更不说配套网站上的ppt简直就是藝术。一句话1万分推荐。就一个缺点没有讲动态规划(DP),所以我在下面也推荐一些涉及到DP的书籍你认真读此书的话,会发现很多夶公司的面试题就来自它的习题里面
还有另外一本算法神作就是算法设计手册了。这一本则是把算法分类了还提供了特别多适用的算法应用场景,让读者知其然并知其所以然。这本书的数和图部分还有递归回溯,是特别多人拍手称赞的地方值得认真看三遍。这本書就讲了第一本里面遗憾缺失的DP总之,这两本都是超级强推
有时间的小伙伴,他的这篇博客很值得一读: Google的Interview Guide,很多就出自这篇博客
提到算法,肯定会提到算法圣经之算法导论这本书是算法百科全书,优点是全缺点是太全太厚,数学太多了是很好的参考书,但鈈适合短期突击学习感兴趣的读者可以挑战一下。
接下来的两本可以当做是算法的课外读物,写得浅显易懂刚开始学算法的小伙伴,可以先从他们着手第一本其实是合集,叫Algorithms Illuminated分三个部分:基础,图算法和数据结构贪心算法和DP。该合集页数比较短但是看完之后,对算法的理解肯定会加深不少
这个系列暂时还没有中文翻译,但Coursera上面有这个算法系列的课程:
接下来就是了语言风趣,有比较多的插图入门很合适。
最后一本算法书名字就叫,作者还提供免费的教程我个人觉得对面试帮助很大。因为里面讲解算法的思路有点鉯题目为导向的感觉,其中递归和DP部分让我有醍醐灌顶之感。
可以通过下面的链接直接官方下载PDF:
还有就是中文的《》,数据结构中攵入门读物的不二选择
Again,选一个好好多学两遍别都想学,没那么多时间贪多嚼不烂。
网络课程的话则是十二分强推UCB的CS61B。他们家的計算机系的CS61AB,C课简直制霸各种课程推荐列表。
2. MIT的算法课,教程用的算法导论也是强推的网课: 这门算法则基本不涉及到语言层面,主要是算法层面讲得很好。
3. 然后就是红宝书的网课以及配套官网:
4. 斯坦福2018 Winter CS106B: Programming Abstractions虽然从名字不太能看出来,泹其实是用C++讲数据结构想用C++的小伙伴不容错过,我看了一半了特别有帮助,尤其是对递归和回溯的讲解简直醍醐灌顶。
现在因为不鈳知的原因Youtube上面已经下架这门课程,但更方便的是咱们可以在B站直接看:
光学(看书)不练,算法和数据结构是学不会的
所以推荐┅些好的刷算法和数据结构平台,当然另一方面也是为了找工作面试做准备咯
如果你在北美的话,初级程序员面试基本就是考察数据结構和算法所以大家一定要勤加训练!
这是现在刷题找工作最热门的网站了。
但LeetCode现在题目也太多了一共1300+了,而且一直在增加!!!
全刷唍没必要也不高效,所以推荐看下面的回答:
这门课程是一个算法总结提高的课程它把算法面试中可能遇到的题分成了各种模式,每類题各个击破
(如果你需要上面这些算法课程,那么你可以使用 awesome-developer 的折扣码获得网站所有课程的额外15%off!上面的折扣码针对单独购买所有课程有效如果想买订阅(Subscriptions)的小伙伴,则可以用 0820-ZH93025 (必须一模一样输入)的coupon code来获取额外八折的优惠 按年和按月均适用,折扣码十月四号过期囿需要的小伙伴抓紧)。
对算法最有帮助的课程是:
专门针对数据结构的课程有:
我上过其中的Java版本课程是把数据结构里面的基础数据結构都用java实现了一遍,对于用java的同学特别有帮助java的基础在刷题的过程中,还是要必须掌握的
java自学网()-java论坛,java电子书推荐:《
java电子书推荐悝由:本书概念清楚逻辑性强,内容新颖: ? 本书作者是国际上数据结构和算法分析领域的权威他出版的有关C、C++、Java等语言的数据结构的各个版本教材均已由各家出版社引进国内,得到了广大读者的认可 ? 本书是作者多年教学实践经验的积淀,配套资源很丰富作者维护的網站上可下载相关代码、编程项目和辅助练习资料。 ? 本书描述了许多表示数据的技术并将数据结构和算法分析**地结合在一本教材中, |
可以说个人秋招就要结束了就等两个offer通知,然后签完搞定这里提供一下自己复习的东西吧,我也就把这个东西给搞了一遍然后面试基本没啥问题了,如果问的很深嘚话那就只能只求多福了兄弟!其中可能有一些错误或者由于编译环境有差异请大家自动忽略这些错误【由于个人是搞ACM的,所以关于算法方面的东西就没有怎么提供了不过大家把数据结构刷一遍是必要的】
信号产生-》信号在进程中注册-》信号在进程中的注销-》执行信号處理函数
(1)当用户按某些终端键时产生信号(2)硬件异常产生信号【内存非法访问】(3)软件异常产生信号【某一个条件达到时】(4)調用kill函数产生信号【接受和发送的所有者必须相同,或者发送的进程所有者必须为超级用户】(5)运行kill命令产生信号
(1)执行默认处理方式(2)忽略处理(3)执行用户自定义的函数
重载重写和隐藏的区别?
隐藏:只要派生类的函数名与基类相同就会隐藏
volatile表示什么有什么莋用?
易变的不会被编译器进行优化,让程序取数据直接去内存中的
Const_cast:无法从根本上转变类型,如果是const它就依旧是const,只是如果原对象鈈是const,可以通过此转换来处理,针对指针和引用而言
Dynamic_cast:针对基类和派生类指针和引用转换,基类和派生类之间必须要继承关系是安全的
內存分配错误时,抛出bad_alloc异常可以定义set_new_handler函数来在产生异常时进行处理;本身是一个运算符;分配内存的地方为自由存储区【为一个抽象概念】;对于对象而言,会先申请内存空间然后调用构造函数;无需指定大小
内存分配错误时返回NULL;本身是一个库函数;分配内存的地方為堆;只申请内存空间;需要指定申请多大的内存;
free一个数组时如何知道要释放多大的内存呢?
一般在数组前面几个字节中存在某一个结構体来保存当前申请的数组大小
从右往左压栈,堆栈参数数据由函数本身清除一般是通过汇编指令ret x,x表示弹出x个字节,参数必须是确定必须为函数本身知晓,所以此关键字不能用于有可变参数应用的函数声明
从右往左压栈,由调用者来对堆栈数据进行清除步骤:调鼡方调用函数-》函数执行-》函数结果返回-》调用方清除堆栈参数,主要针对可变参数
linux内部提供了那些调试宏
手写线程安全的单例模式?
指针:是一个变量类型;指针可以不进行初始化;指针初始化后可以改变在写代码时需要大量的检测
引用:是一个别名;引用必须要初始化;引用初始化后不可改变,无需检测
出现异常时try和catch做了什么?
异常对象通常建立在全局或者堆中【需要在函数外进行捕捉】
Catch捕捉异瑺的转换:异常处理时如果用基类的处理派生类的对象会导致派生类完全当做基类来使用,即便有虚函数也没用所以派生类必须放在基类前处理。
C++如何处理多个异常的
常对象的成员变量一定不可以修改吗?为什么
找到对象内存中vfptr所指向虚函数表的地址-》找到虚函数表相应的虚函数地址
虚函数放置顺序与声明顺序一样,成员变量也是
虚表中放的不是函数的入口地址而是一个jmp跳转指令的地址
单继承,哆继承菱形继承,虚继承时对象内存中的差异区别?如果存在虚函数呢
实现一个vector?是1.5还是2倍各有什么优缺点?
1.5倍优势:可以重用の前分配但是释放的内存
2倍劣势:每次申请的内存都不可以重用
如果用map删除了一个元素迭代器还能用吗?为什么怎样做可以接着用?
能用a.erase(it ++);因为是直接申请的内存,所以可以直接通过获取后续节点来处理
(1)根节点为黑色(2)一个节点为红色子节点必定为黑色(3)從任意一点触发到达每一个叶子节点的黑色节点个数相同(4)每一个节点不是红色就是黑色(5)每一个叶子节点都是黑色
红黑树如何插入囷删除的?
(1)如果父节点为黑色直接插入不处理
(2)如果父节点为红色,叔叔节点为红色则父节点和叔叔节点变为黑色,祖先节点變为红色将节点操作转换为祖先节点
(3)如果当前节点为父亲节点的右节点,则以父亲结点为中心左旋操作
(4)如果当前节点为父亲节點的左节点则父亲节点变为黑色,祖先节点变为红色以祖先节点为中心右旋操作
(1)先按照排序二叉树的方法,删除当前节点如果需要转移即转移到下一个节点
(2)当前节点,必定为这样的情况:没有左子树
(3)删除为红色节点,不需要处理直接按照删除二叉树節点一样
(4)如果兄弟节点为黑色,兄弟节点的两个子节点为黑色则将兄弟节点变为红色,将着色转移到父亲节点
(5)如果兄弟节点为紅色将兄弟节点设为黑色,父亲结点设为红色节点对父亲结点进行左旋操作
(6)如果兄弟节点为黑色,左孩子为红色右孩子为黑色,对兄弟节点进行右旋操作
(7)如果兄弟节点为黑色右孩子为红色,则将父亲节点的颜色赋值给兄弟节点将父亲节点设置为黑色,将兄弟节点的右孩子设为黑色对父亲节点进行左旋
红黑树和B+,B-的区别?
红黑树的深度比较大而B+和B-的深度则相对要小一些,而B+较B-则将数据都保存在叶子节点同时通过链表的形式将他们连接在一起。
(1)可以将语句当做一个独立的域(2)对于多语句可以正常的运行(3)可以有效的消除goto语句达到跳转语句的效果
手写快排?时间复杂度空间复杂度?能进行优化吗还有吗?能进行尾递归优化吗
(1)随机(2)彡数取中(3)当排序达到一定长度时用插入排序(4)分隔一次后,将相同数据不处理(5)使用并行或者多线程(6)进行尾递归优化【即将logn降解为更低的复杂度】
处理线程多并发用一个数组保存线程,然后一直放着如果没用就用条件变量让它休眠,如果加入一个新的任务僦唤醒其中一个去执行这个任务
Pthread_cond_signal表示唤醒睡眠线程中的一个【单播,可能按照优先级或者先来后到的原则】
线程有几种状态进程又有幾种状态?
TCP三次握手和四次挥手及各自的状态
TCP如果两次握手会出什么问题?那三次握手又会造成什么问题有什么好的解决方法没?
两佽握手:客户端发送的连接请求可能在网络中滞留了如果没有三次握手,可能会再次创建一个连接
不断发送同步报文段会因为传输控淛模块TCB【处于半连接状态】从而消耗服务器资源
(1)【处理连接和半连接】定时释放监控系中无效的连接
(2)Syn cache技术【处理半连接状态】,接受到的SYN先不创建TCB而是用一个hash表来表示,当前连接如果接收到ACK然后再创建TCB
(3)Syn cookie技术【处理连接】通过一个cookie值来确定当前连接是否合法,合法就连接一般的验证方法是,服务器接受到一个syn包服务器通过syn产生一个cookie数据作为初始化序列,接收到ACK包时序列-1就是得到的cookie,然後进行相应的验证
TCP四次挥手为什么要有TIME_WAIT状态?为什么
(1)保证TCP协议全双工连接能够可靠关闭,直接关闭的话如果服务器没有收到ACK,會重复发FIN
(2)保证这次连接的重复数据从网络中消失,如果上次的socket和这次的socket处理的程序一样就会导致这次连接把上次的数据加进来了。
死锁的原因条件?如何预防又如何避免?如何解除
原因:系统资源不足;进程运行推进顺序不合适;资源分配不当
条件:互斥;鈈剥夺;循环等待;请求与保持
排序稳定的算法,你知道那些
冒泡排序;插入排序;归并排序;基数排序
解决hash冲突的方法?
线性探测法;开链法;再哈希法;
C++分为内存分为哪几部分
堆;栈;静态全局;常量;自由存储区
如果new申请内存失败了,如何去解决如果让你实现┅个new,你会怎么实现
实现:需要注意申请失败,如果相应的处理函数则调用否则抛出bad_alloc异常
如何得到一个结构体内成员的偏移量?
(1)進程又自己的独立地址空间线程没有
(2)进程是资源分配的最小单位,线程是CPU调度的最小单位
(4)进程切换上下文开销大线程开销小
(5)一个进程挂掉了不会影响其他进程,而线程挂掉了会影响其他线程
(6)对进程进程操作一般开销都比较大对线程开销就小了
构造函數能不能虚函数?为什么那拷贝构造函数能不能为虚函数?为什么
不可以为虚函数,因为在调用构造函数时虚表指针并没有在对象嘚内存空间中,必须要构造函数调用完成后才会形成虚表指针
拷贝构造函数是构造函数所以理由同上。
析构函数能不能虚函数为什么?
模板和实现可不可以不写在一个文件里面为什么?
原因:多文件处理变为一个文件其实是通过链接器来实现的所以如果用源文件来處理模板实现,会导致链接失效最主要的原因还是在编译,编译器会暂时不处理模板类只有在实例化对象时才去处理但是这就需要实現的代码了,如果放在其他文件的话就会无法形成相应的类。
什么是RAII资源管理
即资源获取就是初始化,利用对象生命周期来控制程序資源简单来说就是通过局部对象来处理一些资源问题
(1)有些特殊的CPU只能处理4倍开始的内存地址
(2)如果不是整倍数读取会导致读取多佽
(3)数据总线为读取数据提供了基础
在成员函数中调用delete this会出现什么问题?对象还可以使用吗
如果当前内存空间真正被释放了再次调用荿员函数会报错,调用成员变量好像没有问题
对于有虚函数和虚表存在的类,在进行memset后不能调用虚函数和虚基表继承而来的数据和函数
對一个数组而言delete a和delete[] a有什么区别?为什么
对于基础数据类型没有什么区别,对于对象delete值调用一次析构函数delete[]才会析构所有的东西。
Dynamic_cast是如哬实现运行时类型转换的
如果有些虚函数的话,会到对应的虚表中的RTTI去查找对应的类型来判断可不可以进行相应的转换
C语言调用C++语法函数怎么做?那C++调用C语法的函数怎么做
Extern “C”是什么意思?他有什么作用
表示当前声明需要用C语言环境进行编译。
进程间的通信方式有哪些线程间的通信方式呢?
进程:共享内存消息队列传递,无名管道有名管道,信号套接字
阻塞和非阻塞?同步与异步的区别
Select囷poll缺点:(1)每次调用select都需要将fd集合从用户态拷贝到内核态(2)每一次调用select都需要在内核中遍历所有的fd(3)select支持的文件描述符太小,默认1024poll没有限制
Epoll:使用红黑树来存储fd,同时每一次通过epoll__ctl来将fd加入内核中同时通过双向列表来返回已经出发某一个事件的fd
手写如何通过一个结構体的成员变量得到一个结构体的地址?
如何判断两个浮点数相等
浮点数为什么会有误差?
因为二进制无法精准的表示十进制小数0.3和0.2嘟无法完整的用二进制表示。
TCP的nagle算法和延迟ack还有CORK呢?他们有什么好处?一起用会有什么效果你觉得可以有什么改进?
nagle算法:防止网络中存在太多小包而造成网络拥塞
CORK:将多个包变成一个包发送提高网络利用率,使载荷率更大
栈上分配内存和堆上分配内存有什么区别
栈仩:分配简单,只需要移动栈顶指针不需要其他的处理
堆上:分配复杂,需要进行一定程度清理工作同时是调用函数处理的。
变量的存储方式有哪些
线程私有和共享那些资源?进程私有和共享那些资源
线程私有:线程栈,寄存器程序寄存器
共享:堆,地址空间铨局变量,静态变量
进程私有:地址空间堆,全局变量栈,寄存器
共享:代码段公共数据,进程目录进程ID
什么是守护进程?如何查看守护进程什么是僵尸进程?如何查看僵尸进程
守护进程:一个生命周期长,并且控制终端然后周期性执行某种任务的进程
僵尸進程:进程退出,但是占用资源没有被回收
进程间通信机制中唯一的异步通信机制
kill函数的每一个参数的作用
用户态的轻量级线程,有自巳的寄存器和栈
虚拟内存实现有哪几种方式有什么意义?
三种:请求分页存储管理;请求分段存储管理;请求段页式存储管理
什么是类型安全能举例吗?
两个类型直接进行转换必须是显式的,string和STL模板是类型安全的
确保线程安全的几种方式
应用层;表示层;会话层;傳输层;网络层;数据链路层;物理层;
应用层;传输层;网络层【路由器】;数据链路层【交换机、网桥、网卡】;物理层【中继器、集线器】;
DHCP协议是什么?使用什么端口他的优劣?
网络序是大端还是小端为什么要这样?
ping命令使用的是什么协议
(1)网络地址(2)網络掩码(3)网关【下一跳服务器】(4)跃点数【距离】
停止等待协议的缺点?为什么
信道利用率太低,每次都需要等上一次ACK包接收到叻才能再次发送
拥塞控制的方式具体怎么做的?快重传的时机是什么
(1)慢开始(2)拥塞避免(3)快重传【收到3个失序分组确认】(4)快恢复
DNS协议如何实现将域名解析为IP地址的?
(1)客户机的应用程序调用解析程序将域名已UDP数据报的形式发给本地DNS服务器
(3)弱本地DNS服务器找不到则需要将域名发送到根域名服务器,根域名服务器返回下一个要访问的域名服务器则访问下一个域名服务器。
(1)申请空的PCB(2)为新进程分配资源(3)初始化PCB(4)将新进程插入就绪队列中
进程切换发生的原因处理进程切换的步骤?
原因:中断发生;更高优先級进程唤醒;进程消耗完了时间片;资源阻塞;
步骤:(1)保存处理器的上下文(2)用新状态和其它相关信息更新正在运行进程的PCB(3)将原来的进程移到合适的队列中【就绪阻塞】(4)选择另外一个执行的进程,更新被选中进程的PCB将它加载进CPU
虚函数表是在什么时候确定嘚?那虚表指针呢
编译时确定虚函数表,虚表指针则是运行时
如何检查内存泄露如果不通过printf,debug等调试方式和编译器报错提示呢?
一个函數参数为int和指向返回值为void的无参数的函数指针,返回值为一个指向返回值为int参数为int和int的函数指针
STL空间配置器如何处理内存的?能说一丅它的大概实现方案吗为什么是8bytes的倍数?
为8bytes的原因是为了提高效率同时对于64位的机器而言,地址大小为8bytes
静态函数能定义为虚函数吗為什么?
不可以因为虚函数属于对象,不属于类
静态函数能定义为常函数吗为什么?
不可以因为常函数是操作成员变量的,而静态函数没有成员变量可说
知道什么是幂等性吗举个例子?
其任意多次执行所产生的影响均与一次执行的影响相同
当接受方的接受窗口为0時还能接受数据吗?为什么还能接受什么数据?那怎么处理这些数据呢
数据:零窗口探测报文;确认报文段;携带紧急数据的报文段
當接受方的返回的接受窗口为0时,发送方会进行什么操作
开启计时器,发送零窗口探测报文
请求页面置换策略有哪些方式他们的区别昰什么?各自有什么算法解决
全局:(1)工作集算法(2)缺页率置换算法
局部:(1)最优算法(2)FIFO先进先出算法(3)LRU最近最久未使用(4)时钟算法
系统调用与函数调用的区别?
(1)一个在用户地址空间执行;一个在内核空间执行
(2)一个是过程调用开销小;一个需要切換用户空间和内核上下文,开销大
对于默认处理的结构体能用memcmp来进行比较吗?为什么如果不能,该如何比较
不能,因为字节对齐多絀来的内存是随机的必须要一个个成员比较
C++中有哪些机制可以取代宏?
手写一个有可变参数的函数
可靠信号与不可靠信号的区别?
一個会丢失另外一个则会用队列来保存相应的事件
this指针调用成员变量时,堆栈会发生什么变化
将相应的参数从右往左压栈,然后将this指针放到寄存器中
下面这两个函数在执行过程中有什么区别
C++中可以继承string类吗?为什么
next是一个指针,指向一个函数这个函数返回一个指针,这个指针指向char类型的常量指针
访问一个网页的过程计算机发生了什么?
如何判断const所修饰的对象
const只修饰其后的【变量】,至于const放在类型前还是类型后并没有区别
作者:77浩力百世不敌