● 给定一个字符串（例如abc），和一个文档，给出每个字符在文档中的倒排索引，在文档中找到一个最小窗口（adebdc），使给定字符串是其子串。（解法：使用归并思想，从第一个字符（a）的倒排索引开始，找仅比当前索引大的第二个字符（b）的索引，直到最后一个字符，计算窗口大小，保留最小值，时间复杂度：各字符倒排索引数组大小相加（线性），空间复杂度，O(1)？

● 从字符串中提取所有有效的ip地址？

● 给定一个字符串，和字符串列表，判断能否用字符串列表拼接生成字符串？

● 两个字符串的公共子串，动态规划？

4.1.2 树

4.1.2.1 二叉树

● 求解二叉树的最大高度，用一个非递归的做法

● 二叉树最长叶子结点路径

● 如何判断一棵树是另一棵树的子树？

● 如何判断一棵树是不是平衡二叉树？

● 开发一颗字典树，实现建树和搜索功能

● 有一个词库, 如何像纸制字典一样建立索引？ (B+树)

● 红黑树了解吗，介绍一下？

● 红黑树的查询复杂度？

● 二叉平衡查找树怎么实现平衡？

● 给出二叉树的前序和中序序列恢复二叉树的结构

● 不用递归遍历一棵树

● 二叉树层次遍历

● 给出二叉树的前序遍历和中序遍历结果，构建这棵树

● 描述一下二叉搜索树？

● 时间复杂度为O(n)、空间复杂度为O(k)的树的搜索方法

4.1.2.2 堆

● 什么是堆，构建堆的复杂度，堆找出第k大元素的复杂度？

● 描述一下堆排序、什么是大顶堆、什么是小顶堆

● 一个数组找 top-K，堆遍历数组。（k 最大）为啥用小顶堆。大顶堆小顶堆的区别？

4.1.3 排序

● 有哪些排序算法，他们的时间复杂度是多少

● 海量数据前k大

● 只给一分钟思考口述如何在时间复杂度最低的情况下找到无序数组中的第k个数。（快排+剪枝）

● 一亿个浮点数，大小不超过2^32，均匀分布在值域内，求最快的排序方法；分析排序方法的复杂度（面试官全程提示）

● 手写快排

4.1.6 搜索

● 题目: 最少新建道路条数

已知有N个城市，城市编号1...N

已知M条路，每条路表示为(x_i, y_i), xy分别为城市编号

现在需要新建道路，确保任意两个城市之间，是可以通过一条或者多条道路联通

求解能够达到此目的的最小道路条数

思路：BFS或者DFS应该都可以找到城市簇即可

4.2 算法思想实战及智力题

4.2.1 算法思想实战

● 一条无限长的x轴，假设你站在原点，可以向左走也可以向右走，第n次走n步或者-n步，给一个target，问走到target的最小次数

● 一个黑盒里有n个球，球分为三种颜色，RGB，乱序，每种颜色的球n/3个。这个黑盒有两个接口，一个接口可以获取第i个位置的球颜色，一个接口可以交换两个位置的球。通过这两个接口将球排序成RGBRGB这种的顺序。

面试官先上让我不考虑时间复杂度说出一个解法，我说了一个O(n^2)的解法。

然后他让我想想有没有更好的解法，我想了大概5分钟，恍然大悟，说了一个O(n)的解法

● 一个快递员送快递，有n个城市，怎么选择路线，使得走的路程最短。

● 给一个数，怎么快速求这个数的二进制中有多少个1？

● 实现一个数据结构，满足set(index,value),get(index),setall(value)的操作尽可能高效，使得get(index)返回正确的结果。

4.2.2 智力题

● 有一座桥，A通过需要25分钟，B通过需要20分钟，C通过需要10分钟，D通过需要5分钟，一个桥同时只能走两人，且快的人需要等慢的人到达才能一起到达。走桥时必须要有手电筒才能经过，且手电筒只有一个，问如何在60分钟内使得四人均通过？

● 长m，宽n的长方形，每长度为1画一条线，问可以找到多少正方形（m*n+(m-1)(n-1)+(m-2)(n-2)+...+(m-n+1)*1）？多少长方形（C_{m+1}^2 * C_{n+1}^2，即在m+1个点中随机选2个，在n+1个点中随机选2个）？

● 两个人 A,B；A 红绿色盲，B 声称自己不是红绿色盲，现在 B 两只手上分别有红绿两颗球。

问 A 怎么分辨出 B 是不是红绿色盲。

● 你有两根均匀的绳子，和一个无限燃料的打火机。每根绳子若点燃一头可燃烧1分钟。问如何用这些东西准确测量出45秒的时间？

● 在面试官快要不耐烦的时候想出来了正解…绳A点燃两头，绳B点燃一头。在绳A燃尽时点燃绳B的另一头，两根绳子全部燃尽总耗时45秒。

● 8个小球称重；如果不知道次品轻重怎么办？

4.3 其他方面

4.3.1 数论

● 在A地有两辆公交车，一辆间隔5分钟，一辆间隔7分钟，问等车时间的期望。

● 掷骰子，问掷到6个面全出现的期望？

4.3.2 计算几何

● 拉格朗日乘子法，hessian矩阵

4.3.3 概率分析

● 长度为1的线段，随机地取两点A和B，求AB长度的概率密度函数？

● 8个球有一个重一点，最少称几次能找出来，我说3次，后来鼓起勇气问他要几次，他说两次，让我自己想怎么称？

● 给定随机函数R，以p概率产生1,1-p产生0。生成随机函数R'，以1/2概率产生0,1？

● 54张扑克牌，分成三等份，大小王在同一组的概率？

● 求一根绳子被切两刀能组成一个三角形的概率。

● 有一苹果，两个人抛硬币来决定谁吃，先抛到正面的先吃，问先抛者吃到苹果的概率？

● 0 1 2 3 4 5 6 7 8 9 下面写一个数，使得下面这个数刚好是这个数字在下面一行出现的次数

● 投篮命中率10%，那么a.投10次中1次 b.投10000次中<1000次，哪个概率大？

● 一段绳子分三段，组成三角形概率？

● 棋子在规定走法，规定大小的棋盘上，N步后还在棋盘上的概率，主要考察动态规划

● 一个NxN的棋盘，一个棋子可以等概率地跳八个方向（和象棋中马一样的跳法）。当这个棋子跳出棋盘范围的时候，就停止。问棋子跳了k步之后，棋子还留在棋盘的概率。

● 学校男生的概率2/3，女生的概率1/3，男生穿牛仔的概率2/3，女生穿牛仔的概率1/3，你看到一个穿牛仔的，问他是男生的概率是？

● 六边形，顶点上各有6只毛毛虫，可以沿着边走，两个毛毛虫相遇的概率，n边形呢

● 有A、B两枚不同的硬币，它们正面朝上的概率不一定是0.5，且两枚硬币正面朝上的概率不一定相同。现在做1000次这样的实验：从两枚硬币中随机抽一枚抛一下，记录下正面，重复100次/10次。问如何通过这1000次实验的结果求出A、B两枚硬币正面向上的概率？

● 一个总数很大的数据流，希望以等概率的方式进行样本数为一的抽样，怎么做？

● 将一根木棍分成三段，求这三段构成三角形的概率？

4.3.4 矩阵运算

● 一个m*n矩阵，从左往右逐步递增，下一行比上一行数都打，查找某一个值是否出现？

● 说一下矩阵的秩?再说一下矩阵的特征值和特征向量?(数学专业背景)

4.3.5 其他

● 贪心和DP介绍一下？

● DP 的一般做法流程？

● 布隆过滤器知道吗？用在什么场景下？推导会么（加分项）

● 线性回归多变量求解的过程，为什么这样求解？这样求解为什么是最优解？

● 纳什均衡看过吗？

4.4 Leetcode&剑指offer原题

● Leetcode 原题：接雨水

● Leetcode 23：合并K个升序链表

● Leetcode 236 ：判断围棋死活

● Leetcode139：单词拆分

● Leetcode 382：链表随机节点，并口述蓄水池采样算法的推导

5 编程高频问题：Python&C/C++方面

5.1 python方面

5.1.1 网络框架方面

5.1.1.1 Pytorch相关

● tensorflow和torch的区别？

5.1.1.2 Tensorflow相关

● Tensorflow如何读取数据？

● TensorFlow 的参数初始化机制？

● Tensorflow写一个全连接层的代码？

5.1.1.3 Caffe相关

● 对caffe源码熟悉程度。（我扯了扯源码的底层设计模式，数据流怎么流的，如何添加新层、cuda代码的细节）

5.1.2 基础知识方面

5.1.2.1 线程相关

● Pyhton线程和协程的区别？

5.1.2.2 内存相关

● python语言怎么处理内存溢出的情况，怎么设计内存回收？

● Python的内存管理

● Python垃圾回收机制

5.1.2.3 区别比较

● 说说list和tuple的区别？ list和set的区别，装饰器

● 生成器、迭代器的区别？

● copy，deepcopy，赋值的区别？

5.1.2.4 讲解原理

● Python里面的字典的key可以用list吗？可以用tuple吗？可以用set吗？为什么？从底层实现原理说一下？

● Python里面的循环很慢，为什么？

● Python怎么生成一个迭代器？

● 讲一下yield关键字？它的作用是啥？

● 什么是装饰器？

● 说一说python重载(面像对象)

5.1.2.5 讲解应用

● Python、C++、Java 哪个用的多一点？值传递和引用传递区别。

5.1.3 手写代码方面

● Python字典的删除实现

5.2 C/C++方面

5.2.1 基础知识

5.2.1.1 线程相关

● C++多线程熟不，有什么库？你使用过什么库？

5.2.1.2 内存相关

● C++中的内存泄漏是怎么发生的？

● 如何避免C++中发生内存泄漏？

5.2.1.3 区别比较

● C 的动态库和静态库？

● C++中引用和指针的区别？

● C++ operator new和new operator的区别

● C++的继承和Java继承的区别？

● 接口和类的区别？

● C++、Java、Python的主要区别 (编译型语言和解释性语言)

5.2.1.4 讲解原理

● C 的相关特性，多态？

● C++中map、hash_map底层实现及增删改查的复杂度

● C++智能指针了解吗？

6 操作系统高频问题：数据库&线程&常用命令等

6.1 数据库方面

● 数据库：什么是主键？主键的作用？

6.2 操作系统方面

6.2.1 TCP协议相关

● TCP与UDP的区别

● TCP/UDP 简单介绍一下，如何用UDP来实现TCP

6.2.2 线程和进程相关

6.2.2.1 区别比较

● 线程和进程的区别？

● 进程、线程的区别和联系，线程共享哪些资源

6.2.2.2 讲解原理

● 线程进程是什么、什么关系、什么时候用线程，什么时候用进程？

● Linux 多个进程如何通信的？

6.2.2.3 讲解应用

● 详细讲讲线程进程的区别，还有一些具体场景下的变化

6.2.3 常用命令

● Linux如何查看进程

● Linux中查看进程状态和查看开放端口的命令

● 常见的操作指令，还有一些场景题：例如shell里面写查询一个服务器日志文件中访问最多的那个ip

7 技术&产品&开放性问题

7.1 技术方面

● 问一个区域确定人口中心划区域用什么方法，开始我说用k-means，然后他问我具体怎么实现。我说先设定一个k值，他问k值怎么定，拍脑门吗？不过在没有先验信息的情况下，确实没法选，就多试几个不行吗。然后我说那用密度聚类。那密度聚类的密度函数用什么？

● 由于拍摄焦距的原因，有些图片的前景很清晰，但是背景很模糊。导致分类的之后分成了不清晰的图片。你觉得有什么解决的办法？

学一个mask的网络，把图像中清晰的部分扣出来。再去分类。

我说了用一些传统的手工特征如SIFT，HOG之类。去比较每帧之间的差异。

● 大量数据，亿为单位，找出与给定数据最相似的一个？

● 如何检测视频转场的时间，转场就是拍摄的场景变化了。

用光流算法？或者用LSTM（这里问了很多，比如光流的好处，LSTM的好处之类的，如何使用LSTM）

● 给饭店确定菜系，是鲁菜、川菜、西餐、混合菜系。。。你需要收集哪些数据，用什么方法？

● 对一个数据，比如点击率，应该做哪些处理？

● 现在的搜索技术很少上深度学习或者说很深的网络，你觉得是为什么？如果要用深度学习，你觉得应该往哪些方向思考？deep learning比较吃资源，不太适合业务规模比较大的系统，比如：双十一的压力，如果一定要用，可以考虑深度模型压缩，量化，矮胖网络的并行计算等方向。

● 在一个坐标系内，用户和商户都有自己的坐标（x,y），那么我想找到距离用户最近的k个商户，如何最快的得到？

● 比如淘宝搜索时的自动补全该怎么做，用什么模型或者算法（之后查了一下用模糊匹配）

● 原始数据被污染了怎么办，这时候怎么判断是模型的问题还是数据的问题。

● 通过一个单目固定相机，如何获得室内桌子等物体的3D信息（回答的是3D CNN + 卡尔曼滤波）

● 给了一个情景，如何训练模型、调优。（题目很空，主要考察你对深度学习的理解）

-根据需求（前向传播时间、模型大小），确定模型和基础网络，跑第一版模型。（举了个栗子）

-判断模型是否出现过拟合的情况，来决定下一步的优化方向。

-结果分析(confusionMatrix等)，分析问题，将论文中的方法套上去，如果没有自己创造。（又举了个栗子）

● 设计一个情景，倾斜字体检测，问我有什么好的想法？（我觉得应该是他现在遇到的问题）

数据增强，加入形变扰动。

非end-to-end版本：分别训练检测和分类，举了之前做过的一个文字识别的项目的实现。

end-to-end版本：加入仿射变换学习因子，学习字体倾斜的角度和形变。

● 如果让你设计一个推荐系统，你会设计一个什么样的架构？你设计的重点是什么？

● 在广告推荐的时候，我们常将展示出来但是用户没有点击的广告作为负样本，然而其实有的时候真实的情形是用户没有注意或者没有看见这个广告，

也就是说这条广告不是真正的负样本，用户对其可能是感兴趣的，这种情况该如何处理？

● 对抗学习有了解吗？你觉得该如何将NLP和推荐相互结合？

● 为什么人工智能在图像里应用落地更好，在nlp不行。谈谈你的看法。

● 双十一时向用户发放优惠券，希望在成本一定的前提下，使得盈利最大化，该如何建模发放给用户？用户无法做AB测试，该怎样划定正负样本？

● 模型上线时应该注意的事，如果请求过高模型服务挂了怎么办？

● 假设我们有很多数据给用户看到，但是我们只知道一部分的数据用户是否点击了，其他的我们都不知道用户是否点击了（相当于没有标签），如果是你的话，你怎么解决这个问题？

● 根据你的经验，你认为深度学习比传统机器学习好在哪里？（1. 特征工程：学习能力更强，同样多的数据，深度学习可以更准确地提取特征，而且深度学习可以自动提取特征，而传统机器学习很多需要手动提取特征 2. 比较灵活，我可以自己决定CNN有多少个卷积层，多少个池化层等等）

● 有没有非网络技术上的攻击，就是对模型本身的攻击？如果有，怎么应对？

● 怎么防止新来的错误数据对原有模型进行特别大的改变，怎么防数据污染，蓄意破坏？

● 双目相机识别目标深度的原理，以及PnP算法的原理

● 支付宝年末要出一个年终总结，那么我要对所有用户的交易额度进行全量的排序，那么内存肯定是不够用的，这种情况下应该怎么做？

● 输入是一个短文本，判断是否是服装相关内容

● 阿里有很多商品都是由一段话来描述的，现在让我来设计一个模型，输入是商品的描述，输出是描述商品的一句简短的话，要求用户看到这句话后尽可能保证不降低用户的体验（包括购买率、点击率、浏览量不要下降）

● 给定一堆商品C，每个商品c对应有标题、描述，给定标签：时尚风、复古风、百搭风。设计技术方案，把每个商品c的主题标签给分类/聚类等弄出来。没有训练数据，有哪些方案？

● 做分类的时候如何评估好坏呢？追问比如:你分类总数为2，但是现在出现第3种类别，怎么办，例如做的分类是男女分类，现在有个中性的人，那你怎么办呢？如何应对这种情况？

● 场景题:如何从百万数据中找出最大的k个数？分治+堆排序

● 一个很大的日志文件里面存了各个ip访问的信息，几百G，如何统计里面某个ip地址访问的次数？

答：不一次性读取，分批读，缓存，然后分别统计，最后加起来。

● 开放式探讨：如何使用强化学习去实现个性化商品推荐？

● 一个超级大文件，每一行有一个 ip 地址，内存有限，如何找出其中重复次数最多的 ip 地址

7.2 产品方面

● 怎么给新上架的商品做冷启动？

● 口碑要拉新客，我们的策略是发红包，怎么如何在预算有限的情况下发红包能让最多的用户来安装口碑呢？

● 给你一些用户每天的相对位置信息，怎么区分它们的职业？怎么判断上线的现金贷产品的盈利能力？

● 天猫有1000万条数据，如何找到使用人数最多的前1000个？

● 给你淘宝的商品总量，怎么预测拼多多的商品总量

● 给出用户的数据和交易记录，如何判断是否给他开通花呗？

● 在有各种用户的数据，上网状态，手机型号，用户照片等数据的情况下，怎么判断支付是否存在欺诈？

7.3 开放性问题

● 当碰到难题时，团队士气低落的时候，作为团队的一员，该怎么去做？

● 如何把AI技术用到素材生成和智能分发场景中？

● AI还有哪些能够应用到视频上的？

● 你觉得在公司或企业里，工程和算法的界限是什么？

本文由大白智能作者：凯哲发表，其版权均为大白智能所有，文章内容系作者个人观点，不代表大白智能对观点赞同或支持。如需转载，请注明文章来源。

算法面经(51)

上一篇：字节跳动算法面经秘籍(中) 下一篇：滴滴算法面经秘籍