Amazon 算法题 —— 邮箱账户合并（Accounts Merge）—— Java 面试实录 – 一亩三分地 – 亚麻面试 – 亚麻面经 – 面试辅助 – 代面试
Dr SHI
July 4, 2025
系统公告

Amazon 2025年夏天高强度的发面试中，为了提高效率基本都是3场技术面一起来，全程使用chime平台完成，我们一起来看看最近亚马逊出了什么题目吧。以下来自于我们CSOahelp真实客户的面试记录，CSOahelp面试辅助老师全程提供解题思路、Follow up 以及详细完整代码； 不用刷题轻松进大厂。

Input:
C1: bob@yahoo.com, bob@gmail.com

C2: mary@facebook.com

C3: bob@gmail.com, bob_1@hotmail.com

C4: bob_1@hotmail.com

C5: mary@facebook.com

C6: mark@gmail.com

Output:
((C1, C3, C4), (C2, C5), (C6))

Imagine you have a list of contacts, each identified by a label (C1, C2, …) and associated with one or more email addresses. If two contacts share at least one email, they belong to the same person and should be merged into a single group.


给定若干账户（C1、C2…Cn），每个账户下有一组邮箱地址。若两个账户共享至少一个相同的邮箱地址，则认为属于同一人。请将这些账户合并，输出最终的账户分组。

我思索了一阵子，想出了如下几个思路

  • 并查集（Union-Find）：将每个邮箱视作节点，初始化各自的集合；遍历每个账户，将所属邮箱合并到同一集合；最终通过根节点归类输出账户列表。
  • 图遍历（DFS / BFS）：把邮箱看作图中节点，共同出现在同一账户的邮箱之间连边，遍历每个连通分量，收集邮箱对应的账户标签。
  • 哈希映射：维护邮箱→账户编号列表，以及邮箱→并查集索引的映射，保证字符串操作高效。

考虑到Union-Find更加麻烦，我决定使用图论的方法来实现。这个时候CSOahelp的老师在我的隐藏ipad上提示我，该问Clarification问题了，于是我与面试官开始了沟通。沟通的过程也非常的重要，即要展现自己的思维缜密，也可以给辅助老师争取时间写代码。

我：我们可以假设输入格式总是合法吗？也就是说，不会出现某个 customer 对应的邮箱列表为空？

面试：对，我假设输入就是一个 Map<String, List<String>> —— key 是 customer name，value 是至少含一个 email 的非空列表。

随后我看到ipad上出现了详细的思路描写，我照着念

算法思路（Algorithm）
我：这个问题可以建模成图算法：

  1. 把每个 customer 和每个 email 都视作图中的一个节点；
  2. 如果 customer A 拥有 email x，就在节点 A 和节点 x 之间添加一条无向边；
  3. 那么任意两个处于同一连通分量（connected component）里的 customer 节点，都属于同一个人；
  4. 遍历整张图，用 DFS（或 BFS）找到所有连通分量，然后从每个分量中提取出 customer 节点，就得到合并后的组。

具体步骤老师给我分了3步，ipad上的代码平台出现了大量的java代码，我努力抄写中~


import java.util.*;

public class Main {
    public static List> mergeContacts(List contacts) {
        // Step 1: Build the bipartite graph (undirected)
        // Nodes are either Contact or String (email)
        Map> graph = new HashMap<>();
        for (Contact contact : contacts) {
            for (String email : contact.emails) {
                // contact -> email
                graph.computeIfAbsent(contact, k -> new HashSet<>()).add(email);
                // email -> contact
                graph.computeIfAbsent(email,   k -> new HashSet<>()).add(contact);
            }
        }

        // Step 2: Traverse graph to find connected components
        Set visited = new HashSet<>();
        List> result = new ArrayList<>();

        for (Contact contact : contacts) {
            if (visited.contains(contact)) {
                continue;
            }

            // BFS from this contact
            Set component = new HashSet<>();
            Queue queue = new LinkedList<>();
            queue.add(contact);

            while (!queue.isEmpty()) {
                Object node = queue.poll();
                if (visited.contains(node)) {
                    continue;
                }
                visited.add(node);
                component.add(node);

                for (Object neighbor : graph.getOrDefault(node, Collections.emptySet())) {
                    if (!visited.contains(neighbor)) {
                        queue.add(neighbor);
                    }
                }
            }

            // Step 3: Extract only Contact nodes from the component
            Set group = new HashSet<>();
            for (Object node : component) {
                if (node instanceof Contact) {
                    group.add((Contact) node);
                }
            }
            result.add(group);
        }

        return result;
    }
}

// Assume Contact is defined as:
class Contact {
    String name;           // e.g. "C1", "C2"...
    List emails;   // list of associated email addresses
}

最后是复杂度分析

  • 时间复杂度：O(M α(N))，M 为邮箱总数，N 为账户总数，α 为并查集的逆阿克曼函数；或 O((M+E)·log M) 用排序/哈希。
  • 空间复杂度：O(M+N)，存储映射表、并查集数组和结果列表。

如果你也在准备Amazon、Meta、TikTok等大厂的算法与系统设计面试，却不清楚如何拆题和应对各种边界，欢迎添加微信，即可领取北美面试求职通关秘诀。我们也有代面试，面试辅助，OA代写等服务助您早日上岸~

Share on Facebook
Share on Twitter

Leave a Reply

Your email address will not be published. Required fields are marked *