5 道互联网大厂面试遇到的场景题

avatar
作者
筋斗云
阅读量:0

1.外卖单子只能被一个骑手接单

这是一个典型的分布式锁问题。可以采用以下几种方案:

  1. 基于Redis的分布式锁:
  • 使用Redis的SETNX命令尝试获取锁
  • 设置合理的锁超时时间,防止死锁
  • 使用Lua脚本保证原子性操作
  • 考虑Redis集群环境下的一致性问题
  1. 基于Zookeeper的分布式锁:
  • 创建临时顺序节点
  • 获取所有子节点并排序
  • 判断自己创建的节点是否为当前子节点中序号最小的节点
  • 是则获取到锁,否则对前一个节点注册watcher
  1. 基于数据库的乐观锁:
  • 订单表增加version字段
  • UPDATE时增加version条件
  • 失败则重试
  1. 基于消息队列:
  • 将订单消息发送到队列
  • 骑手消费消息,保证单一消费

最终选择哪种方案,需要根据系统的具体需求和架构来权衡。一般来说,Redis方案在性能和实现复杂度上较为均衡。

2.文件快速下发到 100w 个服务器

这需要考虑网络带宽、服务器负载等多方面因素。可以采用以下策略:

  1. CDN分发:
  • 将文件上传到CDN
  • 服务器从就近的CDN节点下载
  • 充分利用CDN的分布式特性
  1. P2P分发:
  • 将服务器分组,每组选择一个种子服务器
  • 种子服务器从源站获取文件
  • 组内其他服务器通过P2P方式从种子服务器获取
  1. 分布式文件系统:
  • 使用HDFS等分布式文件系统存储文件
  • 服务器挂载分布式文件系统
  • 文件自动同步到各节点
  1. 多级缓存:
  • 设置省级、市级缓存节点
  • 采用树状结构逐级分发
  1. 增量更新:
  • 仅传输文件的变化部分
  • 使用rsync等工具

实践中通常会综合使用多种方案,如CDN+P2P。同时要考虑失败重试断点续传等机制。

3.IP 段快速分组查询

这个问题可以使用**前缀树(Trie树)**来高效解决:

  1. 构建前缀树:
  • 每个IP段作为一个前缀插入树中
  • 叶子节点存储组信息
  1. 查询过程:
  • 将IP转换为二进制
  • 从根节点开始,根据二进制位遍历树
  • 遇到叶子节点则找到对应组
  1. 优化:
  • 使用压缩前缀树减少内存占用
  • 考虑缓存热点IP的查询结果
  1. 持久化:
  • 将前缀树序列化到文件或数据库
  • 系统启动时快速加载
  1. 动态更新:
  • 支持在线新增、删除、修改IP段
  • 考虑更新操作的原子性

这种方案的时间复杂度是O(n),非常适合大规模、高并发的IP查询场景。

4.TOP K 问题

对于10亿个数找最大的10个,可以采用以下方案:

  1. 分治 + 小顶堆:
  • 将数据分成1000份,每份100万个数
  • 每份使用小顶堆维护TOP 10
  • 最后合并1000个堆的结果
  • 在使用小顶堆查询最大的10个
  1. MapReduce:
  • Map阶段:每个节点维护局部TOP 10
  • Reduce阶段:合并所有局部结果

对于10万个单词找重复次数最高的10个:

  1. HashMap + 小顶堆:
  • 用 HashMap 统计频率
  • 用小顶堆维护 TOP 10
  1. Trie树:
  • 用Trie树存储单词
  • 叶子节点记录频率
  • 遍历叶子节点找TOP 10
  1. 外部排序:
  • 如果内存不足,先进行外部排序
  • 再扫描排序后的文件统计频率

实际应用中,需要根据数据规模、内存限制等因素选择合适的算法。

5.微信发红包API设计

  1. 红包分配算法:
  • 二倍均值法:每次随机金额的上限是剩余平均值的2倍

    • 保证了每次抽取的金额不会过大,不会导致后面的人没钱可分
    • 计算当前剩余金额的平均值: avg = 剩余金额 / 剩余人数
    • 设置本次抽取金额的上限为平均值的2倍: max = avg * 2
    • 在 [0.01, max] 范围内随机抽取金额
  • 线段切割法:将金额看做线段,随机切割

    • 生成 n-1 个随机数(n为红包数量),表示切割点
    • 将这些随机数从小到大排序
    • 计算每两个切割点之间的距离,作为每个红包的金额
  1. 数据一致性:
  • 使用分布式事务确保扣款、红包生成、领取的一致性
  • 考虑使用TCC模式处理分布式事务
  1. 高并发处理:
  • 使用缓存(如Redis)存储红包信息
  • 采用乐观锁防止超发
  • 考虑使用队列削峰
  1. 防作弊机制:
  • 限制单个用户领取次数
  • 根据用户画像调整概率
  1. 可用性设计:
  • 服务降级:金额校验失败时先发放,异步校正
  • 熔断:检测到异常时快速失败
  • 限流:控制接口调用频率
  1. 监控告警:
  • 监控红包池余额
  • 监控系统QPS、响应时间等指标

更多惊喜

我还将定期分享:

  • 最新互联网资讯:让你时刻掌握行业动态。

  • AI前沿新闻:紧跟技术潮流,不断提升自我。

  • 技术面试与职业发展:助你在职业生涯中走得更远、更稳。

  • 程序员生活趣事:让你在忙碌的工作之余找到共鸣与乐趣。

关注回复【1024】惊喜等你来拿!

敬请关注【程序员世杰】

点击关注程序员世杰

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!