V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Ymmmmmmmm
V2EX  ›  Java

阿里云技术面试红宝书的一道面试题

  •  
  •   Ymmmmmmmm · 2022-05-26 18:22:05 +08:00 · 1920 次点击
    这是一个创建于 902 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个网站有很多页面 ( url ), 做一个 url 排行榜功能。排行根据 url 的访问次数 (pv) 排行。

    排行榜需要实时准确即:某个页面每一次访问都会实时地影响到排行数据。

    提示:排行榜本身也会有很高的实时访问需求,注意读和写的时间复杂度。

    考察点:数据结构的组合使用。

    这道题的解题思路是不是:redis 的有序集合的跳表啊🤔

    3 条回复    2022-06-22 21:45:02 +08:00
    1194129822
        1
    1194129822  
       2022-05-26 23:22:06 +08:00   ❤️ 4
    的确,redis zset 可以完成任务,但是想要考察的是数据结构和并发吧,参考 zset 的实现,hash + skiplist ,在 Java 对应的并发结构是 ConcurrentHashMap(url, pv),ConcurrentSkipListMap(pv, set(url))。CHM 可以处理高并发读写,CSLM 处理实时排序(如果排序规则是最新的在最前面 set(url)换成 LinkedHashMap ),设计成事件驱动,在 url 被访问的时候加 hook 触发事件,然后面试官问问 CHM 原理之类就差不多了。 还可以优化,比如排行榜实时到什么程度?同一 pv 的 url 太多问题。排行榜既然叫排行榜,肯定不用全排行,一般都是一部分, 这就涉及 topN 问题。等等,能深挖的有很多。
    Ymmmmmmmm
        2
    Ymmmmmmmm  
    OP
       2022-05-27 09:57:04 +08:00
    多谢,受教了
    lihahahayang
        3
    lihahahayang  
       2022-06-22 21:45:02 +08:00
    @1194129822 pv 数量一样的时候,cslm 不是有问题了吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5401 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 05:49 · PVG 13:49 · LAX 21:49 · JFK 00:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.