一亩三分地论坛

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

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

coursera OA 可以重复做,什么鬼

[复制链接] |试试Instant~ |关注本帖
谎言之躯 发表于 2016-8-24 08:06:24 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@coursera - 网上海投 - 在线笔试 |Other其他

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

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

x
http://www.1point3acres.com/bbs/thread-199851-1-1.html

http://www.1point3acres.com/bbs/thread-199852-1-1.html

http://www.1point3acres.com/bbs/thread-199644-1-1.html. from: 1point3acres.com/bbs

今天做了coursera的OA,很不幸,遇到了第三个帖子里的那道coding题,然后就有两个case超时了。最后改来改去,在时间结束时没能提交上去。然后我从邮件里的OA链接再次点进去,发现竟然可以重新做,而且题目还变了,第二次遇到的coding题目做得很顺利,虽然不是上面三个帖子的面经题,但是大家暴力解决定可以通过。
我就想知道有人遇到过这情况吗? 我以前做别的公司的hacckerrank OA,提交之后再次点进去,页面就会显示我已经做过了。但这次这个OA,重复点进去还可以重新开始做,而且题目还换了。

评分

1

查看全部评分

Lynnklj 发表于 2016-9-5 03:49:58 | 显示全部楼层
sapphirew 发表于 2016-8-26 11:31.鐣欏璁哄潧-涓浜-涓夊垎鍦
时间复杂度其实可以做到O(n + max(nums[]) - min(nums[])). Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2016-8-26 11:32):

新开的数组里面的元素应该是有序的吧,时间复杂度不应该是O(n*log(新数组的长度))?
回复 支持 1 反对 0

使用道具 举报

sapphirew 发表于 2016-8-24 10:24:28 | 显示全部楼层
求问楼主第二次做的题目,谢啦
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2016-8-24 13:51:32 | 显示全部楼层
sapphirew 发表于 2016-8-24 10:24
求问楼主第二次做的题目,谢啦
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
木有截图。 第二次做的coding题目描述太长了,大概就是,输入一个全部是正数的数组,然后进行循环,在每次循环中,用数组中最小的数去减数组的每一个非0的数,这样就改变了数组中的数,直到数组中所有的数变成0,循环结束。输出就是每次循环里当前数组的非0的数字的个数。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

apple1003232 发表于 2016-8-25 05:56:04 | 显示全部楼层
感谢lz分享
回复 支持 反对

使用道具 举报

sapphirew 发表于 2016-8-25 06:29:32 | 显示全部楼层
谎言之躯 发表于 2016-8-24 13:51
木有截图。 第二次做的coding题目描述太长了,大概就是,输入一个全部是正数的数组,然后进行循环,在每 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢分享~没有想到什么很好的解法,先sort再计算仿佛也没有降低复杂度,话说楼主是brute force做的吗
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2016-8-25 06:30:36 | 显示全部楼层
sapphirew 发表于 2016-8-25 06:29
谢谢分享~没有想到什么很好的解法,先sort再计算仿佛也没有降低复杂度,话说楼主是brute force做的吗

不用排序呀,就是线性扫描数组,算是暴力吧。
回复 支持 反对

使用道具 举报

sxwxcc 发表于 2016-8-25 09:32:58 | 显示全部楼层
我做了三次。。
回复 支持 反对

使用道具 举报

todayand 发表于 2016-8-25 14:14:38 | 显示全部楼层
sapphirew 发表于 2016-8-25 06:29
谢谢分享~没有想到什么很好的解法,先sort再计算仿佛也没有降低复杂度,话说楼主是brute force做的吗
. more info on 1point3acres.com
多开一个数组存每个数的count,然后再过一遍这个数组,每次用总个数减去count,存起来,时间复杂度O(数组size+数的范围)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Tommzy 发表于 2016-8-26 09:13:09 | 显示全部楼层
todayand 发表于 2016-8-25 14:14
多开一个数组存每个数的count,然后再过一遍这个数组,每次用总个数减去count,存起来,时间复杂度O(数组 ...

大神!能否再详细解释下咩?!
回复 支持 反对

使用道具 举报

sapphirew 发表于 2016-8-26 11:29:10 | 显示全部楼层
todayand 发表于 2016-8-25 14:14
多开一个数组存每个数的count,然后再过一遍这个数组,每次用总个数减去count,存起来,时间复杂度O(数组 ...

厉害啊。。这样算非零的个数时就不用考虑具体的数值了,666
回复 支持 反对

使用道具 举报

sapphirew 发表于 2016-8-26 11:31:54 | 显示全部楼层
todayand 发表于 2016-8-25 14:14
多开一个数组存每个数的count,然后再过一遍这个数组,每次用总个数减去count,存起来,时间复杂度O(数组 ...

时间复杂度其实可以做到O(n + max(nums[]) - min(nums[]))-google 1point3acres
.1point3acres缃
补充内容 (2016-8-26 11:32):
哈哈。。其实和你说的一样,看岔了
回复 支持 反对

使用道具 举报

sapphirew 发表于 2016-8-26 11:37:54 | 显示全部楼层
Tommzy 发表于 2016-8-26 09:13.鐣欏璁哄潧-涓浜-涓夊垎鍦
大神!能否再详细解释下咩?!

假设数组是[2,2,1,3,3],这样可以构建一个size为3的array做频数统计,得到一个[1,2,2]的array分别代表1,2,3出现的频数,每次最小的数字(min)减掉自己后变为0,比最小数字大的数减去min依旧还是正数,这样扫一遍这个array就可以得出答案[4,2,0]了
回复 支持 反对

使用道具 举报

 楼主| 谎言之躯 发表于 2016-8-26 12:28:44 | 显示全部楼层
sapphirew 发表于 2016-8-26 11:37
假设数组是[2,2,1,3,3],这样可以构建一个size为3的array做频数统计,得到一个[1,2,2]的array分别代表1,2 ...

就是用哈希表统计各个数出现的频率。在java里,用TreeMap;在C++里,用map;这两个数据结构都是按照key的大小排好序的。map建立好之后,直接遍历map就行,然后在每层循环里减去key所对应的value。
回复 支持 反对

使用道具 举报

todayand 发表于 2016-8-26 14:22:35 | 显示全部楼层
谎言之躯 发表于 2016-8-26 12:28
就是用哈希表统计各个数出现的频率。在java里,用TreeMap;在C++里,用map;这两个数据结构都是按照key的 ...

用binary search tree复杂度变成O(nlogn), 考虑到worst case用数组存更优吧。
回复 支持 反对

使用道具 举报

really121 发表于 2016-9-10 02:37:26 | 显示全部楼层
感谢楼主分享!!!
回复 支持 反对

使用道具 举报

menghuanboluomi 发表于 2016-9-29 23:04:53 | 显示全部楼层
sapphirew 发表于 2016-8-26 11:31
时间复杂度其实可以做到O(n + max(nums[]) - min(nums[])). 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-8-26 11:32):

我觉得还是得排序呀 不然你哪里知道你的hash里哪个value是最小元素的个数~~~~
回复 支持 反对

使用道具 举报

sapphirew 发表于 2016-9-30 09:52:33 | 显示全部楼层
menghuanboluomi 发表于 2016-9-29 23:04
我觉得还是得排序呀 不然你哪里知道你的hash里哪个value是最小元素的个数~~~~

不用hash啊,一个array就行了
回复 支持 反对

使用道具 举报

ymsf 发表于 2016-10-4 14:10:33 | 显示全部楼层
sapphirew 发表于 2016-9-30 09:52
不用hash啊,一个array就行了

不排序你怎么知道array里的某一个元素对应的是那个数字的出现次数?
[9, 2, 9, 3,5,6, 3,2]不排序给出array是?

补充内容 (2016-10-4 14:18):
倒是不用排序,但是可以用一个min-heap存(数字,次数)pair,这样每次pop出的元素一定是最小的数字和它的次数。不过这样时间复杂度跟排序量级上也差不多,入堆的的时候可能要调整顺序。但调整的次数比排序少
回复 支持 反对

使用道具 举报

sapphirew 发表于 2016-10-6 03:03:07 | 显示全部楼层
ymsf 发表于 2016-10-4 14:10
不排序你怎么知道array里的某一个元素对应的是那个数字的出现次数?
[9, 2, 9, 3,5,6, 3,2]不排序给出ar ...

请你仔细看上面的回复,也请你注意说话的语气。你的方法在array非常稀疏时适用。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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