【字节跳动】数据挖掘面试题0002：从转发数据中求原视频用户以及转发的最长深度和二叉排序树指定值

题目一：从转发数据中求原视频用户以及转发的最长深度

在数据处理和算法面试中，常常会遇到一些基于实际业务场景的题目，
比如根据用户转发数据来分析原视频用户以及转发深度。
今天就来探讨一道这样的面试题：给定被转发用户和转发用户两组数据，求原视频的用户以及转发的最长深度。

有两种数据，分别记录被转发的用户和转发的用户，数据示例如下：

• from：1，1，2，2，3，6
• to：2，3，4，5，6，7

问题分析

• 要求从这两组数据中找出原视频的用户（即没有被其他用户转发，却转发给了其他用户的用户），
• 同时计算出转发的最长深度（从原视频用户开始，到最终转发用户经过的转发次数）。

解题思路

寻找原视频用户

• 原视频用户的特点是在to列表中没有出现过，但在from列表中出现。
• 我们可以利用 Python 中的集合操作，先将to列表转换为集合，方便快速判断元素是否存在，然后遍历from列表，筛选出不在to集合中的元素，这些元素就是原视频用户。

计算转发最长深度

• 为计算转发最长深度，我们可以构建一个图结构，以用户为节点，转发关系为边。

• 从原视频用户开始进行广度优先搜索（BFS），每经过一层节点，深度就增加1，当遍历完所有可达节点后，记录下最大的深度值，即为转发的最长深度 。

  from collections import defaultdictdef find_original_and_max_depth(from_users, to_users):# 找出原视频的用户original_users = set(from_users) - set(to_users)# 构建邻接表来表示树结构tree = defaultdict(list)for f, t in zip(from_users, to_users):tree[f].append(t)# 计算每个原视频用户的最大深度max_depth = 0for user in original_users:# 使用队列进行广度优先搜索来计算深度queue = [(user, 1)]  # (用户, 深度)current_max = 0while queue:current_user, depth = queue.pop(0)current_max = max(current_max, depth)if current_user in tree:for child in tree[current_user]:queue.append((child, depth + 1))max_depth = max(max_depth, current_max)return original_users, max_depth# 示例数据
  from_users = [1, 1, 2, 2, 3, 6]
  to_users = [2, 3, 4, 5, 6, 7]# 计算结果
  original, depth = find_original_and_max_depth(from_users, to_users)
  print("原视频的用户:", original)
  print("转发的最长深度:", depth)
  

题目二：在一棵二叉排序树中，找到比给定数值小的最大节点

要在二叉排序树（BST）中找到比给定数值小的最大节点，可以通过递归或迭代的方式遍历树结构。以下是详细的解决思路和代码实现：

方法思路

二叉排序树特性：左子树所有节点值 < 根节点值 < 右子树所有节点值。
递归遍历：

• 如果当前节点值 大于等于 目标值，递归向左子树查找（因为右子树的所有值都更大，不可能是答案）。

• 如果当前节点值 小于 目标值，递归向右子树查找更大的候选值，同时记录当前节点为候选答案。

  class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef find_largest_smaller(root, target):candidate = Nonecurrent = rootwhile current:if current.val < target:# 当前节点符合条件，记录为候选，并尝试向右找更大的candidate = currentcurrent = current.rightelse:# 当前节点值 >= target，向左找更小的值current = current.leftreturn candidate# 示例用法
  # 构建 BST: [5,3,7,2,4,6,8]
  root = TreeNode(5)
  root.left = TreeNode(3)
  root.right = TreeNode(7)
  root.left.left = TreeNode(2)
  root.left.right = TreeNode(4)
  root.right.left = TreeNode(6)
  root.right.right = TreeNode(8)# 查找比 6 小的最大节点
  result = find_largest_smaller(root, 6)
  print(result.val if result else "None")  # 输出: 5