Yahoo
3.4 of 5 1,679 reviews
www.yahoo.com Sunnyvale, CA 5000+ Employees

Yahoo Intern Interview Question (student candidate)

"Write an algorithm that identifies a prime number from a list of numbers ranging 0-100."
Add Tags [?]
Answer Flag Question

Part of a Intern Interview Review - one of 523 Yahoo Interview Reviews

Answers & Comments

0
of 0
votes
You could do this fairly efficiently using a trivial implementation of the sieve of eratosthenes. The initial setup cost of the sieve is O(n log log n), but once generated the amortised time to identify whether or not a number between 0 .. n is prime ends up being O(1) as n approaches infinity:

function next_prime(i, sieve) {
    for (; i < sieve.length; i++) {
        if (sieve[i] == 0) {
            break;
        }
    }
    return i;
};

function build_sieve(n) {
    var sieve = [];
    var prime = 1;
    var sum = 0;
    while (prime <= n) {
        prime = next_prime(prime + 1, sieve);
        sum = prime;
        while (sum <= n) {
            sum = sum + prime;
            sieve[sum] = 1;
        }
    }
    return sieve;
};

function identify_prime(n) {
    if (n < 0 || n > 100) {
        throw new Error(n + ' is outside accepted range');
    }
    return sieve[n] === undefined;
};

function test_prime(n) {
    if (identify_prime(n)) {
        console.log(n + ' is prime');
    } else {
        console.log(n + ' is not prime');
    }
};

var sieve = build_sieve(100);

test_prime(3);
test_prime(88);
test_prime(17);
test_prime(100);
- Dan on Jul 15, 2013 Flag Response
0
of 0
votes
I feel this is a trick question. Since we know the range and it is such a small range, the quickest algorithm would be:

is_prime = (num)->
  return num in [2, 3, 5, 7, 11, 13, 17, 19, 23...]
- Mihir Sathe on Aug 18, 2013 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Yahoo interview questions and advice. All interview reviews posted anonymously by Yahoo employees and interview candidates.