题目背景
原题:
Stripe 在巴西需将客户的交易数据以每日聚合的方式提交给银行,这些记录被称为 Receivables,由以下三个关键字段标识:
- merchant_id: 表示商户在 Stripe 平台的唯一 ID。
- card_type: 表示交易使用的银行卡类型(例如 Visa)。
- payout_date: 表示 Stripe 可以向商户提供资金的日期。
每笔交易可被表示为如下对象:
Transaction {
string customer_id,
string merchant_id,
string payout_date,
string card_type,
int amount
}
实现一个 register_receivables
函数,该函数接收一个 CSV 格式的字符串作为输入,每行代表一笔交易。目标是对这些交易进行聚合,按商户 ID、卡类型、出账日期分组,输出每日的聚合交易总金额。
输入和输出的具体要求如下:
- 输入的第一行是标题行,可以直接忽略。
- 输出的第一行也是标题行:
id,card_type,payout_date,amount
。 - 输出不要求特定的排序顺序。
输入输出示例
示例输入 1
customer_id,merchant_id,payout_date,card_type,amount
cust1,merchantA,2021-12-30,Visa,150
cust2,merchantA,2021-12-30,Visa,200
cust3,merchantB,2021-12-31,MasterCard,300
cust4,merchantA,2021-12-30,Visa,50
输出:
id,card_type,payout_date,amount
merchantA,Visa,2021-12-30,400
merchantB,MasterCard,2021-12-31,300
示例输入 2
customer_id,merchant_id,payout_date,card_type,amount
cust1,merchantA,2021-12-29,MasterCard,50
cust2,merchantA,2021-12-29,Visa,150
cust3,merchantB,2021-12-31,Visa,300
cust4,merchantB,2021-12-29,MasterCard,200
输出:
id,card_type,payout_date,amount
merchantA,MasterCard,2021-12-29,50
merchantA,Visa,2021-12-29,150
merchantB,Visa,2021-12-31,300
merchantB,MasterCard,2021-12-29,200
解题思路
初步设计
为解决此问题,我的设计思路如下:
- 解析输入数据:
使用标准的 CSV 库读取数据,跳过标题行。将每行解析为交易对象,存入内存方便后续处理。 - 数据分组与聚合:
- 使用一个字典,键为
(merchant_id, card_type, payout_date)
的三元组,值为交易金额的累加值。 - 遍历交易记录,更新字典中的金额累加值。
- 使用一个字典,键为
- 格式化输出:
- 将字典中的数据提取并格式化为 CSV 输出格式。
- 添加标题行,输出结果即可。
数据结构选择
- 字典:
适合作为存储分组数据的容器,以(merchant_id, card_type, payout_date)
为键,可以快速查找和更新金额。 - CSV 解析:
使用标准的 CSV 库进行数据读取和写入,保证代码简洁且易于维护。
具体实现步骤
- 解析输入数据:
- 使用 Python 的
csv.reader
逐行读取输入数据。 - 跳过标题行,将后续行解析为交易对象。
- 使用 Python 的
- 分组与聚合:
- 遍历每一行交易数据,提取
merchant_id
、card_type
和payout_date
。 - 检查是否已存在于字典中,若存在则更新金额;否则初始化为当前交易金额。
- 遍历每一行交易数据,提取
- 生成输出:
- 使用
csv.writer
格式化输出数据。 - 输出时按照
id,card_type,payout_date,amount
的顺序构造每一行。
- 使用
示例干跑(Dry Run)
以示例输入 1 为例:
输入:
customer_id,merchant_id,payout_date,card_type,amount
cust1,merchantA,2021-12-30,Visa,150
cust2,merchantA,2021-12-30,Visa,200
cust3,merchantB,2021-12-31,MasterCard,300
cust4,merchantA,2021-12-30,Visa,50
步骤 1:解析数据
读取后存储为:
[{"merchant_id": "merchantA", "card_type": "Visa", "payout_date": "2021-12-30", "amount": 150},
{"merchant_id": "merchantA", "card_type": "Visa", "payout_date": "2021-12-30", "amount": 200},
{"merchant_id": "merchantB", "card_type": "MasterCard", "payout_date": "2021-12-31", "amount": 300},
{"merchant_id": "merchantA", "card_type": "Visa", "payout_date": "2021-12-30", "amount": 50}]
步骤 2:分组与聚合
创建字典并逐步更新:
- 初始状态:
{}
- 第一条交易:
{("merchantA", "Visa", "2021-12-30"): 150}
- 第二条交易:
{("merchantA", "Visa", "2021-12-30"): 350}
- 第三条交易:
{("merchantA", "Visa", "2021-12-30"): 350, ("merchantB", "MasterCard", "2021-12-31"): 300}
- 第四条交易:
{("merchantA", "Visa", "2021-12-30"): 400, ("merchantB", "MasterCard", "2021-12-31"): 300}
步骤 3:格式化输出
生成的 CSV 格式数据为:
id,card_type,payout_date,amount
merchantA,Visa,2021-12-30,400
merchantB,MasterCard,2021-12-31,300
时间和空间复杂度分析
- 时间复杂度:
- 解析 CSV 数据的时间复杂度为 O(n),其中 n 是交易记录的数量。
- 分组与聚合的时间复杂度为 O(n)。
- 格式化输出的时间复杂度为 O(k),其中 k 是最终输出的聚合组数量。
- 总时间复杂度为 O(n + k)。
- 空间复杂度:
- 存储交易记录的字典占用 O(k) 的空间,其中 k 是聚合组的数量。
- 输入数据存储所需的空间为 O(n)。
- 总空间复杂度为 O(n + k)。
Thanks to the rigorous preparation provided by CSOAHelp's Interview Coaching and VO Support, the candidate excelled in this challenging interview. They confidently tackled each question, earning the interviewer’s praise and securing a solid opportunity for their future career. For aspiring candidates, this demonstrates the value of structured preparation and expert guidance.
经过csoahelp的面试辅助,候选人获取了良好的面试表现。如果您需要面试辅助或面试代面服务,帮助您进入梦想中的大厂,请随时联系我。
If you need more interview support or interview proxy practice, feel free to contact us. We offer comprehensive interview support services to help you successfully land a job at your dream company.