一亩三分地论坛

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

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

pocket gems三面跪经

[复制链接] |试试Instant~ |关注本帖
luckyg 发表于 2016-4-8 07:01:44 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 本科 全职@PoketGem - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
悲伤的第三轮电面,烙印面的一句提示没有。希望能帮助以后的同学吧,这题从来没见过,哎
Given an array of integers between 1 and 25,000, describe an algorithm to print each integer which occurs more than once.
先用hashset做的,谁都会。
然后用swap或者xor都没做出来,
哎,三面真是苦
大米,求大神


补充内容 (2016-4-8 07:03):
说最多用4kbytes,妈的,烙印说话也真是听不懂,我让他给我写一下,都他妈不行。真是sb

评分

1

查看全部评分

diyutianshi 发表于 2016-4-8 09:12:29 | 显示全部楼层
luckyg 发表于 2016-4-8 08:50
ohoh,我研究研究,不知道啥是bitmap

其实就是个hash,不过hash是用一个bit记录的

比如说
for (int i = 0; i < A.size(); i++) hash[A / 32] |= 1 << (A % 32);
回复 支持 2 反对 0

使用道具 举报

Chi2829 发表于 2016-4-8 07:14:40 | 显示全部楼层
in place sort一下然后遍历一遍不就可以么?
回复 支持 反对

使用道具 举报

 楼主| luckyg 发表于 2016-4-8 07:28:41 | 显示全部楼层
Chi2829 发表于 2016-4-8 07:14
in place sort一下然后遍历一遍不就可以么?

O(n) time
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-4-8 07:40:29 | 显示全部楼层

。。。这个有点狠啊。。。

最多4kbytes是除结果以外的空间吧?能想到的笨方法是对每1000的值区间做类似sort color那种处理,然后用这额外的区间做count sort。如果intergers的值域结果也算O(n)吧?
回复 支持 反对

使用道具 举报

daiziyeye 发表于 2016-4-8 08:38:09 | 显示全部楼层
Chi2829 发表于 2016-4-8 07:14
in place sort一下然后遍历一遍不就可以么?

没听懂… 大神可以举个例子说下吗…
回复 支持 反对

使用道具 举报

diyutianshi 发表于 2016-4-8 08:42:24 | 显示全部楼层
把25K每个压缩到bit就可以了,也就是说开一个4K byte的bitmap。
回复 支持 反对

使用道具 举报

 楼主| luckyg 发表于 2016-4-8 08:50:26 | 显示全部楼层
diyutianshi 发表于 2016-4-8 08:42
把25K每个压缩到bit就可以了,也就是说开一个4K byte的bitmap。

ohoh,我研究研究,不知道啥是bitmap
回复 支持 反对

使用道具 举报

 楼主| luckyg 发表于 2016-4-8 08:51:17 | 显示全部楼层
Chi2829 发表于 2016-4-8 07:40
。。。这个有点狠啊。。。
. visit 1point3acres.com for more.
最多4kbytes是除结果以外的空间吧?能想到的笨方法是对每1000的值区间做类 ...

sortcolor好像不行吧,你不知道一共多少个integer比如[25000]
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-4-8 09:32:00 | 显示全部楼层
luckyg 发表于 2016-4-8 08:51
sortcolor好像不行吧,你不知道一共多少个integer比如[25000]

没表达清楚。我的意思就是第一次便利就找值在1-1000中的重复的数,第二次找1000-2000的,。。。一共25次。但是太笨拙了:(,用@diyutianshi 说的bitmap是正解。
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-5-1 09:05:43 | 显示全部楼层
请问数组有多少元素啊?
回复 支持 反对

使用道具 举报

treebug 发表于 2016-5-2 14:24:12 | 显示全部楼层
最多4kbytes的话,建立一个bytes array 长度为4000. From 1point 3acres bbs
然后把每个数字 / 8 看它在array哪个byte里面
然后把数字 % 8 看它在byte的哪个bits里面
然后用1左移动记住他的位置,如果未来有数字和这个&不是0的话,说明有重复,print出来~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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