阿里面试：全国14亿个姓名，统计出重名最多的前100个

尼恩说在前面

全国14亿人的数据中，统计出重名人数最多的前100位姓名

《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请到文末公号【技术自由圈】获取

本文的2个重量级作者：

• 第一重量级作者 yupeng（资深架构师，负责写初稿 ）
• 第二重量级作者 尼恩 （40岁老架构师， 负责提升此文的 技术高度，让大家有一种 俯视 技术的感觉）

本文目录

- 尼恩说在前面

- 本文的2个重量级作者：

- 1. 问题描述:

- 2. 问题分析:

- 3. 如何选择一种最低成本、最高性能的数据结构？

- 4. 如何快速筛选出Top 100？

- 5. 前缀树Trie树介绍

- 6. Trie树的基本操作:

- 7. Trie树的应用场景:

- 8. Trie树的代码实现:

- 9. TOP N问题发散:

- 10. topK问题,典型的解题思路

说在最后：有问题找老架构取经

1. 问题描述:

2. 问题分析:

• 需要有一个高效的数据结构来统计每个名字出现的次数,
• 并快速找到出现次数最多的前100个名字.

3. 如何选择一种最低成本、最高性能的数据结构？

• 数组:

• 链表:
  链表的插入和查找的操作时间复杂度为O(N), 并且，在大规模数据下性能低下,也不适合快速查找的场景
• 跳表:

• 哈希表:

• 平衡二叉搜索树(如AVL树或红黑树):

• 前缀树:

4. 如何快速筛选出Top 100？

• 如果堆的大小小于100，将当前姓名及其出现次数插入堆中。
• 如果当前姓名的出现次数大于堆顶元素的出现次数，则移除堆顶元素，并将当前姓名及其出现次数插入堆中。

5. 前缀树Trie树介绍

• 根节点没有数据
• 从根节点到某一个节点,将他们的路径进行连接就组成了对应的字符串

Trie树，又称为前缀树或字典树, 是一种用于高效存储和检索字符串集合的数据结构, 每个节点代表一个字符, 边表示从一个字符到另一个字符的路径, Trie树通过共享相同前缀的节点来节省存储空间

6. Trie树的基本操作:

• 插入:将一个字符串逐字符插入到Trie树中
• 查找:检查Trie树中是否存在某个字符串
• 前缀匹配:查找所有以某个前缀开头的字符串
• 删除:从Trie树中删除一个字符串

7. Trie树的应用场景:

• 应用场景:快速检索字典中的单词
• 使用原因:Trie树通过逐字符匹配,可以在O(L)时间内完成字符串的检索,其中L是字符串的长度,比传统的线性搜索更加高效

• 应用场景:搜索引擎和输入法中的自动补全功能
• 适用原因:Trie树可以通过前缀查找快速提供所有以给定前缀开头的单词,有效提升用户输入体验

• 应用场景:寻找以特定前缀开头的所有字符串,如电话号码前缀匹配
• 适用原因:Trie树天生适合处理前缀匹配问题,可以在O(L)时间内找到所有以特定前缀开头的字符串

• 应用场景:文本分析中统计单词出现频率
• 适用原因:Trie树可以在插入过程中记录每个单词的出现次数,通过遍历Trie树可以快速统计所有单词的频率

• 应用场景:从文本中同时搜索多个模式(模式匹配算法)
• 适用原因:Trie树可以构建多个模式的结构,通过一次遍历文本同时匹配多个模式,提高匹配效率

• 共享前缀:Trie树通过共享前缀节点，减少了重复存储相同前缀的空间开销。
• 节省内存:对于大量前缀相同的字符串集合，Trie树显著节省内存使用。

• O(L)复杂度:插入、查找和前缀匹配操作的时间复杂度为O(L),其中L是字符串的长度,显著提高了操作效率
• 快速检索:相比于其他线性结构(如数组或链表),Trie树在处理大量字符串时更快

8. Trie树的代码实现:

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class TrieNode {
    Map<Character, TrieNode> children;
    int count;

    public TrieNode() {
        children = new HashMap<>();
        count = 0;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String name) {
        TrieNode node = root;
        for (char ch : name.toCharArray()) {
            node = node.children.computeIfAbsent(ch, k -> new TrieNode());
        }
        node.count++;
    }

    public void getAllNames(TrieNode node, StringBuilder prefix, PriorityQueue<NameCount> minHeap, int k) {
        if (node == null) return;
        if (node.count > 0) {
            if (minHeap.size() < k) {
                minHeap.offer(new NameCount(prefix.toString(), node.count));
            } else if (node.count > minHeap.peek().count) {
                minHeap.poll();
                minHeap.offer(new NameCount(prefix.toString(), node.count));
            }
        }
        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            prefix.append(entry.getKey());
            getAllNames(entry.getValue(), prefix, minHeap, k);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    public PriorityQueue<NameCount> getTopKNames(int k) {
        PriorityQueue<NameCount> minHeap = new PriorityQueue<>(k);
        getAllNames(root, new StringBuilder(), minHeap, k);
        return minHeap;
    }
}

class NameCount implements Comparable<NameCount> {
    String name;
    int count;

    public NameCount(String name, int count) {
        this.name = name;
        this.count = count;
    }

    @Override
    public int compareTo(NameCount other) {
        return Integer.compare(this.count, other.count);
    }

    @Override
    public String toString() {
        return name + ": " + count;
    }
}

public class Main {
    public static void main(String[] args) {
        String[] names = {"张伟", "王伟伟", "王芳", "李伟", "李娜"}; // 示例数据
        int k = 100; // 找到前100个重名人数最多的姓名

        Trie trie = new Trie();
        for (String name : names) {
            trie.insert(name);
        }

        PriorityQueue<NameCount> topKNames = trie.getTopKNames(k);
        while (!topKNames.isEmpty()) {
            System.out.println(topKNames.poll());
        }
    }
}

9. TOP N问题发散:

这里使用hashmap，而不适用 trie树的原因是？

trie树是按照字符为粒度组织树的节点的，进行磁盘操作性能不高，而且进行磁盘操作时算法更加复杂。

hashmap 是以key为单位操作的， 磁盘操作的效率高。而且 hashmap 统计的时候，代码简洁清晰。

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class NameCount implements Comparable<NameCount> {
    String name;
    int count;

    public NameCount(String name, int count) {
        this.name = name;
        this.count = count;
    }

    @Override
    public int compareTo(NameCount other) {
        return Integer.compare(this.count, other.count);
    }

    @Override
    public String toString() {
        return name + ": " + count;
    }
}

public class ExternalMemoryTopK {
    private static final int CHUNK_SIZE = 1000000; // 每个块处理100万条记录

    public static void main(String[] args) throws IOException {
        String inputFile = "names.txt";
        String outputFile = "top100names.txt";
        int k = 100;

        // 第一步：分块读取数据并统计词频
        int chunkIndex = 0;
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        String line;
        while ((line = reader.readLine()) != null) {
            Map<String, Integer> frequencyMap = new HashMap<>();
            int lineCount = 0;
            while (line != null && lineCount < CHUNK_SIZE) {
                frequencyMap.put(line, frequencyMap.getOrDefault(line, 0) + 1);
                line = reader.readLine();
                lineCount++;
            }
            writeFrequencyMapToFile(frequencyMap, "chunk_" + chunkIndex + ".txt");
            chunkIndex++;
        }
        reader.close();

        // 第二步：合并所有块的词频统计结果
        Map<String, Integer> globalFrequencyMap = new HashMap<>();
        for (int i = 0; i < chunkIndex; i++) {
            mergeFrequencyMapFromFile(globalFrequencyMap, "chunk_" + i + ".txt");
        }

        // 第三步：使用小顶堆找出前100个重复最多的名字
        PriorityQueue<NameCount> minHeap = new PriorityQueue<>(k);
        for (Map.Entry<String, Integer> entry : globalFrequencyMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(new NameCount(entry.getKey(), entry.getValue()));
            } else if (entry.getValue() > minHeap.peek().count) {
                minHeap.poll();
                minHeap.offer(new NameCount(entry.getKey(), entry.getValue()));
            }
        }

        // 输出结果
        BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile));
        while (!minHeap.isEmpty()) {
            writer.write(minHeap.poll().toString());
            writer.newLine();
        }
        writer.close();
    }

    private static void writeFrequencyMapToFile(Map<String, Integer> frequencyMap, String filename) throws IOException {
        BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
        for (Map.Entry<String, Integer> entry : frequencyMap.entrySet()) {
            writer.write(entry.getKey() + " " + entry.getValue());
            writer.newLine();
        }
        writer.close();
    }

    private static void mergeFrequencyMapFromFile(Map<String, Integer> globalFrequencyMap, String filename) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(filename));
        String line;
        while ((line = reader.readLine()) != null) {
            String[] parts = line.split(" ");
            String name = parts[0];
            int count = Integer.parseInt(parts[1]);
            globalFrequencyMap.put(name, globalFrequencyMap.getOrDefault(name, 0) + count);
        }
        reader.close();
    }
}

10. topK问题,典型的解题思路

1. 先统计数量, 使用前缀树，hashmap等
2. 再用小顶堆或者 大顶堆

说在最后：有问题找老架构取经

• 大龄男的最佳出路是 架构+ 管理
• 大龄女的最佳出路是 DPM，

部分历史案例

• 被裁太爽：每月大涨1W，10年CRUD小伙，靠转架构一个月上岸，年薪50W爽歪了！

• 小白转架构，逆涨30%：CRUD小伙7年，狠卷3个月升级为架构师，爽爆了

• 绝地逢生：9年经验自考小伙伴，跟着尼恩狠卷3月硬核技术，面试机会爆表，2周后收3个offer ，满血复活

• 硬转架构：35岁被裁6个月 职业绝望，转架构急救上岸，DDD和3高项目太重要了
  

• 逆天改命：3年经验2本，卷3个月涨薪60%，进准大厂(得物、乐信、58集团等)，年薪36W

• 女35岁CRUD程序媛，12月被裁后，拿30个机会2个offer上岸，年底大裁员太不容易了

• 38还有救吗？有。42岁被裁2年天快塌了，急救1个月上岸，成开发经理offer，起死回生

• 被裁不慌，9年小伙1个月喜提年薪60W offer，做中间件架构，爽歪了

• 12年小伙转架构，1小时蜕变收年薪55万offer，秘诀：GO+Java双栖架构

• 年薪百万：40岁小伙被裁6个月，跟着尼恩猛卷3月硬核技术，100W年薪逆袭 ，上岸秘诀：首席架构/总架构

• 不怕裁员，8年小伙去中年危机，秘诀：换架构师赛道，上得厅堂，下得厨房，越早越好

• 被裁员后因祸得福，拿N+1后，逆涨30%，如何实现？

• 逆天啦：4年crud小伙收shein+银行两优质offer，狠卷1月收年薪43万大涨30%

• 原来，拿大厂offer 有捷径......

• 太劲爆.... 被裁4个月，38岁Android转Java，2个月提架构offer

• 起死回生：8年小伙高中毕业+频繁跳槽，狠卷2月，提Java高级offer

• 爽翻了：指导3轮，5年小伙收5大offer，涨50%，领路模式太牛

• 降维攻击，37年大龄老伙喜提60W年薪offer，1个月顺利上岸

• 架构速成：从一面杀到一次过，记7年女架构的速成经历

• 极速拿offer：阿里P6被裁后极速上岸，1个月内喜提2优质offer(含滴滴)

• 大逆袭：做化工12年，35岁转Java，被裁4个月后，1个月收架构Offer，大龄跨行，超级牛

• 被裁后炸爽：10年小伙12天火速上岸，反涨20%，爽暴了

• 裁就裁，6年小伙60W极速上岸，白拿20W还游一圈拉萨，真香

• 极速拿offer：被毕业3个月，11年经验小伙0.5个月极速拿offer，领路模式的巨大威力

• 惊天大逆袭：8年小伙20天时间提75W年薪offer，逆涨50%，秘诀在这