Android 业务算法场景
Android 面试里的算法不只 LeetCode。真实业务更常问:图片缓存怎么淘汰、埋点怎么采样、请求怎么限流、日志怎么去重、Feed 分页怎么合并、设备指纹怎么做相似度。本篇把算法落到移动端工程场景。
一、LRU cache 与图片缓存淘汰
LRU(Least Recently Used)适合“最近访问还会再访问”的局部性场景。Android 图片库、页面数据缓存、解码 Bitmap 复用池都常用 LRU 或近似 LRU。
| 场景 | Key | Value | 淘汰依据 | 注意点 |
|---|---|---|---|---|
| 内存图片缓存 | URL + resize + transform | Bitmap/Drawable | 占用字节数 | 防 OOM,按 maxMemory 比例设置 |
| 磁盘图片缓存 | 安全 hash 后的 URL | 文件 | 总大小/最近访问 | 避免文件名过长,写入原子性 |
| 页面接口缓存 | route + params | JSON/Entity | TTL + LRU | 过期和一致性比命中率更重要 |
| BitmapPool | width/height/config | 可复用 Bitmap | 大小分桶 | 避免频繁分配导致 GC |
class BitmapMemoryCache(maxBytes: Int) : LruCache<String, Bitmap>(maxBytes) {
override fun sizeOf(key: String, value: Bitmap): Int = value.allocationByteCount
}
图片缓存面试要讲完整链路:内存 LRU → 磁盘 LRU → 网络下载 → 解码采样 → 写缓存 → 生命周期取消。只讲“用 HashMap + 双向链表”不够,要补 Android 内存预算、列表复用和 OOM 风险。
二、日志采样、去重与压缩上报
埋点/APM/Crash SDK 都会遇到“数据太多不能全传”的问题。业务算法目标是降低流量、电量和服务端压力,同时保留可分析性。
- 固定比例采样:按随机数或用户 hash 采样,适合普通埋点。
- 稳定采样:按
hash(userId/deviceId) % 100 < rate决定,同一用户长期一致,便于漏斗分析。 - 分层采样:错误、Crash、支付链路高采样;普通曝光低采样。
- 去重:短时间重复日志用
(eventName, page, keyParams)做 fingerprint,窗口内只保留一次或计数。 - 批量压缩:本地队列按数量/大小/时间触发 gzip 上报,失败后退避重试。
event → fingerprint → sliding window dedup
→ sampling decision
→ local queue(Room/file)
→ batch gzip upload with retry
三、限流、滑动窗口与重试保护
限流(rate limiting)在移动端用于保护接口、SDK 回调、日志上报、按钮连点和弱网重试。常见算法要结合业务选择。
| 算法 | 机制 | 适用场景 | 缺点 |
|---|---|---|---|
| 固定窗口 | 每个时间窗最多 N 次 | 简单按钮防抖、低风险接口 | 窗口边界可能突刺 |
| 滑动窗口 | 记录最近 T 时间内请求数 | 登录、验证码、上报保护 | 需要维护时间队列 |
| 令牌桶 | 固定速率生成 token,允许突发 | 网络请求、日志上报 | 参数要调优 |
| 漏桶 | 匀速流出 | 平滑上传队列 | 突发吸收能力弱 |
滑动窗口移动端实现直觉:
- 用队列保存事件时间戳。
- 新事件到来时移除超过窗口的旧时间。
- 队列大小小于阈值则允许,否则拒绝或延迟。
- 对持久化场景可只存计数桶,避免内存无限增长。
四、设备指纹相似度、布隆过滤器与本地风控
设备指纹/风控 SDK 常需要“快速判断是否见过、是否相似、是否命中黑名单”。这类题能把你的业务背景讲成算法亮点。
- 指纹相似度:把设备属性向量化,对稳定字段加高权重(硬件、系统特征),对易变字段低权重(IP、网络);用加权 Jaccard/余弦相似判断是否同设备族。
- SimHash/局部敏感哈希:把高维特征压成指纹,海明距离小表示相似,适合快速近似匹配。
- 布隆过滤器:本地黑名单、已上报 ID、去重 key 的快速存在性判断;回答“一定不存在/可能存在”和误判率。
- Counting Bloom Filter:需要删除时使用计数器,但空间变大。
- 隐私注意:指纹算法要服务于合规风控,最小化采集、脱敏、加密存储,不能无限收集敏感信息。
五、TopK、热点统计与本地搜索
移动端也有 TopK:热门搜索词、最近联系人、异常日志 TopN、耗时接口 TopN。核心是不要全量排序。
- 小顶堆 TopK:维护大小 K 的堆,新元素大于堆顶才替换,O(n log K)。适合日志/性能指标本地聚合。
- Space Saving/Misra-Gries:近似高频统计,适合内存很小但数据流很大的场景。
- Trie/倒排索引:本地搜索联系人、城市、商品名;前缀匹配用 Trie,关键词搜索用倒排。
- 拼音/模糊搜索:联系人搜索要建立 name、pinyin、首字母索引,并做结果排序。
- Room FTS:正文搜索可用 SQLite FTS,比
like '%x%'更适合大文本。
本地搜索索引:
keyword/token → [entityId1, entityId2, ...]
查询:分词/拼音归一化 → 取倒排列表 → 交并集 → 按权重排序
六、分页合并、去重与一致性
Feed、IM、订单列表常见问题:分页返回重复、刷新和加载更多交错、服务端数据更新导致顺序变化。本质是有序流合并与去重。
- 唯一 key 去重:用 itemId/serverId 去重,不要用 position。
- 游标分页优先:使用 cursor/lastId/createdAt,比 offset 更稳。
- 本地合并:新页与旧列表按排序 key 归并,重复 item 更新内容。
- 状态分离:refresh、append、prepend 分别维护 loading/error/cursor。
- Room + Paging3:RemoteMediator 把网络页落库,UI 观察数据库,降低进程死亡和旋转带来的状态丢失。
常见坑:服务端删除或置顶会改变排序,客户端只 append 可能出现缺失或重复;要定期 refresh 或使用版本号/增量同步。
高频面试题
Q1:设计图片内存缓存为什么用 LRU? 列表和详情页存在时间局部性,最近展示过的图片很可能再次出现。LRU 能在固定内存预算下保留热点 Bitmap,但要按字节数计算 size,并结合磁盘缓存、采样解码和生命周期取消。
Q2:埋点日志太多怎么上报? 用稳定采样控制比例,错误链路提高采样;对短时间重复事件做 fingerprint 去重或合并计数;本地队列批量 gzip 上报,失败指数退避,并设置磁盘上限防止撑爆存储。
Q3:移动端限流怎么实现? 按钮防抖可固定窗口,接口/上报更适合滑动窗口或令牌桶。要限制次数、设置退避,对非幂等请求避免自动重发,必要时让服务端用幂等 key 去重。
Q4:布隆过滤器适合哪些 Android 业务? 适合本地黑名单、已上报事件去重、缓存穿透保护、设备指纹快速存在性判断。它能回答“一定不存在/可能存在”,有误判但不会漏判,需要删除时用 Counting Bloom Filter。
易错点 / 追问
- 易错:只背 LRU 的 HashMap+双向链表,不讲 Bitmap 字节数、OOM、磁盘缓存和生命周期。
- 追问:滑动窗口和固定窗口区别?滑动窗口按最近 T 时间精确限制,固定窗口边界可能出现双倍突刺。
- 易错:TopK 直接全量排序;数据流或日志聚合应使用大小为 K 的小顶堆或近似高频算法。
- 追问:分页去重为什么不能按 position?刷新、插入、置顶会改变位置,必须用稳定业务 id。