2021 年 6 月底,拼多多搜索广告算法暑假实习面试题 2 道

star2017 1月前 ⋅ 99 阅读

文末彩蛋:七月在线干货组最新升级的《2021 大厂最新 AI 面试题 [含答案和解析, 更新到前 121 题]》免费送!

问题 1:算法题:leetcode 687.最长同值路径

方法:递归

可以将任何路径(具有相同值的节点)看作是最多两个从其根延伸出的箭头。具体地说,路径的根将是唯一节点,因此该节点的父节点不会出现在该路径中,而箭头将是根在该路径中只有一个子节点的路径。然后,对于每个节点,我们想知道向左延伸的最长箭头和向右延伸的最长箭头是什么?我们可以用递归来解决这个问题。

令 arrow_length(node) 为从节点 node 延伸出的最长箭头的长度。如果 node.Left 存在且与节点 node 具有相同的值,则该值就会是 1 + arrow_length(node.left)。在 node.right 存在的情况下也是一样。

当我们计算箭头长度时,候选答案将是该节点在两个方向上的箭头之和。我们将这些候选答案记录下来,并返回最佳答案。

代码如下:

2021 年 6 月底,拼多多搜索广告算法暑假实习面试题 2 道

时间复杂度: O(N),其中 N 是树中节点数。

空间复杂度: O(H),其中 H 是树的高度。

问题 2:算法题:leetcode 322.零钱兑换

完全背包问题——填满容量为 amount 的背包最少需要多少硬币

dp[j]代表含义: 填满容量为 j 的背包最少需要多少硬币

初始化 dp 数组: 因为硬币的数量一定不会超过 amount,而 amount <= 10^4,因此初始化数组值为 10001;dp[0] = 0



转移方程: dp[j] = min(dp[j], dp[j - coin] + 1)

当前填满容量 j 最少需要的硬币 = min( 之前填满容量 j 最少需要的硬币, 填满容量 j - coin 需要的硬币 + 1 个当前硬币)

返回 dp[amount],如果 dp[amount]的值为 10001 没有变过,说明找不到硬币组合,返回-1

代码如下:

2021 年 6 月底,拼多多搜索广告算法暑假实习面试题 2 道

\

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

空间复杂度: O(amount)


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

持续无限期更新大厂最新面试题,AI 干货资料,目前干货组汇总了今年 3 月-6 月份,各大厂面试题。

2021 年 6 月底,拼多多搜索广告算法暑假实习面试题 2 道

2021 年 6 月底,拼多多搜索广告算法暑假实习面试题 2 道


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

更多内容请访问:IT源点

相关文章推荐

全部评论: 0

    我有话说: