内容简介
本书是面向程序员面试的参考书,书中囊括了各种编程解决方案,可以用来有效地应对面试、考试及校园招聘。内容涵盖了编程基础、架构设计、数据库技术、数据结构及算法等主要的话题,而且还介绍了趣味谜题以及非技术的问题。
目录
Contents 目 录
译者序
前 言
致 谢
第1章 编程基础1
1.1 变量1
1.2 数据类型1
1.3 数据结构2
1.4 抽象数据类型3
1.5 内存与变量3
1.6 指针4
1.6.1 指针的声明4
1.6.2 指针的使用5
1.6.3 指针的操纵6
1.6.4 数组与指针7
1.6.5 动态内存分配7
1.6.6 函数指针7
1.7 参数传递的方式8
1.7.1 实际参数与形式参数8
1.7.2 参数传递的语义8
1.7.3 各种编程语言所支持的参数传递方式9
1.7.4 按值传递9
1.7.5 按结果传递10
1.7.6 有可能发生的参数冲突10
1.7.7 按值-结果传递11
1.7.8 按引用传递(别名机制)11
1.7.9 按名称传递12
1.8 绑定12
1.8.1 静态绑定(前期绑定)13
1.8.2 动态绑定(后期绑定)13
1.9 作用域13
1.9.1 静态作用域13
1.9.2 动态作用域14
1.10 存储类别15
1.10.1 存储类别为auto的变量15
1.10.2 存储类别为extern的变量16
1.10.3 存储类别为register的变量18
1.10.4 存储类别为static的变量19
1.11 存储空间的安排19
1.12 编程方式22
1.12.1 无结构的编程22
1.12.2 过程式的编程22
1.12.3 模块式的编程22
1.12.4 面向对象的编程23
1.13 面向对象编程的基本概念23
1.13.1 类与对象24
1.13.2 封装24
1.13.3 抽象25
1.13.4 数据隐藏25
1.13.5 多态25
1.13.6 继承26
1.13.7 继承的类型26
1.13.8 动态绑定27
1.13.9 消息传递28
第2章 脚本语言83
2.1 解释器与编译器83
2.1.1 编译器83
2.1.2 解释器84
2.1.3 编译器与解释器的区别84
2.2 什么是脚本语言84
2.3 shell脚本编程85
2.3.1 命令的重定向与管道85
2.3.2 变量86
2.3.3 命令行参数87
2.3.4 命令替换88
2.3.5 算术扩展88
2.3.6 控制结构88
2.3.7 函数92
2.4 Perl94
2.4.1 从“Hello world!”程序开始94
2.4.2 Perl的命令行参数95
2.4.3 Perl的数据类型与变量95
2.4.4 引用98
2.4.5 声明变量98
2.4.6 变量的作用域99
2.4.7 字符串字面量99
2.4.8 Perl的标准输入端100
2.4.9 Perl语言的运算符101
2.4.10 条件语句110
2.4.11 循环113
2.4.12 子例程115
2.4.13 字符串操作117
2.4.14 包/模块118
2.5 Python118
2.5.1 什么是Python118
2.5.2 布尔类型119
2.5.3 整数119
2.5.4 字符串119
2.5.5 列表与元组121
2.5.6 函数122
2.5.7 把代码包装成模块123
第3章 与设计有关的面试题124
3.1 术语介绍124
3.2 技巧125
3.3 可供练习的其他设计问题179
第4章 操作系统的概念180
4.1 术语介绍180
4.2 与操作系统概念有关的问题183
第5章 计算机网络的基础知识188
5.1 介绍188
5.2 局域网与广域网188
5.3 数据包分割与多路复用189
5.4 终端设备190
5.5 中介设备190
5.6 集线器、交换机与路由器的定义191
5.7 介质192
5.8 端对端网络与客户端/服务器网络192
5.9 互联网是如何运作的193
5.10 OSI模型与TCP/IP模型的区别196
5.11 客户端/服务器结构与互联网197
5.12 ARP与RARP198
5.13 子网199
5.14 路由器的工作原理200
5.15 单播、广播、多播201
5.16 tracert/traceroute及ping命令的工作原理202
5.17 什么是QoS203
第6章 数据库概念204
6.1 术语介绍204
6.2 与数据库概念有关的问题206
第7章 智力题213
7.1 智力题213
第8章 算法介绍217
8.1 什么是算法217
8.2 为什么要做算法分析218
8.3 算法分析的目标218
8.4 什么是运行时间分析218
8.5 怎样对比不同的算法218
8.6 什么是增长率219
8.7 几种常见的增长形式219
8.8 算法分析的类型220
8.9 渐近表示法221
8.10 大O表示法221
8.11 大Ω表示法222
8.12 大Θ表示法223
8.13 算法分析为什么又叫渐近分析225
8.14 渐近分析指南225
8.15 三种表示法的性质227
8.16 常用的对数公式与求和公式227
8.17 分治算法的主定理227
8.18 与分治算法的主定理有关的问题228
8.19 递减式递推(减而治之)算法的主定理229
8.20 另一种递减式递推(减而治之)算法的主定理229
8.21 与算法分析有关的问题230
第9章 递归与回溯240
9.1 介绍240
9.2 什么是递归240
9.3 为什么要用递归的办法解决问题240
9.4 递归函数的格式241
9.5 演示递归调用时的内存占用情况241
9.6 递归与迭代242
9.7 运用递归时的注意事项243
9.8 递归算法举例243
9.9 与递归有关的问题243
9.10 什么是回溯245
9.11 回溯算法举例245
9.12 与回溯有关的问题245
第10章 链表248
10.1 什么是链表248
10.2 将链表用作抽象的数据类型248
10.3 为什么要用链表249
10.4 数组概述249
10.5 比较链表、数组与动态数组250
10.6 单链表251
10.7 双链表256
10.8 循环链表261
10.9 节省内存的双链表266
10.10 松散链表268
10.11 跳跃链表273
10.12 与链表有关的问题276
第11章 栈295
11.1 什么是栈295
11.2 怎样使用栈296
11.3 将栈用作抽象数据类型296
11.4 栈的运用296
11.5 实现297
11.6 对比各种实现方式302
11.7 与栈有关的问题303
第12章 队列324
12.1 什么是队列324
12.2 如何使用队列324
12.3 将队列用作抽象数据类型325
12.4 异常325
12.5 运用325
12.6 实现326
12.7 与队列有关的问题331
第13章 树337
13.1 什么是树337
13.2 术语表337
13.3 二叉树339
13.4 二叉树的类型339
13.5 二叉树的性质340
13.6 遍历二叉树342
13.7 泛化树(N叉树)362
13.8 通过线索二叉树来遍历369
13.9 表达式树376
13.10 异或树379
13.11 二叉搜索树380
13.12 平衡二叉搜索树395
13.13 AVL树396
13.14 其他形式的树413
13.14.1 红黑树413
13.14.2 伸展树414
13.14.3 扩充树(增强树)414
13.14.4 区间树(区段树)415
13.14.5 替罪羊树416
第14章 优先级队列与堆418
14.1 什么是优先级队列418
14.2 将优先级队列用作抽象数据结构418
14.3 运用419
14.4 实现419
14.5 堆与二叉堆420
14.6 二叉堆421
14.7 与优先级队列和堆有关的问题428
第15章 图算法442
15.1 介绍442
15.2 术语表442
15.3 图的运用446
15.4 将图用作抽象的数据结构446
15.4.1 邻接矩阵446
15.4.2 邻接列表447
15.4.3 邻接集合449
15.4.4 表示图的方法的对比449
15.5 图的遍历449
15.5.1 深度优先搜索(DFS)450
15.5.2 广度优先搜索(BFS)454
15.5.3 对比DFS与BFS456
15.6 拓扑排序457
15.7 最短路径算法458
15.8 最小生成树465
15.9 与图算法有关的问题469
第16章 排序475
16.1 什么是排序475
16.2 为什么要排序475
16.3 排序算法的分类方式475
16.3.1 按照比较的次数来分类475
16.3.2 按照交换操作的次数来分类476
16.3.3 按照内存使用量来分类476
16.3.4 按照是否递归来分类476
16.3.5 按照是否稳定来分类476
16.3.6 按照适应性来分类476
16.4 其他的分类方式476
16.5 冒泡排序477
16.6 选择排序478
16.7 插入排序479
16.8 希尔排序481
16.9 归并排序483
16.10 堆排序485
16.11 快速排序485
16.12 树排序488
16.13 线性时间的排序算法489
16.14 计数排序489
16.15 桶排序490
16.16 基数排序490
16.17 拓扑排序491
16.18 外部排序491
16.19 与排序有关的问题492
第17章 搜索500
17.1 什么是搜索500
17.2 为什么要搜索500
17.3 各种类型的搜索500
17.4 在无序的数据中执行线性搜索501
17.5 在已经排好序/有序的数组中执行线性搜索501
17.6 二分搜索501
17.7 对比几种基本的搜索算法502
17.8 符号表与哈希502
17.9 字符串搜索算法502
17.10 与搜索有关的问题503
第18章 选择算法530
18.1 什么是选择算法530
18.2 通过排序来选择530
18.3 基于分区的选择算法531
18.4 线性选择算法—中位数的中位数算法531
18.5 把最小的k个元素找出来531
18.6 与选择算法有关的问题531
第19章 符号表541
19.1 介绍541
19.2 什么是符号表541
19.3 实现符号表542
19.4 比较实现符号表的各种方式543
第20章 哈希544
20.1 什么是哈希544
20.2 为什么要使用哈希544
20.3 将哈希表用作抽象数据结构544
20.4 哈希技术的原理545
20.5 哈希技术的组成要素546
20.6 哈希表546
20.7 哈希函数547
20.8 负载因子547
20.9 冲突547
20.10 冲突解决技术548
20.11 单独链接法548
20.12 开放定址548
20.12.1 线性探测548
20.12.2 二次探测549
20.12.3 二次哈希550
20.13 比较各种冲突解决技术550
20.14 哈希技术如何把复杂度降为O(1)551
20.15 哈希技术551
20.16 哪些问题不适合用哈希表解决551
20.17 Bloom过滤器552
20.17.1 工作原理552
20.17.2 选择合适的哈希函数553
20.17.3 设置长度合适的位向量553
20.17.4 空间方面的优势553
20.17.5 时间方面的优势554
20.17.6 实现554
20.18 与哈希有关的问题554
第21章 字符串算法565
21.1 介绍565
21.2 字符串匹配算法565
21.3 蛮力法566
21.4 Rabin-Karp字符串匹配算法566
21.5 用有限状态机来实现字符串匹配算法567
21.5.1 状态机的运作过程568
21.5.2 构建有限状态机时的注意事项568
21.5.3 匹配算法568
21.6 KMP算法569
21.6.1 前缀表569
21.6.2 匹配算法571
21.7 Boyce-Moore算法573
21.8 适合用来保存字符串的数据结构573
21.9 用哈希表来保存字符串574
21.10 用二叉搜索树来存放字符串574
21.11 前缀树574
21.11.1 什么是前缀树574
21.11.2 为什么要使用前缀树575
21.11.3 声明前缀树575
21.11.4 向前缀树中插入字符串576
21.11.5 在前缀树中查找字符串576
21.11.6 用前缀树来表示字符串有什么缺点577
21.12 三元搜索树577
21.12.1 声明三元搜索树577
21.12.2 向三元搜索树中插入字符串578
21.12.3 在三元搜索树中查找字符串580
21.12.4 显示三元搜索树中的全部字符串580
21.12.5 在三元搜索树中查找最长的字符串581
21.13 比较二叉搜索树、前缀树及三元搜索树581
21.14 后缀树581
前言/序言
Preface 前 言
亲爱的读者:
请先别急着翻过这一页。我知道,有很多人是不看前言的,但是这次,强烈建议大家读一读接下来的几段话,因为这里面有一些和其他前言不同的地方。
本书的前提是,读者已经掌握了一些计算机科学的基本知识。它的主要目标并不是提供与数据结构和算法有关的定理及证明,而是以一种逐步完善的方式来告诉大家:我们可以使用那些复杂度各不相同的办法来解决同一个编程问题。也就是说,针对每一个编程问题,笔者都会按照复杂度递减的顺序来讲解各种解法。总的来说,本书中囊括了各种编程解决方案,可以用来有效地应对面试、考试及校园招聘。
求职者如果能够读完本书,并很好地理解其中的内容,那么笔者保证:你肯定能够反过来给面试官提出几个难题。这正是本书想要达成的效果。
本书对于攻读工程学位及工程硕士的学生也会很有帮助。书中的每一章都会把重心放在编程问题及对这些问题所做的分析上,而不会只谈理论。笔者会在每章的开头讲解阅读此章所需的基础理论知识,然后列出一组问题。全书大约有700道算法题,而且每道题都有解答。
本书的大多数章节都会专注于问题本身,并对这些问题做出分析,而不会过多地聚焦在理论上面。各章开头会给出该章所要求的基本理论,然后提出问题。
书中的许多问题都有不止一种解法,而且这些解法的复杂度也各不相同。我们首先会讲解一种蛮力解法(brute force solution),然后逐渐改进,以求找到该问题的最佳解法(best solution)。笔者尽量使大家能够理解每个算法所耗费的时间,以及它所占据的内存量。
你至少应该将本书通读一遍,以求对其中的全部话题都有所了解。然后可以根据自己的需要,直接跳到某一章,以参考其内容。尽管本书经过多次校对,但错误在所难免,本书勘误会更新在www.CareerMonk.com网站上。你可以定期查阅此网站,以了解最新的勘误、习题及解决方案。也欢迎你发送邮件到Info@CareerMonk.com,给笔者提出宝贵的建议。
祝万事顺心、阅读愉快!
—Narasimha Karumanchi
印度理工学院孟买校区技术硕士、CareerMonk.com创始人
致 谢 Acknowledgements
妈妈、爸爸,我不知道应该怎样对你们表示感谢才好。你们不遗余力地养育我,使我能够在稳定的环境中成长;你们始终坚持传统的美德,使我学会了赞美并热爱生活。对我来说,你们是最棒的父母,也是最好的榜样。我从你们身上懂得一个道理:有志者,事竟成!
这本书能够问世,得益于很多人的帮助。感谢他们为完善本书内容所做的努力。然而在这之前,我必须说:我已经尽力修正了审阅者所指出的错误,并且尽可能准确地描述了相关的协议与机制。如果还有尚未改正之处,那么应该归咎于我。
首先,要感谢在写书过程中提供支持的诸君,感谢你们能够与我讨论问题、阅读书稿、撰写内容、提出评价,并允许我引用相关的意见。同时感谢你们为编辑、校对及设计工作提供协助。尤其要感谢下面几位:
来自印度理工学院孟买校区、在dataRPM公司担任架构师的Mohan Mullapudi
在瞻博网络担任高级顾问的Navin Kumar Jais
程序员面试手册:概念、编程问题及面试题 epub pdf mobi txt 电子书 下载 2024
程序员面试手册:概念、编程问题及面试题 下载 epub mobi pdf txt 电子书 2024
评分
☆☆☆☆☆
。。。。。。。。。。。。。。。。。。。。。。。。。。。。
评分
☆☆☆☆☆
挺好的,能学到一些东西……
评分
☆☆☆☆☆
挺好的,能学到一些东西……
评分
☆☆☆☆☆
。。。。。。。。。。。。。。。。。。。。。。。。。。。。
评分
☆☆☆☆☆
此用户未填写评价内容
评分
☆☆☆☆☆
挺好的,能学到一些东西……
评分
☆☆☆☆☆
此用户未填写评价内容
评分
☆☆☆☆☆
。。。。。。。。。。。。。。。。。。。。。。。。。。。。
评分
☆☆☆☆☆
此用户未填写评价内容