2021 年七月中旬,虾皮北京提前批 - 算法工程师 5 道面试题

福利 | 文末免费送电子书:七月在线干货组最新 升级的《2021最新大厂AI面试题》免费送!

问题1:删除链表倒数第K个节点

该题为leetcode第19题。

在对链表进行操作时,一个常用的技巧就是添加一个哑结点(dummy node),它的next忠贞纸箱链表的头结点,这样就不需要对头结点进行特殊判断了。

  • 思路一:计算链表长度

先对链表进行一次遍历,得到链表的长度L,随后再从头节点开始对链表进行一次遍历,当遍历到第L-n+1个节点时,就是需要删除的节点。当我们在头结点前面加上dummy节点后,删除的节点就变为了L-n+1的下一个节点,通过修改指针来完成删除操作。

代码如下:
在这里插入图片描述

时间复杂度:O(L),其中 L 是链表的长度。

空间复杂度:O(1)。

  • 方法二:栈

在对链表进行遍历时将所有的节点依次放入栈,根据栈先进后出的原则,我们弹出的第n个节点就是需要删除的节点,且此时栈顶的节点就是待删除节点的前驱节点。

代码如下:
在这里插入图片描述
时间复杂度:O(L),其中 L 是链表的长度。

空间复杂度:O(L),其中 L 是链表的长度。主要为栈的开销。

  • 方法三:双指针

该方法的优点在于不需要预处理链表的长度

使用两个指针 first 和 second 同时对链表进行遍历,并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时second 就恰好处于倒数第 n 个节点。

代码如下:
在这里插入图片描述
时间复杂度:O(L),其中 LL 是链表的长度。

空间复杂度:O(1)。


今天给大家一个超棒的课程福利——【金融欺诈比赛与序列模型】特训课程!限时1分秒杀!

image.png

本课从kaggle欺诈比赛和序列模型两个角度带你深入了解金融风控领域知识!

kaggle欺诈比赛中:会从比赛背景知识介绍、效率优化,到数据分析、特征工程,再到模型分析、超参数调优,给你一个参赛必备整体思路;

序列模型中:会从RNN、LSTM、GRU,到Seq2seq、Attention,再到Transformer及案例,带你充分了解金融风控领域中需要掌握的序列模型。


课程配备优秀讲师和助教团队跟踪辅导、答疑,班主任督促学习,群内学员一起学习,对抗惰性。同时课程还配备专业职业规划老师,为你的求职规划,涨薪跳槽保驾护航。


课程链接:https://www.julyedu.com/course/getDetail/303

问题2:将数组划分为给定和为k的2部分。

该题为leetcode416题,结题思路如下:

背包问题——能不能装满容量为target的背包

本题要求把数组分成两个等和的子集,相当于找到一个子集,其和为sum/2,这个sum/2就是target

具体步骤如下:

  1. 特例:如果sum为奇数,那一定找不到符合要求的子集,返回False。
  2. dp[j]含义:有没有和为j的子集,有为True,没有为False。
  3. 初始化dp数组:长度为target + 1,用于存储子集的和从0到target是否可能取到的情况。

比如和为0一定可以取到(也就是子集为空),那么dp[0] = True。



  1. 接下来开始遍历nums数组,对遍历到的数nums[i]有两种操作,一个是选择这个数,一个是不选择这个数。

-不选择这个数:dp不变

-选择这个数:dp中已为True的情况再加上nums[i]也为True。比如dp[0]已经为True,那么dp[0 + nums[i]]也是True

  1. 在做出选择之前,我们先逆序遍历子集的和从nums[i]到target的所有情况,判断当前数加入后,dp数组中哪些和的情况可以从False变成True。

(为什么要逆序,是因为dp后面的和的情况是从前面的情况转移过来的,如果前面的情况因为当前nums[i]的加入变为了True,比如dp[0 + nums[i]]变成了True,那么因为一个数只能用一次,dp[0 + nums[i] + nums[i]]不可以从dp[0 + nums[i]]转移过来。如果非要正序遍历,必须要多一个数组用于存储之前的情况。而逆序遍历可以省掉这个数组)

dp[j] = dp[j] or dp[j - nums[i]]

这行代码的意思是说,如果不选择当前数,那么和为j的情况保持不变,dp[j]仍然是dp[j],原来是True就还是True,原来是False也还是False;

如果选择当前数,那么如果j - nums[i]这种情况是True的话和为j的情况也会是True。比如和为0一定为True,只要 j - nums[i] == 0,那么dp[j]就变成了True。

dp[j]和dp[j-nums[i]]只要有一个为True,dp[j]就变成True,因此用or连接两者。

最后就看dp[-1]是不是True,也就是dp[target]是不是True

代码如下:
在这里插入图片描述

时间复杂度:O(n * target)

空间复杂度:O(target)

参考:
https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/416-fen-ge-deng-he-zi-ji-dong-tai-gui-hu-csk5/


问题三:二叉树的后序遍历(非递归)

  • 方法一:递归

树本身就有递归的特性,因此递归方法最简单。

代码如下:
在这里插入图片描述

时间复杂度:O(n),n 为树的节点个数

空间复杂度:O(h),h 为树的高度

  • 方法二:迭代

注意:该代码是基于前序遍历改来的,由于前序遍历是中左右,后序遍历是左右中,所以只需要写出中右左,再进行反转即可得到左右中。

代码如下:
在这里插入图片描述

时间复杂度:O(n),n 为树的节点个数

空间复杂度:O(h),h 为树的高度


问题4:怎么求特征重要性(GBDT RF等)

RF有两种方法:

  1. 通过计算Gini系数的减少量 VIm=GI−(GIL+GIR) 判断特征重要性,越大越重要。
  2. 对于一颗树,先使用OOB样本计算测试误差a,再随机打乱OOB样本中第i个特征(上下打乱特征矩阵第i列的顺序)后计算测试误差b,a与b差距越大特征i越重要。

GBDT计算方法:所有回归树中通过特征i分裂后平方损失的减少值的和/回归树数量 得到特征重要性。

在sklearn中,GBDT和RF的特征重要性计算方法是相同的,都是基于单棵树计算每个特征的重要性,探究每个特征在每棵树上做了多少的贡献,再取个平均值。

Xgb主要有三种计算方法:

  1. importance_type=weight(默认值),特征重要性使用特征在所有树中作为划分属性的次数。
  2. importance_type=gain,特征重要性使用特征在作为划分属性时loss平均的降低量。
  3. importance_type=cover,特征重要性使用特征在作为划分属性时对样本的覆盖度。


评论区回复 “2021”,七月在线干货组最新升级的《2021大厂最新AI面试题 [含答案和解析, 更新到前121题]》,免费送!

持续无限期更新大厂最新面试题,AI干货资料,目前干货组汇总了今年3月-6月份,各大厂面试题。
在这里插入图片描述


本文地址:https://www.6aiq.com/article/1630696606845
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出