亞麻 2024 New Grad OA

本來想說憑著 LC 500+ 的努力加上幾乎穩定三題的週賽
亞麻 OA 應該是輕輕鬆鬆
結果馬上就被下馬威了
雖然最後是過了
但這次教訓讓我很是刻苦銘心

OA 第一題：prefix sum and postfix sum
OA 第二題：dfs or monostack (find the previous greater)

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

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

[結語]

遇到任何問題
都要好好思考再下手

我當時第二題直接 monostack next greater + 暴力分支判斷
覺得題目不會太難應該可以無腦簡單過
結果花了很多時間做了不必要的處理

其實工作上遇到任何事情都一樣
這種細節決定了一位工程師的效率
好的思考習慣讓我們事半功倍！

匿名用户 发表于 2024-5-30 16:57
第二题是不是有O(n)的解法啊
先从前往后算0:i的最大值。然后从后往前，开始找划分点。对于i，只要arr比最 ...

原题是10^ 5的数据量，所以希望你给出来的解法是nlogn复杂度，一般如果是10 ** 9的数据量的话就暗示只能n的复杂度，算是一个偷鸡小窍门

第二题我想到一个解法，是先用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)

复制代码

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

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

赞楼主的思考和感悟

可以问问楼主是在职跳槽吗？工作时间小于一年？

匿名用户 发表于 2024-5-30 07:42
可以问问楼主是在职跳槽吗？工作时间小于一年？

是的，我是在職跳槽
不過我的現職工作時間約一年又三個月

lz当时选毕业时间/工作时间的时候选的是毕业超过一年吗

匿名用户 发表于 2024-05-30 05:55:53
lz当时选毕业时间/工作时间的时候选的是毕业超过一年吗

是的 畢竟已經先去其他公司工作了 會希望先待滿一年再跳

感谢分享！我做德国亚麻oa的时候也是遇到第二题，用优先列+贪心可以过。另请问楼主两轮vo的形式大概是怎么样呢，bq和做题的比重多大呢？感谢！

第二题是不是有O(n)的解法啊
先从前往后算0:i的最大值。然后从后往前，开始找划分点。对于i，只要arr[i]比最后的值大，同时arr[i-1]不是0:i-1的最大值，i就可以作为一个划分点。

levi947tw 发表于 2024-5-30 17:54
是的 畢竟已經先去其他公司工作了 會希望先待滿一年再跳

奥不是这个意思，那个jd上要求是1年以内毕业的人，不过lz这样也能拿到oa，那应该没啥问题