在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 939|回复: 11
收起左侧

[CareerCup] 【第三轮】7.24-7.31 CareerCup 5.2

[复制链接] |试试Instant~ |关注本帖
林微熙 发表于 2014-7-25 06:27:49 | 显示全部楼层 |阅读模式

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

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

x
5.2 Given a real number between 0 and 7 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR."



回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】



Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改
grassgigi 发表于 2014-7-25 12:04:27 | 显示全部楼层
本帖最后由 grassgigi 于 2014-7-25 12:06 编辑

【解题思路】
Basic decimal representation, keep adding 2^-1,  2^-2... 2^-32 until the result equals to original decimal.

I'm having a hard time to understand what is "accurately" means...does it mean the result should strict equal to the original decimal, or could have some tiny rounding differences?

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/fb3d73fc268b19b122d5
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
jyh橘子 发表于 2014-7-25 12:45:20 | 显示全部楼层
between 0 and 1
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-25 13:09:26 | 显示全部楼层
【解题思路】
check if x >0.5  if yes add 1 and x= x-0.5;   x = x*2 and check again;
【时间复杂度】
O(N)  N is the number of digits in Binary representation
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/jyhjuzi/7c30e0bd0a6b80e6bbef
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-26 04:07:54 | 显示全部楼层

【解题思路】
理解错题了,写了个输出IEEE754标准的,结果也懒得改了,基本思路都在里面,转化2进制,乘2或除2这两种思路都可以
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/Noahsark/8eaba401fdf37ef740c9
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-27 21:00:26 | 显示全部楼层
【解题思路】
keep substracting 0.5^n from the input value


【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/e3e05b8f3937ce114e49



回复 支持 反对

使用道具 举报

bearkino 发表于 2014-7-28 16:39:42 | 显示全部楼层
【解题思路】
not even easy than the solution in the book.
multiply by 2 and check if 2n is greater than or equal to 1.


【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/UncleGarden/6c4e61c377da227fd4ff
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-29 12:07:29 | 显示全部楼层
【解题思路】
multiply by 2 and extract integer fraction
【时间复杂度】
O(1) - no more than 32
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/49aee9c2f58e46b4c38a
回复 支持 反对

使用道具 举报

 楼主| 林微熙 发表于 2014-8-3 06:51:32 | 显示全部楼层
【解题思路】keep substracting 0.5^n from the input value,理解了好久才理解题目。果真智商让人捉急
【时间复杂度】o(n),不超过32位,是不是可以理解为n<32
【空间复杂度】o(1)
【gist link】https://gist.github.com/hilda8519/7aeb3efcbc60786edc6c
回复 支持 反对

使用道具 举报

wangjianze 发表于 2014-8-3 09:32:46 | 显示全部楼层
I wonder that maybe the worst case of accurately representing a number in exactly 32 bits means:
the last digit (let's say X) of this number represented in decimalism must obey--->
assume the number has length N
0.0.....0X * 2^32 ==1
=>
X==(2^-32)*10^N;
from X is between 1~9 we can obtain N <= 9.633 , which means  N<10
Now we can assume all numbers represented in decimalism whose length is more than 11 will be a "ERROR" case, checking the length computation time is less than 12 (1 digit at a time) at the same time we do the transforming from decimalism to bits,less than 12.
Space to save the outcome of every multiplication and to save the final binary representation will be needed.
Time complexity is N(1)
Space complexity is N(1)
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-8-4 05:53:00 | 显示全部楼层
【解题思路】
if number is no less than 0.5, that bit is 1, otherwise 0. Then multiply that remain number with 2 for the next bit.
【时间复杂度】
O(d), d is the number of bits
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/b562f5d2cdb8ba0f8af5
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-8-4 13:02:50 | 显示全部楼层
【解题思路】Recursion, compare the remaining value vs. 2^n till 32 bits
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/bitcpf/525dec151918061e350b
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 13:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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