今天要分享的是来自Axon公司的两道面试真题，这些题目分别涉及相机ID管理系统设计和警察单位平均旅行时间计算。下面是对这两道题目的详细分析和解题思路。
题目一：相机ID管理系统
英文原文：
We are designing a system for officers to checkout a body worn camera from a pool of available cameras. We need an object to store a collection of camera ids and our checkout system needs to get a random id out of this collection when an officer wants to check out a camera to use for their shift. When cameras are checked in, we need to insert the id into the pool, and when they are checked out, they need to be removed. Let’s use integers to represent the camera Ids.
We will need to be able to insert and remove ids, so we need APIs for those operations. We also need an API to be able to get a random id from within the collection.
Some agencies can be very large, and shifts can overlap, so these 3 APIs are going to be used very often, and we want to be able to fill the collection with a very large set of ids. Because we want the checkout/checkin operations to be quick, we want to optimize this structure for performance. Our goal is to get average time complexity to “constant time” (i.e. O(1)) for each of these 3 operations.
题目描述
我们需要设计一个系统，让officer从可用相机的池中借出一个随身相机。需要一个对象来存储相机ID的集合，当officer需要借出相机时，系统要从集合中随机取出一个ID。相机归还时，需要将ID插入到池中，借出时需要将ID移除。我们用整数来表示相机ID。
我们需要能够插入和移除ID，因此需要相关的API。此外，还需要一个API能够从集合中获取随机ID。
考虑到有些机构规模很大，且班次可能重叠，这三个API会被频繁使用，而且集合中的ID可能非常庞大。为了使借出和归还操作快速，我们希望优化这个结构以提高性能。我们的目标是使每个操作的平均时间复杂度达到常数时间（O(1)）。
题目二：警察单位平均旅行时间计算
英文原文：
We are adding a new feature to the Dispatch system at Axon, which will allow us to determine the average travel time of police units between different locations.
Implement a DispatchTravel class that is initialized with a List of data points related to dispatched police units (unitId, location, timestamp), and that is able to return the AVERAGE travel time from any one location to another through the following method:
getAverageTime(String startLocation, String endLocation)
The average travel time is computed from all trips that happened directly FROM startLocation TO endLocation.
Input format:
[unitId, location, timestamp], [unitId, location, timestamp], ...
When a Unit ID is first encountered, it means the unit was dispatched and a trip started from that location and timestamp. When that same Unit ID is encountered again, it means the trip ended at that location and timestamp. The travel time is the difference in timestamps.
题目描述
我们正在为Axon的调度系统添加一个新功能，允许我们确定officer单位在不同位置之间的平均行进时间。
实现一个 DispatchTravel 类，该类初始化时接收与调度的警察单位相关的数据点列表（unitId, location, timestamp），并且能够通过以下方法返回从一个位置到另一个位置的平均旅行时间：
getAverageTime(String startLocation, String endLocation)
平均行进时间是从所有直接从 startLocation 到 endLocation 的旅行中计算得出的。
输入格式：
[unitId, location, timestamp], [unitId, location, timestamp], ...
当首次遇到某个Unit ID时，表示该单位被调度并从该位置和时间戳开始了一次旅行。当再次遇到相同的Unit ID时，表示该旅行在该位置和时间戳结束。旅行时间是时间戳之间的差值。
面试对话
在面试过程中，面试官与我进行了详细的讨论，以下是一些关键对话片段：
题目一：相机ID管理系统
面试官：请描述一下你对这道题的理解。
我：这道题要求我们设计一个系统来管理officer的相机ID集合。系统需要支持ID的插入、移除和随机获取操作，并且这些操作的时间复杂度需要达到O(1)。
面试官：你打算如何实现这三个API？
我：我打算使用哈希表和动态数组结合的方式。哈希表用于存储相机ID及其在数组中的位置，数组用于存储相机ID本身。这样可以在常数时间内完成插入、删除和随机获取操作。
面试官：你能详细解释一下每个操作的具体实现吗？
我：插入操作时，将ID添加到数组末尾，并在哈希表中记录该ID及其索引。删除操作时，从哈希表中找到要删除ID的索引，并将数组末尾的ID与该ID交换，然后更新哈希表，最后删除数组末尾的元素。随机获取操作则直接从数组中随机选择一个元素。
题目二：officer单位平均行进时间计算
面试官：你如何理解这道题的要求？
我：题目要求我们计算officer单位在不同位置之间的平均旅行时间。我们需要解析日志，记录每个单位的旅行起点和终点，并计算所有行进的平均时间。
面试官：你会用什么数据结构来实现这一点？
我：我会使用哈希表来记录每个单位的当前位置和开始时间。当遇到一个新的位置记录时，计算该单位从上一次位置到当前位置的行进时间，并更新哈希表。
面试官：你能解释一下如何处理多次行进的情况吗？
我：对于每次旅行，我们都记录起点和终点的时间戳，并计算旅行时间。所有行进时间累加起来，除以行进次数，就得到平均行进时间。
解题思路
相机ID管理系统
- 数据结构选择：
- 使用哈希表和动态数组结合的方式，实现O(1)的插入、删除和随机获取操作。
- 插入操作：
- 将ID添加到数组末尾，并在哈希表中记录该ID及其索引。
- 删除操作：
- 从哈希表中找到要删除ID的索引，并将数组末尾的ID与该ID交换，然后更新哈希表，最后删除数组末尾的元素。
- 随机获取操作：
- 直接从数组中随机选择一个元素。
警察单位平均旅行时间计算
- 数据结构选择：
- 使用哈希表来记录每个单位的当前位置和开始时间。
- 解析日志：
- 遍历日志，记录每个单位的行进起点和终点，计算所有行进的时间差。
- 计算平均旅行时间：
- 所有旅行时间累加起来，除以旅行次数，得到平均行进时间。
总结
通过这两道题目，我们学会了如何设计高效的数据结构来处理常数时间复杂度的操作，以及如何解析日志记录来计算平均旅行时间。这些技能在实际开发中非常有用，不仅能提升我们的算法能力，还能帮助我们更好地进行系统设计和性能优化。
希望这个分享对大家有所帮助，如果有任何问题或建议，欢迎在评论区留言！
我们提供面试辅助，代面试服务，助您进入梦想大厂，欢迎随时咨询我。
