一亩三分地论坛

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

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

推特 OA

[复制链接] |试试Instant~ |关注本帖
hakase 发表于 2014-10-24 02:32:37 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Twitter - 网上海投 - 在线笔试 |Other

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

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

x
Twitter的HR发来邮件,告诉我先做题(OA性质)。题目是在HackerRank上做。
第一题:. visit 1point3acres.com for more.
给定两个数字M,N,代表闭区间[1, M]和[1, N],在两个范围里选两个数字a,b,
其中a属于区间[1, M]
b属于区间[1, N],
这两个数字要满足 "(a^(1/3) + b^(1/3))^3 是一个整数" 这个性质。(立方根相加的立方是个整数). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
求这个范围里有多少组数字满足这个性质?. 鍥磋鎴戜滑@1point 3 acres
  • 比如给定范围1,1,则只有一组数字(1,1)满足性质,应该返回“1”。
  • 给定范围1,8,有两组数字满足性质:(1,1) and (1,8),所以返回2.

楼主这道题给的解法复杂度是O(M * N), 有8个test cases超时,加了一个cache还是超时,我勒个去。(所以跪了). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
各位有什么好解法?

第二题:. more info on 1point3acres.com
给定一个数列,求最长增长子序列长度。(longest increasing subsequence)——这个题目在网上已经被做烂了,自己搜一下吧。
.1point3acres缃
不过值得吐槽的是,楼主code不变,提交两次得到的运行结果不一样(不是超时哦)。
并且我的code是没有状态的(没有静态或者全局的东西)。这种现象遇到了两次,可见hackerRank的OJ做的是多么的不靠谱。



补充内容 (2014-10-28 07:48):
今天告诉我后天要电面,老子已经接了AMZN的offer了,老子不面了!!!哦也

评分

1

查看全部评分

1guangnian 发表于 2014-10-24 04:09:39 | 显示全部楼层
hakase 发表于 2014-10-24 03:40
. Waral 鍗氬鏈夋洿澶氭枃绔,记得是1到10^5
-google 1point3acres
那应该可以,(a^(1/3) + b^(1/3))^3 = a + 3*a^(2/3)*b^(1/3) + 3*a^(1/3)*b^(2/3) + b
所以应该是3*a^(2/3)*b^(1/3)和3*b^(2/3)*a^(1/3)是整数,可以推出上面是整数,如果他俩不都是整数的话,感觉上面也不会是整数,这里不会证明
另x = 3*a^(2/3)*b^(1/3), 如果x是整数,那么把它质因数分解后,每个素数的指数都是整数,所以分别把3*a^(2/3), b^(1/3)分解后,相同素数的指数和也应该是整数.假设一个素数p在3*a^(2/3), b^(1/3)分解下指数分别是k1,k2, 那么(2/3) * k1 + (1/3) * k2必须是整数,于是对于一个a,你可以知道最小的t,使得3*a^(2/3)*t是一个整数, 那么看1-M里面有多少个t的倍数,即M/t, . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
同理,可以找到b对应的在1-N中的个数,最后每组答案被统计了两次除以2就好

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

1guangnian 发表于 2014-10-24 03:37:18 | 显示全部楼层
结果不同可能是test case不一样?
顺便问一下第一题M和N的范围多大?我感觉N*N^(1/2)是可以做的
回复 支持 反对

使用道具 举报

 楼主| hakase 发表于 2014-10-24 03:40:37 | 显示全部楼层
1guangnian 发表于 2014-10-24 03:37
结果不同可能是test case不一样?
顺便问一下第一题M和N的范围多大?我感觉N*N^(1/2)是可以做的

记得是1到10^5
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-24 04:11:53 | 显示全部楼层
hakase 发表于 2014-10-24 03:40. 1point 3acres 璁哄潧
记得是1到10^5

说的有一点点错误,不是(2/3)*k1,因为3*a^(2/3)中,3没有指数2/3,不过意思你应该明白的了
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-24 04:13:19 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
最后统计答案也不是那么算的。。需要a对应的b和b对应的a做个交集

补充内容 (2014-10-24 04:22):. From 1point 3acres bbs
感觉另N = M = min(N, M)之后,就可以统计答案除二了。。想不清楚了=。=
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-24 05:08:57 | 显示全部楼层
不对。。对于a, 得到的t,是看M/t里面有几个完全立方数=。=
回复 支持 反对

使用道具 举报

迷茫的考拉 发表于 2014-10-24 05:35:33 | 显示全部楼层
做一下变量替换,不然看得太蛋疼了。。. 1point3acres.com/bbs
假设 x = a^(1/3), y = b^(1/3),题目变为 (x + y)^3 = x^3 + y^3 + 3xy(x+y) 为整数。
故而变为xy(x+y)为整数。. 1point3acres.com/bbs

下面这段是感觉上是对的,不会证明,求轻喷,求数学大神
即是要求a和b提取完全立方数之后,剩下的部分相等。(这个条件足够证明得到整数,但是是不是充要条件想不出来). more info on 1point3acres.com

实现很简单,循环1-m;
把a的完全立方数提取出来之后,剩下k,用k乘以1,8,27....直到这个值大于n。这样每次都是符合要求的一对数。
回复 支持 反对

使用道具 举报

迷茫的考拉 发表于 2014-10-24 06:10:24 | 显示全部楼层
不知道如何修改发出去的回复。。就新回复一个了。。。
又重新想了下
假设a = i^3 * c, b = j^3 * d;这样i,j就可以直接忽略掉了。
同样根据 (x + y)^3 = x^3 + y^3 + 3xy(x+y) ,问题就变为(c^2 * d)^(1/3) + (c * d^2)^(1/3)。
两个非负无理数相加和要为整数,也就是他们都要是整数。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
即:
c^2 *d = p^3
c * d^2 = q^3
上式除以下式得到 c * q^3 = d * p^3
由于c和d都不含有完全立方数了,故c = d
即要求a和b提取完全立方数之后,剩下的部分相等。

好吧。可能还有不严谨的地方,求轻喷~

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

paradise2009 发表于 2014-10-24 09:35:29 | 显示全部楼层
public static int pairCubicSum(int M, int N) {
                int a = (int) Math.ceil(Math.cbrt(M));
                int b = (int) Math.ceil(Math.cbrt(N));
                return a * b;
}
回复 支持 反对

使用道具 举报

MTC 发表于 2014-10-24 22:49:06 | 显示全部楼层
LZ很牛啊,有面试,我认识的大部分人,投简历直接被T拒了......
回复 支持 反对

使用道具 举报

 楼主| hakase 发表于 2014-10-24 23:02:28 | 显示全部楼层
MTC 发表于 2014-10-24 22:49
LZ很牛啊,有面试,我认识的大部分人,投简历直接被T拒了......
. 1point3acres.com/bbs
我投了好几次才拿到面试的,坚持不懈的投吧
回复 支持 反对

使用道具 举报

MTC 发表于 2014-10-24 23:11:00 | 显示全部楼层
hakase 发表于 2014-10-24 23:02
我投了好几次才拿到面试的,坚持不懈的投吧

没小黑屋??
回复 支持 反对

使用道具 举报

 楼主| hakase 发表于 2014-10-24 23:19:04 | 显示全部楼层
MTC 发表于 2014-10-24 23:11. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
没小黑屋??

没,邮箱账号也是原来的。
回复 支持 反对

使用道具 举报

paradise2009 发表于 2014-10-25 03:07:23 | 显示全部楼层
应该用floor,不是ceil。
回复 支持 反对

使用道具 举报

majiamajia 发表于 2014-10-28 05:17:47 | 显示全部楼层
感觉题目好难。。即将要做的飘过
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 01:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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