面试场景题:如何设计一个红包随机算法

目前在阿里云的面试过程中遇到了这道算法题,今天搜了下解法,整理出来

面试官:咱来写个算法题吧

设计一个抢红包的随机算法,比如一个人在群里发了100块钱的红包,群里有10个人一起来抢红包,每人抢到的金额随机分配。

1.所有人抢到的金额之和要等于红包金额,不能多也不能少。

2.每个人至少抢到1分钱。

3.最佳手气不超过红包总金额的90%

解题思路1:随机分配法

  • 钱的单位转换为分,每次在[1, leaveMoney]这个区间内随机一个值,记为r;
  • 计算一下剩余金额leaveMoney-r,剩余金额(单位:分)必须大于剩余人数,不然后面的人无法完成分配,例如10个人,有1个人抢了红包,剩余的money至少还需要9分钱,不然剩余的9人无法分;
  • 按照顺序随机n-1次,最后剩下的金额可以直接当做最后一个红包,不需要随机;

解题代码:

 public static List<Double> generate(double totalMoney, int people) {
        // 转换为分处理避免浮点误差
        double totalCents = Math.round(totalMoney * 100);
        double maxLimit = (totalCents * 0.9); // 总金额的90%
        double leaveMoney = totalCents;
        List<Double> result = new ArrayList<>();
        //判断钱不够分,不处理
        if ((int)totalCents < people) {
            return result;
        }
        Random random = new Random();

        //每次生成随机数
        int n = people - 1;
        while (n > 0) {
            //随机数在[1, min(maxLimit, leaveMoney)]之间,单位是:分
            double min = Math.min(leaveMoney, maxLimit);
            double allocResult = 1 + random.nextInt((int)min);
            //判断这次分配后,后续的总金额仍然可分,且不超过90%总金额
            if (allocResult > maxLimit || (leaveMoney - allocResult) < n) {
                continue;
            }
            leaveMoney -= allocResult;
            n--;
            result.add(allocResult / 100.0);
        }
        result.add(leaveMoney / 100.0);
        return result;
    }

以下是多次运行的结果:

[37.77, 50.76, 1.89, 7.89, 0.26, 0.24, 0.25, 0.78, 0.06, 0.1]
[89.38, 2.45, 3.5, 4.43, 0.03, 0.08, 0.06, 0.04, 0.01, 0.02]
[53.51, 40.86, 5.48, 0.04, 0.06, 0.01, 0.01, 0.01, 0.01, 0.01]
[42.71, 0.27, 38.99, 4.5, 4.02, 4.58, 2.97, 0.84, 0.21, 0.91]

通过多次运行的结果,可以看到越早抢红包的人,抢到的金额越大,所以题目还可以变形

要求红包金额分布均衡

面试官:继续改进红包生成算法,要求:

1.要保证红包拆分的金额尽可能分布均衡,不要出现两极分化太严重的情况。

解题思路2:二倍均值法

二倍均值法:假设剩余红包金额为m元,剩余人数为n,那么有如下公式:

每次抢到的金额 = 随机区间 [0.01,m /n × 2 - 0.01]元

这个公式,保证了每次随机金额的平均值是相等的,不会因为抢红包的先后顺序而造成不公平。

举个例子如下:

假设有5个人,红包总额100元。100÷5×2 = 40,所以第1个人抢到的金额随机范围是[0.01,39.99]元,在正常情况下,平均可以抢到20元。

假设第1个人随机抢到了20元,那么剩余金额是80元。80÷4×2 = 40,所以第2个人抢到的金额的随机范围同样是[0.01,39.99]元,在正常的情况下,还是平均可以抢到20元。假设第2个人随机抢到了20元,那么剩余金额是60元。60÷3×2 = 40,所以第3个人抢到的金额的随机范围同样是[0.01,39.99]元,平均可以抢到20元。以此类推,每一次抢到金额随机范围的均值是相等的。

解题代码:

public static List<Double> allocateRedEnvelop(double totalMoney, int people) {
        // 转换为分处理避免浮点误差
        double totalCents = Math.round(totalMoney * 100);
        double maxLimit = (totalCents * 0.9); // 总金额的90%
        Random random = new Random();
        double leaveMoney = totalCents;
        List<Double> result = new ArrayList<>();
        int n = people;
        //注意是大于1,最后1个人领取剩余的钱
        while (n > 1) {
            //生成随机金额的范围是[1, leaveMoney / n * 2 - 1], 注意nextInt方法生成结果范围是左闭右开的
            double allocatMoney = 1 + random.nextInt((int)leaveMoney / n * 2 - 1);
            result.add(allocatMoney / 100.0);
            n--;
            leaveMoney -= allocatMoney;
        }
        result.add(leaveMoney / 100.0);
        return result;
    }

生成结果测试如下,结果值比较随机了,领取的红包金额和先后顺序无关了

[8.58, 4.56, 20.88, 13.83, 7.6, 3.94, 10.87, 8.66, 20.92, 0.16]
[3.31, 2.08, 15.99, 16.79, 13.13, 0.61, 17.38, 10.93, 4.93, 14.85]
[0.24, 21.86, 15.57, 16.86, 3.45, 3.18, 5.48, 13.01, 6.76, 13.59]

解题思路3:线段切割法

考虑一种新的解法,把红包总金额想象成一条很长的线段,而每个人抢到的金额就是这条主线段上的某个子线段,如下图:

  • 假设有N个人一起抢红包,红包总金额为M,就需要确定N-1个切割点;
  • 切割点的随机范围是(1,M),所有切割点确认后,子线段长度也就确定了
  • 如果随机切割点出现重复,则重新生成切割点

解题代码如下:

    /**
     * 线段切割法
     */
    public static List<Double> allocateRedEnvelopNew(double totalMoney, int people) {
        // 转换为分处理避免浮点误差
        double totalCents = Math.round(totalMoney * 100);
        double maxLimit = (totalCents * 0.9); // 总金额的90%
        Random random = new Random();
        double leaveMoney = totalCents;
        List<Double> result = new ArrayList<>();
        Set<Integer> pointCutSet = new HashSet<>();
        int n = people;
        while (pointCutSet.size() < people - 1) {
            //生成n - 1个切割点,随机点取值范围是[1, totalCents]
            pointCutSet.add(random.nextInt((int) totalCents) + 1);
        }
        //接着生成对应子线段的钱数
        Integer[] points = pointCutSet.toArray(new Integer[0]);
        Arrays.sort(points);
        result.add(points[0] / 100.0);
        //子线段+ 最后那段的长度 = totalCents,注意上一步是已经加了points[0],result中的所有元素和累加后的结果一定是totalCents,
        for (int i = 1; i < points.length; i++) {
            result.add((points[i] - points[i - 1]) / 100.0);
        }
        result.add((totalCents - points[points.length - 1]) / 100.0);
        return result;
    }

最后跑几次看看生成的随机效果,可以看到手气最佳的有到37块钱的,相比较二倍均值法,该方法手气最佳获取的金额可能更高

[20.24, 3.9, 7.63, 9.62, 15.41, 2.32, 0.21, 24.94, 9.66, 6.07]
[8.64, 33.55, 3.76, 15.35, 4.41, 9.85, 4.81, 15.9, 2.71, 1.02]
[11.31, 13.32, 16.53, 5.91, 8.69, 17.29, 11.09, 7.62, 7.14, 1.1]
[21.34, 8.24, 1.9, 7.98, 0.49, 0.32, 13.75, 37.27, 0.03, 8.68]

以上就是关于红包随机算法的所有解题方法了,面试中如果遇到考这道算法题,需要问清楚红包随机的情况,有没有要求分布均衡。

如果觉得对面试有帮助的话,记得给文章点赞哦~

#软件开发笔面经#
全部评论
最后一种方法如何限制金额不大于总数的90%呢?好像有点问题
1 回复 分享
发布于 04-04 20:22 广东
你是我见过最美丽的牛客男孩
点赞 回复 分享
发布于 04-04 20:03 广东
思路1会不会存在最后一个人金额大于90%的情况
点赞 回复 分享
发布于 04-04 16:14 广东
前段时间面试京东被问到这个,没答出来
点赞 回复 分享
发布于 03-23 20:12 湖北

相关推荐

有没有26,27届在找实习的学弟学妹~&nbsp;抖音搜索质量架构组内直招,搜索稳定性、告警治理、性能平台开发&nbsp;等你来战,组里技术氛围好,需求专项复杂,同事也都很nice,是一次镀金的好机会~&nbsp;可长期稳定实习是加分项哦~详细job信息:ByteIntern:面向2026届毕业生(2025年9月-2026年8月期间与毕业),为符合岗位要求的同学提供转正机会。团队介绍:搜索QA团队职责为搜索全链路质量保障,业务涵盖抖音搜索、头条搜索、西瓜搜索、火山搜索和其他字节系app的搜索能力支持。有活力、有创造力、有韧性的QA搜索团队,加入我们,为用户提供极致和更未来化的搜索体验。充分整合内容,高效连接人与信息,致力于成为用户首选的搜索引擎,做“最懂你的搜索”!1、对互联网产品进行测试,对围绕测试展开的开发任务进行落地实现;2、负责搜索特型产品的关键指标的数据分析,提取,建模和相关开发工作;3、对搜索特型产品核心指标和问题收敛工作进行平台化开发。职位要求1、2026届本科及以上学历在读,计算机、数学等相关专业优先;2、掌握基本的测试理论和开发技能;3、良好的沟通表达和团队合作能力;4、熟练掌握Linux常用操作,熟悉Python、Go、C++、Php等语言的一种或几种;5、对自己的工作认真负责,对代码格式与最终效果追求极致;6、能保证至少3个月以上的实习,每周可出勤至4天及以上。有意愿的同学可以投递简历至lvjinhong@bytedance.com,私聊我了解详情
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
06-06 21:46
门头沟学院 Java
怎么说呢,感觉跟我看的面经不太一样,和我准备的更是大相径庭。1、自我介绍2、项目拷打 &nbsp;&nbsp;&nbsp;&nbsp;(1)&nbsp;我感觉是我不太理解面试官的问题。面试官问&nbsp;“怎么实现登录模块,鉴权保证,业务完备性”,我听起来感觉是这个意思。然后大概互相掰扯大概下面几个方面:密码传输加密(HTTPS&nbsp;+&nbsp;前端哈希)与存储强哈希(BCrypt);多因素认证与失败次数限制(防暴力破解);会话安全管理(JWT/Redis&nbsp;+&nbsp;过期策略);攻击防御(SQL&nbsp;注入、CSRF、XSS)与日志审计。但是似乎感觉面试官不是很满意我的回答,觉得我的回答很多是技术相关的。蒟蒻牛真的想不到要怎么回答啊啊啊啊啊。求牛友解答。然后面试官就继续根据我回答的一些内容,可能是感兴趣的,问:对称加密和非对称加密。JWT怎么实现,然后我就讲了一下这个的组成,讲了JWT的三部分,再简单结合我的项目讲了一下JWT场景使用的流程。后面好像还延伸了一些问题,好像是跟我上面掰扯的几个方面详细问了一下。因为后面还有个笔试,忘记了。我们这个项目遇到的挑战。直接巴拉巴拉讲了一堆,项目上线遇到的一些问题反馈和解决方案。然后顺带问了一下项目里面的MQ的幂等性和可靠性。然后引出“明天高考,如果考生想要查看高考分数,应该怎么高效快速得知自己的分数”。因为前面面试官铺垫“河南省,很多考生,高考查分”,然后我的侧重点就再高并发和可用性啥的上面了,但是面试官说不是想问这个,说是想要查看“某一个考生的分数”,经过一波(忘记了)的说明/提示,说是要用怎样的排序算法,能够快速知道自己的分数/成绩。然后,脑子里全是快排和归并排序,胡编乱造分数的随机性啥的,选了个归并排序,结果面试官(提示?)强调分数只有0到150(我的理解是分数上限是固定而且比较小的),然后我回答“桶排序”,似乎面试官是想要这个答案?继续问问什么使用桶排序,(完蛋了,排序还是两年前学的,现在都没怎么记得少用的排序桶排序了,就掰扯了一小会)。面试官继续问“如果使用桶排序的话,怎么查到这个考生的成绩,复杂度是多少?”,怕什么来什么,最后似乎记错了,然后就拷打收尾了。我不知道为什么只问第二个项目,而且还是问“登录模块”的,其实还有一个项目是青训营做的微服务项目,但是似乎面试官不感兴趣,难道是那个项目是学校团队合作做的?已经上线使用了?嗯嗯嗯,不理解,求解。最后:算法题:leetcode678(非hot100),没刷到,感觉这个题很熟悉,但是似乎没做过(可能之前算法比赛训练有做过,但是忘记了),大概讲了一下思路,然后面试官问了一下时间复杂度、空间复杂度。反问:业务end:只能说,跟tencent的真的很不一样的面试提问
字节跳动一面1215人在聊 查看6道真题和解析
点赞 评论 收藏
分享
评论
16
69
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务