Citadel Campus Software Engineering OA (2020-2021)

标题是： Citadel and Citadel Securities Campus Software Engineering Challenge (2020-2021)

海

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

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

的序列的个数
同 LC Consecutive Numbers Sum

ALEXJI19991007 发表于 2020-8-3 17:13
第一题我写的答案，我网上看到的test case都过了至少……
[mw_shl_code=bash,true]public class Throttlin ...

Gateway用python直接记录每个时间点的request会有memory问题，4个test跑不过。下面这个test-case至少都过了。 觉得有用的话求加米啊！

def droppedRequests(requestTime):
    # Write your code here
    if not requestTime:
        return 0
    alldrop = 0
    reqmap = dict()
    for r in requestTime:
        reqmap[r] = reqmap.get(r, 0)+1
    # print(reqmap)
    reqpair = [(0,0)]+sorted([x for x in reqmap.items()])
    for i in range(1,len(reqpair)):
        time, cnt = reqpair[i]
        reqpair[i] = (time, reqpair[i-1][1] + cnt)
        drop = 0
        if cnt > 3:
            drop = max(drop, cnt - 3)
        j = i
        while j > 0 and time - reqpair[j][0] < 10:
            j -= 1
        if reqpair[i][1]-reqpair[j][1] > 20:
            exceed = min(cnt, reqpair[i][1]-reqpair[j][1] - 20)
            drop = max(drop, exceed)
        k = i
        while k > 0 and time - reqpair[k][0] < 60:
            k -= 1
        if reqpair[i][1]-reqpair[k][1] > 60:
            exceed = min(cnt, reqpair[i][1]-reqpair[k][1] - 60)
            drop = max(drop, exceed)
        alldrop += drop
    # print(reqpair)
    return alldrop

第一题竟然全网没答案，lc上讨论的答案都过不去所以cases，老子自己钢了……天

第一题我写的答案，我网上看到的test case都过了至少……

1. public class ThrottlingGateway {
   
2.     public static final int MAX_PER_SECOND = 3;
   
3.     public static final int MAX_TEN_SECONDS = 20;
   
4.     public static final int MAX_PER_MINUTE = 60;
   
5. 
   
6.     public static void main(String[] args) {
   
7.         int[] requestTime1 = new int[]{1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 11, 11, 11, 6, 6, 6, 5, 5, 5};
   
8.         int[] requestTime2 = new int[]{1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 11, 11, 11, 11};
   
9.         int[] requestTime3 = new int[]{1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9,
   
10.                 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 14, 16, 16, 16, 16, 16,
    
11.                 16, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20};
    
12.         ThrottlingGateway test = new ThrottlingGateway();
    
13.         System.out.println(test.droppedRequests(requestTime1));
    
14.     }
    
15. 
    
16.     public int droppedRequests(int[] requestTime) {
    
17.         if (requestTime == null || requestTime.length == 0) {
    
18.             return 0;
    
19.         }
    
20.         int drop = 0;
    
21.         Map<Integer, Integer> map = new HashMap<>();
    
22.         int lastReqTime = 0;
    
23.         for (int i : requestTime) {
    
24.             map.put(i, map.getOrDefault(i, 0) + 1);
    
25.             lastReqTime = Math.max(lastReqTime, i);
    
26.         }
    
27.         int[] nums = new int[lastReqTime + 1];
    
28.         for (int i = 1; i < nums.length; ++i) {
    
29.             int numReqThisSecond = map.getOrDefault(i, 0);
    
30.             nums[i] = nums[i - 1] + numReqThisSecond;
    
31.             if (numReqThisSecond == 0) {
    
32.                 continue;
    
33.             }
    
34.             int toDrop = 0;
    
35.             if (numReqThisSecond > MAX_PER_SECOND) {
    
36.                 toDrop = Math.max(toDrop, numReqThisSecond - MAX_PER_SECOND);
    
37.             }
    
38. 
    
39.             int timeTenSecondsAgo = Math.max(i - 10, 0);
    
40.             int numReqPastTenSecond = nums[i] - nums[timeTenSecondsAgo];
    
41.             if (numReqPastTenSecond > MAX_TEN_SECONDS) {
    
42.                 int numReqExceeded = Math.min(numReqThisSecond, numReqPastTenSecond - MAX_TEN_SECONDS);
    
43.                 toDrop = Math.max(toDrop, numReqExceeded);
    
44.             }
    
45. 
    
46.             int timeOneMinuteAgo = Math.max(i - 60, 0);
    
47.             int numReqPastMinute = nums[i] - nums[timeOneMinuteAgo];
    
48.             if (numReqPastMinute > MAX_PER_MINUTE) {
    
49.                 int numReqExceeded = Math.min(numReqThisSecond, numReqPastMinute - MAX_PER_MINUTE);
    
50.                 toDrop = Math.max(toDrop, numReqExceeded);
    
51.             }
    
52.             drop += toDrop;
    
53.         }
    
54.         return drop;
    
55.     }
    
56. }
    

复制代码

小堆堆 发表于 2020-7-31 06:34
第一题竟然全网没答案，lc上讨论的答案都过不去所以cases，老子自己钢了……天

老哥能看一下我下面写的能过test cases不 感恩

ALEXJI19991007 发表于 2020-08-03 02:14:37
老哥能看一下我下面写的能过test cases不 感恩

这种短的好过应该没问题，oa当时有十万级别的长度的case

小堆堆 发表于 2020-08-03 07:56:11
这种短的好过应该没问题，oa当时有十万级别的长度的case

wtf……

666666666666666

bzybc1405 发表于 2020-8-10 13:55
Gateway用python直接记录每个时间点的request会有memory问题，4个test跑不过。下面这个test-case至少都过 ...

很多bugs呀

有人知道矩阵的是什么题么？差9个积分看不到。。。