寻找拥有最长推荐链的员工——面试算法问题求助

问题描述 #

给定自发入职员工和被推荐入职员工的关系，找出拥有最长推荐链的员工：

• 示例：A自发入职，推荐C，C再推荐D；B自发入职，推荐F → 结果为A
• 补充多根树场景：

  J                    A                Y                
                              / | \             /                 
                            C   E  G           I                   
                          / | \
                         D  H  Z
  

现有尝试与疑问 #

1. 初始数据结构与伪代码 #

最初使用一对一映射的map存储推荐关系：

map = {
A: C
C: D
B: F
}

尝试的伪代码实现：

int countReferrals(employee, map, int& last_index){
    if(!map.find(employee)){
     //no referrals hired by this employee
     return 0;
    }
    last_index++;
    int count_referred = 1 + countReferrals(map.find(employee)->second, map, last_index);
    return count_referred;
}

employee mostReferrals(map){
   int last_index = 0;   // first index to start iterating
   int most = 0;
   employee most_refs = map[0];
   while(last_index < map.size()){
      employee curr_empl = map[last_index];
      int curr_refs = countReferrals(map[last_index], map, last_index);
      if(most<curr_refs){
         most = curr_refs;
         most_refs = curr_empl;
      }
      
   }
   return most_refs;
}

2. 核心疑问 #

• 如何正确遍历推荐关系列表？仅靠输入顺序+顶点计数器是否可行？
• 数据结构选择是否最优？map查找效率高，但无法追踪无父节点的自发入职员工
• 多根树场景下的遍历方法？尝试过定义tree类存储节点关系，但不确定实现逻辑：

  Class tree {
    char value;
    vector<char> children;
  } 
  

问题分析与优化方案 #

1. 数据结构的关键修正 #

你的初始map只能表示一对一推荐关系，无法覆盖一个员工推荐多人的场景（比如示例中的A推荐C、E、G）。正确的基础结构应该是：

• map<员工ID, vector<员工ID>>：键为员工ID，值为该员工直接推荐的所有员工列表
• 额外维护根节点集合（自发入职员工）：若输入未直接提供，可通过以下步骤推导：
  1. 收集所有出现过的员工ID（遍历map的键和所有值）
  2. 收集所有被推荐的员工ID（遍历map的所有值）
  3. 根节点 = 所有员工ID - 被推荐员工ID，即没有父节点的员工

2. 遍历逻辑修正 #

你的伪代码中last_index的用法存在逻辑错误：递归递增last_index会跳过部分员工，且map的索引和推荐链无关。正确的流程是：

1. 先找出所有根节点（自发入职员工）
2. 对每个根节点，计算其推荐链的最长长度（或总推荐人数，需明确题目定义）

3. 具体实现方案 #

方案1：计算最长推荐链（路径深度）

这里的“最长链”指从根到最远下属的路径长度（比如A→C→D的深度为2），使用记忆化递归避免重复计算：

// 计算单个员工的最长推荐链深度
int calculateMaxChainDepth(char emp_id, const map<char, vector<char>>& referral_map, map<char, int>& memo) {
    // 记忆化缓存，避免重复计算同一员工的深度
    if (memo.count(emp_id)) {
        return memo[emp_id];
    }
    int max_depth = 0;
    if (referral_map.count(emp_id)) {
        for (const char& child : referral_map.at(emp_id)) {
            // 子节点深度 = 1 + 子节点的最长链深度
            int child_depth = 1 + calculateMaxChainDepth(child, referral_map, memo);
            max_depth = max(max_depth, child_depth);
        }
    }
    memo[emp_id] = max_depth;
    return max_depth;
}

// 找出最长推荐链的根节点
char findLongestChainRoot(const map<char, vector<char>>& referral_map, const vector<char>& root_employees) {
    map<char, int> memo;
    char result = root_employees[0];
    int max_depth = 0;
    for (const char& root : root_employees) {
        int depth = calculateMaxChainDepth(root, referral_map, memo);
        if (depth > max_depth) {
            max_depth = depth;
            result = root;
        }
    }
    return result;
}

方案2：计算总推荐人数

若题目要求的是推荐的总员工数（比如A的总推荐数是C、D、E、G、H、Z，共6人），只需修改递归逻辑为累加下属数量：

int calculateTotalReferrals(char emp_id, const map<char, vector<char>>& referral_map, map<char, int>& memo) {
    if (memo.count(emp_id)) {
        return memo[emp_id];
    }
    int total = 0;
    if (referral_map.count(emp_id)) {
        for (const char& child : referral_map.at(emp_id)) {
            // 总人数 = 1（当前子节点） + 子节点的总推荐数
            total += 1 + calculateTotalReferrals(child, referral_map, memo);
        }
    }
    memo[emp_id] = total;
    return total;
}

4. 关于tree类的思路 #

你定义的tree类思路可行，但工程中用map+vector的组合更灵活，无需额外定义类。如果用树结构，需先将所有员工构建为树节点，再对每个根节点做深度优先搜索（DFS）或广度优先搜索（BFS）计算最长链。

内容的提问来源于stack exchange，提问作者Rupakshi