亚麻SDE OA

亚麻内推OA   1/28 拿到并做完OA   1/28 拿到Phone Interview

OA的两道题目大致为：

Q1:Given a list of prime and non-prime orders, where each order is a string consist of ID and metadata. Sort the list of orders by:
a. prime orders before non-prime orders
b. prime orders are sorted lexicographically by mtadata, then by ID in case of ties.

d. the relative order of non-prime orders remain as they were

Example input:
[aa1 243 345 456][bbf kindle book][bae echo prime][a1a 123 456 789][b1b kindle book]
Example output:
[bae echo prime][b1b kindle book][bbf kindle book][a1a 123 456 789][aa1 243 345 456]

我的思路是先区分prime和nonprime orde

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

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

大sum，一边增加a的pointer，如果sum超过了target，那就减小b的pointer。一直重复直到任意一个pointer到头。个人感觉这样的好处是best case会比brute force好不少 (O(max(n,m))，但worst case应该是跟brute force一样的 (O(nm))。

纯分享，欢迎大家讨论指正

第二题感觉就sort一个array，然后遍历第二个array，再针对每个第二array的元素二分比较好，这样是O(n log n + m log n)

菜鸡水平想问一下区分prime和nonprime是需要挨个字母遍历string吗 （java 。。我好蠢。。。

小亩_ef1e39e 发表于 2022-1-29 08:31
菜鸡水平想问一下区分prime和nonprime是需要挨个字母遍历string吗 （java 。。我好蠢。。。

不需要的，如果是字母的话整个string就是纯字母，如果是数字的话就是纯数字。所以我认为只用判断第一个字符是字母还是数字即可。