搜狗后端笔试真题详解：TopK、LRU与Trie树-北京尧图网络

2019年秋天我参加了搜狗后端工程师的秋招笔试第一场的三道编程题到现在都记得很清楚。倒不是题目难到让人记仇而是这三道题几乎精准踩在了搜狗自己的业务场景上搜索日志统计、缓存淘汰、前缀联想。后来我复盘时发现这三道题其实不只是搜狗的笔试风格更是后端工程师日常基本功的浓缩版TopK、LRU、Trie这三个点直到今天面试大厂后端都还在反复出现。如果你正在准备后端方向的校招或者社招这篇文章把这三道题从题目分析、思路推导到AC代码完整拆开讲清楚还会补充我在现场踩过的坑和后来复盘总结的优化方案。不管你用的是Java、C还是Python核心思路都是通用的。1. 搜狗后端笔试的出题逻辑三道题背后的业务影子1.1 笔试整体形式与时间分配搜狗这场笔试是在牛客网平台上做的ACM模式也就是程序要自己处理输入输出函数不是预留给你的那种核心代码模式。总时长我记得是90分钟三道编程题题量不算大但每一道都需要完整思考。这里有个很实际的问题ACM模式下输入输出怎么写直接影响你能否AC。很多人思路对了结果Scanner读数据太慢导致超时或者没处理空行导致数组越界最后整题零分非常可惜。后面的避坑章节我会专门说这块。时间分配上三道题如果都属于中等难度偏上我建议按先易后难但别轻易放弃的原则每道题留20到25分钟。如果一道题15分钟内完全没思路先跳下一道不要死磕因为最后一题往往也有送分部分。1.2 为什么偏偏是这三类题搜狗的核心业务是搜索引擎和输入法这两个产品对后端工程师的能力要求其实非常具体。搜索业务每天产生海量日志离线或者在线场景都要做词频统计、TopN排行后端服务为了扛住高并发缓存系统必不可少LRU就是最经典的淘汰策略输入法和搜索引擎的前缀提示功能底层必然依赖字典树一类的数据结构。这三道题看似各自独立其实背后有一条隐藏的逻辑线海量数据处理能力、存储与淘汰策略设计、文本检索与匹配能力。这三块刚好是搜索引擎后端最核心的三种基本功。对比之下有些大厂喜欢考动态规划、图论这类偏数学的题目搜狗的风格明显更工程化更偏向数据结构与业务场景的结合。业务场景对应考点典型题目类型搜索日志统计 / 热词排行哈希表、堆排序、外部排序TopK 词频统计搜索服务缓存 / Session 管理哈希表、双向链表LRU 缓存淘汰输入法联想 / 搜索框提示Trie树、DFS、堆排序前缀自动补全2. 第一题海量搜索词TopK统计2.1 题目回顾整理版题目大概是这样的给定一个日志文件每一行是一个被搜索的关键词关键词只包含小写字母和数字长度不超过64。需要统计所有关键词的出现次数输出出现次数最多的前K个关键词。如果出现次数相同按字典序升序输出。输入第一行是一个整数K随后是若干行搜索词读到文件末尾结束。输出K行每行是关键词和出现次数空格分隔。数据范围我记得大概是N在10^6量级K在100以内。这意味着关键词总量可能很大但Java的HashMap是能扛住的。真正麻烦的不是存不下而是全排序浪费输出顺序坑人。2.2 从全排序到小顶堆三步推导第一步是条件反射统计频率用HashMap变量名就是freqMapkey存词value存次数。这里有个小技巧Java 8以后可以写freqMap.put(word, freqMap.getOrDefault(word, 0) 1)一行搞定累加不用先判断containsKey。第二步是排序。拿到所有词频后最直观的做法是把所有entry丢进一个List按频率降序排取前K个。这个方案在数据量小的时候完全没问题但仔细一想就能发现为了找前100个最大频率把10万个词都做了全排序时间复杂度O(M log M)M是不同关键词的数量。这里的浪费在于频率排在100名之后的那些词它们的内部顺序我们根本不关心排序的代价白付了。第三步就是优化点用小顶堆维护当前频率最高的K个词。为什么是小顶堆而不是大顶堆因为小顶堆的堆顶是这K个元素里最小的那个也就是最差的一个。新来一个元素只需要和堆顶比较如果比堆顶大就说明比当前TopK里最差的还好那就弹出堆顶、把新元素放进去。这样全程堆里只有K个元素时间复杂度降到O(M log K)。K只有100的情况下这个差距非常可观。2.3 AC代码HashMap 小顶堆的Java实现这里的关键难点其实不在堆的维护而在比较器的书写。因为题目要求频率降序、同频字典序升序而我们的小顶堆淘汰规则恰好是频率越小越先淘汰频率相同字典序越大越先淘汰。很多人在这个比较器上写反导致结果反着输出。import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int K Integer.parseInt(br.readLine().trim()); MapString, Integer freqMap new HashMap(); String word; while ((word br.readLine()) ! null) { word word.trim(); if (word.isEmpty()) continue; freqMap.put(word, freqMap.getOrDefault(word, 0) 1); } // 小顶堆频率小的在堆顶频率相同字典序大的在堆顶 PriorityQueueMap.EntryString, Integer minHeap new PriorityQueue((a, b) - { if (!a.getValue().equals(b.getValue())) { return Integer.compare(a.getValue(), b.getValue()); } return b.getKey().compareTo(a.getKey()); }); for (Map.EntryString, Integer entry : freqMap.entrySet()) { if (minHeap.size() K) { minHeap.offer(entry); } else if (compareEntry(entry, minHeap.peek()) 0) { minHeap.poll(); minHeap.offer(entry); } } ListMap.EntryString, Integer result new ArrayList(minHeap); result.sort((a, b) - { if (!a.getValue().equals(b.getValue())) { return Integer.compare(b.getValue(), a.getValue()); } return a.getKey().compareTo(b.getKey()); }); StringBuilder sb new StringBuilder(); for (Map.EntryString, Integer entry : result) { sb.append(entry.getKey()).append( ).append(entry.getValue()).append(\n); } System.out.print(sb.toString()); } private static int compareEntry(Map.EntryString, Integer a, Map.EntryString, Integer b) { if (!a.getValue().equals(b.getValue())) { return Integer.compare(a.getValue(), b.getValue()); } return b.getKey().compareTo(a.getKey()); } }这段代码的主干并不复杂但有两个细节值得注意。第一个细节比较器里的Integer.compare不要直接写a.getValue() - b.getValue()。频率虽然是正数但万一哪天数据范围扩大两个int相减溢出整个堆的顺序就全部错乱。这种坑线上调试非常难发现。第二个细节最后输出前不要以为直接从堆里遍历就是有序的。PriorityQueue内部只保证堆顶最小不保证整体有序所以必须把堆里的元素倒到List里重新sort一次。这步漏掉的话输出顺序会非常混乱。2.4 海量数据变体的应对思路笔试原题的数据量用HashMap完全能扛但面试官几乎一定会追问如果日志文件有几百个GB不同关键词超过一亿内存根本放不下完整的HashMap怎么办这个问题的标准答案是分治先对关键词做哈希取模hash(word) % M把大文件拆成M个小文件保证同一个词一定落在同一个小文件里。然后对每个小文件单独用HashMap统计频率各自求出TopK最后对M个TopK结果做多路归并得到全局的TopK。之所以强调同一个词一定落在同一个小文件是因为哈希取模的确定性。你甚至可以顺手把所有hash值相同的词放进同一个分区文件这样每个分区之间互不干扰最后归并时也不会漏词。如果K也非常大甚至大到内存放不下那就要换思路了。比如用外部排序先按频率排序再取前K个或者用近似算法比如Count-Min Sketch做频率估计牺牲一点精确性换内存。但笔试现场通常把K控制在100以内小顶堆足够。3. 第二题手写LRU缓存3.1 题目回顾整理版设计一个LRU缓存结构支持get(key)和put(key, value)两个操作。get时如果key存在返回对应的value并把该key标记为最近使用如果key不存在返回-1。put时如果key已存在更新value并标记为最近使用如果key不存在插入该键值对。当缓存容量达到上限时淘汰最久未被使用的key。输入第一行是缓存容量capacity随后若干行是操作指令包括get 1、put 1 10这样的格式。输出是所有get操作的结果。这道题在很多大厂笔试面试里都出现过但搜狗的版本更强调手写底层不太建议直接用LinkedHashMap一把梭因为面试官想看到你理解数据结构组合的原理。3.2 核心考点为什么必须是HashMap双向链表先想一个问题如果只用HashMap能做到O(1)查找但怎么知道哪个key最久没被使用你需要维护一个访问顺序这个顺序会随着每次get和put动态变化。再想如果只用LinkedList维护访问顺序很容易但查找key需要遍历链表O(n)复杂度不可接受。所以标准解法是HashMap 双向链表。HashMap保证O(1)的key查找value存的是链表节点引用双向链表维护访问顺序头节点是最近使用的尾节点是最久未使用的。为什么必须用双向链表而不是单向因为当你访问某个节点后需要把它从当前位置摘除再放到头部。这个摘除操作单向链表需要知道前驱节点而你没有额外的指针可以快速获取前驱。双向链表每个节点都存了prev引用摘除和插入都是O(1)操作。生活化类比就是食堂排队HashMap是每个学生对应的饭卡刷卡就知道这人在队伍中的位置双向链表是队伍本身有人刚打完饭想重新排到最前面就需要前后的人同时配合让出位置。3.3 完整实现与关键边界处理import java.io.*; import java.util.*; class LRUCache { static class Node { int key, value; Node prev, next; Node(int key, int value) { this.key key; this.value value; } } private final int capacity; private final MapInteger, Node map; private final Node head; private final Node tail; public LRUCache(int capacity) { this.capacity capacity; this.map new HashMap(); this.head new Node(-1, -1); this.tail new Node(-1, -1); head.next tail; tail.prev head; } public int get(int key) { if (!map.containsKey(key)) return -1; Node node map.get(key); moveToHead(node); return node.value; } public void put(int key, int value) { if (map.containsKey(key)) { Node node map.get(key); node.value value; moveToHead(node); } else { Node node new Node(key, value); map.put(key, node); addToHead(node); if (map.size() capacity) { Node removed removeTail(); map.remove(removed.key); } } } private void addToHead(Node node) { node.next head.next; node.prev head; head.next.prev node; head.next node; } private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(Node node) { removeNode(node); addToHead(node); } private Node removeTail() { Node node tail.prev; removeNode(node); return node; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int capacity Integer.parseInt(br.readLine().trim()); LRUCache cache new LRUCache(capacity); StringBuilder sb new StringBuilder(); String line; while ((line br.readLine()) ! null) { String[] parts line.trim().split(\\s); if (parts.length 0) continue; if (get.equals(parts[0])) { int key Integer.parseInt(parts[1]); sb.append(cache.get(key)).append(\n); } else if (put.equals(parts[0])) { int key Integer.parseInt(parts[1]); int value Integer.parseInt(parts[2]); cache.put(key, value); } } System.out.print(sb.toString()); } }这段代码里最值得学习的地方是哑节点设计。head和tail两个哨兵节点不存实际数据它们存在的意义是避免在链表为空或者操作头尾节点时写一堆if判断。比如addToHead里不管链表是空还是非空head.next一定存在所以可以直接操作。这个技巧在写各种链表题目时都非常实用。边界情况要特别注意几个缓存容量为1时put一个新key后满需要淘汰唯一的节点反复get同一个key时节点要不断移动到头部put一个已存在的key时不需要检查容量因为容量没有变化。3.4 面试官最喜欢的三个追问第一个追问是get和put的时间复杂度分别是多少答案都是O(1)因为HashMap查找O(1)链表插入删除O(1)移动节点是删除插入两步依然是O(1)。第二个追问是用Java的LinkedHashMap怎么实现核心是重写removeEldestEntry方法让它判断size是否超过capacity。但注意LinkedHashMap默认的accessOrder是false即按插入顺序排列要设置成true才会按访问顺序排列。我当时还补了一句这道题手写LinkedHashMap虽然代码短但体现不出你对双向链表底层原理的掌握笔试推荐手写。第三个追问是如果要求实现LFULeast Frequently Used最不经常使用淘汰策略呢LFU不仅要考虑最近是否被访问还要考虑访问频率高低。简单做法是维护一个HashMapkey, Node加一个TreeMapfrequency, LinkedHashSetkey每次get更新频率淘汰时找频率最小的那个集合中的最久未访问key。这个作为延伸思考能答上来会给面试官留下不错的印象。4. 第三题搜索框前缀自动补全4.1 题目回顾整理版搜狗搜索框和输入法都依赖一个词典给定N个词条每个词条有一个热度值。现在有M次查询每次查询给一个前缀prefix需要返回以该前缀开头的所有词条中热度最高的前K个。如果热度相同按字典序升序。输入第一行是三个整数N、K、M接下来N行每行是一个词条和对应的热度接下来M行每行是一个查询前缀。输出对每个查询输出热度最高的前K个词条每行是词条和热度查询之间用空行隔开。词条只包含小写字母。这道题的数据量我记得N在10^5级别K在10以内词条长度不超过20。如果每次查询都遍历全部词条做前缀匹配然后排序理论上是能跑出结果的但10^5词条乘以10^4次查询复杂度直接到10^9超时基本没跑。必须用数据结构优化。4.2 Trie树设计与TopK下沉策略前缀匹配问题第一反应就应该是Trie树也叫字典树。Trie树的核心思想是把所有词条按字符逐层挂到树上从根节点到某个节点的路径就是一个前缀。查询某个前缀是否存在只需要沿着树往下走走完前缀的所有字符看看是不是走到了一个有效节点。这道题的巧妙之处在于要求热度最高的前K个。最朴素的做法是查询时DFS遍历前缀下所有子树把所有词条收集起来排序取前K。这个方案空间复杂度很低但时间复杂度不行因为每次查询都可能遍历大量节点。搜狗这道题或者说这类联想题标准优化就是TopK下沉在每个Trie节点上直接维护一个大小为K的小顶堆存的是以当前节点为前缀的所有词条中热度最高的K个。这样插入词条时每经过一个节点就把这个词条尝试加入该节点的TopK堆查询时只需要走到前缀末尾节点直接读出该节点的堆内容O(K)级输出非常快。空间换时间的代价很明显每个节点都维护一个K大小的堆N个词条平均长度L节点总数最多NL堆总容量就是NL*K。所以这道题的K一般会给得很小否则内存会爆炸。这也是为什么题目把K限定在10以内。4.3 工程实现让每个节点自带小顶堆import java.io.*; import java.util.*; public class Main { static class Word { String word; int heat; Word(String word, int heat) { this.word word; this.heat heat; } } static class TrieNode { TrieNode[] children new TrieNode[26]; PriorityQueueWord topK; int K; TrieNode(int K) { this.K K; this.topK new PriorityQueue((a, b) - { if (a.heat ! b.heat) return Integer.compare(a.heat, b.heat); return b.word.compareTo(a.word); }); } void add(Word word) { topK.offer(word); if (topK.size() K) { topK.poll(); } } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int N Integer.parseInt(st.nextToken()); int K Integer.parseInt(st.nextToken()); int M Integer.parseInt(st.nextToken()); TrieNode root new TrieNode(K); for (int i 0; i N; i) { st new StringTokenizer(br.readLine()); String word st.nextToken(); int heat Integer.parseInt(st.nextToken()); Word w new Word(word, heat); TrieNode cur root; cur.add(w); for (char c : word.toCharArray()) { int idx c - a; if (cur.children[idx] null) { cur.children[idx] new TrieNode(K); } cur cur.children[idx]; cur.add(w); } } StringBuilder sb new StringBuilder(); for (int i 0; i M; i) { String prefix br.readLine().trim(); TrieNode cur root; boolean found true; for (char c : prefix.toCharArray()) { int idx c - a; if (cur.children[idx] null) { found false; break; } cur cur.children[idx]; } if (!found || cur.topK.isEmpty()) { sb.append(\n); continue; } ListWord list new ArrayList(cur.topK); list.sort((a, b) - { if (a.heat ! b.heat) return Integer.compare(b.heat, a.heat); return a.word.compareTo(b.word); }); for (Word w : list) { sb.append(w.word).append( ).append(w.heat).append(\n); } sb.append(\n); } System.out.print(sb.toString()); } }这个实现的思路非常直白插入时从根节点开始路径上每个节点的堆都尝试加入这个词条查询时走到前缀的最后一个字符所在节点把这个节点的堆内容倒出来排序输出。需要注意两点。第一TrieNode.add内部用offer加元素如果堆满了就poll掉堆顶。因为堆顶是热度最低的所以这样保证堆里一直都是当前热度最高的K个。第二最后排序时不能直接依赖堆的遍历顺序和第一题一样PriorityQueue内部不保证全序必须倒到List里重新sort。这一点几乎所有写堆的题都会踩到我在现场也在这翻了车。还有一个工程上的细节每个词条插入时创建了一个Word对象然后路径上每个节点都会持有对这个对象的引用。这意味着同一个词条会被多个节点共享引用并不会复制多份字符串数据内存上还算友好。当然如果词条数量巨大可以考虑用一个全局数组存所有词条节点堆里只存数组下标能进一步压缩内存。4.4 复杂度权衡与内存优化思路构建阶段的时间复杂度是O(N * L * logK)N是词条数L是平均词长K是堆大小。查询阶段是O(prefix长度 K logK)因为要排序输出。空间复杂度是O(N * L * K)这也是为什么K必须小。我在复盘时想过一个更省内存的替代方案不在每个节点维护完整堆而是只维护一个长度为K的热度阈值数组。插入时只在到达单词末尾的节点做完整TopK更新中间前缀节点不存完整TopK查询时再沿子树DFS收集。这个方案查询慢一些但内存降了一个数量级。笔试里通常不需要走到这一步但如果你在系统设计面试里讨论搜索框联想功能这个内存权衡是很好的加分项。5. 笔试题实战的常见问题与避坑指南5.1 输入输出方式的选择搜狗这场笔试是ACM模式输入输出完全靠自己写这里有个非常现实的坑Java的Scanner在大数据量下会很慢同样的逻辑Scanner可能要跑2000msBufferedReader只要500ms。所以建议一开始就写BufferedReader加StringTokenizer的组合。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int K Integer.parseInt(st.nextToken());BufferedReader.readLine()按行读取StringTokenizer按空格切分速度比Scanner快得多。输出同理不要一行行System.out.println而是全部拼进StringBuilder最后一次性输出。这是笔试的基本功但很多人到交卷前才意识到。另一个坑是空行。笔试的输入数据里偶尔会出现空行如果用readLine()直接拿到的字符串可能是空字符串直接split或者parseInt会抛异常。稳妥做法是每次读入后先trim()如果是空字符串就continue。5.2 高频翻车点自查清单翻车点说明对应策略比较器方向写反TopK输出顺序要求频率降序、字典序升序堆内比较器写反全盘皆输写之前明确堆顶是最该被淘汰的元素以此推导比较规则int溢出频率相减、热度相减可能溢出使用Integer.comparePriorityQueue遍历顺序直接遍历堆不是有序的倒到List再sortLRU哑节点指针搞乱插入、删除顺序不对导致链表成环画图理清四步操作先连新节点的next/prev再改前后节点的指向Trie节点重复创建插入时没检查children是否为空就new导致覆盖先判断再创建创建完赋值给children[idx]输出格式多一个空格或少一个空行ACM模式对输出格式敏感先拼StringBuilder检查首尾再统一输出第4点值得多说一句。手写双向链表插入节点时正确顺序是先设置新节点的next和prev再修改旧节点的prev.next和next.prev。顺序写反的话可能在第一步就把旧节点的引用覆盖了链表随后断掉。我建议每次写链表操作都画个简单示意图前后节点互相指一下逻辑就清晰了。5.3 时间管理与做题顺序策略三道题如果按我的难度排序第一题TopK和第三题Trie属于思路对了就能过的题第二题LRU属于代码实现细节多、容易翻车的题。我的建议是先把第一题完整拿下再写LRU最后回头处理第三题。但这里有个重要的取舍原则如果时间只剩15分钟而第三题还没动笔优先保证把Trie树的插入和查询框架写出来哪怕TopK的维护逻辑不完整也能拿一部分分。ACM模式虽然看的是最终运行结果但很多OJ平台会按测试点给分部分通过总比零分强。我自己当时就犯过一个错误在LRU的put方法里更新已存在key的value后忘记调用moveToHead结果缓存顺序完全错乱。这种错误不是思路问题而是边界场景没考虑全。建议写完代码后自己用一两组小数据在本地跑一下比如capacity为2get一个不存在的keyput三个key逐个验证。经过这次笔试我最大的体会是搜狗给的这三道题本质上是在模拟一个搜索后端工程师每天都会遇到的真实问题。TopK对应热词统计LRU对应缓存设计Trie对应搜索联想。准备这类笔试与其刷一堆偏难怪的算法题不如把数据结构的基本功打扎实尤其是堆、哈希、链表、树这四者之间的组合应用。如果你把这些题的思路吃透不管去面哪家大厂的后端都不会亏。

搜狗后端笔试真题详解：TopK、LRU与Trie树

相关推荐

NUCLEO-32引脚命名冲突排查：手册、原理图与实测验证指南

后渗透文件传输

Web后台管理系统UI样式参考示例集：统一前端样式规范

更多资讯

淄博考电工证到哪里考千万别踩坑，新手必看的报名避坑指南

宁河登高架设资格证有效期多久良心建议给学历不高怕报不上名的人

青海考电工证培训机构怎么选？郑州报考避坑指南帮你少走弯路

巴中电工证培训时长怎么安排才能拿到电子证书

市区怎么考取电工证官方回应实操考试心里没底怕挂科

杭州低压电工证试题怎么准备?郑州报考避坑指南帮你少走弯路

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

NUCLEO-32引脚命名冲突排查：手册、原理图与实测验证指南

后渗透文件传输

Web后台管理系统UI样式参考示例集：统一前端样式规范

更多资讯

淄博考电工证到哪里考千万别踩坑，新手必看的报名避坑指南

宁河登高架设资格证有效期多久 良心建议给学历不高怕报不上名的人

青海考电工证培训机构怎么选？郑州报考避坑指南帮你少走弯路

巴中电工证培训时长怎么安排才能拿到电子证书

市区怎么考取电工证官方回应实操考试心里没底怕挂科

杭州低压电工证试题怎么准备?郑州报考避坑指南帮你少走弯路

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

宁河登高架设资格证有效期多久良心建议给学历不高怕报不上名的人

新疆电工作业干活累吗良心建议助你避开考不过的坑

新疆电工作业干活累吗良心建议助你避开考不过的坑