Google 面试经验分享：Google Fiber事件分析系统设计题 - Oavoservice

Google 0605 面经

Candidate 在 Google coding 环节遇到了设计题 —— Google Fiber事件分析系统。

今天面试官是一个资深工程师，看起来比较专业，先是双方自我介绍，然后直接就是 Coding，上来就出一道经典的系统设计题。

题目描述

Google fiber wants to analyze events occurring on in-home devices (such as router)，我们需要实现两个方法：

1. addEvent(deviceId, timestamp) - 添加设备事件
2. getCount(timestamp) - 获取指定时间戳的事件数量

解题思路

这是一道经典的时间序列数据处理问题，关键在于高效的时间范围查询：

1. 数据结构选择：使用有序数据结构存储时间戳
2. 时间范围查询：快速找到指定时间范围内的事件
3. 内存优化：考虑数据量大的情况下的内存使用
4. 查询优化：支持高效的时间范围统计

代码实现

from collections import defaultdict
import bisect

class EventAnalyzer:
    def __init__(self):
        # 存储所有事件的时间戳
        self.events = []
        # 按设备ID分组存储事件
        self.device_events = defaultdict(list)
    
    def addEvent(self, deviceId, timestamp):
        """添加设备事件"""
        self.events.append(timestamp)
        self.device_events[deviceId].append(timestamp)
        print(f"设备 {deviceId} 在时间 {timestamp} 发生事件")
    
    def getCount(self, timestamp):
        """获取指定时间戳的事件数量"""
        # 使用二分查找找到小于等于timestamp的事件数量
        count = bisect.bisect_right(self.events, timestamp)
        print(f"时间 {timestamp} 之前的事件数量: {count}")
        return count
    
    def getCountInRange(self, start_time, end_time):
        """获取时间范围内的事件数量"""
        start_count = bisect.bisect_left(self.events, start_time)
        end_count = bisect.bisect_right(self.events, end_time)
        count = end_count - start_count
        print(f"时间范围 [{start_time}, {end_time}] 内的事件数量: {count}")
        return count
    
    def getDeviceCount(self, deviceId, timestamp):
        """获取指定设备在指定时间之前的事件数量"""
        if deviceId not in self.device_events:
            return 0
        
        device_timestamps = self.device_events[deviceId]
        count = bisect.bisect_right(device_timestamps, timestamp)
        print(f"设备 {deviceId} 在时间 {timestamp} 之前的事件数量: {count}")
        return count

优化版本

使用更高效的数据结构：

class OptimizedEventAnalyzer:
    def __init__(self):
        # 使用有序列表存储时间戳
        self.events = []
        # 使用字典存储设备事件
        self.device_events = defaultdict(list)
        # 缓存查询结果
        self.cache = {}
    
    def addEvent(self, deviceId, timestamp):
        """添加设备事件"""
        # 插入到有序位置
        bisect.insort(self.events, timestamp)
        bisect.insort(self.device_events[deviceId], timestamp)
        
        # 清除相关缓存
        self._clearCache(timestamp)
    
    def getCount(self, timestamp):
        """获取指定时间戳的事件数量"""
        if timestamp in self.cache:
            return self.cache[timestamp]
        
        count = bisect.bisect_right(self.events, timestamp)
        self.cache[timestamp] = count
        return count
    
    def _clearCache(self, timestamp):
        """清除相关缓存"""
        keys_to_remove = [k for k in self.cache.keys() if k >= timestamp]
        for key in keys_to_remove:
            del self.cache[key]

算法分析

• 添加事件：O(log n) - 二分插入
• 查询计数：O(log n) - 二分查找
• 空间复杂度：O(n) - 存储所有事件
• 核心思想：有序数据结构 + 二分查找实现高效时间范围查询

测试用例

# 测试代码
analyzer = EventAnalyzer()

# 添加事件
analyzer.addEvent("router1", 100)
analyzer.addEvent("router2", 150)
analyzer.addEvent("router1", 200)
analyzer.addEvent("router3", 250)

# 查询计数
analyzer.getCount(200)  # 应该返回3
analyzer.getCount(150)  # 应该返回2
analyzer.getDeviceCount("router1", 200)  # 应该返回2

面试官看完直接点头："Excellent design! The time series approach is very efficient."

Candidate 成功拿下这一轮。

这就是 OAVOSERVICE 实时 VO 辅助 的威力：

不是死记硬背题库，而是帮你在最关键的时刻，快速理清思路，稳定发挥，稳稳过关！

面试技巧分享

在 Google 的面试中，除了算法实现，面试官还会关注：

1. 数据结构选择

能够合理选择有序数据结构来实现高效的时间范围查询。

2. 性能优化

能够提供多种优化方案，包括缓存和内存优化。

3. 系统设计思维

从实际应用角度考虑大规模数据处理的设计。

4. 代码质量

写出清晰、高效的代码，注意类的设计和接口。

Oavoservice 实时辅助服务

在这次 Google 面试中，我们的实时辅助系统发挥了关键作用：

• 快速思路提示：在候选人卡壳时，立即提供时间序列处理的核心思路
• 算法指导：推荐使用有序数据结构和二分查找来实现高效查询
• 代码优化：提供最优的代码实现，包括基础版本和优化版本
• 系统设计：帮助候选人从实际应用角度思考问题

结语

Google Fiber事件分析系统设计虽然是一道经典题目，但在面试的紧张环境下，能够快速理清思路并正确实现并不容易。这就是为什么我们的实时辅助服务如此重要。

如果你正在准备 Google 或其他公司的技术面试，欢迎联系 Oavoservice。我们拥有丰富的面试经验和专业的辅助团队，能够在你最需要的时候提供及时有效的帮助。

Oavoservice - 让每一次面试都成为成功的机会！

需要辅助的同学随时dd哦，vo开始前支持mock！