84669인 학습
152542인 학습
20005인 학습
5487인 학습
7821인 학습
359900인 학습
3350인 학습
180660인 학습
48569인 학습
18603인 학습
40936인 학습
1549인 학습
1183인 학습
32909인 학습
前天面试了一个问题请使用js,python,java,c,c++之类的语言,在10秒内计算出100亿的数据,并且(只能在3秒内)完成,偶数在奇数前格式如下1,2,3,4,5输出结果是2,1,4,3,6,5,问题2:在1的代码之上,要求不能使用for while关键字,从100亿里面取所有的质数(时间不能超过3秒)这个怎么搞?
认证高级PHP讲师
第一个问题没看懂,是说2个数字为一对,然后偶数在奇数前面?
第二个问题简单啊,不能用循环,那就用数组迭代呗。
话说 php 的 foreach 算么(笑
php
foreach
我觉得面试官的意图是让你写一个递归函数?嗯估计是。
那么递归性能不太够。。。但是我还是用了一些。。 For Performance
For Performance
。。。 100亿 的体量 应该是有的。 我还没发现。
100亿
100 亿有点大啊 我先 10 万了
var n = 1000 * 1000; var test = new Array(n).fill(n).map((e, idx) => idx);
这样可以获得到 10 万长度的数组 自然数。
偶数在前 奇数在后
观察之后发现,奇数 + 1、 偶数 - 1 就可以了
奇数 + 1
偶数 - 1
var isEven = n => n % 2 === 0; var res001 = test.map((e, idx) => { if (isEven(e)){ return e - 1; } else { return e + 1; } });
完成第一个问题
下一个问题是在上面的基础上取得质数 即从 zs 里取得所有质数
zs
查了一下关于质数的问题,别人说 质数分布在 6 的倍数的左边或者右边 那么我只要遍历 每一个6的倍数的左边和右边 并判断他们是不是质数即可。
质数分布在 6 的倍数的左边或者右边
链接: 判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路
// 剔除第一个负数 var zs = res001.slice(1); var is6x = n => n % 6 === 0; var isPrime = n => { let temp = Math.sqrt(n); for(let i = 2; i <= temp; i++){ if(n % i === 0){ return false; } } return true; } var lasts = zs.filter(is6x).reduce((acc, cur) => { let left = cur - 1, right = cur + 1; if (isPrime(left)) acc.push(left); if (isPrime(right)) acc.push(right); return acc; }, []); console.log(lasts);
不知道对不对 ...
不过还需要把 小于 6 的质数 1 2 3 5 单独拼回去。 (这里没拼)
小于 6
把上面写的代码黏起来
var isEven = n => n % 2 === 0; var is6x = n => n % 6 === 0; var isPrime = n => { let temp = Math.sqrt(n); for(let i = 2; i <= temp; i++) if(n %i== 0){ return false; } return true; } function timeTest(n){ var test = new Array(n).fill(n).map((e, idx) => idx); var res001 = test.map((e, idx) => { if (isEven(e)){ return e - 1; } else { return e + 1; } }); var zs = res001.slice(1); var lasts = zs.filter(is6x).reduce((acc, cur) => { let left = cur - 1, right = cur + 1; if (isPrime(left)) acc.push(left); if (isPrime(right)) acc.push(right); return acc; }, []); return lasts; }
test
var n = 1000 * 10000; console.time('1000 万') timeTest(n); console.timeEnd('1000 万');
1000 万 结果如图
1000 万
花了 13.8 秒 不可能做到 10 + 3 秒内完成 100亿 的体量。
13.8
10 + 3
我的电脑是 i5-4210M 12G Chrome 58
i5-4210M
12G
Chrome 58
JavaScript 做不到这样的性能: 100亿 个数字 13 秒内 ....
JavaScript
13
好几个 G 的数据 ......
G
按照上面的思路来做,即使是 C/C++ 估计也很难13秒跑完100亿。
C/C++
解决问题为主。
判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路
首先感谢楼上的求质数的算法,我贴下我的结果和代码(只有1000万,一亿浏览器直接炸掉了,而且求质数那里不能用递归(我测试的结果),不然也得炸,只能迭代)。
浏览器里面的结果:
node里面的结果:
var arr = []; console.time("1000万"); for( var i = 1; i <= 10000000; i++ ){ arr.push(i); } for( var j = 0, len = arr.length;j < len; j+=2 ){ arr[j]++; arr[j+1]--; } function isPrime(num,sqrt){ if(num == 1) return false; if(num == 2 || num == 3 ) return true; if(num % 6 != 1 && num % 6 != 5) return false; var tmp = sqrt(num); for(var i= 5;i<=tmp; i+=6 ) if(num % i == 0 || num % ( i + 2) == 0 ) return false ; return true; }; function getPrime(sourceArray,array,isPrime,sqrt){ sourceArray.map(function(num,idx){ if(isPrime(num,sqrt)){ array.push(num); } }); return array; }; var result = getPrime(arr,[],isPrime,Math.sqrt); console.timeEnd("1000万");
第一个问题没看懂,是说2个数字为一对,然后偶数在奇数前面?
第二个问题简单啊,不能用循环,那就用数组迭代呗。
话说
php
的foreach
算么(笑我觉得面试官的意图是让你写一个递归函数?嗯估计是。
既然不能用 for while
那么递归性能不太够。。。但是我还是用了一些。。
For Performance
可能有很巧妙的办法
。。。
100亿
的体量 应该是有的。 我还没发现。代码
100 亿有点大啊 我先 10 万了
这样可以获得到 10 万长度的数组 自然数。
Next
偶数在前 奇数在后
观察之后发现,
奇数 + 1
、偶数 - 1
就可以了完成第一个问题
ScreenShot One
Next
下一个问题是在上面的基础上取得质数 即从
zs
里取得所有质数查了一下关于质数的问题,别人说
质数分布在 6 的倍数的左边或者右边
那么我只要遍历 每一个6的倍数的左边和右边 并判断他们是不是质数即可。链接: 判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路
ScreenShot Two
不知道对不对 ...
不过还需要把
小于 6
的质数 1 2 3 5 单独拼回去。 (这里没拼)性能
把上面写的代码黏起来
test
1000 万
结果如图花了
13.8
秒 不可能做到10 + 3
秒内完成100亿
的体量。我的电脑是
i5-4210M
12G
Chrome 58
JavaScript
做不到这样的性能:100亿
个数字13
秒内 ....好几个
G
的数据 ......按照上面的思路来做,即使是
C/C++
估计也很难13秒跑完100亿。解决问题为主。
Links
判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路
首先感谢楼上的求质数的算法,我贴下我的结果和代码(只有1000万,一亿浏览器直接炸掉了,而且求质数那里不能用递归(我测试的结果),不然也得炸,只能迭代)。
浏览器里面的结果:
![](http://img.php.cn/upload/image/000/000/000/2cdb25c27bc98819504e866c14852fb3-0.png)
node里面的结果:
![](http://img.php.cn/upload/image/000/000/000/d657cc526dea2a7351d686ea07f4fbc5-1.png)