亜麻OA

题一Bag of Rices, 需用二分搜索否则很多case会超时
题二像是新题

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

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

在这里提供一个第二题解法，但是直觉告诉我可能不是最优的，因为搜索范围是[-10^9, 10^9]，数组长度最大在10^5，感觉这个数量级走两遍binary search还是很容易TLE。抛砖引玉，看看有没有更好的解法

1. 
   
2. public class Main {
   
3.     public static void main(String[] args) {
   
4.         List<Integer> center = new ArrayList<>();
   
5.         center.add(-2);
   
6.         center.add(1);
   
7.         center.add(0);
   
8.         long d = 8;
   
9.         
   
10.         System.out.println(numberOfSuitableLocations(center, d));
    
11.     }
    
12.    
    
13.     public static int numberOfSuitableLocations(List<Integer> center, long d) {
    
14.         int n = center.size();
    
15.         d /= 2;
    
16.         
    
17.         Collections.sort(center);
    
18.         
    
19.         long minDistance = 0L;
    
20.         for(int i = 0; i < n / 2; i++) {
    
21.             minDistance += center.get(n - 1 - i) - center.get(i);
    
22.         }
    
23.         if(minDistance > d)
    
24.             return 0;
    
25.         
    
26.         int left = searchLeft(center, -1_000_000_000, center.get(n / 2), d);
    
27.         int right = searchRight(center, center.get(n / 2), 1_000_000_000, d);
    
28.         
    
29.         return right - left + 1;
    
30.     }
    
31.    
    
32.     private static int searchLeft(List<Integer> center, int start, int end, long d) {
    
33.         while(start < end) {
    
34.             int mid = start + (end - start) / 2;
    
35.             if(canFulfill(center, mid, d)) {
    
36.                 end = mid;
    
37.             } else {
    
38.                 start = mid + 1;
    
39.             }
    
40.         }
    
41.         return start;
    
42.     }
    
43.    
    
44.     private static int searchRight(List<Integer> center, int start, int end, long d) {
    
45.         while(start < end) {
    
46.             int mid = start + (end - start + 1) / 2;
    
47.             if(canFulfill(center, mid, d)) {
    
48.                 start = mid;
    
49.             } else {
    
50.                 end = mid - 1;
    
51.             }
    
52.         }
    
53.         return start;
    
54.     }
    
55.    
    
56.     private static boolean canFulfill(List<Integer> center, int mid, long d) {
    
57.         long distance = 0L;
    
58.         for(int c: center) {
    
59.             distance += (long)Math.abs(mid - c);
    
60.             if(distance > d)
    
61.                 return false;
    
62.         }
    
63.         return true;
    
64.     }
    
65. }
    

复制代码

MichelleX 发表于 2023-8-17 06:38
感谢感谢～～我就是对系统设计这块感觉没底，不知道考的啥

会给你一些场景让你做技术选型，你要给不同选项打分（五分制）

这是亚麻什么职位的啊感谢

匿名用户 发表于 2023-8-1 07:19
这是亚麻什么职位的啊感谢

SDE2紫薯紫薯

匿名用户 发表于 2023-08-01 13:07:35
SDE2紫薯紫薯

sde 2 是不是现在都内部转岗fill 了

请问申的是哪个组

想问第二题brute force不可以么？就从左边-d/2 到右边+d/2走一遍 看哪些点符合 |x-A| + |x-B| + |x-C| ... <= d/2? 如果是二分的话是怎么个分法呀？

求问楼主，你的oa有系统设计吗，谢谢！

MichelleX 发表于 2023-8-16 19:15
求问楼主，你的oa有系统设计吗，谢谢！

有的，包含在work simulation部分，不限时，评价方式不详

匿名用户 发表于 2023-8-17 01:44
有的，包含在work simulation部分，不限时，评价方式不详

感谢感谢～～我就是对系统设计这块感觉没底，不知道考的啥