TwoSigma OA 附思路

原题见图
第一题 股票拍卖
有n份股票，有k个bid，bid里包括userId, price, quantity, timestamp。bid分发要求从价格高的开始，同价格的按照timestamp从小的开始每人发一份，如果股票够多就再发一轮，直到股票发完，或者所有bid都满足。要求返回一份股票都没有领到的userId，按照从小到大排序。

思路
先sort，然后安拍序处理就行了。需要注意的是，这题只要求每个bid最少拿一份股票，所以很简单。

第二题 树状流量切分
给了两个等长的list，一个是parent，一个是size。对于第i个，parent<i>表示父节点的index，size<i>表示净流入的流量大小。一个节点的总流量是自己的净流入量和所有子节点的流量的综合。要求把这个树分成两个树，让两个树的总流量的差值最小。返回最小差值。

思路
数据结构上比较像线段树，所以父节点的index永远小于子节点。我们可以从后往前扫描，1pass得到每个节点的总流量。
对于总流量S，两个树的总流量分别就等于N和S-N，那么最小差值就是求min(abs(S-2N)。2pass就能解决这个问题了

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一题代码

1. 
   
2. funtion (shareSize, bids) {
   
3.     sort(bids)
   
4. 
   
5.     index = 0
   
6.     while(index < len(bids) and shareSize > 0) {
   
7. 
   
8.         int groupSize = 0
   
9.         int groupShare = 0
   
10.         while((index + groupSize) < len(bids)
    
11.             and (bids[index].price == bids[index + groupSize].price)) {
    
12.             groupSize += 1
    
13.             groupShare += bids[index + groupSize].quantity
    
14.         }
    
15. 
    
16.         if(shareSize >= groupSize) {
    
17.             index += groupSize
    
18.         } else {
    
19.             index += shareSize
    
20.         }
    
21.         shareSize -= groupShare;
    
22.     }
    
23. 
    
24. 
    
25.     result = []
    
26.     while(index < len(bids)) {
    
27.         result.push(bids[index].userId)
    
28.         index += 1
    
29.     }
    
30.     return result
    
31. }
    

复制代码

第二题代码

1. funtion (parents, sizes) {
   
2.     sums = []
   
3. 
   
4.     for i in [n-1, 0]:
   
5.         parent = parents[i]
   
6.         size = sizes[i]
   
7. 
   
8.         sums[i] += size
   
9.         sums[parent] += sums[i]
   
10. 
    
11.     totalSum = sums[0]
    
12.     minDiff = totalSum
    
13. 
    
14.     for sum in sums:
    
15.         minDiff = min(minDiff, abs(totalSum - sum - sum))
    
16. 
    
17.     return minDiff
    
18. }
    

复制代码

这个代码看起来是javascrip写的，但是怎么还有int 呢，看不懂。

匿名用户 发表于 2022-10-25 21:08
第一题代码

chat说这个代码有语法错误