字节跳动算法岗武功秘籍（中）-FlyAI

字节跳动算法岗武功秘籍（中）

Python3

最后更新 2021-06-16 14:40 阅读 5323

最后更新 2021-06-16 14:40

阅读 5323

Python3

![](https://pic2.zhimg.com/v2-b4fc97de009143765121a34ef013d3de_r.jpg)

字节面经目录

> 1 字节跳动面经汇总资料
2 字节跳动面经涉及基础知识点
3 字节跳动面经涉及项目知识点
4 数据结构与算法分析相关知识点
5 编程高频问题：Python&C/C++方面
6 操作系统高频问题：数据库&线程&常用命令等
7 技术&产品&开放性问题

**3 字节跳动面经涉及项目知识点**

3.1 深度学习-CNN卷积神经网络方面

3.1.1 目标检测方面

3.1.1.1 讲解原理

●  RoI Pooling 和 RoI Align， 怎么做插值，线性插值，spline插值，写插值公式,这个问题二面和三面都被问到了

●  比如ROI Align相较于ROI Pooling有什么改进之类的

●  detection 的发展，从 RCNN 到 CenterNet

●  着重讲 Faster RCNN，问的非常细, RPN原理,。9 种Anchor怎么来的，为什么这样设计Anchor。哪些为正类，哪些为负类。Loss怎么设计的，tx，ty，tw，th。

●  说下R-FCN与Faster RCNN的区别

●  怎样理解R-FCN的PS RoiPooling？

●  RPN中正负样本的阈值为（0.7、0.3），中间（0.3-0.7）的不选用会有什么后果？为什么需要把正负样本的阈值设定在这两个相隔较远的值？

●一直在问faster rcnn，faster rcnn RPN流程，anchor选的太大或太小有什么影响，正负样本选取的时候为什么用0.7和0.3的超参，与nms使用0.3的超参是否有关，smooth l1损失为什么不用l1，为什么不用l2，w，h回归的时候为什么要用log，x，y回归的时候为什么用除法等等。

●  讲一下SSD流程

●  faster rcnn、yolo、ssd的区别？

●  ssd 各种变体

●  Yolov2 v3的提升：小物体检测上的提升

●  Anchor free检测算法了解吗，怎么回事

●  发展过来的前世今生，yolo全套,ssd,faster rcnn具体细节，代码实现，工程中需要考虑的实际问题

●  anchor free框架，基本思想，不同网络的具体对比，hourglass结构的好处，损失函数，我自己的框架具体结构，和sota比性能如何（map更高速度更快），新的损失函数为什么这么设计？

●  介绍下cascade rcnn

●  目标检测框架，two-stage， one-stage；

●  对目标检测问了很大细节，包括BN的训练，ROI Pooling和Allign的细节，FPN网络的细节

●  YOLOv3和其他的目标检测有研究吗？为什么选YOLOv3？这个和其他Fast-RCNN类型的有什么区别？SSD和YOLOv3的区别？

●  问检测中能提升速度但不损失性能的操作有哪些？用过的没用过都行。

●  介绍一下retinaface？

●  介绍了一下Centernet?

●  单阶段的检测方法如YOLO为什么对负样本需求更大？

●  Yolov3中anchor尺寸的设置？

●  数据增强的常用方法，以及项目里用的数据增强，目标检测中的数据增强？

●  两阶段方法与一阶段方法的对比及其优缺点，focal loss的表达式，anchor free方法的优缺点？

3.1.1.2 损失函数

●  讲一下Focal loss，公式是什么?它解决了一个什么东西？答：难易样本不平衡再问:如何解决的,和难例挖掘OHEM有什么区别?

●  Focal Loss和OHEM的区别，Focal Loss解决了正负样本不均衡吗？

●  faster rcnn损失函数的构成？

3.1.1.3 手写代码

●  手写NMS（真的是非常简单的一个题了），我是把官方的NMS背下来然后写上去了

●  画出faster rcnn 流程以及RPN的具体过程

●  实现NMS的全过程：包括按score排序（我当时选的归并），IOU的计算，NMS的操作（选出最后的框）

●  实现计算IOU的函数，扩展：当bounding box与坐标轴不平行时怎么计算，说出思路？

3.1.2 目标追踪

●  目标跟踪里匈牙利算法的流程？

3.1.3 图像分割

●  讲一下unet和deeplabv2的流程，顺便问了下deeplabv3是否了解？

●  介绍一下Unet？为啥要这么设计，好处是什么？

●  FPN和Unet的上采样用了直接想加和concat，有什么区别，从反向传播的角度来说说

●  基础知识，比如分割的网络有哪些，网络是如何优化的等等？

●  语义分割中miou计算公式?

●  了解哪些语义分割算法？

3.1.4 OCR

●  我有一个中文的OCR识别模型，现在如何得到一个日文的识别模型？    （这里我想说翻译，但是感觉OCR本身就有自己的误差，加上翻译的误差可能会导致准确率很低， 所以我说的是中文训练之后再做迁移。但是感觉他想听的是翻译模型。）

●  OCR可以在不同的场景下识别出文字，但是在我们做AR实景翻译的时候，由于场景很复杂，所以识别出来的文字送到翻译模型中的时候就无法确定位置关系    
例如    
离野    
离火    
原烧    
上不    
草尽    
，，    
一春    
岁风    
一吹    
枯又    
荣生

翻译的时候可能会翻译 离野 这种情况该怎么设计一个解决方案？

3.1.5 超分辨

●  自己做的超分辨项目有没有什么创新点

●  超分辨今年有什么改进，有没看过今年的超分辨paper

●  超分辨率用的什么损失函数？（MSE, RMSE，感知损失等）

3.1.6 关键点检测

●  检测到的人脸如何对齐，warpaffine参数，转换矩阵M有几维？

3.1.7 图像分类

●  分类网络训练样本有噪声(错误标注)怎么办

●  分类网络样本不均衡怎么办

●  分类网络想要分很细的类(比如阿拉斯加和哈士奇)怎么办

●  图像分类一般用什么损失函数？（回答交叉熵）  那说一下交叉熵的形式吧？可以写下来，讲一讲怎么来的？  举了逻辑回归中的交叉熵损失，然后讲了公式变换以及对数似然等

●  如果数据集有20%的噪声数据，会有什么影响？可以按照上面写的损失函数来想？

●  对图像分类网络的发展历程和进展有了解过吗？比如resnet, inception这些

3.1.8 姿态估计

●  姿态估计方向的一些知识，比如openpose的实现过程，PAF的原理？

●  姿态估计除了MSE还能用什么loss，还讲了些其他相关论文里用到的一些方法，面试官对相关方向很懂，问了很多问题？

3.1.9 目标重识别

●  Reid里MGN网络的设计，为什么有三条支路？将局部特征加入的会有特征冗余，为什么还要加入局部特征？

3.1.10 人脸识别

●  FaceNet里的triplet loss的公式，反向传播如何更新？

3.1.11 图形图像方面

●  Phong模型，如果能量不守恒了怎么办

●  渲染管线

●  迟渲染和前向渲染的区别，Tile-Based Rendering

●  MRT

●  FrameBuffer

●  Z fighting

●  光线与三角形求交

●  你所理解的PBR

●  抗锯齿技术(MSAA TAA等等)

●  OpenGL中Blend方式

●  渲染半透明物体，次序无关的半透明(Depth Peeling和Per-Pixel Linked Lists3.1.12 视频编解码

●  VVC都了解哪些部分？

●VVC affine AMVP的参数获取流程（讲了构建候选列表，利用梯度计算偏移值做运动搜索，cost比常规amvp小再做八个点的小范围搜索）

●  前面说的梯度计算偏移值，公式推导背景原理知道吗?

●  运动补偿的差值怎么做的知道吗？

●  merge列表构建过程（空域相邻、时域同位块、基于历史、成对平均、零mv）

●  DMVR、PROF和BDOF这些了解多少？

●  编写代码：PSNR计算函数

●  编写代码：十进制转十六进制函数

**3.2 深度学习-RNN递归神经网络方面 **

3.2.1 自然语言处理NLP

3.2.1.1 讲解原理① Bert

●  Bert的输入是什么？讲一些细节，你对BERT有什么可以改进的地方？

●  说一下Bert的嵌入层，然后就是各种关于Bert的细节问题？

●  Elmo和Bert的区别？ Bert细节（多头和缩放）

●  Bert的原理和Word2vec的区别？

●  解释Bert， Bert好在哪里？

●  ELMO模型和Bert模型的比较，position embedding|sentence embedding|mask embedding如何拼接的，position embedding细节？② Transformer

●  解释下Transformer结构？

●  Transformer的结构。bert里的编码方式。

●  Transformer中为什么要除以根号dk，为什么能加快收敛速度，为什么加了根号？

●  说一下 Transformer 中为什么 decoder 比 LSTM 慢？③ CRF

●  阐述CRF的原理？

●  CRF与HMM关系，区别？

●  阐述BiLSTM的BP过程，为何BiLSTM后接一层CRF会有提升？CRF层自己是怎么实现的④ Word2vec

●  神经网络中的word2vec了解么？详细讲解一下它们的原理？包括两种训练方式及效率等

●  W2V 的原理 ，两种生成方式，W2V的思想到底是什么，为什么要这样做，W2V的缺点，W2V中所用的softmax 比起普通softmax有何区别，为什么能减少计算量（我并不是搞自然语言的，这一波问的我有点捉襟见肘，只是勉强回答了，面试官很好，我没回答清楚地就给我讲，引导我）

●  word2vec如何训练，hierarhical softmax和negative sampling（后面的没印象了）

●  Word2vec两种方式，怎么优化，负采样

●  除了word2vec的其他embedding方法

●  word2vec如何训练的，细节，权值矩阵如何训练

●  word2vec训练时如何加速

●  word2vec原理，如何得到词向量？如何分词，分词原理？

●  说一下 word2vec，为什么通过对单词预测可以学习到单词的 Embedding？⑤ CNN的应用

●  CNN在文本中的用法，pooling的作用，有哪些pooling？

●  CNN，RNN，Tansformer分别如何编码文本⑥ 其他

●  词向量 onehot的缺点 word2vec，glove，elmo，bert区别

●  你能详细的说一下CBOW和skip-garm它们的区别么？分别适用于什么场景？

●  千万向量中如何找到和单个向量相似的那个

●  给你一段文字，如何提取文本特征    答：TF-IDF（解释了一下原理）；word2vec；one-hot；（其实GLOVE ELMO这些也可以讲一讲，不过一时间没想起来）

●  现在最火的NLP模型是啥（项目中用了BERT， 然后上个月的XLNet目测效果更好）

●  聊了textcnn，lstm attention

●  TF-IDF分别表示什么及公式？

●  Fasttext模型为什么比word2vec快，隐层怎么处理的？

●  知识图谱学习得到的Graph Embedding是用于召回还是排序（召回）（1.有噪声；2.因为对于传统观点的召回来说，精准并不是最重要的目标，找出和用户兴趣有一定程度相关性但是又具备泛化性能的物品是召回侧的重点，所以可能知识图谱的模式更适合将知识图谱放在召回侧。）

3.2.1.2 损失函数类

●  讲一下NLP中常用的损失函数？

●  项目里有CTCLoss，问了一下CTC loss有什么用，不用CTC的话怎么办？3.3 强化学习3.3.1 讲解原理

●  强化学习DQN，DDQN，AC，DDPG的区别

●  介绍一下什么是GAN？GAN用来干啥的,是怎么训练的?

●  GAN是怎么训练生成器、判决器的？（楼主就说了最原始的GAN的交替训练的方法）

●  因为项目中用到了强化学习DDPG，介绍了ddpg的原理，训练细节等

●  介绍GAN中的生成器和判别器

●  通常GAN有不收敛、模式崩溃的问题。怎么让GAN更稳定更好。不收敛的原因分析：在最优解附近震荡，需要约束梯度。

●  让GAN稳定的trick:WGAN的地球移动距离衡量数据分布差异零中心梯度惩罚。权重的L2正则化权重平滑移动（EMA)。均衡学习率。权重归一化。

●  主要介绍了实习项目基于GAN做图像补全的项目：包括网络结构、损失函数、实际效果、指标

●  介绍强化学习的项目（背景、动机、如何建模、输入输出和训练算法说了一遍，说完后面试官问了一些细节）

3.3.2 损失函数

●  我实习中有用过GAN生成人脸，所以问我：GAN的损失函数形式是什么样的？（楼主写出来了，不过忘了写前面的min、max目标，面试官表示没关系，知道我是懂的就行了）

●  GAN的损失函数形式是什么样的？

3.3.3 其他方面

●  强化学习PG的推导

●  新闻推荐如果用强化学习，怎么设计。

●  有木有试过StarGAN之外的方法？

●  文字生成可以用除了GAN其他的吗（说了说RNN，但是感觉NLP这边很多自然语言模型都可以做文本生成啊，根据模型调整输出层？）

●  问在用StarGAN合成人脸表情的时候训练有没有遇到什么困难（额感觉面试官都好喜欢问GAN方向的问题）

**3.4 机器学习方面**

3.4.1 推荐系统

3.4.1.1 讲解原理

●  xdeepfm模型结构公式等

●  user-cf、item-cf公式，原理以及区别？

●  embeding的方法？FM FFM deep FM

●  DeepFM与FM的关联，并描述DeepFM的结构

●  问了下fm，ffm，deepfm的区别

●  讲述一下FFM和FM，之后问了如何处理特征？

●  FM了解么，具体怎么做的，怎么解决权重系数难训练的问题，梯度怎么更新的 ？

●  DeepFM了解么，embedding层是怎么训练的，结构是什么样的，比赛的DeepFM是自己写的么（用的DeepCTR） ？

● 做用户商品交互特征的时候，你知道业界是怎么做的？扯了一下DIN模型的和目标商品的attention做法?

● 排序阶段你知道业界是怎么做的？说了一下点击率模型：deepfm，nfm，wide & deep，dcn，deepcrossing?

3.4.1.2 手写代码

●  了解Deep 模型吗？说了deepFM，手写deepFM的结构（代码）

3.4.1.3 其他方面

●  推荐系统模型收敛的很好，但是多样性可能不好的情况下如何解决

●  搜索引擎算法：搜索引擎的流程是什么样的（不太会，只说了query分析，然后匹配doc）4 数据结构与算法分析相关知识点

**4.1 数据结构与算法分析**

4.1.1 线性表

4.1.1.1 数组

●  排序数组中绝对值不同的个数

●  手撕代码，1.给定一个数组，前面一部分已经排好序，后面一部分也排好序，将整个数组排序

●  数组前半部分和后半部分有序，然后排序(用的归并)

●  S1, S2两个整数数组，已经从大到小排序。 输出最大的K个数, 时间复杂度: 通过k/2的思想，直到把k为到1为止。

●  给定一个数组，找出数组的最长连续子序列。例：3,3,4,7,5,6,8，最长的连续子序列（这里的连续是说连续整数，整个子序列是连续整数，我一开始题都没看明白）应该是(3,4,5,6)，需要返回它们的下标(1,2,4,5)。如果存在多种答案，只需给出任意一组下标。面试官看我不会，让我先写一个暴力的方法，我还是不会啊，然后一个小时过完了，凉凉。

●  n*n的二维数组，求最长上升序列，每个位置都可以上下左右走。 例如：   6，9，9   4，6，8   3，1，3   最长就是1-3-4-6-8-9？解法：DFS   问复杂度是多少，我说n四次方   问怎么优化？用缓存保存dfs过的值，减少重复递归。

●  求无序数组的不连续递增子序列？

● 给定2个数组，一个数组是PID ，里面存的进程号。一个数组是PPID 代表着PID对应位置进程的父进程号。然后删除一个进程，问因为这个进程被删除，而牵连都被删除的进程号打印出来。 其实就是个简单的DFS，建立一个graph，然后dfs直接输出即可。

● 有一个长度为n的数组，求一个数k，k的取值区间为[1, n-1]，使得数组的前k个数和后n-k个数的方差和最小。要求化简方差公式，达到计算子序列方差的时间复杂度为O(n)。化简后要求空间复杂度为常数级别。●  将一个数分成给定的一些数的组合，给出所有这样的组合。比如将10 分成[1,2,3],其中一种为[1,1,1,1,1,1,1,1,1,1]

●  给你一个数组,[1 2 3 5 5 3 ]，每次可以溢出连续的重复数字，移除后得到的分数为连续数字的长度的平方，求让数组全为空时获得的最大分数1 2 3 5 5 3 第一次移除5 5 得到1 2 3 3 ，得到分数是2*2第二次移除3 3 ，得到1 2 ，得到分数是2*2 第三次第四次分别移除1和2，最后得到的总分数为2*2+2*2+1+1第一反应是区间dp,每次遇到连续的重复数字就dp求一次，取最大，但是没考虑2 1 1 1 3 1 1 ，去除3 后又变连续的情况，到最后也没调出来

●  给一个无序数组，找到其中位数（快排，O(n)），问时间复杂度？

●  给定无序的数组，求出连续相邻的子数组中最小值乘以长度，使得值最大的连续数组？

●  给一个无序数组，输出最小的不在数组中的正数

●  非递减数组中查询某个目标值出现个数。解法：二分查找左右边界。

●  扭转有序数组中查找， 比如说[5,6,7,8,1,2,3,4]{ [ 5,6,7,8,1,2,3,4] }[5,6,7,8,1,2,3,4]这种， 要求时间复杂度O(lgN)O(lgN)O(lgN)先看是否扭转，没有扭转用普通的二分做。否则用二分查找查找出扭转点， 然后看要查询的keykeykey在哪一边， 再二分查找就行。

●  数组中元素两两成对，除了一个元素只出现一次，找出该元素。异或有交换律吗？

●  数组中元素两两成对，除了两个个元素只出现一次，找出这两个元素。

●  两个有序数组的中位数？●  [2,3,4,6,2,3],找出数组中每个数字的后边比它大的第一个数？

●  输出数组中位数，第k个元素为前k个数的中位数。

●  连续数组，给定k，求连续数组最小区间。

●  空间上如何优化：滚动数组

●  一维01数组中，求最长的区间，其中0和1数量相等。

●  一个非负数组，求出和为m的最长连续子序列的长度

●  vector<vector<int> >  x 里面，求min(∑i=0n−1∣xi+1[k]−xi[m]∣)min(\sum _{i=0}^{n-1}{|x_{i+1}[k]-x_i[m]|} )min(∑i=0n−1∣xi+1[k]−xi[m]∣),就是每个数组任选一个数字，相邻求差的绝对值，然后再求和求最小。●  编程题：给定一个数组，数组长度为n,数组所有元素x满足：0<x<=n<=1000。求数组中出现次数最多的元素，若多个元素出现次数相同，输出元素值较大的，要求时间复杂度O(n),空间O(1)。

●  给一个数组，求其所有数都平方后，共有多少个唯一的值。

●  数组的全排列（空间复杂度O（1））

●  判断是否存在个数超过数组长度一半的数

●  给一个数组，长度是N，里面的大小也是0～N，用O(n)的时间，O(1)的空间复杂度统计里面数字的个数？

●  旋转数组查找，一个二维DP

●  旋转数组中搜索某个目标值

●  查找一个有序数组旋转后中有无key值。

●  单调不减数组找出一个数最后出现的位置（二分变形）

●  两个排好序的数组，找中位数。这个题如果复杂度O(n)就没意义了，显然是要求写O(log n)的二分查找

●  整数数组找两个相加为k的两个数，先写了扫一遍数组用map存扫描过的元素，她说你这个空间复杂度高，能不能换一个，后来又写个排序后用双指针的版本。

●  给定数组返回任意满足（当前数大于左右两个数），要求时间小于O(n) ，开始想返回随机数，面试官提示小于O(n)就是logn 就是二分

●  K个有序数组，找一个长度最小的区间，在这个区间里至少包含每个数组各一个数。分析：初始化带下为K的最小堆，K个数字是每个数组中的最小值，设置变量max记录k个数字中的最大值，删除堆顶元素，将原堆顶元素对应的数组中下一个元素加入到堆中，调整堆，并且记录当前区间范围为（max-min），重复执行直到某个数组所有值都被删除。

●  问怎么实现一个字符串中找最小的包含所有不同字符的子串，回答用双指针，让证明双指针的正确性。

●  长度为n的数组中有一个数字出现了n/2次，快速找到这个数

●  输入一个二维数组和一个一维数组，例如 [1,2,3,4,5] [1,2,3,4,6] [6,1,2,3,7] [0,0,5,3,2] 和 [1,2,3] 输出[1,2,3]在二维数组中的位置 (0,0) (0,1) (1,2) 直接遍历，然后代码行云流水的写出，然后问我时间复杂度。

●  给定两个unordered数组，数组中每个元素都包含一个int和一个bool,bool表示这个int数值是否应该被delete，每个元素的值可能会出现多次，和不同的状态，将2个数组合并成一个要求：merged后返回一个数组，每个元素智能出现一次不能包含曾经被delete过的元素，这道题我用hashmap做的，做出来分析时间复杂度

●  从n个数字的数组中任取m个为一个组合，返回所有组合，顺序不一样的算一个组合（递归遍历+回溯）

●  给出一个数组，数组中有正数和负数，要求重新排列这个数组，使得原始数组中的正负数交替排列，且保证各自的相对顺序不变。

●  合并n个有序数组

●  二维数组逆时针螺旋打印比如输入123456789abc输出159abc843267

●  最大数组连乘值

●  给定一个数组，找到这个数组中，和等于0的所有三元组。 我说我只能想到n^2logn复杂度的，在面试官提醒下写了，依然没提交，大概思路对就过了

●  一个正整数数组，寻找连续区间使得和等于target，简单的用两个指针做出来了，不过让我证明一下解法的正确性，纠结了一会儿也算是证明出来了。然后如果里面有负数怎么做？

●  数组连续元素最大值的和，动态规划解决

●求和为k的子数组个数

●  两个有序数组求交集

●  两个数组自身元素一样，各自内部的元素不能比较，实现两个数组的排序

●  给了一个字符数组，求这些数组的组合，例如{a,b,c}的答案是{a,b,c,ab,ac,bc,abc}

●  一个数组，一个数出现一次，其他数出现两次，求出现一次的那个数。

●  一个数组，两个数出现一次，其他数出现两次，求那两个数。

●  O(n)时间复杂度和O(1)空间复杂度删除重复元素，数组有序，输入a=[1,1,1,2,5,6,6]，输出a=[1,2,5,6]

●  双指针：比较 i，j，a[i]==a[j] ，j++；不等就交换i+1和j，然后j++，最后返回有效长度。

●  长度为n的字符串中包含m个不同的字符，找出包含这m个不同字符的最小子串。

●  如果用数组实现，数组初始容量为n，每次push到容量上限之后都扩容到原来的两倍，现在push进去m个数，m远大于n，求相比于m的时间复杂度

●  无序数组 Top K，时间复杂度，给出一个最坏复杂度的样例

●  给定一个数组，返回每个对应位置右边第一个比他大的数，没有就是-1，如【4，1，2，5，8】返回【5，2，5，8，-1】

4.1.1.2 链表

●  递归和迭代的反转链表

●  链表反转，二叉树中序遍历递归+非递归

●  二叉树转双向链表（中序非递归遍历修改指针）

●  反转链表中偶数位置的值，例如1-2-3-4-5-6-7 变为 1-6-3-4-5-2-7

●  链表判断是否有环

●  找一个链表中的环

●  链表找环并证明？

●  删除链表A中出现在链表B的元素

●  删除链表重复节点。如1-2-3-3-5-5-6 变为1-2-6

●  删除倒数第k个链表节点？

●  如何用链表实现一个栈，O(1)获取最小值，get_min、如何节省空间，存放最小值，如果有多个，不想多次存放

●  有两个数字，用链表表示，如第一个数123的链表是1-2-3，第二个数4123的链表表示是4-1-2-3，输出两个数求和后的链表表示。

●  求两个链表的第一个公共结点。

●  如何判断两个单链表是否相交并找到交点，这个题没反应过来，所以答得并不好，只大概给了个思路。用两个队列实现栈的入栈和出栈操作。

●  链表的冒泡排序

●k个有序链表合并，问时间复杂度

●  一个链表，奇数下标递增，偶数下标递减，排序使其总体递增。

●  已知单链表，要求奇数位置降序，偶数位置升序，说下思路，再写代码？

4.1.1.3 栈

●  栈和堆的原理和区别？

4.1.1.4 队列

●  两个栈模拟一个队列

●  给定栈，保证栈的效率的同时能够在O(1)返回栈的最大值

4.1.1.5 字符串

●  将一个字符串通过 增、删、改 三种操作得到另一个字符串的最少操作，我当时选的动态规划。

●  有两个字符串，你只可以进行删除操作，问最少进行多少次操作可以使两个字符串相等？例：sea，eat需要两次删除操作

A：这个简单，思路就是用动态规划求两个字符串的最大公共字串的长度。然后使用每一个字符串的长度减去公共子字符串的长度。

Q：那咱们再加一点，如果我想要知道每个字符串需要删除的字符是那些呢？

A：那我们就需要求出最大公共字串具体是由什么字符构成的，思路也是动态规划。(很快就写完了)

Q：好的，那你有什么想要问我的么？

●  字符串最小编辑路径

●  字符串转数字，及边界条件

●  删除字符串中连续的重复字符

●  isUniqueChar 一个字符串内是否有重复字符

●  1，2，...，N中，字符1出现的次数？

●  给定字符串，求最大不重复子串长度

●  最长公共子序列

●  两个字符串，求最短编辑次数使相等

●  给一个字符串，列出所有可能的ip组合

●  给出字符串x，和字符集合y，求x中包含所有y中元素的最短字串？

●  我们输入两个值n和k，n表示我们有从1到n个整数，然后将这些整数都字符串化之后按字典排序，找出其中第K大的。例如:n=15,k=5.那么1-15字符串化之后排序如下:1,10,11,12,13,14,15,2,3,4,5,6,7,8,9。其中第5大的就为13。

●  给定一个字符串S[0...N-1],要求把S的前K个字符移动到S的尾部，比如字符串"abcdef"，前面两个字符 'a' 'b'移动到字符串的尾部，得到新字符串"cdefab"，即字符串循环左移K。要求：时间复杂度O(n)，空间复杂度。

●  给定random7返回random10

●  用 [1,5][1,5][1,5]的随机数生成器生成 [1,7][1, 7][1,7].我给出了一种非常naiive的做法。就是调用两次随机数生成器，变成1 - 25的数。1-21每3个对应1-7里面的一个数， 剩下4个重来。

●  [9,91,87]，变成字符串组合成最大数?

●  判断输入字符串开始或者结尾是否包含非法字符串(前缀树)

●  给定一个n*n的字符盘，和一个字符串，看改字符串是否出现在字符盘中？

●  有一个字符串，判断QWER出现次数是否相同？如果次数不相同，如何修改可以让他们相同。

●  设计一个可动态扩展的字符串类，尽可能降低占用空间和时间复杂度。

●  字符串的全排列，问了时间复杂度（O（n*n！）），以及详细的时间复杂度推导（n是怎么来的，n！是怎么来的），怎么优化（DFS剪枝）。

4.1.1.6 列表

●  列表数字排列可组成的最大数字？

4.1.2 树

4.1.2.1 二叉树

●  什么是二叉树？

●  构建哈夫曼树：本身不了解哈夫曼树，但是了解哈夫曼编码的一些思想，讲出来后，小哥哥引导着思路，然后我写出了代码。代码本身还有优化空间，但是小哥哥也说通过了。

●  二叉树子路径和为k的路径个数

●  给一个类似树的结构，每个节点都可以有多个节点（不止两个树）然后每个根节点和字节点间的路径不一样，求叶子结点到叶子结点的最大路径？

●  两个树节点的最近公共祖先节点？时间复杂度？

●  给定一颗二叉数，每两个结点路径为1，求相隔最远的两个结点的距离

●  蛇形打印二叉树？

●  给出二叉树的层次遍历和先序遍历，求二叉树的后序遍历

●  求两棵二叉树最大公共子结构的节点数目

●  红黑树描述？答：节点是红色或者黑色的，红色节点的子节点必须是黑色的，根节点为黑色，叶子节点（Nil节点）为黑色的，根节点到叶子节点的路径上的黑色节点一样多。

●  加问为什么要使用不同颜色的点？答：红黑树是平衡二叉树的变形，由于平衡二叉树插入删除操作复杂特别是如果插入有序的数字时，二红黑树只要满足节点的颜色要求，在插入删除过程中满足红黑树定义要求，就能满足二叉树的相对平衡。

●  红黑树和AVL的区别？

●  二叉树最大深度，地图中找出大陆的个数（一道BFS题）

●  二叉树最远节点距离

●  给定一个二叉树，求出这个二叉树的宽度和高度

●  什么是平衡二叉树？平衡二叉树的应用都有哪些？

●  判断是否是二叉平衡树？

●  二叉树前序中序遍历，重建二叉树

●  非递归中序遍历二叉树

●  二叉搜索树已知先序求后序(代码实现)

●  二叉树层次遍历

●  二叉树之字型遍历，每行打印

●  打印二叉树中最左边节点

●  一个二叉树的所有右叶子结点之和

●  判断给定序列是否为二叉搜索树的前序遍历

●  给N个数字，返回这N个数字能组成的所有二叉搜索树

●  二叉树输出给定节点到目标节点的路径，寻找两个字符串中只有首尾字符相同的所有子串？例如 ABCDE 和 ADCAE中包含（ABC--ADC）以及（CDE--CAE）

●  给一个二叉树，输出所有完全一样的（重复的）子树。 要求O（N）（code）

●  设计一个数据库的表来存储树形结构（不一定是二叉树），要求（1）输入父节点返回所有子节点（2）输入某节点返回所有兄弟节点

●  判断二叉树上是否存在一条从根结点到叶结点的路径，满足其上的元素之和等于target。

●  给定m个不重复的字符 [a, b, c, d ...]，以及一个长度为n的字符串tbcacbdata，   问能否在这个字符串中找到最长的连续子串，使得这个子串由上面m个字符组成。   return: 子串和起始位置

4.1.2.2 多路查找树

●  给你一个二叉查找树，还有一个数K。如果能找到，就返回节点，如果找不到，就返回空。

4.1.2.3 堆

●  最小K堆，只写伪代码就行

●  找出一颗完全二叉树最后一个节点，时间复杂度要求 logN的平方

●  有M个有序链表（从大到小）。现在我们要取出前K大的元素。

A：（这个我见过，内心美滋滋）我们应该把M个链表的头节点做成一个大小为M的最大堆，每次取出堆中最大的节点，然后将这个节点的后序节点放进来，重新对堆进行排序。

Q：好的，那这个算法的时间复杂度和空间复杂度是多少呢

A：时间复杂度，每次需要 O(logm)O(log^{m})O(logm) ，需要k次，那么总的时间复杂度为 O(klogm)O(klog^{m})O(klogm) 。空间复杂度为 O(m)O(m)O(m)

Q：那建立这个堆的时候时间复杂度是多少？

A： O(mlogm)O(mlog^{m})O(mlogm) ，那总的时间复杂度应该为O((k+m)logm) O((k+m)log^{m})O((k+m)logm) 。

4.1.2.4 其他

●  线段树和树状数组的异同？

●  树的路径和

4.1.3 图

4.1.3.1 拓扑排序

●  写一下拓扑排序

4.1.3.2 最短路径

●  无向无环图中，最短路径的最大值（O(n^3)的解法)，这里考察的其实就是Floyd算法。

4.1.4 排序

●  说几个常用排序算法的时间复杂度、空间复杂度、稳定性？

●  说一下所有的排序方法，并给出他们的时间复杂度？

●  为什么归并排序、快速排序和堆排序都是o（nlogn）的时间复杂度，大家都习惯用快速排序，归并排序和堆排序差在哪？

●  希尔排序知道吗？为什么这么操作？答：改良的插入排序。插入排序在数组基本有序的时候可大大降低时间复杂度，希尔排序通过将数组分块后对每块数组进行插入排序，每次排序完成，块数减少一倍，数组也相对变得有序，知道最后对整个数组进行插入排序，则排序完成。

●  写一个归并排序

●  快速排序和归并排序描述一下，优缺点（描述）答：快速排序：先选定一个基准元素，按照这个基准元素将数组划分，再在被划分的数组上重复上过程，最后可以得到排序结果。	归并排序：将数组不断细分成最小的单位，然后每个单位分别排序，排序完以后合并，重复这个过程就得到了排序结果 。优缺点：归并排序稳定且最高最低时间复杂度都是nlogn，但是占用额外空间；不稳定，最高时间复杂度n2，最低时间复杂度nlgn，不占用额外空间。

●  快速排序很多重复数字如何优化答：返回基准元素位置时返回基准元素的最左和最有索引，减少排序次数。

●  input : 无序的实数数组output：求大小相邻两个数之间的最大差？   排序可以o(nlogn)解决，然后问我怎么优化?

●  手写快排,求TOPK

●  找第K大的数（快排）

●  一亿个浮点数，大小不超过2^32，均匀分布在值域内，求最快的排序方法；分析排序方法的复杂度。

●  有两个数列，将两个数列排序，但是自己数列里面的数字不能和自己数列里面的相比较（快速排序变种）

●  前序中序，求后序

●  手写堆排序

●  海量数据TopK问题。一般这种问题都是用哈希表分治+堆排序，但是当时不会，所以挂了。

●  写一下桶排序

4.1.5 搜索

4.1.5.1 深度优先搜索（DFS）

●  求矩阵中连通域的个数，用bfs或dfs做，很简单。先说思路，然后用自己喜欢的语言做

●  二维数组找最长递增路径。很简单的题，DFS即可4.1.5.2 广度优先搜索（BFS）

●  寻找迷宫中的最短路径，迷宫中1表示有墙，路不通，0表示可以走。我脑子不知道怎么抽了，直接想用DFS来解，给面试官讲了一下思路。面试官提醒我，DFS和BFS你是怎么考虑用哪个的。然后我就明白了，应该用BFS，讲了一下BFS和DFS适用的场景。然后用BFS比较顺利的写出了程序。

**4.2 算法思想实战及智力题**

4.2.1 算法思想实战

●  岛计数问题 dfs

●  两堆钞票，尽可能均分（利用背包问题的思想）

●  著名的 小兔的棋盘，我后来查了一下，是什么卡特兰数。然而面试的时候我没听说过这一道题，不过还是磕磕绊绊地用DFS解出来了，面试官说可以了，也没让我继续用DP来解。哎，算法还是有点菜的。

●  给一个表只有id和时间，如何估算平均访问时长 【撕代码】

●  从用户的访问日志中，选出访问次数最多的topK的用户 我的思路： 因为是实际应用，所以我会想到对数据进行预处理，比如对同一用户在同一分钟内（时间阈值可以自己设定）的多条相同访问日志就保留一条的情况，因为会有因为网络异常或者服务器异常的情况，所以对于用户来说真实的访问记录应该是一条记录。 第二步在用快速排序的思想实现

●  过河问题小明需要踩着石头过河，下一步只能到达距离为3、4、5石头。给一个数组，里面是n个石头，以及石头到岸边的距离。假设从小到大排序，问能否到达对岸（到达第n块石头）？我的方法：用深搜+剪枝的递归实现。复杂度O(n)

●  给定一个词典，词典里是分好的词，再给定一串文本，找到所有可能的分词序列。我用的dfs，优化问题整了我好久。

●  棋盘上的连通棋子团数（最基本的dfs）

●  经典的接雨水问题，然后问能不能空间优化？进一步提问，再给你k个格子，你可以随意安防他们，问安放后最多能接多少雨水？

●  不用api实现 sqrt(x)，要求时间复杂度小于 O(n)

●  不用api实现 pow(x, n) 时间复杂度小于O(n)

●  假设现在你全中国的一亿个商家的位置信息，现在输入一个坐标x，y找出距离你最近的k个商家，收一下思路，写一下代码？

●  小机器人从左下角走到右上角，只能向上或者向右，有多少种走法？

●  如果把一次拐弯当做k，现在传入一个参数k，问在k次转弯下，有多少种走法?

●  给一个数组，进行两次股票交易，最大收益是多少？

●  给定k和n，A和B先后从1-k之间挑出一个数，不可以重复挑，然后每次挑出来都加在一起，当当前的和大于等于n时，当前选手获胜，求给定k和n时，A先手是否能赢（假设两个人每次都是最优策略）

●  一个无序数组，数字代表挡板的高度，挡板没有厚度最多可以盛多少水，如[3, 1, 2] 输出:
44.2.2

智力题

●  在一片草原上有1只羊和若干只狼，狼可以吃羊或不吃羊，但狼吃羊后会变成羊，从而被其它狼吃掉，已知羊不能被两只或以上的狼分着吃掉，并且每一只狼都会先保证自己不被吃掉，而在此前提下每一只狼又都想吃到羊，那么羊是否会被吃掉？

●  43个石头，A,B轮流拿，每次可以拿1~3个，A先拿能否保证自己获胜？

●  1000盏灯开着，1000个人标号1~1000依次进入，每个人进去按一下自己标号倍数的开关，问最后哪些灯亮着？

●  一个人初始体力为m，起始点为0，终点为n。一路上有毒蘑菇和体力蘑菇，用v_i表示，吃了会有体力的增加或减少，走多少步就消耗多少体力。问这个人能否到达终点，如果能，最小体力是多少。

●  我手中有一堆扑克牌， 但是观众不知道它的顺序。 第一步， 我从牌顶拿出一张牌， 放到桌子上。 第二步， 我从牌顶再拿一张牌， 放在手上牌的底部。 第三步， 重复第一/二步的操作， 直到我手中所有的牌都放到了桌子上。最后， 观众可以看到桌子上牌的顺序是：13\12\11\10\9\8\7\6\5\4\3\2\1 请问， 我刚开始拿在手里的牌的顺序是什么？

●  求股票的最大利润，例如[1, 3, 1, 8, 10, 3]，只能买卖一次，计算最大收益能买卖无数次，计算最大收益只能买卖两次，计算最大收益

●  十个红球十个白球，无放回抽出10个然后红球互不相邻的可能性。没想好，不过具体思想就是一红一白相间地摆好先，然后再在白球红球之间插入白球，面试官说时间关系就先这样了，但是很接近了。

●  A和B比赛，A、B获胜的概率分别是0.6、0.4，如果你是A，3局2胜和5局3胜你会选择哪个。

●  n个人之间存在m个关系对，关系具有传递性，假如A关注B，B关注C，那么A就间接关注了C。如果一个人被除他之外的所有人都直接或间接关注，那么这个人就是抖音红人，求抖音红人的总数。

●  25匹马赛跑，5个跑道，怎么以最少的比赛次数来决出最快的3匹(思路分析)

●  三扇门问题。三个门里其中一个有宝石，刚开始你选了一个门，然后主持人开了一个没有宝石的门，问你要不要换？给出具体求解方法。

●  疯狗问题

●  找山顶元素

●  一个岛上有若干人，每个人都戴一顶帽子，不是绿帽子就是白帽子，每个人看不见自己的帽子颜色，可以看见别人的帽子颜色，不能交流。现在知道至少有一顶绿帽子。

●  一个人确定知道自己帽子颜色的时候就会离开，请问岛上会发生什么？ 4.3 其他方面4.3.1 数论

●  求几何分布的期望？

●  泰勒公式，用泰勒公式实现e的计算求值？

●  x,y属于[0,1]的均匀分布，求max（x,y）的期望？

●  丢硬币，连续丢出2次正面才停止，求丢硬币次数的期望？

●  一辆巴士载了25人，路经10个车站。每个乘客以相同的概率在各个车站下车。如果某个车站有乘客要下车，则大巴在该站停车。每个乘客下车的行为是独立的。记大巴停车次数为X，求X的数学期望（要求通过编程求数学期望）。

●  求max(x1, x2)期望？

●  已知var(x),var(y),E(x),E(y)。求 Var(x*y)

●  a , b ~ U(0,1), a 和 b 独立。求 E(max(a,b))

●  假设有一组基向量b1,b2,...,bn,现在有一个向量x，希望能用这组基向量中的三个表示，也即x=w1bi+w2bj+w3bkx = w_1b_i + w_2b_j + w_3b_kx=w1bi+w2bj+w3bk,问如何求解这个问题？

●  定义域值域都是正整数的单调递增函数f，给一个值y，找到使|f(x)-y|最小的x。 （肯定是二分，但其实有很多细节值得注意。如定义域值域都是正整数，所以可以推出f（x）是不可能小于x的，应该是x^n的形式，所以开始搜索的范围就是ed=y）。

●  给一个中文数字，比如一百二十，如何转换为整形数字

●  由长度为length的array表示的整数，允许相邻位数交换，求n步交换内能得到的最小整数

●  编程题：3*x+7*y=125,x,y为质数。如何快速求解？

●  把只包含质因子2、3和5的数称作丑数。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

●  从K个整数中，组合出能被3整除的最大数，例如: [1, 2, 3]，组合出能最大能被3整除的数是3214.3.2 计算几何

●  一个图片中心逆时针旋转30度后，求最小外接矩形长和宽，说一下有哪些解决方法？第一种初中数学，几何知识；第二种，求解仿射变换矩阵（2x3），然后和原图相乘，就得到变换后的图片，也就知道了最小外接矩形的长和宽。

●  现在有一堆点，求一个点到每个点的距离之和最小，证明这个点是质心。4.3.3 概率分析

●  给一个01二项分布的随机器，参数为p，用它设计一个0-1的均匀分布的随机器（连续的）

●  已知x.y的概率分布，求max x,y的分布？

●  一个圆上随机三点，求形成锐角三角形概率，要求数学推导

●  现在我有抛一枚硬币，正面朝上的概率是p,反面是1-p。那么第k次抛的时候出现第一次正面的概率是多少?<img src="https://pic4.zhimg.com/v2-10c8835287846b5464fb8cfea3e9beab_b.jpg" data-caption="" data-size="normal" data-rawwidth="669" data-rawheight="193" class="origin_image zh-lightbox-thumb" width="669" data-original="https://pic4.zhimg.com/v2-10c8835287846b5464fb8cfea3e9beab_r.jpg"/>

●  抛2k+1次硬币，问正面次数比背面多的概率是多大，并讲出数学证明思路。

●  3种颜色砖块，单位长宽，铺满单位宽，长m的地板有多少种铺法？

●  A、B交替抛硬币，正面概率为1/2，谁先抛到正面谁胜。问A先抛并获胜的概率

●  13个人生日都不是同一天的概率，要求给出表达式和最终结果（不用计算器估算）

●  给你一个圆，让你在上面画三角形，要求三个顶点在圆周上，问画的三角形是锐角三角形的概率是多少。怎么求解？

●  2 个人玩游戏，每局获胜的概率都是 50%，A 赢 3 次胜利，B 赢 2 次胜利，求 A B 的获胜概率（就是一个状态转移问题，画了图，秒掉）

●  斗地主农民拿到炸弹的概率是多少，听到这个题都蒙了，完全不知道怎么解，面试官也说他自己都不知道答案，然后就在面试官的一次次提问下写了个大概思路

●  一条线段分成三段能够组成三角形的概率，这个题目碰到过，不过当时没想起来，面试官提示了下解答出来了

●  抛一个不均匀硬币五次，两次正三次反，下一次正的概率p1是多少？

●  抛一个不均匀硬币五十次，二十次正三十次反，下一次正的概率p2是多少？

●  概率题：x, y服从0-1均匀分布，求x+y<1的概率？x, y, z服从0-1均匀分布，求x+y+z<1的概率？

●  一道数学题，A、B两人投硬币，谁先投到正面谁就赢，求先投的人赢的概率

●  问：我们来讨论一个下雨的问题     今天下雨的概率是0.2，天气预报的准确率是0.8. 问已知今天下雨，天气预报预测下雨的概率？

●  在[a,b]之间，a，b为正整数，问其中不包含数字3，5，7数字的个数；

●  一个硬币，正面向上是p，投2k+1次，正面比反面多的概率，写出表达式

●  真硬币m个，假币n个。假币只有正面。真币投掷正面概率为p。其中某硬币投掷k次都是正面，求它为真币概率。

●  斗地主中一个农民抓到王炸的概率

●  一分钟看到红车的概率是0.2，一个小时看到1辆红车的概率是多少

●  N个相同的球，取其中M个(M<N），如何保证每个球取的概率一致？    我答了有放回取样，已取样的做标记，若再次取到有标记的则放回重新取，直到取得M个。    考官让算一下，这么做的期望复杂度是多大。没算出来。

●  如果是头条的用户场景，每天用户总数量是不确定的，但是要抽M人，如何保证概率一致。 考官提示：如果已经有一个函数，使N-1个人中等概率抽取了M-1个人，那么下一个人加入的时候如何保证等概率。    在这个提示下我想到了需要列式使新加入进来的人概率和前一个人上一次中的概率和这一次的概率之和是一致的，以此类推。其实一下子还是没有写出完整表达式，因为时间比较捉急了，我直接用N个人抽N-1个的特殊情况写了递推式，表示取M个的话需要进行变形。考官应该是认为我已经理解了思路，所以结束了这个问题。    总结：保持和考官的交流，有思路及时沟通，一下写不出答案可以先考虑特化情况。

●  x, y服从0-1均匀分布，求x+y<1的概率？x, y, z服从0-1均匀分布，求x+y+z<1的概率？

●  一个概率问题，每个人投票给a概率51%，每个人投票给b概率49%，问投票人数和a最终获得更多票数之间的关系

●  概率题：飞机上有100个座位，有100个乘客准备登机，每个乘客按顺序上飞机，但是第一个乘客喝醉了，随机挑了一个座位来坐。每个乘客的选座位规则：1）如果自己的座位没被坐，则坐自己的位置；2）如果自己的座位被坐了，则从剩下的座位中随机选一个来坐。则第100个人能做到自己座位的概率是？

●  甲乙射击比赛，单局甲胜率0.6，3局2胜和5局3胜两种赛制甲如何选择？

●  网游中杀死小怪时候，有P=0.2的概率掉落一把宝剑，野猪的死亡是独立事件，某玩家杀了10个小怪，求掉落4把宝剑的概率？

●  你有1000瓶饮料，其中有1瓶有毒，你有许多老鼠，老鼠喝完饮料之后24小时会死，请问你平均需要多少天找出这个有毒的饮料？需要多少老鼠？

●  你有1000法力值，有4个技能，技能伤害值与消耗魔法值成正比，请问你怎样用技能，才能做到伤害输出最大？

●  打怪有80%概率掉落a装备，20%概率掉落B装备，请问一个人平均要打几次怪，才可以凑齐ab装备？

●  人群中男人色盲的概率为5%，女人为0.25%。从男女人数相等的人群中随机选一人，恰好是色盲。求此人是男人的概率。

●  甲扔n次骰子，取其中最大的点数作为它的最终点数，乙扔一次骰子得到点数，求乙的点数大于甲的概率。

●  某种病的发病率为1/100，某种检测该病的技术检测正确率为99/100，现有一人被检测到生病的概率为p，求他真实生病的概率是多少？在上一问的基础上，现在连续两次检测为有病才会停止检测，求检测次数的期望值。

●  10个人里每个人在10分钟内的任何一个分钟到达的概率是均匀分布的，问所有人都到达的时刻在几分钟时概率最大。

●  问比赛甲获胜概率0.6，乙获胜概率0.4，该选三局两胜还是五局三胜。再问不通过计算怎么判断？当n为一个趋近于无穷大的奇数时，甲乙获胜概率如何？

●  斗地主有人拿到2张王的概率

●  已知1-5的随机数发生器，怎么生成1-7的随机数发生器

●  假定一个人胜的概率是p，判断五局三胜有利还是七局四胜有利

●  有100个乘客，每个乘客手里有一张座位票，座位是1到100标号。正常情况下应该对号入座。但是第一个乘客喝醉了，他没坐在1号位置，而是从其他99个座位随机选了一个座位。从第二个乘客开始，如果他的座位没有被前面的人占领，他就对号入座，如果被前面的人占了，他就在剩下的座位里随机选一个，问第100个人正确坐到自己座位上的概率是多少？

●  一个圆，问走n步回到原点多少种方法？

●  10个球放到12个盒子里 空盒子=5的概率P=? 用代码模拟10000次的概率是多少？

●  10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用Python程序模拟十万次，暴力求出该概率。

●  假设现在有一个函数random(), n为未知数，1/n的概率返回0，2/n的概率返回1，写一个newRandom()，让返回0,1的概率各为1/2。medium。

●  给定N种不同颜色的球以及每种颜色的球的数量，把它们放进一个容器里面，随机抓取。要求写程序实现该功能，并且要按照每种颜色球的概率返回对应的球的编号。

●  比如，有A, B, C 3种颜色的球，数量分别是1，2，3。然后把它们统一放入盒子里，随机抓取（使用random随机生成(0, 1)之间的小数），要求按照它们各自的频数返回对应的颜色的球。

●  有两张表，第一张表有n个专有名词，比如今日头条、抖音等，第二张表有m条query，比如今日头条是怎样的应用、有多少人喜欢刷抖音等，如何统计表1中所有名词在表2中出现的频次。

●  有一个生成 0-4的均匀分布的整数随机数生成函数，利用这个函数生成0-9均匀分布的整数随机数生成函数。

●  n个[0,n)的数，求每个数的出现次数（不能开辟额外空间）

●  有一个0-1的均匀分布随机器，用它实现一个N(0, 1)的正太分布随机器?

●  一根木棍, 随机切成三段, 求能围成三角形的概率？

●  三个盒子分别放的球为：“红 红”，“红 蓝”， “蓝 蓝”，第一次取出一个红球后，取出两个红球且为第一个盒子的概率？

●  给一个现成的生成器，可以以概率p生成1，概率1-p生成0，让我用这个生成器构造一个新的生成器，满足每次均匀返回0-1之间的一个浮点数？

4.3.4 矩阵运算

●  二维矩阵，求连通区域数量（连通的定义： 两个像素是四邻接的邻居，并且像素值的差的绝对值小于等于16，那么这两个像素是连通的）。

●  蛇形打印n*n的矩阵

●给出一个数字矩阵，寻找一条最长上升路径，每个位置只能向上下左右四个位置移动。

●  m*n矩阵从左上角走到右下角一共有多少种走法？如果有障碍物的话怎么求？求最大的路径和？先从左上到右下在从右下返回到左上，重复走的节点值为0，求两条路径加和最大值？（都是DP）-问时间复杂度

●  矩阵的转置和回旋输出

●  写个矩阵乘法，不让用numpy，再优化下

●  由0和1组成的二维矩阵，找出1的最大连通域，计算其面积。

●  矩阵TopK问题？先说思路，思路不对、复杂度太高的话就不用写了。

●  [(“A”， “B"), ("C", "D"), ("B", "A")]找出该列表中所有的环路？

●  一个二维矩阵由小到大排列，找target数字？

●  给定一个矩阵里面只包含0和1两种数字，给出每个单元距离最近的0的距离？上下左右都算作相邻，相邻的距离为1。

●  有序矩阵中第k小个元素

●  三数之和 = target 找出所有可能三元组4.3.6 其他

●  一个无序数字序列，每次只能左旋操作3个数，求要求有序下，证明能否通过有限次数能否有序。

●  如何判断一个算法是线性的还是非线性的？

●  中位数与平均数什么时候会相等？貌似是数据分布对称就行？

●  手撕代码，开根号，以前没遇到过这个问题，于是写了二分查找。面试官问会不会牛顿法，现场推了下公式，结果牛顿法太久不用公式都忘了，用泰勒展开推了一下写成了拟牛顿法

●  求2的平方根，精度0.00001

●  分解质因数【撕代码】

●  输出幂集（比较简单，给了两种方法，迅速的过了）

●  给出 6 * n 的方块，用 1 * 2 或者 2 * 1 的方块覆盖它。不要求求出具体的个数，证明该方法时多项式级数还是指数级数？

**4.4 Leetcode&剑指offer原题**

●  Leetcode 3 最长不重复子串

●  Leetcode 11

●  Leetcode  32

●  Leetcode 34（简单变形）

●  Leetcode 42

●  Leetcode 72：字符串的编辑距离

●  LeetCode 76：Minimum Window Substring

●  Leetcode 123

●  Leetcode 124

●  Leetcode 148

●  Leetcode 206

●  Leetcode 224：hard，实现一个基本的计算器来计算一个简单的表达式字符串。表达式字符串只包含非负整数、+, -, *, /操作符。可以假设给定的表达式总是有效的。

●  Leetcode 284：一个类A有next，has_next两个方法，其中next调用会返回值，但索引会自增。实现一个peek访问只返回值，索引不自增。

●  Leetcode 306

●  Leetcode 315

●  Leetcode 378

●  Leetcode 448：要求时间o(n)，空间o(1)。

●  Leetcode 560

●  Leetcode 786

●  Leetcode958：判断一棵树是不是完全二叉树

●  Leetcode1047

●  Leetcode原题：链表采样，resevior sampling。要求在一个无限长的单向链表中采样，当遍历的节点数量充分多时，每个节点被采样到的概率应相等。

●  Leetcode原题：正则表达式匹配

●  Leetcode原题：求数x的开方，精确到小数点后一位

●  Leetcode原题：旋转数组查找target

●  Leetcode原题：字符串左移K位

●  Leetcode原题：股票价格

●  Leetcode原题：矩阵右旋

●  Leetcode原题：01 矩阵找最大子矩阵大小

●  Leetcode原题：n的平方根，精度十位小数

●  Leetcode原题：计数质数

Leetcode原题：蚂蚁爬杆●  Leetcode原题：屋舍打劫

●  Leetcode原题：数据流中，按照某个窗口大小，找窗口中的最大值

●  Leetcode原题：最长回文子串

●  Leetcode原题：medium，假设现在有一个函数random(), n为未知数，1/n的概率返回0，2/n的概率返回1，写一个newRandom()，让返回0,1的概率各为1/2。

●  Leetcode原题：一个字符串，一个单词字典，把字符串分成若干个子串，每个子串都包含在字典中，返回多少种分割法？

●  Leetcode原题：hard，现在有一个每行每列递增的2D数列，比如[[1,2,3,4], [2,3,4,5], [4,5,6,7]]，在O(nm)的时间复杂度返回最小的k个数。.

●  剑指offer 41：数据流中的中位数，设计一个数据结构，有插入和删除操作，并且能随时得到数据中的中位数。

>本文来源：知乎

>作者：江大白

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，转载请附上原文出处链接和本声明。
本文链接地址：https://flyai.com/article/918

讨论

500字

表情

发送

删除确认

是否删除该条评论？

取消删除