logo资料库

BAT经典面试题100道.pdf

发布时间：2022-06-16 发布人：admin 分类：说明书 资料大小：1.58M 资料格式：pdf 举报 版权申诉
第1页 / 共51页
第2页 / 共51页
第3页 / 共51页
第4页 / 共51页
第5页 / 共51页
第6页 / 共51页
第7页 / 共51页
第8页 / 共51页
资料共51页，剩余部分请下载后查看
    九章算法 http://www.jiuzhang.com BAT 经典面试题 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好 工作，由美国硅谷顶尖 IT 企业一线工程师提供算法培训、面试咨询等服务。 官网：http://www.jiuzhang.com。 目 录 1. 笔/面试风格及准备 ............................................................................................................................................................. 7 1.1 实现一个 MEMCPY 函数 ..................................................................................................................................................7 1.2 STL 中 VECTOR 的实现原理 (衍生：MAP, SET 等实现原理).........................................................................7 1.3 给定 N 张扑克牌和一个随机函数，设计一个洗牌算法。 .............................................................................9 参考答案： ....................................................................................................................................................................................9 1.4 25 匹马，5 个跑道，每个跑道最多能有 5 匹马进行比赛，最少比多少次能比出前 3 名？前 5 名？ ...................................................................................................................................................................................................9 1.5 100 亿个整数，内存足够，如何找到中位数？内存不足，如何找到中位数？................................. 10 2. C/C++基础(上) ................................................................................................................................................................... 11 2.1 请简述智能指针原理，并实现一个简单的智能指针。 ................................................................................ 11 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 1 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    九章算法 http://www.jiuzhang.com 2.2 如何处理循环引用问题？ ........................................................................................................................................... 13 2.3 请实现一个单例模式的类，要求线程安全......................................................................................................... 14 2.4 如何定义一个只能在堆上（栈上）生成对象的类? ....................................................................................... 15 2.5 下面的结构体大小分别是多大（假设 32 位机器）？ .................................................................................. 15 2.6 引用和指针有什么区别？ ........................................................................................................................................... 16 2.7 CONST 和 DEFINE 有什么区别？................................................................................................................................ 17 2.8 DEFINE 和 INLINE 有什么区别？................................................................................................................................. 17 2.9 MALLOC 和 NEW 有什么区别？ .................................................................................................................................. 17 2.10 C++中 STATIC 关键字作用有哪些？ .................................................................................................................... 18 2.11 C++中 CONST 关键字作用有哪些？..................................................................................................................... 19 2.12 C++中成员函数能够同时用 STATIC 和 CONST 进行修饰？ ....................................................................... 19 2.13 下面三个变量分别代表什么含义？..................................................................................................................... 20 2.14 C++中包含哪几种强制类型转换？他们有什么区别和联系？ ................................................................ 20 3. C/C++基础(下) ................................................................................................................................................................... 22 3.1 下面两段代码的输出分别是什么？ ........................................................................................................................ 22 3.2 一个对象访问普通成员函数和虚函数哪个更快？ .......................................................................................... 24 3.3 在什么情况下，析构函数需要是虚函数？......................................................................................................... 24 3.4 内联函数、构造函数、静态成员函数可以是虚函数吗？ ........................................................................... 25 3.5 构造函数中可以调用虚函数吗？ ............................................................................................................................ 25 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 2 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    九章算法 http://www.jiuzhang.com 3.6 简述 C++中虚继承的作用及底层实现原理? ..................................................................................................... 25 4 智力题 ..................................................................................................................................................................................... 26 4.1 1000 个灯围成一个环，初始状态是熄灭的，按一个灯，它以及它的左右两盏灯的状态会改变， 问 如何让所有灯都亮？....................................................................................................................................................... 26 4.2 N 条直线最多能将一个平面分成多少部分？...................................................................................................... 26 4.3 N 个平面最多能将一个空间切成多少部分？...................................................................................................... 26 4.4 两个机器人,初始时位于数轴上的不同位置。给这两个机器人输入一段相同 的程序,使得这两个 机 器人保证可以相遇。程序只能包含“左移 N 个单位”、“右移 N 个单位”,条件判断语句 IF,循环语句 WHILE, 以及两个返回 BOOLEAN 值的 函数“在自己的起点处”和“在对方的起点处”。你不能使用其它 的变量和 计数器，请写出该程序。 .............................................................................................................................. 29 4.5 有 N 个人互相比赛（N 已知）, 一个人输掉 4 次就出局(不能继续比赛),赢 7 次通过(可以继续 比赛), 问最多通过人数? ...................................................................................................................................................... 29 4.6 两个软硬程度一样的鸡蛋，它们在某一层摔下会碎，有个 100 层的建筑，要求最多用两个鸡蛋 确 定鸡蛋安全下落的临界位置，给出临界位置？如果是 N 层楼，M 个鸡蛋，请给出确定临界位置 的算法 ........................................................................................................................................................................................... 30 4.7 N 个人，只有 1 个人是明星，明星所有人都认识，但明星不认识其他任何人，如何找到该明星？ 如果 N 很大很大，如果改进你的算法？ ...................................................................................................................... 30 4.8 给 50 个硬币,面值可以不同,排成一排,两个人轮流取,只能从两端取,先取的人如何保证取到的 币值大于等于另一个人......................................................................................................................................................... 30 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 3 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    九章算法 http://www.jiuzhang.com 4.9 一个绳子从一头开始烧是 1 小时，要求想办法测出 45 分钟。 .............................................................. 31 4.10 囚犯猜帽子问题 ............................................................................................................................................................ 31 5. 概率题与操作系统题....................................................................................................................................................... 34 5.1 如何等概率地从 N 个数中随机抽出 M 个数？ ................................................................................................... 34 5.2 给定一个能够生成 0,1 两个数的等概率随机数生成器”，如何生成⼀个产生 0,1,2,3 的等概率随机 数生成器? ................................................................................................................................................................................... 34 5.3 有一枚硬币,以 P 的概率产生正面，以 1-P 的概率产生背面，如何利用它产生个 0.5 概率的生成 器？ ................................................................................................................................................................................................ 35 5.4 A,B,C 三人轮流扔硬币，第一个扔到正面的人算赢，问三个人赢的概率分别为多大？ ............. 35 5.5 A 有 N 个硬币,B 有 N+1 个硬币,谁丢的正面多谁赢,问 A 不输的概率？ ........................................ 35 5.6 一个机器人在原点，右边有一个距离为 K 的点，机器人以 P 的概率右移一步，1-P 概率左移一 步， 问经过 M 步机器人处于 K 点的概率? ................................................................................................................ 36 5.7 扔硬币直到连续两次出现正面，求扔的期望次数 .......................................................................................... 36 5.8 同样可以实现互斥，互斥锁和信号量有什么区别？ ..................................................................................... 37 5.9 请用普通的互斥锁编程实现一个读写锁.............................................................................................................. 37 5.10 编程实现三个线程 ABC，并让它们顺次打印 ABC .................................................................................... 39 5.11 简述 LINUX 进程内存空间分为哪几个段？作用分别是什么？ ............................................................... 39 5.12 简述 LINUX 内存分配--伙伴系统 原理................................................................................................................ 40 5.13 简述 MALLOC 实现原理 ............................................................................................................................................. 41 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 4 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    九章算法 http://www.jiuzhang.com 5.14 使用 MMAP 读写文件为什么比普通读写函数要快？ ................................................................................... 41 6. 面向对象及数据结构设计............................................................................................................................................. 42 6.1 LINUX 中如何实现 SIGNAL?......................................................................................................................................... 42 6.2 设计一个抽象类，使得它可以完成有序数组归并的任务 ........................................................................... 42 6.3 设计一个多终端日志打印的接口，使得它可以动态支持不同终端的日志打印 ............................... 43 6.4 设计并实现一个 LRU CACHE .................................................................................................................................... 44 6.5 设计一个数据结构，能够支持插入、删除、返回最大值、最小值、随机返回一个数的操作 .. 45 6.6 设计一个 QUERY SUGGESTION 的服务.................................................................................................................. 45 6.7 什么是双数组 TRIE 树？它的实现原理是什么？ ............................................................................................. 46 6.8 设计 QPS (QUERY PER SEC)函数，用它控制 API 调用，使得 API N 毫秒内只能被调用 M 次?.... 46 6.9 如何设计一个短网址服务系统？ ............................................................................................................................ 46 6.10 如何设计一个网页爬虫系统？ ............................................................................................................................... 47 7. 大数据 .................................................................................................................................................................................... 47 7.1 给一个超过 100G 大小的 LOG FILE, LOG 中存着 IP 地址, 设计算法找到出现次数最多的 IP 地址？ .......................................................................................................................................................................................................... 47 7.2 给定 100 亿个整数，设计算法找到只出现一次的整数 ................................................................................ 48 7.3 给两个文件，分别有 100 亿个整数，我们只有 1G 内存，如何找到两个文件交集...................... 48 7.4 1 个文件有 100 亿个 INT，1G 内存，设计算法找到出现次数不超过 2 次的所有整数? .............. 49 7.5 给两个文件，分别有 100 亿个 QUERY，我们只有 1G 内存，如何找到两个文件交集？分别给出 精确 算法和近似算法? ......................................................................................................................................................... 49 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 5 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    九章算法 http://www.jiuzhang.com 7.6 如何扩展 BLOOMFILTER 使得它支持删除元素的操作？ .............................................................................. 49 7.7 如何扩展 BLOOMFILTER 使得它支持计数操作？............................................................................................. 50 7.8 给上千个文件，每个文件大小为 1K—100M。给 N 个词，设计算法对每个词找到所有包含它的 文件，你只有 100K 内存..................................................................................................................................................... 50 7.9 有一个词典，包含 N 个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所 有英文单词 ................................................................................................................................................................................. 50 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 6 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    九章算法 http://www.jiuzhang.com 1. 笔/面试风格及准备 1.1 实现一个 Memcpy 函数 1.2 STL 中 vector 的实现原理 (衍生：Map, Set 等实现原理) 参考答案： vector 的数据安排以及操作方式，与 array 非常相似。两者的唯一区别在于空间的运用的 灵活性。array 是静态空间，一旦配置了就不能改变；要换个大（或小）一点的房子，可 以，一切琐细都得由客户端自己来：首先配置一块新空间，然后将元素从旧址一一搬往新 址，再把原来的空间释还给系统。vector 是动态空间，随着元素的加入，它的内部机制会 自行扩充空间以容纳新元素。因此，vector 的运用对于内存的合理利用与运用的灵活性有 很大的帮助，我们再也不必因为害怕空间不足而一开始要求一个大块头的 array 了，我们 可以安心使用 array，吃多少用多少。 vector 的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。一旦 vector 的旧有空间满载，如果客户端每新增一个元素，vector 的内部只是扩充一个元素的空间， 实为不智。因为所谓扩充空间（不论多大），一如稍早所说，是” 配置新空间/数据移动/ 释还旧空间 “的大工程，时间成本很高，应该加入某种未雨绸缪的考虑。稍后我们便可看 到 SGI vector 的空间配置策略了。 另外，由于 vector 维护的是一个连续线性空间，所以 vector 支持随机存取。 注意：vector 动态增加大小时，并不是在原空间之后持续新空间（因为无法保证原空间之 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 7 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    九章算法 http://www.jiuzhang.com 后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷 贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操 作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。这是程序员易犯的 一个错误，务需小心。 本套面试题由@九章算法 整理奉献。九章算法致力于帮助更多中国人找到好工作，由美国硅谷顶尖 IT 企业 8 一线工程师提供算法培训、面试咨询等服务。官网：http://www.jiuzhang.com 。
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料