东邪老师讲解 Post 系统的设计

文章预览

实现前5分钟，1小时，24小时内分享最多的post的系统 这个题是一个很好的面试题，因为可以从算法和系统两个角度进行考察。 从算法的角度分析 可以简单的称之为   Top K Frequent Elements in Recent X mins. 算法的角度，本质就是设计一个 数据结构 ，支持给某个key的count+1（有一个post被分享了），给某个key的count-1（有一个分享的计数已经过期了），然后查询Top k。 做法是维护一个有序序列（用链表来维护），每个链表的节点的key是 count，value是list of elements that has this count，也用linked list串起来。 比如 a出现2次，b出现3次，c出现2次，d出现1次。那么这个链表就是： {3: [b]} --> {2: [a ->c]} --> {1: [d]} 然后另外还需要一个hashmap，key是element，value是这个element在链表上的具体位置。 因为每 ………………………………