一亩三分地论坛

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

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

Coursera Summer Intern OA 题目

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

2017(7-9月) 码农类 本科 实习@Coursera - 网上海投 - 在线笔试 |Other其他

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

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

x
第一次发帖,如果有什么不合适的地方欢迎大家指点。

前不久申请的Coursera, 今天有一点时间来做了一下OA。
总体来说难度适中,限制时间90分钟,我用了一小时左右。第一次OA,有点紧张。。

两道选择一个问二分的时间复杂度,另一个问时间复杂度为O(1)的操作是哪些。

第一道编程题比较简单:
    给一个binary array, 假设叫A吧。定义一个move:对A, 可以swap(A, A[i-1])或者swap(A, A[i+1])
    问题是最少需要多少次move,使得A中所有0在一端,1在另一端
. 鍥磋鎴戜滑@1point 3 acres
第二道题难一些:
    给一个integer array A和一个integer K。求元素和小于等于K的subarray的最大长度。
    举个栗子:
        A = [3, 1, 2, 1], K = 4-google 1point3acres
        元素和小于K的subarray有:[3], [3, 1], [1], [1, 2], [1, 2, 1]...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.         其中长度最长的是[1, 2, 1]
        所以返回其长度, 3。.1point3acres缃

.鐣欏璁哄潧-涓浜-涓夊垎鍦



补充内容 (2016-10-9 04:28):
btw,第一题我用的是时间复杂度为O(n)的算法。第二题用的是DP,时间复杂度应该也是O(n)。不知道有没有什么更好的算法~

评分

2

查看全部评分

vlpckznet 发表于 2016-10-20 06:47:48 | 显示全部楼层
想问下第一题具体的解法是什么?多谢
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-10-24 01:31:43 | 显示全部楼层
请问楼主 swap(A, A[i-1]) 是swap(A[i], A[i-1])的意思吗?
由于看你说的 没有指定0要在左边还是右边  所以是两种情况都得考虑吗? 而且你说的O(n)  为啥我觉得不可能O(n)  举个栗子  01010101  你怎么在O(N)的时间内吧0全移左,或者把1全移右..不可能吧  
回复 支持 反对

使用道具 举报

karajan 发表于 2016-10-28 00:42:49 | 显示全部楼层
做完有回应吗?
回复 支持 反对

使用道具 举报

 楼主| cornmonster 发表于 2016-10-28 02:38:34 | 显示全部楼层

过了很久才有回应的,拒了
回复 支持 反对

使用道具 举报

 楼主| cornmonster 发表于 2016-10-28 02:39:16 | 显示全部楼层
格格笑 发表于 2016-10-24 01:31
请问楼主 swap(A, A) 是swap(A, A)的意思吗?
由于看你说的 没有指定0要在左边还是右边  所以是两种情况都 ...

题目是问你最少多少次move呀
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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