年金三银四的招聘旺季已经悄然开始,各个大厂已经开始摩拳擦掌准备招兵买马了,作为竞争最激烈的算法领域,你准备好如何应对算法面试了么?
3月10日,我们邀请到清华大学博士、CCF数据库专委陈旸老师来详解,大厂面试算法都面什么。
大厂面试都面什么?
目前BAT等大厂算法面试基本从理论基础、工程能力、业务理解三个方面来考核候选人。理论方面,会问你分类树和回归树的区别是什么?红黑树和平衡二叉树的区别?工程方面会问你,之前有用过XGBoost和LightGBM么,你们是如何防止过拟合的?业务方面就看公司类型了,比如对于互联网公司,也许会问,对于海量数据相似查找,你们采用的什么技术?
有些公司可能会有现场coding的环节,这个没有讨巧的方法,开个LeetCode会员,开始刷题模式吧。
算法面试题分析
我们通过两个经典算法面试题来看,面对这种题,应该如何向面试官展示分析思路
对10亿个数,取TOP-(有限的内存和计算复杂度)
这道题我们很容易想到排序的方法,比如快速排序,把10亿个数全部排一变,取出前,计算复杂度是n·logn,但这是面试官想要的结果么,有没有复杂度比n·logn小的方法?
要解这个题,我们就要用到「堆」这个数据结构,我们先来回忆一下堆的性质是什么?每一个节点比它的左右子节点小,根据这个性质,再思考,首先要考虑计算复杂度,先取N个数构成一个顶堆,再拿文件数据与顶堆比较,这是一个比较优的解法,整体步骤如下:
-先取前N个数,构成小顶堆,即在内存中维护一个数的小顶堆-然后对文件中读取数据,和堆顶比较:-if比堆顶小,则丢弃-if比堆顶大,替换根节点,并且调整堆,保持小顶堆的性质-所有数据处理完,得到的即是Top-N,算法复杂度O(Nlog(k))
不用任何数学库,如何求出sqrt(10),并且精确到小数点后10位
这是一个典型的二分法的题,我们先考虑10的平方根是在哪两个数之间,是在3和4之间,再精确一点是在两个3.X数之间,且这个数的平方要小于10,核心思想是确定数值的上限与下限,具体代码如下
下面我们来加大难度,给定两个句子words1,words2,和一个相似单词对的列表pairs,判断是否两个句子是相似的,这道题应该如何解?
这里,我们介绍一种非常优雅的数据结构—并查集,这个数据结构主要用于解决一些元素分组的问题,并查集特点如下
-一个树状的结构,要寻找集合的代表元素,只需要一层一层往上访问父节点-根节点的父节点是它自己-管理一系列不相交的集合,并支持两种操作:-合并(Union):把两个不相交的集合合并为一个集合-查询(Find):查询两个元素是否在同一个集合中理解了并查集这个数据结构的特点就好办了,只需通过下面两步就可以判断两个句子的相似度
1、将所有相似的词都合并成相同的集合,在这个集合中每个词的parent都一样2、最后判断words1和words2中的每个词的parent是否一样就行了
解析算法原理
在了解了典型的算法面试题后,接下来我们看下面试过程中经常遇到的算法原理问题,以GBDT与神经网络过拟合两个为案例,我们看看其背后的算法原理有哪些
机器学习面试:请简述GBDT与XGBoost的区别?
GBDT是机器学习算法,XGBoost是算法的工程实现XGBoost加入了正则项来控制模型的复杂度,有利于防止过拟合,从而提高模型的泛化能力GBDT在模型训练时只使用了代价函数的一阶导数信息,XGBoost对代价函数进行二阶泰勒展开,可以同时使用一阶和二阶导数传统GBDT在每轮迭代时使用全部的数据,XGBoost则采用了与随机森林相似的策略,支持对数据进行采样传统的GBDT没有设计对缺失值进行处理,XGBoost能够自动学习出缺失值的处理策略深度学习面试:如何处理神经网络中的过拟合问题?
比较常见的方法是加正则化的系数。在神经网络中损失函数中,可以增加一个额外的正则项(L1或L2)看做是损失函数的惩罚项
L1正则,权值向量w中各个元素的绝对值之和L2正则,权值向量w中各个元素的平方和然后再求平方根其他处理过拟合问题方法,如Dropout、DataArgumentation、EarlyStop等也都是常见的解决方案
常见算法模型
考验你知识广度的时候到了,我们列出了常用的算法模型,供你在备战面试的时候查漏补缺
分类算法:LR、DecisionTree、NaiveBayes、SVM、KNN矩阵分解:ALS-WR、FunkSVD、BiasSVD、SVD++FM模型:FM、FFM、DeepFM、NFM、AFM、xDeepFM树模型:GBDT、XGBoost、LightGBM、CatBoost、NGBoostAttention模型:DIN、DIEN、DSIN、Transformer、BERTEmbedding:Word2vec、DeepWalk、Node2Vec、GCN时间序列:AR、MA、ARMA、ARIMA、LSTM强化学习:Value-Based、Policy-Based、Actor-Critic大数据计算:PySpark
常用工具箱
没有人能熟悉所有的工具,根据你的技术栈选择合适的工具即可
数据预处理
特征编码:OneHotEncoder,LabelEncoder,SparseFeat,DenseFeat,PCA
特征工程:FeatureTools
Embedding:Gensim
模型工具
机器学习:sklearn,LibFM,xlearn
深度学习:tensorflow,keras,pytorch(掌握其一即可)
自动机器学习:TPOT,auto-sklearn,autokeras
深度学习CTR:DeepCTR
推荐系统:Surprise,lightfm
评估指标:
Accuracy,Precision,Recall,AUC,F1,LogLoss,MAPE,SMAPE
可视化:
Matplotlib,Seaborn,PyEcharts
Offer4步法
在准备简历与面试时,陈旸老师建议通过四个步骤来准备面试,如果你根据岗位JD通过下面方法准备,相信offer离你已经不远啦
Step1:知识储备(必备知识)
面试官考核:相关知识点是否有具备=关键知识点Cover90%
Step2:工程力(上手能力)
面试官考核:给你一个题目,能否在1小时内完成,计算复杂度如何
之前是否有相关项目经验=积累项目简历
Step3:业务能力
对大厂的核心业务,未来战略是否了解,是否match
=大厂之间的交流,参加峰会
Step4:影响力
开源社区影响力
今日话题:说一下你面试遇到问题
你的点赞与