美团校招笔试必看——测试版

美团第一批秋招笔试于8月9日上午10:00进行！
来看看往年都考些什么！速来复习！笔试过过过！

试卷入口：2024年秋招-美团-测试岗-第一批笔试

经典的一道题

【编程题】小美的数组询问

题目描述： 给定一个长度为的数组和次询问。每次询问包含三个整数, , ，要求查询在数组的下标区间 内，数字出现了多少次。

输入描述： 第一行两个整数, ，表示数组长度和询问次数。第二行个整数，表示数组。接下来行，每行三个整数, , 。

输出描述： 对于每次询问，输出一个整数表示答案。

解题思路： 这道题是典型的区间查询问题，核心在于如何优化查询效率。

1. 暴力解法：对于每次查询，直接遍历从到的子数组，统计的出现次数。这种方法的时间复杂度是，当和很大时会超时，通常只能通过部分测试用例。
2. 预处理优化：为了快速查询，可以预处理数据。一个有效的方法是使用哈希表（或Map）来存储每个数字及其出现的所有下标列表，即 。
3. 查询阶段：当查询 时，首先在哈希表中找到 对应的下标列表。然后，在这个有序的下标列表上使用二分查找，找到第一个大于等于的下标位置和第一个大于的下标位置。两个位置之差即为在区间 内的出现次数。
4. 这种方法将单次查询时间复杂度从降低到（为出现的次数），总时间复杂度约为，可以满足性能要求。

【写在最后】

特别提醒：美团在近年来的技术布局中，对大语言模型（LLM）领域展现出了极大的投入和关注。无论是从官方的技术分享还是部分岗位的笔试题中，我们都能看到大模型相关知识点的身影。因此，强烈建议各位同学在准备笔试时，除了传统的计算机基础知识外，也花时间了解和学习大模型的基本原理、应用场景及最新进展，如Transformer架构、微调技术、提示工程等。这很可能会成为未来笔试中的一个重要加分项，甚至是区分项。祝大家笔试顺利，成功上岸！