查看: 741|回复: 3
收起左侧

亚麻SDE OA

|只看干货
匿名用户-741  发表于 2022-1-29 11:29:26 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2022(1-3月) 码农类General 硕士 全职@Amazon - 内推 - 在线笔试  | 😃 Positive 😐 AveragePass | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
亚麻内推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))。

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

评分

参与人数 1大米 +9 收起 理由
清道神君 + 9

查看全部评分


上一篇:亚麻 SDE3 全套
下一篇:小马店面挂经
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
第二题感觉就sort一个array,然后遍历第二个array,再针对每个第二array的元素二分比较好,这样是O(n log n + m log n)
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
菜鸡水平想问一下区分prime和nonprime是需要挨个字母遍历string吗 (java 。。我好蠢。。。
回复

使用道具 举报

地里的匿名用户
匿名用户-741  发表于 2022-2-1 03:57:33
本楼: 👍   0% (0)
 
 
0% (0)   👎
小亩_ef1e39e 发表于 2022-1-29 08:31
菜鸡水平想问一下区分prime和nonprime是需要挨个字母遍历string吗 (java 。。我好蠢。。。

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表