职场话题

从支付宝P0事故处理方案，合理推测损失金额

支付宝

支付宝昨天（2024-01-16）的无差别"送钱"的事儿，大家都知道了吧。

具体的，就是在昨天 14:40~14:45 期间，所有支付宝的支付订单都被减免了 20%，减免原因在界面上显示为"政府补贴"。

这里指的订单，是指所有通过支付宝产生的交易，包括「购物、信用卡、生活缴费、个人转账」等等，而且和此前（消费类的）有减免上限的政府补贴不同，本次减免无上限，统统 20%。

好家伙，个人转账 5W 减免 1W，那些刚好在那段时间有大额支付的幸运儿，你能想象他们多开心吗 🤣🤣🤣🤣

如此重大的 P0 事故（互联网公司对线上事故的评级，代表事故最高等级），虽然只有短短的 5 分钟，但如果被反应快又别有用心的不法分子利用上（同一笔钱，两个账号来回转），那就可不是一点羊毛的事儿，可能几十上万上百万，整条羊村都被薅走了。

正当所有人都觉得支付宝一定会或多或少有"追回"行动时，凌晨一则来自「支付宝官方微博」的公告说明来了：

简单总结的话：错误在支付宝一方，给出的优惠不会再追回。

好家伙，这属于是给这小部分的幸运儿发"过年费"了 🍋🍋🍋

虽然犯的是如此低级的错误，不像大公司所为，但处理方案又是实打实的"有格局"。搞得我都不好意思笑支付宝"草台班子、降本增笑"了 🤣🤣🤣

从本次的处理方案来看，我们可以做一些合理的猜测：

从这个发布声明的时间点来看，不难猜测，对于这次事故，支付宝经过了「修正模板 -> 统计事故损失金额 -> 事件逐级上报到高层 -> 高层决议最后处理方案 -> 将处理方案下发对应部门 -> 公关拟对外声明 -> 走声明审批流程 -> 正式发出」等多步环节，导致了声明发出的时间已经接近凌晨一点。

由于声明中涉及「提醒大家不要点击诈骗短信/链接」，因此必然不存在支付宝故意推迟声明时间的可能性，他们从事故到发声明，确实就是花了 10+ 小时。

另外，关于支付宝损失金额的猜测。

如果简单结合数据来看，这个数字会很大。

根据易观分析报告的公开数据，支付宝 2024 年第一季度的交易量为 118.19 万亿元，即每个月 39.4 万亿，折合每天约 1.31 万亿，每小时约 0.0546 万亿，每分钟约 9.1 亿。

事故维持 5 分钟，减免力度为 20%，就当全部订单都是不符合"政府补贴"要求的支付订单，那么损失金额约 $9.1 \times 5 \times 0.2 = 9.1$ 亿。

但实际情况并不会如此直接了当，支付订单的流量也不可能是均摊每天，甚至是每分钟。

从日期来说，1-16 是一个没有节日加成的普通周四；从时间点来说，14:40~14:45 虽然属于"白天"范畴，但也不是什么支付高峰期。

我问了在支付宝工作的朋友，他跟我分享道：一整周里的交易，会有接近一半的交易流水，会在周末假期产生；而如果是周内的工作日的话，会有 8 成的流水会在上班时间（09:00~18:00）以外的时间段产生。

基于此，虽然没有具体数字，同时事故维持时间段（5 分钟），不考虑传播效应导致的交易激增。可以合理推算 2025-01-16 14:40~14:45 产生的交易最多不会超过 20 亿，即亏损最多不会超过 4 亿。相比于简单线性均摊的 9.1 亿，还是要小不少的。

支付宝（蚂蚁金服）是一家全年净利润 238.2 亿的公司，4 个亿的事故，还是支付得起的，只不过导致事故发生的员工和部门，估计要面临大处罚了。

对此，你怎么看？昨天有薅到支付宝的羊毛吗？欢迎评论区交流。

...

回归主题。

来一道和「阿里（校招）」相关的算法题。

题目描述

平台：LeetCode

题号：406

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 $people[i] = [h_i, k_i]$ 表示第 $i$ 个人的身高为 $h_i$ ，前面正好有 $k_i$ 个身高大于或等于 $h_i$ 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 $queue[j] = [h_j, k_j]$ 是队列中第 $j$ 个人的属性（ $q u e u e [0]$ 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]


输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]


解释：

编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。

编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。

编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。

编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。

编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。

编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。

因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]


输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

$1 <= p eo pl e . l e n g t h <= 2000$
$0 <= h_i <= 10^6$
$0 <= k_i < people.length$
题目数据确保队列可以被重建

构造 + 二分 + 树状数组

这是一道非常综合的题目。

首先根据双关键字排序：当「高度（第一维）」不同，根据高度排升序，对于高度相同的情况，则根据「编号（第二维）」排降序。

采取这样的排序规则的好处在于：在从前往后处理某个 $p eo pl e [i]$ 时，我们可以直接将其放置在「当前空位序列（从左往后统计的，不算已被放置的位置）」中的 $p eo pl e [i] [1] + 1$ 位（预留了前面的 $p eo pl e [i] [1]$ 个位置给后面的数）。

关于「空位序列」如图所示（黄色代表已被占用，白色代表尚未占用）：

具体的，我们按照构造的合理性来解释双关键字排序的合理性，假设当前处理的是 $p eo pl e [i]$ ：

根据「高度」排升序，根据「编号」排降序：由于首先是根据「高度」排升序，因此当 $p eo pl e [i]$ 被放置在「当前空位序列」的第 $p eo pl e [i] [1] + 1$ 之后，无论后面的 $p eo pl e [j]$ 如何放置，都不会影响 $p eo pl e [i]$ 的合法性：后面的数的高度都不低于 $p eo pl e [i] [0]$ ，无论放在 $p eo pl e [i] [1] + 1$ 前面还是后面都不会影响 $p eo pl e [i]$ 的合法性。

同时对于高度（第一维）相同，编号（第二维）不同的情况，我们进行了「降序」处理，因此「每次将 $p eo pl e [i]$ 放置在空白序列的 $p eo pl e [i] [1] + 1$ 位置的」的逻辑能够沿用：

对于「高度」相同「编号」不同的情况，会被按照「从右到左」依次放置，导致了每个 $p eo pl e [i]$ 被放置时，都不会受到「高度」相同的其他 $p eo pl e [j]$ 所影响。换句话说，当 $p eo pl e [i]$ 放置时，其左边必然不存在其他高度为 $p eo pl e [i] [0]$ 的成员。

剩下的在于，如何快速找到「空白序列中的第 $k$ 个位置」，这可以通过「二分 + 树状数组」来做：

对于已被使用的位置标记为 $1$ ，未使用的位置为 $0$ ，那么第一个满足「 $0$ 的个数大于等于 $k + 1$ 」的位置即是目标位置，在长度明确的情况下，求 $0$ 的个数和求 $1$ 的个数等同，对于位置 $x$ 而言（下标从 $1$ 开始，总个数为 $x$ ），如果在 $[1, x]$ 范围内有 $k + 1$ 个 $0$ ，等价于有 $x - (k + 1)$ 个 $1$ 。

求解 $[1, x]$ 范围内 $1$ 的个数等价于求前缀和，即「区间查询」，同时我们每次使用一个新的位置后，需要对其进行标记，涉及「单点修改」，因此使用「树状数组」进行求解。

Java 代码：

class Solution {
int n;
int[] tr;
int lowbit(int x) {
return x & -x;

    }
void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;

    }
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;

    }
public int[][] reconstructQueue(int[][] ps) {

        Arrays.sort(ps, (a, b)->{
return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];

        });

        n = ps.length;

        tr = new int[n + 1];
int[][] ans = new int[n][2];
for (int[] p : ps) {
int h = p[0], k = p[1];
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (mid - query(mid) >= k + 1) r = mid;
else l = mid + 1;

            }

            ans[r - 1] = p;

            add(r, 1);

        }
return ans;

    }

}

C++ 代码：

class Solution {
public:
int n;

    vector<int> tr;
int lowbit(int x) {
return x & -x;

    }
void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;

    }
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;

    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& ps) {
sort(ps.begin(), ps.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] != b[0] ? a[0] < b[0] : b[1] < a[1];

        });

        n = ps.size();

        tr.resize(n + 1, 0);

        vector<vector<int>> ans(n, vector<int>(2));
for (auto& p : ps) {
int h = p[0], k = p[1];
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (mid - query(mid) >= k + 1) r = mid;
else l = mid + 1;

            }

            ans[r - 1] = p;
add(r, 1);

        }
return ans;

    }  

};

Python 代码：

class Solution:
def __init__(self):

        self.n = 0

        self.tr = []

def lowbit(self, x):
return x & -x

def add(self, x, v):
while x <= self.n:

            self.tr[x] += v

            x += self.lowbit(x)

def query(self, x):

        ans = 0
while x > 0:

            ans += self.tr[x]

            x -= self.lowbit(x)
return ans

def reconstructQueue(self, ps: List[List[int]]) -> List[List[int]]:

        ps.sort(key=lambda x: (x[0], -x[1]))

        self.n = len(ps)

        self.tr = [0] * (self.n + 1)

        ans = [[0, 0] for _ in range(self.n)]
for p in ps:

            h, k = p

            l, r = 1, self.n
while l < r:

                mid = l + r >> 1
if mid - self.query(mid) >= k + 1:

                    r = mid
else:

                    l = mid + 1

            ans[r - 1] = p

            self.add(r, 1)
return ans

TypeScript 代码：

let n: number;
let tr: number[];
function lowbit(x: number): number {
return x & -x;

}
function add(x: number, v: number): void {
for (let i = x; i <= n; i += lowbit(i)) tr[i] += v;

}
function query(x: number): number {
let ans = 0;
for (let i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;

}
function reconstructQueue(ps: number[][]): number[][] {

    ps.sort(((a, b) => {
return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];

    }));

    n = ps.length;

    tr = new Array(n + 1).fill(0);
const ans = new Array(n).fill([0, 0]);
for (const p of ps) {
const [h, k] = p;
let l = 1, r = n;
while (l < r) {
const mid = l + r >> 1;
if (mid - query(mid) >= k + 1) r = mid;
else l = mid + 1;

        }

        ans[r - 1] = p;
add(r, 1);

    }
return ans;

};

时间复杂度：排序的复杂度为 $O(n\log{n})$ ；共要处理 $n$ 个 $p eo pl e [i]$ ，每次处理需要二分，复杂度为 $O(\log{n})$ ；每次二分和找到答案后需要操作树状数组，复杂度为 $O(\log{n})$ 。整体复杂度为 $\times \log{n} \times \log{n})$
空间复杂度： $O (n)$

作者：宫水三叶的刷题日记
来源：juejin.cn/post/7460696845434961920

0

2025-01-26

0 个评论

要回复文章请先登录或注册

从支付宝P0事故处理方案，合理推测损失金额

支付宝

题目描述

构造 + 二分 + 树状数组

0 个评论

发起人