亞麻 2024 New Grad OA

请问lz 28号面的出结果了吗

levi947tw 发表于 2024-5-30 20:37
看來你也快 VO 了，那我大概描述一下。
一輪 VO 一個小時， 一至二位面試官，但只有一位面試官會負責問你 ...

用倒序pq，这样最大的数永远在最前面，村的时候除了存值也要同时存index。然后按顺序弹出pq，每次判断在数组中这个元素的后两位，如果后一位没被选择作为切点且再后一位不是数组尾端点的话，则标记被弹出的当前元素后一位为切点，然后记录到一个set里。重复整个流程直到pq弹空。祝楼主面试顺利！

第二题我想到一个解法，是先用greedy去找最多的分区，到最后一个分区如果无法满足要求，再将它与前一个分区合并，直到合并成一个满足要求的分区，不知道大家觉得这样可以吗？我自己测试起来还没发现问题，O(n)

1. def max_balanced_shipments_optimized(weights):
   
2.     if weights[-1] == max(weights):
   
3.         return 0
   
4. 
   
5.     n = len(weights)
   
6.     shipments = []
   
7.     left, right = 0, 1
   
8.     while left < n:
   
9.       current_max = weights[left]
   
10.       balanced = False
    
11.       while right < n:
    
12.         current_max = max(current_max, weights[right])
    
13.         if weights[right] < current_max:
    
14.           shipments.append((left, right))
    
15.           left = right + 1
    
16.           right = left + 1
    
17.           balanced = True
    
18.           break
    
19.         right += 1
    
20. 
    
21.       if not balanced:
    
22.         break
    
23. 
    
24.     for i, j in shipments[::-1]:
    
25.       if weights[-1] >= max(weights[i:j]):
    
26.         shipments.remove((i, j))
    
27.       else:
    
28.         break
    
29. 
    
30.     return len(shipments)

复制代码

匿名用户 发表于 2024-5-30 17:35
原题是10^ 5的数据量，所以希望你给出来的解法是nlogn复杂度，一般如果是10 ** 9的数据量的话就暗示只能n ...

学到了 多谢老哥

请问一下楼主或者其他朋友，BQ会考虑你之前经历和岗位的相关性吗？我面的也是楼主这个方向，但是因为转码简历里几乎没有这些东西，到时候BQ是要瞎编一个类似的项目还是就说其他方向的项目就好？

这题一开始我也想monotonic stack，但是感觉不对，就只要碰到有递减的时候就可以了，最后如果连续递增那就返回0

1. public int findMaximumBalancedShipments(int[] weight) {
   
2.         if (weight == null || weight.length < 2) {
   
3.             return 0;
   
4.         }
   
5.         int n = weight.length;
   
6.         int res = 0;
   
7.         boolean isAsending = false;
   
8.         for (int i = 1; i < n; i++) {
   
9.             if (weight[i - 1] > weight[i]) {
   
10.                 res++;
    
11.                 i++;
    
12.                 isAsending = false;
    
13.             }else {
    
14.                 isAsending = true;
    
15.             }
    
16.         }
    
17. 
    
18.         return isAsending ? 0 : res;
    
19.     }
    
20. 
    

复制代码

匿名用户 发表于 2024-6-7 05:03
用倒序pq，这样最大的数永远在最前面，村的时候除了存值也要同时存index。然后按顺序弹出pq，每次判断在 ...

麻烦可以再多解释一下吗？ 有了每一个切点，之后要怎么操作运算呢 🙏

Falldawn 发表于 2024-6-21 04:06
这题一开始我也想monotonic stack，但是感觉不对，就只要碰到有递减的时候就可以了，最后如果连续递增那就 ...

不对，照着这个思路[1,2,3,1,2]输出是0，但其实应该是1

lz 面試用中文還英文？
應該是EERO？