javascript - programming, algorithm problems

Question

I had an interview question the day before yesterday
Please use js, python, java, c, c and other languages ​​to calculate 10 billion data in 10 seconds, and complete it (only within 3 seconds), even number Before the odd number
the format is as follows
1, 2, 3, 4, 5
The output result is
2, 1, 4, 3, 6, 5,
Question 2: In 1 Above the code, it is required not to use the for while keyword and to get all the prime numbers from 10 billion (the time cannot exceed 3 seconds)
How to do this?

Answer 1

I don’t understand the first question. Does it mean that 2 numbers are a pair, and the even number comes before the odd number?

The second question is simple. If you can’t use a loop, then use array iteration.

Answer 2

By the way, php’s foreach doesn’t count (laughs

I think the interviewer’s intention is to ask you to write a recursive function? Well I guess so.

Answer 3

I had an interview question the day before yesterday
Please use languages ​​such as js, python, java, c, c++ to calculate 10 billion data in 10 seconds, and complete it (only within 3 seconds), even numbers come before odd numbers
The format is as follows
1, 2, 3, 4, 5
The output result is
2, 1, 4, 3, 6, 5,
Question 2: On top of the code in 1, it is required that the for while keyword cannot be used, from Get all the prime numbers out of 10 billion (the time cannot exceed 3 seconds)
How to do this?

---

Since it cannot be used for while

Then the recursive performance is not enough. . . But I still use some. . For Performance

There may be a clever way

. . . There should be a size of 10 billion. I haven't found it yet.

Code

10 billion is a bit big, I’ll take 100,000 first

var n = 1000 * 1000; 
var test = new Array(n).fill(n).map((e, idx) => idx); 

In this way, you can get an array of natural numbers with a length of 100,000.

---

Next

1. Even numbers first, odd numbers last

After observation, we found that odd number + 1, even number - 1 is fine

var isEven = n => n % 2 === 0; 

var res001 = test.map((e, idx) => {
    if (isEven(e)){
        return e - 1; 
    } else {
        return e + 1; 
    }
}); 

Complete the first question

ScreenShot One

Next

The next question is to get the prime numbers based on the above, that is, get all the prime numbers from zs

I checked the question about prime numbers, and others said Primes are distributed on the left or right of multiples of 6 Then I just need to traverse the left and right of each multiple of 6 and determine whether they are prime numbers.

Link: Determining whether a number is a prime number/prime number - from ordinary judgment algorithm to efficient judgment algorithm idea

// 剔除第一个负数 
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); 

ScreenShot Two

I don’t know if it’s right...

But we still need to piece together the prime numbers less than 6 1 2 3 5 separately. (No spelling here)

Performance

Adhere the code written above

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 万');

10 million The result is as shown in the picture

---

It took 13.8 seconds. It is impossible to complete 10 billion in 10 + 3 seconds.

My computer is i5-4210M 12G Chrome 58

JavaScript cannot achieve this performance: 10 billion numbers 13 seconds....

Data from several G...

According to the above idea, even C/C++ is estimated to be difficult to run 10 billion in 13 seconds.

Focus on solving problems.

Links

Determine whether a number is a prime number/prime number - from ordinary judgment algorithm to efficient judgment algorithm idea

Answer 4

First of all, thanks to the algorithm for finding prime numbers upstairs. I will post my results and code (only 10 million, 100 million browsers directly exploded, and recursion cannot be used to find prime numbers (results of my test), otherwise it will be Exploded, can only iterate).

Results in browser:

The result in

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万");