Android 业务算法场景

Android 面试里的算法不只 LeetCode. 真实业务更常问: 图片缓存怎么淘汰, 埋点怎么采样, 请求怎么限流, 日志怎么去重, Feed 分页怎么合并, 设备指纹相似度怎么算. 本篇把算法落到移动端工程场景.

学习目标与章节边界

本章给出 Android 进程内可操作的业务算法 Kotlin 片段, 重点是生命周期, 时钟, 内存和持久化边界; 通用题解见 LeetCode Hot 100 算法清单, 超内存的分桶, 位图与外排见海量数据处理. 完成后应能说明一个算法的输入规模, 线程模型, 进程重启行为和测试证据.

一, LRU cache 与图片缓存淘汰

LRU (Least Recently Used) 适合 “最近访问还会再访问” 的局部性场景. Android 图片库, 页面数据缓存, 解码 Bitmap 复用池都常用 LRU 或近似 LRU.

class BitmapMemoryCache(maxBytes: Int) : LruCache<String, Bitmap>(maxBytes) {
    override fun sizeOf(key: String, value: Bitmap): Int = value.allocationByteCount
}

面试手写 LRU 见 53 算法补充专题.

图片缓存面试要讲完整链路: 内存 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

以下是纯 Kotlin/JVM 上下文片段. 调用方应在单一串行 dispatcher 或锁保护下使用同一个实例; 它们不负责 Room 写入, 网络或隐私授权.

import java.nio.charset.StandardCharsets
import java.security.MessageDigest

fun isStablySampled(subjectId: String, ratePercent: Int): Boolean {
    require(ratePercent in 0..100)
    val digest = MessageDigest.getInstance("SHA-256")
        .digest(subjectId.toByteArray(StandardCharsets.UTF_8))
    val bucket = ((digest[0].toInt() and 0xff) shl 8 or (digest[1].toInt() and 0xff)) % 100
    return bucket < ratePercent
}

class FingerprintDeduplicator(private val windowMs: Long, private val maxKeys: Int) {
    private val seenAt = LinkedHashMap<String, Long>()
    fun shouldKeep(fingerprint: String, nowElapsedMs: Long): Boolean {
        require(windowMs >= 0 && maxKeys > 0)
        val iterator = seenAt.entries.iterator()
        while (iterator.hasNext()) if (nowElapsedMs - iterator.next().value > windowMs) iterator.remove()
        if (seenAt.containsKey(fingerprint)) return false
        seenAt[fingerprint] = nowElapsedMs
        while (seenAt.size > maxKeys) seenAt.entries.iterator().also { it.next(); it.remove() }
        return true
    }
}

执行时 Android 应传入 SystemClock.elapsedRealtime(), 不要传 currentTimeMillis(), 后者会因校时倒退. 稳定采样对同一实现 / ID 每次结果一致, 但哈希实现或 ID 规范变更会改变分桶, 需版本化. 容量淘汰会让很旧的 key 提前再次通过; 进程死亡会清空内存窗口, 关键幂等仍须服务端用事件 ID 保证.

三, 限流, 滑动窗口与重试保护

限流 (rate limiting) 在移动端用于保护接口, SDK 回调, 日志上报, 按钮连点和弱网重试. 常见算法要结合业务选择.

滑动窗口移动端实现直觉:

1. 用队列保存事件时间戳.
2. 新事件到来时移除超过窗口的旧时间.
3. 队列大小小于阈值则允许, 否则拒绝或延迟.
4. 对持久化场景可只存计数桶, 避免内存无限增长.

// 非线程安全;一个实例由单一串行 dispatcher 所有,或由调用方同步.
class SlidingWindowLimiter(private val limit: Int, private val windowMs: Long) {
    private val timestamps = ArrayDeque<Long>()
    fun tryAcquire(nowElapsedMs: Long): Boolean {
        require(limit > 0 && windowMs > 0)
        while (timestamps.isNotEmpty() && nowElapsedMs - timestamps.first() >= windowMs) timestamps.removeFirst()
        if (timestamps.size >= limit) return false
        timestamps.addLast(nowElapsedMs)
        return true
    }
}

// 非线程安全;一个实例由单一串行 dispatcher 所有,或由调用方同步.
class TokenBucket(private val capacity: Double, private val tokensPerSecond: Double) {
    private var tokens = capacity
    private var lastMs: Long? = null
    fun tryAcquire(nowElapsedMs: Long, cost: Double = 1.0): Boolean {
        require(capacity > 0 && tokensPerSecond > 0 && cost > 0)
        val previousMs = lastMs
        require(previousMs == null || nowElapsedMs >= previousMs) { "elapsed time must not move backwards" }
        if (previousMs != null) tokens = minOf(capacity, tokens + (nowElapsedMs - previousMs) * tokensPerSecond / 1_000.0)
        lastMs = nowElapsedMs
        if (tokens < cost) return false
        tokens -= cost
        return true
    }
}

参数示例: 上传希望稳定平均 2 req/s, 允许网络恢复后最多突发 5 个批次, 设 capacity=5, tokensPerSecond=2. 这不是通用推荐值, 应在真实 429, 耗电和服务端配额数据下调整. 滑窗测试: limit=2, window=1_000, 在 0,100,200ms 三次请求预期通过, 通过, 拒绝, 1_000ms 再请求通过. 令牌桶测试: capacity=2, tokensPerSecond=2, 在 0ms 请求成本 2 后, 在 500ms 请求成本 1 应通过, 证明 0ms 是有效初始化时间而非未初始化哨兵; 随后传入更小时间必须拒绝.

四, 设备指纹相似度, 布隆过滤器与本地风控

设备指纹 / 风控 SDK 常需要 “快速判断是否见过, 是否相似, 是否命中黑名单”.这类题能把你的业务背景讲成算法亮点.

• 指纹相似度: 把设备属性向量化, 对稳定字段加高权重 (硬件, 系统特征), 对易变字段低权重 (IP, 网络); 用加权 Jaccard / 余弦相似判断是否同设备族.
• SimHash / 局部敏感哈希: 把高维特征压成指纹, 海明距离小表示相似, 适合快速近似匹配.
• 布隆过滤器: 本地黑名单, 已上报 ID, 去重 key 的快速存在性判断; 回答 “一定不存在 / 可能存在” 和误判率. 原理与误判公式详见 54 海量数据处理.
• Counting Bloom Filter: 需要删除时使用计数器, 但空间变大.
• 隐私注意: 指纹算法要服务于合规风控, 最小化采集, 脱敏, 加密存储, 不能无限收集敏感信息.

fun simHash64(weightedFeatures: Map<String, Int>): Long? {
    if (weightedFeatures.isEmpty()) return null
    require(weightedFeatures.size <= 10_000) { "too many features" }
    val sums = LongArray(64)
    for ((feature, weight) in weightedFeatures) {
        require(weight in 1..1_000_000) { "feature weight must be positive and bounded" }
        val h = feature.hashCode().toLong() * -0x61c8864680b583ebL
        for (bit in 0 until 64) sums[bit] += if (((h ushr bit) and 1L) == 1L) weight.toLong() else -weight.toLong()
    }
    var fingerprint = 0L
    for (bit in 0 until 64) if (sums[bit] >= 0) fingerprint = fingerprint or (1L shl bit)
    return fingerprint
}
fun hammingDistance(a: Long, b: Long): Int = java.lang.Long.bitCount(a xor b)

这是近似相似度候选生成, 不是身份判定: 阈值需在标注样本上评估误报 / 漏报, 并按版本记录特征集合. hashCode() 仅为教学 hash; 生产指纹需稳定, 可版本化的散列和合规评审. 权重必须为正且受上限保护, 以免累加溢出; 空特征返回 null, 表示没有可比较的指纹.

五, 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, ...]
查询:分词/拼音归一化 → 取倒排列表 → 交并集 → 按权重排序

// 非线程安全;一个实例由单一串行 dispatcher 所有,或由调用方同步.
class InvertedIndex {
    private val postings = mutableMapOf<String, MutableSet<Long>>()
    fun add(documentId: Long, normalizedTokens: Iterable<String>) {
        normalizedTokens.filter { it.isNotBlank() }.forEach { postings.getOrPut(it) { linkedSetOf() }.add(documentId) }
    }
    fun andQuery(tokens: List<String>): Set<Long> {
        if (tokens.isEmpty()) return emptySet()
        val lists = tokens.map { postings[it] ?: return emptySet() }
        return lists.drop(1).fold(lists.first().toSet()) { result, ids -> result.intersect(ids) }
    }
}

加入文档 1 的 android cache, 文档 2 的 android room 后, 查询 android, cache 预期只得到 1. 真实联系人检索还要统一大小写, 拼音和分词版本; 删除 / 更新必须删除旧 posting. 文本规模大时优先 Room FTS, 而不是把全量索引常驻内存.

图片采样解码: 按目标尺寸而非原图解码

以下为 Android 上下文片段, 调用方应在后台线程读取流, 并负责关闭流或让图片库管理生命周期.

import android.graphics.Bitmap
import android.graphics.BitmapFactory

fun calculateInSampleSize(width: Int, height: Int, requestedWidth: Int, requestedHeight: Int): Int {
    require(requestedWidth > 0 && requestedHeight > 0)
    var sample = 1
    while (width / (sample * 2) >= requestedWidth && height / (sample * 2) >= requestedHeight) sample *= 2
    return sample
}

fun decodeSampled(bytes: ByteArray, requestedWidth: Int, requestedHeight: Int): Bitmap? {
    val options = BitmapFactory.Options()
    with(options) {
        inJustDecodeBounds = true
        BitmapFactory.decodeByteArray(bytes, 0, bytes.size, this)
        if (outWidth <= 0 || outHeight <= 0) return null
        inSampleSize = calculateInSampleSize(outWidth, outHeight, requestedWidth, requestedHeight)
        inJustDecodeBounds = false
        return BitmapFactory.decodeByteArray(bytes, 0, bytes.size, this)
    }
}

4000x3000 ARGB_8888 原图约 45.8 MiB; 目标 1000x750, sample=4 时约 2.86 MiB. 损坏输入可能使 outWidth/outHeight <= 0, 应返回失败而非进入采样循环; 解码结果可为 null, UI 必须有错误状态.

六, 分页合并, 去重与一致性

Feed, IM, 订单列表常见问题: 分页返回重复, 刷新和加载更多交错, 服务端数据更新导致顺序变化. 本质是有序流合并与去重.

1. 唯一 key 去重: 用 itemId/serverId 去重, 不要用 position.
2. 游标分页优先: 使用 cursor/lastId/createdAt, 比 offset 更稳.
3. 本地合并: 新页与旧列表按排序 key 归并, 重复 item 更新内容.
4. 状态分离: refresh, append, prepend 分别维护 loading/error/cursor.
5. Room + Paging3: RemoteMediator 把网络页落库, UI 观察数据库, 降低进程死亡和旋转带来的状态丢失.

常见坑: 服务端删除或置顶会改变排序, 客户端只 append 可能出现缺失或重复; 要定期 refresh 或使用版本号 / 增量同步.

七, 从抽象算法到真实约束

回答业务算法题要给实际规模和失败边界: 缓存按字节而非条目评估, LRU 命中率需按真实访问分布基准; 去重窗口要说明最大事件数和误判/漏判; 限流使用单调时钟并处理进程重启; TopK 指明是否允许近似和多线程更新; 分页合并处理重复, 删除, 乱序和刷新边界. 性能结论应在代表性低端设备和数据分布上用 benchmark/trace 验证, 不只给复杂度.

高频面试题

Q1: 设计图片内存缓存为什么用 LRU? 列表和详情页存在时间局部性, 最近展示过的图片很可能再次出现. LRU 能在固定内存预算下保留热点 Bitmap, 但要按字节数计算 size, 并结合磁盘缓存, 采样解码和生命周期取消.

Q2: 埋点日志太多怎么上报? 用稳定采样控制比例, 错误链路提高采样; 对短时间重复事件做 fingerprint 去重或合并计数; 本地队列批量 gzip 上报, 失败指数退避, 并设置磁盘上限防止撑爆存储.

Q3: 移动端限流怎么实现? 按钮防抖可固定窗口, 接口 / 上报更适合滑动窗口或令牌桶. 要限制次数, 设置退避, 对非幂等请求避免自动重发, 必要时让服务端用幂等 key 去重.

Q4: 布隆过滤器适合哪些 Android 业务? 适合本地黑名单, 已上报事件去重, 缓存穿透保护, 设备指纹快速存在性判断. 它能回答 “一定不存在 / 可能存在”, 有误判但不会漏判, 需要删除时用 Counting Bloom Filter.

易错点 / 追问

• 易错: 只背 LRU 的 HashMap+ 双向链表, 不讲 Bitmap 字节数, OOM, 磁盘缓存和生命周期.
• 追问: 滑动窗口和固定窗口区别? 滑动窗口按最近 T 时间精确限制, 固定窗口边界可能出现双倍突刺.
• 易错: TopK 直接全量排序; 数据流或日志聚合应使用大小为 K 的小顶堆或近似高频算法.
• 追问: 分页去重为什么不能按 position? 刷新, 插入, 置顶会改变位置, 必须用稳定业务 id.

主题练习与预期证据

1. 固定 subjectId 连续稳定采样 100 次, 预期结果完全相同; 更换 ID 不承诺必然改变结果.
2. 为去重器在 0ms/500ms/1001ms 同一指纹调用, 窗口为 1000ms, 预期为通过, 拒绝, 通过.
3. 用 4000x3000 输入和 1000x750 目标手算采样内存, 预期能解释为何按条目数做图片 LRU 会有 OOM 风险.