牧舟的博客

向所有虚度的时光宣战

实现带过期时间的LRU

Implementation of LRU cache with an expiry time for each entry

设计一个带有过期时间的LRU缓存。仍旧是同事面试时遇到的题，记录一下我的解法。经典的LRU题目，leetcode上有初始版本，lru-cache。这道面试题在leetcode题目的基础上增加了过期时间，到达容量上限后，先逐出过期的数据，然后再逐出最久未使用的数据。仿照leetcode的题目，本题大致是实现这样一个数结构。 class LRUCache { ...

Posted by MuZhou on March 2, 2023

分配红包算法

If you're not making mistakes, then you're not making decisions.

请编写一个红包随机算法。需求为：给定一定的金额，一定的人数，保证每个人都能随机获得一定的金额。比如100元的红包，10个人抢，每人分得一些金额。约束条件为，最佳手气金额不能超过红包总额的90% 最近同事面试某公司，被问到了这个题，记录一下我的解法。（为了简化问题，钱的单位统一为分）首先，借鉴微信红包的分配算法，在 [1, 2倍剩余平均值) 之间随机（注意是左闭右开区间）。...

Posted by MuZhou on February 28, 2023

三个线程交替打印ABC

Never let your fear decide your fate.

编写一个程序，开启三个线程，这三个线程的 ID 分别是 A、B 和 C ，每个线程把自己的 ID 在屏幕上打印 10 遍，要求输出结果必须按 ABC 的顺序显示，如 ABCABCABC… 依次递推最近同事面试阿里某部门，被问到了这个题，遥想18年的时候就被问过，记录一下。信号量版本 import java.util.concurrent.Semaphore; pub...

Posted by MuZhou on February 27, 2023

糟了，线上kafka消息积压了

Luck is what happens when preparation meets opportunity.

某天，深夜突然收到线上报警，某个业务的kafka消息消费发生堆积了。【阿里云】尊敬的用户xxx , 22:34 您的消息队列 Kafka实例instanceId=xxxxx，consumerGroup=xxxxx 消息堆积量当前值超过10000Count, 请登录云监控关注由于发生在深夜，很快确定对应时间点没有进行任何线上变更，流量也并没有突增，consumer业务服务也正...

Posted by MuZhou on December 30, 2021

救命，线上表varchar长度不够用了！

Know your limits but never stop trying to exceed them.

最近收到了一个线上报错，线上某个业务表（数据量7000w行）varchar(5120)字段长度不够用了。第一反应，不然直接把varchar(5120)改成text？但直接改表结构会影响业务吗？于是搭建了一个测试库，写入同等规模的数据量后，执行表结构变更： alter table `xxx` modify column `column_xxx` text 果不其然，确实有影响。 alt...

Posted by MuZhou on December 3, 2021

记一次美团面试的算法题

Somewhere, something incredible is waiting to be known.

上半年打算跳槽的时候参加了美团的一次面试，面试中问到了一道美团业务中的算法题，当时没有反应过来，答得也不好。大半年过去了，这期间一直时不时想起这道题，琢磨它的解法。最近在学习动态规划，有了一点新思路，记录一下。这道题题目大意是这样的（时间太久记不起原话了）：美团外卖每天都会产生很多订单，外卖小哥基于订单进行配送，系统会标记小哥每个订单开始配送和结束配送的时间点。求单日配送最高峰时...

Posted by MuZhou on November 14, 2018