《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2636|回复: 15
收起左侧

Twitter OA 经

[复制链接] |试试Instant~ |关注本帖
anitamengzhuolu 发表于 2016-3-21 08:44:30 | 显示全部楼层 |阅读模式

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

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

x
下午昨晚的Twitter OA,感觉题不是很简单,发上来攒攒人品~
60min两道题,第一道是给两个数M和N,求从1到M和1到N之间的数有哪些组合满足两个数立方根的和的三次方是整数。
第二道感觉大家遇到的比较多一些,cutting stick,就是一堆stick,每次可以都切特定的长度直到切完,问每一次切完后还剩几根。
供大家参考~

评分

2

查看全部评分

本帖被以下淘专辑推荐:

UFO 发表于 2016-4-10 10:47:16 | 显示全部楼层
hison7463 发表于 2016-3-25 04:42
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^ ...

先求平方数的思路很好,不过a,b立方根并不一定要是整数,比如a=40=5*8, b=135=5*27,结果也是整数。
发一个代码吧
  1. int cubeNumbers(int M, int N) {
  2.         List<Integer> lm = new ArrayList<Integer>();
  3.         List<Integer> ln = new ArrayList<Integer>();
  4.         int count = 0, i, a, b;. 1point 3acres 璁哄潧
  5.         for (i = 1; i <= M / i/i; i ++) {
  6.             lm.add(i * i * i);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.         }
  8.         for (i = 1; i <= N / i/i; i ++) {
  9.             ln.add(i * i * i);
  10.         }
  11.         HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
  12.         for (int cubeA : lm) {
  13.             for (int cubeB : ln) {
  14.                 for (i = 1; i <= M; ++i) {
  15.                     if ((a = i * cubeA) > M || (b = i * cubeB) > N) break;.1point3acres缃
  16.                     if (!map.containsKey(a)) map.put(a, new HashSet<Integer>());
  17.                     if (!map.get(a).contains(b)) {
  18.                         map.get(a).add(b);
  19.                         count ++;. 1point3acres.com/bbs
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.         return count;
  25.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

sniffsky 发表于 2016-3-24 06:42:35 | 显示全部楼层
hison7463 发表于 2016-3-24 05:20
第一题先把式子展开,发现只要找到a^(1/3), b^(1/3), a^(2/3), b^(2/3)(其实也就是a^(1/3), b^(1/3))同时 ...

感觉这是充分条件。比如3和24,立方根和的立方也是整数

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xiaojunji 发表于 2016-3-21 10:14:43 | 显示全部楼层
第一道怎么做?跪求代码和思路!谢谢好人
回复 支持 反对

使用道具 举报

lzb940214 发表于 2016-3-21 12:20:33 | 显示全部楼层
感觉第一题要用到一个数的质数分解吧,但具体还不知道怎么做。第二题排序用nlogn, 每次询问用logn,还有更好的方法吗?
回复 支持 反对

使用道具 举报

lzb940214 发表于 2016-3-21 12:21:31 | 显示全部楼层
对了,请教楼主,OA上用什么语言都可以吗?都有什么可用的语言?
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-3-24 00:01:19 | 显示全部楼层
第一题暴力可以通过吗?O(MN)。。。
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-24 05:20:06 | 显示全部楼层
第一题先把式子展开,发现只要找到a^(1/3), b^(1/3), a^(2/3), b^(2/3)(其实也就是a^(1/3), b^(1/3))同时为整数的情况就行了。
我的方法就是:
.鐣欏璁哄潧-涓浜-涓夊垎鍦对于1 - n的情况O(n^(1/3))
int cur = 1;. from: 1point3acres.com/bbs
List list1;
while(cur <= n) {
      if(cur * cur * cur < n) {
             list.add(cur * cur * cur);
      }
      else {
            break;
      }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      cur++;.1point3acres缃
}
对于1 - m的情况O(m^(1/3))
int cur = 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
List list2;
while(cur <= m) {
      if(cur * cur * cur < m) {. 1point3acres.com/bbs
             list.add(cur * cur * cur);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
      }
      else {
            break;
      }
      cur++;
}
再把list1和list2组合一下就行了
回复 支持 反对

使用道具 举报

kiss 发表于 2016-3-24 06:23:10 | 显示全部楼层
请问楼主自己投的还是内推的?
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-3-24 06:36:02 | 显示全部楼层
hison7463 发表于 2016-3-24 05:20
第一题先把式子展开,发现只要找到a^(1/3), b^(1/3), a^(2/3), b^(2/3)(其实也就是a^(1/3), b^(1/3))同时 ...

(x+y)^3=x^3+y^3+3xy(x+y)
这个3xy(x+y)不一定要求x, y都要是整数吧?比如x=1/3, y=3.
当然,当x,y都分别为某整数的1/3次幂时,是否还有这种特例,还需要求证。。。. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-3-24 09:52:11 | 显示全部楼层
lzb940214 发表于 2016-3-21 12:20. more info on 1point3acres.com
感觉第一题要用到一个数的质数分解吧,但具体还不知道怎么做。第二题排序用nlogn, 每次询问用logn,还有更 ...

第二题只用排序就好了吧,排序nlogn,肯定是先砍短的过一遍时间O(n), 每次输出 length-index
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-25 02:03:45 | 显示全部楼层
tldxk 发表于 2016-3-24 06:36
(x+y)^3=x^3+y^3+3xy(x+y)
这个3xy(x+y)不一定要求x, y都要是整数吧?比如x=1/3, y=3.
当然,当x,y都分 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对诶,那就再加上一个限定条件,a^(1/3) = b^(1/3) * x (x为整数),满足这个式子,即a = b * x ^ 3的所有a,b组合
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-25 04:42:37 | 显示全部楼层
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^(2 / 3)和a^(2 / 3) * b^(1 / 3)为整数就能保证结果为整数,如果a^(1 / 3) = b^(1 / 3) * X (X为整数)和b(1 / 3) = a ^ (1 / 3) * X (X为整数),那么a^(1 / 3) * b^(2 / 3) = b * X和a^(2 / 3) * b^(1 / 3) = a * X就肯定是整数,即找到满足a = b * X ^ 3和b = a * X ^ 3的所有a,b组合
  1. public List<int[]> cubeRoot(int m, int n) {
  2.                 List<int[]> res = new ArrayList<int[]>();
  3.                 List<Integer> listM = new ArrayList<Integer>();
  4.                 List<Integer> listN = new ArrayList<Integer>();. from: 1point3acres.com/bbs
  5.                 int cur = 1;
  6.                 while(cur <= m / cur / cur) {
  7.                         listM.add(cur * cur * cur);
  8.                         cur++;. From 1point 3acres bbs
  9.                 }. more info on 1point3acres.com
  10.                 cur = 1;
  11.                 while(cur <= n / cur / cur) {. From 1point 3acres bbs
  12.                         listN.add(cur * cur * cur);. From 1point 3acres bbs
  13.                         cur++;
  14.                 }
  15.                 int a = 1;
  16.                 int b = 1;
  17.                 HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
  18.                 while(b <= n) {. 1point3acres.com/bbs
  19.                         for(int numA : listM) {
  20.                                 a = b * numA;
  21.                                 if(a <= m) {
  22.                                         if(!map.containsKey(a)) {
  23.                                                 map.put(a, new HashSet<Integer>());
  24.                                         }
  25.                                         map.get(a).add(b);
  26.                                         res.add(new int[]{a, b});
  27.                                 }
  28.                                 else {
  29.                                         break;
  30.                                 }
  31.                         }
  32.                         b++;
  33.                 }
  34.                 a = 1;
  35.                 b = 1;
  36.                 while(a <= m) {
  37.                         for(int numB : listN) {
  38.                                 b = a * numB;
  39.                                 if(b <= n) {
  40.                                         if(!map.containsKey(a)) {
  41.                                                 map.put(a, new HashSet<Integer>());
  42.                                         }
  43.                                         else {
  44.                                                 if(map.get(a).contains(b)) {. from: 1point3acres.com/bbs
  45.                                                         continue;
  46.                                                 }
  47.                                         }
  48.                                         map.get(a).add(b);
  49.                                         res.add(new int[]{a, b});
  50.                                 }
  51.                                 else {. 1point 3acres 璁哄潧
  52.                                         break;
  53.                                 }
  54.                         }
  55.                         a++;
  56.                 }. 1point 3acres 璁哄潧
  57.                 return res;
  58.         }
复制代码
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-3-29 09:06:50 | 显示全部楼层
hison7463 发表于 2016-3-25 04:42
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^ ...

这个最后的pair有重复的吧
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-31 03:07:15 | 显示全部楼层
zoufengboy 发表于 2016-3-29 09:06. 1point3acres.com/bbs
这个最后的pair有重复的吧

没有吧,我已经用map把遇见的pair存起来了,下次遇到的话会跳过
回复 支持 反对

使用道具 举报

jefferyy 发表于 2016-4-8 13:11:34 | 显示全部楼层
hison7463 发表于 2016-3-25 04:42
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^ ...
. visit 1point3acres.com for more.
这个的时间复杂度是什么?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-20 05:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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