2027日常-腾讯微信支付开发支持工具平台监控组件全栈三面

你在实习或项目中遇到了什么bug？

你优化或修了bug后从中总结了什么以后能用的上的范式？

你做了哪些有亮点的工作？

你自己对哪些前沿技术感兴趣？（要求和面试无关，和课题无关）

思考题+代码题（面完后实现并提交）：M匹马N个赛道(M>N)，至少几轮才能得到第K名次的赛马(K<N)？

• n*n匹马和n赛道，求前k名问题1
• n*n匹马和n赛道，求前k名问题2

把马分成若干组，每组最多 N 匹，先在每组内跑一次，得到组内的相对名次。 记第一轮需要的组数（也是第一阶段的比赛轮数）为 G1 = ⌈M / N⌉ 把每组的“组内第一名”（即各组胜者）再分组比赛，得到这些胜者的相对次序； 如果胜者数量仍 > N，就对胜者再分组比赛，重复这个“分层归并/汇总”的过程，直到胜者的数量 ≤ N 为止。这样我们可以把马按“组”层次把候选的快马缩减并对组间强弱作出排序。 在把组与组之间的大致次序确定后（即把各层的胜者做完必要的比赛、并最终把若干组的胜者放在一个最多 N 匹的比赛里得到组间的完全排序），只需要考虑来自前若干组的有限集合就可以决定整体的第 K 名。 若经过上一步我们把组的胜者排序，记排在第 1 的组为 A，第 2 的组为 B，……，则整体第 K 名必然来自以下这些马（只列出上界情况）：组 A 的前 K 名，组 B 的前 K-1 名，组 C 的前 K-2 名，直到第 K 个组的前 1 名。 这组候选马的总数上界为 S = 1 + 2 + … + K = K(K+1)/2，注意其中第一名（全局最快）已在前面的比较中被锁定，因此还要减去1，所以实际还需再比赛的马数上界为 S’ = K(K+1)/2 - 1。 用赛道把这些候选马再分批（每批最多 N 匹）比赛，得到最后的名次（或直接取前 K）。所需轮数为 ⌈S’ / N⌉（可能为 0，当 S’ = 0 时）。 情形1：当 M <= N^2 时，即第一轮分组后胜者数量 G(1) = ⌈M/N⌉ <= N 第一阶段（把所有马按 N 分组并跑完）：⌈M / N⌉ 轮 对各组胜者做一次比赛以得到组间排序：+ 1 轮 最后在候选马（数量上界 S’ = K(K+1)/2 - 1）中再分批比赛：+ ⌈S’ / N⌉ 轮 情形2：当 M > N^2 时，即第一轮分组后胜者数量 G(1) > N，需要分层汇总 定义层 i 的组数为 G(i) = ⌈M/N(i)⌉ 继续进行直到某层 L 满足 G(L) <= N（其中 L 是满足 ⌈M/N(L)⌉ <= N 的最小整数，直到把胜者数缩减到 <= N 为止），为了把这一层的胜者做完全排序还要再做一轮（实际上这相当于继续算下一层直到 1）。 所以把所有“分层汇总”需要的轮数为 G(1)+G(2)+…+G(L+1) 然后最后处理候选集合（大小上界仍为 S’ = K(K+1)/2 - 1 需要再加上 ⌈S’ / N⌉ 轮。 注意，下面的代码在赛道数 N=2 的边界情况时有问题（可能要特殊判断，类似冒泡排序，最少要几轮比赛才能得到第 K 快的就是冒泡排序排出前 K 个有序时的比较次数），自己后续再改改

package com.learn.normal;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * @Author : lowo
 * @Time : 2025/10/16 17:40
 * @Description : M匹马N个赛道(M>N)，至少几轮才能得到第K名次的赛马(K<N)
 */


/**
 * 返回值包含：
 * - List<BigInteger> layerGroupCounts: 每层组数 G1,G2,...
 * - BigInteger roundsForLayers: 分层汇总所需轮数 sum(G_i)
 * - BigInteger candidateUpperBound: 候选集合上界 S' = K(K+1)/2 - 1
 * - BigInteger roundsForCandidates: 在候选集合上再分批比赛所需轮数 ceil(S'/N)
 * - BigInteger totalRounds: 至少几轮才能得到第K名次的赛马 roundsForLayers + roundsForCandidates
 * - String note: 说明或备注
 */
public class HorseRaceRounds {

    /**
     * 结果封装类
     */
    public static class Result {
        public List<BigInteger> layerGroupCounts;
        public BigInteger roundsForLayers;
        public BigInteger candidateUpperBound;
        public BigInteger roundsForCandidates;
        public BigInteger totalRounds;
        public String note;

        public Result() {
            layerGroupCounts = new ArrayList<>();
            roundsForLayers = BigInteger.ZERO;
            candidateUpperBound = BigInteger.ZERO;
            roundsForCandidates = BigInteger.ZERO;
            totalRounds = BigInteger.ZERO;
            note = "";
        }
    }

    /**
     * 使用 BigInteger 实现的向上取整：ceil(a / b)
     */
    public static BigInteger ceilDiv(BigInteger a, BigInteger b) {
        if (b.equals(BigInteger.ZERO)) {
            throw new ArithmeticException("Division by zero in ceilDiv");
        }
        // (a + b - 1) / b
        BigInteger numerator = a.add(b).subtract(BigInteger.ONE);
        return numerator.divide(b);
    }

    /**
     * 计算至少几轮才能得到第K名次的赛马
     * 参数：
     * numHorses  - M，赛马总数 (M >= 0)
     * numTracks  - N，赛道数 (N >= 2)
     * targetRank - K，要求第 K 名 (1 <= K <= M)
     */
    public static Result computeMinRoundsUpperBound(long numHorses, long numTracks, long targetRank) {
        // 把输入转为 BigInteger，便于大整数计算
        BigInteger M = BigInteger.valueOf(numHorses);
        BigInteger N = BigInteger.valueOf(numTracks);
        BigInteger K = BigInteger.valueOf(targetRank);

        Result result = new Result();

        // 输入合法性检查
        if (numTracks < 2) {
            throw new IllegalArgumentException("numTracks (N) must satisfy (N >= 2)");
        }
        if (numHorses < 0) {
            throw new IllegalArgumentException("numHorses (M) must satisfy (M >= 0)");
        }
        if (numHorses == 0) {
            // 无马的特殊情况，直接返回 0
            result.note = "no horses (M=0)";
            result.layerGroupCounts = new ArrayList<>();
            result.roundsForLayers = BigInteger.ZERO;
            result.candidateUpperBound = BigInteger.ZERO;
            result.roundsForCandidates = BigInteger.ZERO;
            result.totalRounds = BigInteger.ZERO;
            return result;
        }
        if (targetRank < 1 || targetRank > numHorses) {
            throw new IllegalArgumentException("targetRank (K) must satisfy (1 <= K <= M)");
        }

        // 若 M <= N，则一次比赛即可得到所有名次
        if (M.compareTo(N) <= 0) {
            result.layerGroupCounts.add(BigInteger.ONE);
            result.roundsForLayers = BigInteger.ONE;
            result.candidateUpperBound = BigInteger.ZERO;
            result.roundsForCandidates = BigInteger.ZERO;
            result.totalRounds = result.roundsForLayers.add(result.roundsForCandidates);
            result.note = "M <= N: one race suffices to rank all horses";
            return result;
        }

        // 一般情况：M > N，需要分层计算 Gi = ceil(M / N^i) 直到 Gi <= N，并把 G_{L+1} 加入(L 是满足 ceilDiv(M, N^L) <= N 的最小整数)
        List<BigInteger> layerCounts = new ArrayList<>();
        // 当前 powN = N^i，初始 i = 1
        BigInteger powN = N;
        while (true) {
            BigInteger Gi;
            // 若 powN > M，则 ceil(M/powN) = 1
            if (powN.compareTo(M) > 0) {
                Gi = BigInteger.ONE;
            } else {
                Gi = ceilDiv(M, powN);
            }
            layerCounts.add(Gi);

            // 若 Gi <= N，说明胜者已缩减到 <= N，按策略还需把 G_{L+1} 加入
            if (Gi.compareTo(N) <= 0) {
                // 计算下一层的 powN
                powN = powN.multiply(N);
                BigInteger gNext;
                if (powN.compareTo(M) > 0) {
                    gNext = BigInteger.ONE;
                } else {
                    gNext = ceilDiv(M, powN);
                }
                layerCounts.add(gNext);
                break;
            }
            // 否则继续下一层（powN *= N）
            powN = powN.multiply(N);
        }

        // 计算 roundsForLayers = sum(Gi)
        BigInteger sumGi = BigInteger.ZERO;
        for (BigInteger g : layerCounts) {
            sumGi = sumGi.add(g);
        }

        // 计算候选集合上界 S' = K(K+1)/2 - 1
        BigInteger ksum = K.multiply(K.add(BigInteger.ONE)).divide(BigInteger.valueOf(2));
        if (powN.compareTo(M.add(ksum)) >= 0) {
            ksum = BigInteger.ZERO;
        }
        BigInteger candidateUpperBound = ksum.compareTo(BigInteger.ZERO) > 0 ? ksum.subtract(BigInteger.ONE) : BigInteger.ZERO;

        // 计算 roundsForCandidates = ceil(S' / N)
        BigInteger roundsForCandidates = candidateUpperBound.equals(BigInteger.ZERO) ? BigInteger.ZERO : ceilDiv(candidateUpperBound, N);

        // 填充结果
        result.layerGroupCounts = layerCounts;
        result.roundsForLayers = sumGi;
        result.candidateUpperBound = candidateUpperBound;
        result.roundsForCandidates = roundsForCandidates;
        result.totalRounds = sumGi.add(roundsForCandidates);
        result.note = "nomal result";

        return result;
    }

    /**
     * 打印函数，输出结果与字段含义
     */
    public static void printResult(long M, long N, long K, Result result) {
        System.out.println("输入: M=" + M + " (马数), N=" + N + " (赛道数), K=" + K + " (求第 K 名)");
        System.out.println("说明: " + result.note);
        if (result.layerGroupCounts == null || result.layerGroupCounts.isEmpty()) {
            System.out.println("各层组数 (layerGroupCounts): (empty)");
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < result.layerGroupCounts.size(); ++i) {
                if (i > 0) {
                    sb.append(", ");
                }
                sb.append("G").append(i + 1).append("=").append(result.layerGroupCounts.get(i).toString());
            }
            System.out.println("各层组数 (layerGroupCounts): " + sb.toString());
        }
        System.out.println("分层汇总所需轮数 (roundsForLayers): " + result.roundsForLayers.toString());
        System.out.println("候选集合上界 S' (candidateUpperBound = K(K+1)/2 - 1): " + result.candidateUpperBound.toString());
        System.out.println("候选集合分批所需轮数 (roundsForCandidates): " + result.roundsForCandidates.toString());
        System.out.println("=> 至少几轮才能得到结果 (totalRounds): " + result.totalRounds.toString());
        System.out.println("------------------------------------------------------------");
    }

    /**
     * 主函数：包含测试用例
     */
    public static void main(String[] args) {

        long[][] tests = {
                {25, 5, 3},       // 期望 totalRounds = 7
                {64, 8, 4},       // 期望 totalRounds = 11
                {36, 6, 6},       // 期望 totalRounds = 11
                {30, 5, 3},       // M > N^2 的例子，期望 totalRounds = 9
                {9, 10, 4},       // M < N 的例子，期望 totalRounds = 1
                {5, 5, 3},        // M == N 的例子，期望 totalRounds = 1
                {6, 5, 2},        // M 接近 N，期望 totalRounds = 3
                {0, 5, 1},        // M == 0，期望 totalRounds = 0
                {12, 4, 1},       // K==1（只求最快），期望 totalRounds = 4
        };

        for (long[] tc : tests) {
            long M = tc[0], N = tc[1], K = tc[2];
            try {
                Result b = computeMinRoundsUpperBound(M, N, K);
                printResult(M, N, K, b);
            } catch (Exception e) {
                System.out.println("测试 (M=" + M + ", N=" + N + ", K=" + K + ") 发生异常: " + e.getMessage());
                System.out.println("------------------------------------------------------------");
            }
        }
    }
}