一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1049|回复: 5
收起左侧

LiveRamp OA 新题

[复制链接] |试试Instant~ |关注本帖
trumpet1987 发表于 2016-10-17 10:30:28 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 实习@LiveRamp - 网上海投 - 在线笔试 |Passfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
跟最近一个贴一样的新题:
LiveRamp 实习OA出新题了. Waral 鍗氬鏈夋洿澶氭枃绔,
http://www.1point3acres.com/bbs/ ... &fromuid=223635
(出处: 一亩三分地论坛)


Task 1. 输入是4个数字,返回可能生成的最大时间. 范围应该是 00:00 到 23:59。不要求复杂度,要求解的正确性。
Task 2. N个学生排队,给定每个学生i的身高h: Height = h。允许调换一组相邻学生的次序使最终的队伍按照身高递增排列, 求这一组相邻学生至少有多少个。比如[1,2,3,8,7,6,12],需要重排的是[8,7,6],最后变成[1,2,3,6,7,8,12],因此输出是3。要求时间复杂度O(N*LogN),空间复杂度好像是O(N)。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Task 3. 给一个不懂算法的人解释Task 2. Why LiveRamp.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

思路:
1. 硬做就行。分类讨论每个位置上的范围。
2. 好像做的不太对但是莫名其妙给过了。现在想想既然是NLogN, 可以先排序,然后two pointers跟原来的序列比一下就行。


doufu 发表于 2016-10-22 10:00:16 | 显示全部楼层
楼主你好。
对于Task2, 如果先排序的话,是要自己写排序吗,还是说可以直接调用相关的函数就可以了,比如leetcode里可以直接调用algorithm里的排序,不知道codility里面允许这样吗。
回复 支持 反对

使用道具 举报

 楼主| trumpet1987 发表于 2016-10-22 12:48:26 | 显示全部楼层
doufu 发表于 2016-10-22 10:00. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主你好。. visit 1point3acres.com for more.
对于Task2, 如果先排序的话,是要自己写排序吗,还是说可以直接调用相关的函数就可以了,比如 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
你说的algorithm指的是STL? 我用python写的。你可以注册一个codility的账号找个题试试各种API。我觉得常规的API应该没啥问题...
回复 支持 反对

使用道具 举报

likeawind 发表于 2016-10-22 13:53:24 | 显示全部楼层
我也碰到一样的题了。。。第二题我没用排序,用了两个数列。时间复杂度O(N), 空间复杂度也是O(N). 话说他们实习和全职居然一样的题目。。。

补充内容 (2016-10-22 13:53):
好吧,原来楼主也是实习。。
回复 支持 反对

使用道具 举报

 楼主| trumpet1987 发表于 2016-10-22 14:17:16 | 显示全部楼层
likeawind 发表于 2016-10-22 13:53
我也碰到一样的题了。。。第二题我没用排序,用了两个数列。时间复杂度O(N), 空间复杂度也是O(N). 话说他们 ...

用两个数列是啥思路
回复 支持 反对

使用道具 举报

likeawind 发表于 2016-10-22 14:21:19 | 显示全部楼层
就是一个数列记录从0-i的最大值,然后从后往前遍历这个数列,第一个不等于A的就是最右边的out of order的。第二个数列记录的是从i-N的最小值,然后从前往后遍历这个数列,第一个不等于A的就是最左边的out of order的。这两个index一减就是答案

补充内容 (2016-10-22 14:22):
当时是看到要nlogn,然后quick sort又是n^2. 自己又不想写merge。就想了这个做法

补充内容 (2016-10-22 14:22):
A\[i\]..还要转义吗。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 04:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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