一亩三分地论坛

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

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

Twitter OA 02/13,求RP,求OFFER,求内推

[复制链接] |试试Instant~ |关注本帖
wh688 发表于 2015-2-14 11:06:54 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Twitter - 内推 - 在线笔试 |Other

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

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

x
先说下Twitter的办事效率真是快!周四(2/12)内推的,周五(2/13)就接到OA。

废话不多说直接上题,1小时2道算法:

第一题是leetcode原题,integer to roma,不同的是给的input是int[],output是String[]。

第二题楼主给的解法超时了,还求各路大神多给思路!拜谢
题目如下:. more info on 1point3acres.com
You are given two integers, M and N, count the pairs (A,B) where:
1<= A <= M
1<= B <= N. From 1point 3acres bbs
(A^(1/3) + B^(1/3)) ^ 3 is an integer.
楼主直接用的Math函数加暴力搜索。

最后祝大家都有好offer!



补充内容 (2015-2-14 12:58):
Twitter效率实在高,几小时后就发来了拒信,move on了。

评分

1

查看全部评分

sterne 发表于 2015-2-14 11:41:27 | 显示全部楼层
感谢楼主分享!我咂摸了,但是也没想出暴力的思路,能不能说一下楼主的解法,再就是OA可以用电脑查吗?如果碰到原题,可以查查原来的记录?谢谢。祝顺利!
回复 支持 反对

使用道具 举报

TsenAlex 发表于 2015-2-14 12:24:42 | 显示全部楼层
LZ 内推投的什么职位?
回复 支持 反对

使用道具 举报

 楼主| wh688 发表于 2015-2-14 12:55:44 | 显示全部楼层
TsenAlex 发表于 2015-2-14 12:24
. 1point3acres.com/bbsLZ 内推投的什么职位?

Software Engineer - Entry-Level - 2015
回复 支持 反对

使用道具 举报

 楼主| wh688 发表于 2015-2-14 12:57:22 | 显示全部楼层
sterne 发表于 2015-2-14 11:41. Waral 鍗氬鏈夋洿澶氭枃绔,
感谢楼主分享!我咂摸了,但是也没想出暴力的思路,能不能说一下楼主的解法,再就是OA可以用电脑查吗?如果 ...

没试过用OA查原题哦,哈哈。我的思路就是两个for loop,就不献丑了,这题应该有犀利的解法,还请路过的大神给点提示
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-2-14 13:07:44 | 显示全部楼层
第二题这样行吗?

(int) Math.cbrt(m) * (int) Math.cbrt(n)
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-2-14 13:09:04 | 显示全部楼层
wh688 发表于 2015-2-14 12:55. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Software Engineer - Entry-Level - 2015

这个职位网页上没有呀???
回复 支持 反对

使用道具 举报

mayyyyyy 发表于 2015-2-14 13:50:13 | 显示全部楼层
想到一个剪枝的方案
把(x^ 1/3 + y ^ 1/3) ^ 3拆开得到x + y + (3 * x ^ 2/3 * y ^1/3) + (3 * x ^ 1/3 * y ^ 2/3).鐣欏璁哄潧-涓浜-涓夊垎鍦
其中x 和 y 不用管,需要关心的是那两个括号里的
如果把x和y都拆成素数幂乘积的形式并合并成(p1 ^ q1 * p2 ^ q2 ...) + (r1 ^ s1 * r2 ^ s2...)的形式,会发现最终结果为整数的条件是括号里的q1, q2, q3... s1, s2, s3...均为3的倍数. 1point3acres.com/bbs
因此对于某个x,可以直接dfs出结果

外层仍然是一个x的loop 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
内层先将x分解,然后dfs找出满足分解后满足以下条件的数:
1. x自己包含有某个素数的3倍次幂
2. 如果x中某个素因子不满足条件1, 则y中必须也包含这个素因子,且于x中的这个素因子的成绩为3倍次幂

空间复杂度为栈深度,时间复杂度为O(解的个数)
回复 支持 反对

使用道具 举报

gf1748 发表于 2015-2-15 08:09:39 | 显示全部楼层
先找出M,N以下的所有cubic number,再两两配对,配对同时可以各自乘以一个non-cubic number,
如M=65, N=29
比M小的立方数有1 8 27 64
比N小的立方数有1 8 27
count of pair (1,1): 可以各自乘以2,3,。。。29,一共24对,再加上(1,1)自身
count of pair (1,8): 可以各自乘以2,3,一共2对,再加上(1,8)自身
count of pair (1, 27): 自身(1,27)
count of pair (8,1): 可以各自乘以2,3,一共2对,再加上自身. 鍥磋鎴戜滑@1point 3 acres
count of pair (8,8): 可以各自乘以2,3,一共2对,再加上自身
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴。。。。
  1. public int getPairs(int m, int n) {
  2.         int cubicX = 1, cubicY = 1;
  3.         Set<Integer> cubics = new HashSet<Integer>();
  4.         for (; cubicX * cubicX * cubicX <= m; cubicX++)
  5.                 cubics.add(cubicX*cubicX*cubicX);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.         for (; cubicY * cubicY * cubicY <= n; cubicY++)
  7.                 cubics.add(cubicY*cubicY*cubicY);
  8.         cubicX--; cubicY--;. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.         int count = 0;
  10.         for (int i = 1; i <= cubicX; i++). Waral 鍗氬鏈夋洿澶氭枃绔,
  11.                 for (int j = 1; j <= cubicY; j++) {
  12.                         count++;
  13.                         for (int k = 1; k <= Math.min(m, n); k++) {
  14.                                 if (cubics.contains(k))
  15.                                         continue;
  16.                                 else if (i*i*i*k > m || j*j*j*k > n)
  17.                                         break;
  18.                                 else
  19.                                         count++;
  20.                         }
  21.                 }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.         return count;
  23. }
复制代码
回复 支持 反对

使用道具 举报

ppips 发表于 2015-2-15 11:23:25 | 显示全部楼层
gf1748 发表于 2015-2-15 08:09
先找出M,N以下的所有cubic number,再两两配对,配对同时可以各自乘以一个non-cubic number,
如M=65, N=2 ...

用这个方法还是会超时的
回复 支持 反对

使用道具 举报

babysor 发表于 2015-2-16 17:06:03 | 显示全部楼层
@ppips @gf1748  应该感觉跳过了一下case....
话说 当A=B时不都是符合条件的么?(5^(1/3)+5^(1/3) )^3 应该是40.

补充内容 (2015-2-16 17:07):
说错了,(1,1)这个覆盖了
回复 支持 反对

使用道具 举报

kaimiku 发表于 2015-2-16 20:22:52 | 显示全部楼层
yy了一个算法..不知道是否正确- --google 1point3acres


将任意整数I
表示为质因数次幂的积的形式I=(2^i0)*(3^i1)*(5^i2)*...*(P^in)
用I表示所有[1,M]的A以及[1,N]的B中多出完全立方的部分
比如
I(15)=2^0*3^1*5^1*7^0*11^0*13^0=011000
I(1456)=2^4*3^0*5^0*7^1*11^0*13^1=400101=100101
I(54)=2^1*3^3*5^0*7^0*11^0*13^0=130000=100000.鏈枃鍘熷垱鑷1point3acres璁哄潧
I(15^2)=022000.鏈枃鍘熷垱鑷1point3acres璁哄潧
I(15^2^2)=011000


. From 1point 3acres bbs

F=(A^(1/3)+B^(1/3))^3=a+b+3a^(2/3)*b(1/3)+3a^(1/3)*b^(2/3)
那么

F是整数 <=> I(2*AA+BB)和I(AA+2*BB)为0
满足以上条件的I必须是互为对称, 也就是说I(2*AA)==I(BB)并且I(AA)==I(2*BB)
比如
I(15)=011000和I(15^2^2)=011000
那么I(15^2+15^2^2)=000000
再比如
012210和021120

.鐣欏璁哄潧-涓浜-涓夊垎鍦
用sieve筛我们得到所有[1,max(M,N)]质数的个数P
那么答案就是Q*3^P
其中Q是[1,max(M,N)]中的所有完全立方数的个数

. From 1point 3acres bbs




回复 支持 反对

使用道具 举报

lll_2013 发表于 2015-2-17 08:24:40 来自手机 | 显示全部楼层
我不知道可不可行,就是凭感觉写一个思路哈
回复 支持 反对

使用道具 举报

lll_2013 发表于 2015-2-17 08:37:36 | 显示全部楼层
A^(1/3) + B^(1/3) = A + B + 3A^(1/3)B(2/3) + 3A^(2/3)B(1/3)
suppose A = XB
A^(1/3) + B^(1/3) = A + B + 3B (X^(1/3) + X^(2/3)) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
BX < M
for( i = 1; i < M ; i++)
   upper =int( M/i)
   j = 1
   while(1)
     if( j^3 <upper)
         X = j
         B =  i
     if(j ^ 3 > upper). more info on 1point3acres.com
         break
     
      
      
回复 支持 反对

使用道具 举报

tyr034 发表于 2015-3-2 06:19:04 | 显示全部楼层
这道题咋做啊?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 15:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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