Google Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
7
of 7 vote

Primes after a point in the series are multiples of 6 +/-1. that is 31 = 30 + 1, 37 = 36 + 1 and so on.
So find the first number in 10 digits that is divisible by 6 and then from then on check if no-1 or no+1 is prime. increment by 6 and do the same check until the prime count = 5

- Phoenix July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrong check these prime numbers with gap less than 6, 41 43 47 53 59 61 67 71

- abcd July 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

he said multiples of 6 +/- 1, all the primes you listed fit that criteria. 41 = 42 -1 ; 43 = 42 + 1; 47 = 48 - 1; 53 = 54 - 1 and so forth...

- Anonymous July 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your logic is too good! Strange I never read about this before.

- Rohitraman2006 July 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I doubt if this would make the answer.

i) "From then on check if no-1 no+1 is prime" : this is not trivial. If this was fine, than we could just check for all digits larger than 100..0 which would be only take x3 amt of time.

ii) I interpret "10 digit number" as "a very large number". Also note multiplication/division/sqrt is very expensive. So I would prefer a solution that does not involve mult/div/sqrt and large amt of memory.

The best I can think of is a "lazy" version of sieve of Eratosthenes where the end of sieve may move with delayed sieving. But still this would require remembering all previously found primes.

- Anon July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

The mentioned answer seems not applicable for all the numbers.
Number 49 is not prime but as per the logic mentioned in the answer it should be prime.
So the answer is wrong.

- Aakash July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Aakash, he never said it's applicable to all numbers, he said generate numbers in the form of 6k - 1 and 6k + 1 and then CHECK if they are prime, so there is a primality test involved for each number generated. Even though such a test becomes non-trivial for numbers with 8-9+ digits, it's still a solid answer IMO.

- Anonymous July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Not all primes are in the form of 6n+1 and 6n-1. This holds true up to a certain digits, but definitely not 10 digits:

1,000,000,000 / 6 = 166,666,666 (integer division)
166,666,666 * 6 = 999,999,996
999,999,996 + 6 = 1,000,000,002

when n = 166,666,667

6n-1 = 1,000,000,001
6n+1 = 1,000,000,003

Both 1,000,000,001 and 1,000,000,003 are not prime:
1,000,000,001 = 1,001×999,001


However when when n = 166,666,668

6n-1 = 1,000,000,007
6n+1 = 1,000,000,009

Which are both prime.

In conclusion, this method of generating primes holds true for most integer "n", but not always.

- oOZz July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@oOZz: wrong, all PRIMES are in the form of 6n-1 or 6n+1 but not all numbers in the form of 6n-1 or 6n+1 are not PRIME.

Proof:
Checking a million primes is certainly energetic, but it is not necessary (and just looking at examples can be misleading in mathematics). Here is how to prove your observation: take any integer n greater than 3, and divide it by 6. That is, write

n = 6q + r

where q is a non-negative integer and the remainder r is one of 0, 1, 2, 3, 4, or 5.

If the remainder is 0, 2 or 4, then the number n is divisible by 2, and can not be prime.
If the remainder is 3, then the number n is divisible by 3, and can not be prime.

So if n is prime, then the remainder r is either

1 (and n = 6q + 1 is one more than a multiple of six), or
5 (and n = 6q + 5 = 6(q+1) - 1 is one less than a multiple of six).

Remember that being one more or less than a multiple of six does not make a number prime. We have only shown that all primes other than 2 and 3 (which divide 6) have this form.

- Anonymous July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Up
Easy tiger :) that's what i meant, sorry for the bad wording, but it's clear from the example that I gave, isn't it?

The point is this method is not accurate. This 6n+/-1 formula is like saying "pick an odd number", because all the primes are odd, but in fact not all the odd number are primes.

- oOZz July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Haha sorry, I didn't mean to come off as angry :) I just wanted to make it clear that we were talking about primes and non-primes hence the capitalization. We could generate all 6n-1, 6n+1 numbers that are 10 digits and do a primality test on them but that would not be an optimal solution.

I suggested using the sieve of eratosthenes to generate all 10 digit primes as they are considered "small" relative to the 100+ digit primes used in real-world applications and would take linear time to generate with some optimizations done to the algorithm.

- Anonymous July 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you check if 6n +/- 1 is prime or not? If there is a easy way to do it then we would as well incrementally check all the numbers above 1000000000 to be prime or not. What this 6n is doing is just skipping to every sixth number.

- Zero2 August 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one, Phoenix! I had the same idea. If you eliminate the prime factors of 6, which are 2 and 3, then you can expand on that idea for all numbers. Here is the sequence of all prime numbers. Unfortunately, this sequence is infinite, so let's only take a few primes at a time, okay? :)

static IEnumerable<int> FindPrimes(int lower, int count)
{
    var primes = from n in Sequence(lower)
                    where n == 2 || n % 2 != 0
                    where n == 3 || n % 3 != 0
                    where n >= 2
                    where !Enumerable.Range(1, n)
                                    .Where(k => 36 * (long)k * k - 12 * k < n)
                                    .Any(k => n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0)
                    select n;
    return primes.Take(count);
}

In this code "lower" is the start of where we look for prime numbers. The parameter "count" specifies how many prime numbers we want.

Oh, almost forget. I chose a generator to get the sequence started:

public static IEnumerable<int> Sequence(int start)
{
    for (int i = start; ; i++) yield return i;
}

Or you can simply return the entire sequence of prime numbers and take as many as you want! (or as many as your memory allows you)

- The Internet August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

BTW, first three prime numbers above 1,000,000 are 1000003, 1000033, and 1000037.

- The Internet August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oops! Did you ask for primes larger than a billion?

Well ... this LINQ mess above won't cut it today then. We should probably implement a version of the Miller-Rabin primality test and eliminate numbers through the use of witnesses. I don't think I want to implement Miller-Rabin again. I'm sure there are enough implementations floating around.

- The Internet August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually ... I thought about it some more and thought to myself that the runtime of finding primes in that range shouldn't be as bad as my tests showed. My LINQ code is just horrible. If you unroll the mess above, the following runs just fine:

static bool IsPrime(int n)
        {
            if (n != 2 && n % 2 == 0) return false;
            if (n != 3 && n % 3 == 0) return false;
                
            for (int k = 1; 36 * k * k - 12 * k < n; ++k)
                if (n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0)
                    return false;
            
            return true;
        }

Let this be the driver:

int count = 3;
for (int i = 1000000000; ; i++)
{
    if (IsPrime(i)) count--;
    if (count == 0) break;
}

That runs within a second on my i7 and we didn't even need Miller-Rabin! Apologies. I am apparently running out of coffee. And no more LINQ for me today.

BTW, first three prime are: 100000007, 1000000009, 1000000021. The next three are 1000000033, 1000000087, 1000000093 - if you want to check your solution some more.

- The Internet August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Aww man :( I'm really not paying attention anymore. Now I haven't even made use of Phoenix's suggestion to only look at numbers adjacent to multiples of six! Please give me another chance to fix this:

int n = 1000000000 - 1;
while (n % 6 != 0) n++;
int count = 3;
var primes = new List<int>();
for (; n < int.MaxValue; n += 6)
{
    if (IsPrime(n + 1)) { primes.Add(n + 1); count--; }
    if (IsPrime(n - 1)) { primes.Add(n - 1); count--; }
    if (count == 0) break;
}

Pay attention to subtracting one from the start value, because it could lay just above a multiple of six. The code above looks for the first number divisible by six and then goes in steps of six to check primes. Actually ... if we want to make this effort and go in steps of six to eliminate candidates, maybe we should go all the way and rather eliminate numbers through Miller-Rabin after all ... not sure anymore.

- The Internet August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

BTW, why do people on here claim that a primality test for that number range is non-trivial? Is there an error in my solution? It appears to run just fine and I have just generated the first 300 prime numbers above a billion. Can you explain why you thought it is non-trivial or has my solution (or non-solution depending on your answer) refuted that claim already?

- The Internet August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Brute force solution: check every number begin from 1 000 000 000 by dividing on every integer from 2 to sqrt(n).

void print_5_primes_10_digit() {
  for (int prime = 1000000000, count = 0; count < 5; prime++) {
    bool is_prime = true;
    for (int divisor = 2; divisor <= std::sqrt(prime); divisor++) {
      if (prime % divisor == 0) {
        is_prime = false;
        break;
      }
    }
    if (is_prime) {
      printf("%d\n", prime);
      count++;
    }
  }  
}

It runs 0.006 sec on my computer.

1000000007
1000000009
1000000021
1000000033
1000000087

- zprogd August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can initiate prime to 1 million +1 and then increment by two since even numbers won't be prime.

- praveenkcs28 August 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is some optimization even for brute force: memorize prime numbers and for the next number (K) to check we could check if the number is divisible by those early memorized prime numbers only (not all the numbers from 2 to Sqrt(K)).
And there is another pretty simple and efficient algorithm to compute prime numbers: check sieve of Eratosthenes algorithm.

- Alex M. June 28, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def specificPrimes():
    from math import pow

    primes = []
    for i in range(2, 10**5):
        isPrime = True
        for j in primes:
            if pow(j, 2) > i:
                break
            elif i % j != 0:
                isPrime = False
                break
        if isPrime:
            primes.append(i)

    largePrimes = []
    for i in range(10**9, 10**10):
        if len(largePrimes) == 10:
            break
        isPrime = True
        for j in primes:
            if pow(j, 2) > i:
                break
            elif i % j != 0:
                isPrime = False
                break
        if isPrime:
            largePrimes.append(i)

    return largePrimes

This one's pretty straightforward. Get all the primes up til the square root of 10,000,000,000 (11 digits), and use those primes to find the first 10 primes above 1,000,000,000 (10 digits).

- Nick July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, I accidentally returned the first 10 primes instead of the first 5... oh well. Does anyone have a clever way of doing this?

- Nick July 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Write a method to return first five 10 digit prime numbers.
*/

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric> // std::accumulate
#include <sstream>
#include <stack>
#include <string>

using namespace std;

vector<int> vecPrimeTable;
int nPrimeTableMax = 0;

class Solution
{
public:
	static inline bool IsPrime( int nInt )
	{
		int nSqrt = static_cast<int>( sqrt( nInt * 1.0 ) );

		if ( nSqrt > nPrimeTableMax )
			CalculatePrimeTable( static_cast<int>( nSqrt * 1.1 ) );

		for ( vector<int>::iterator ii = vecPrimeTable.begin(); ii != vecPrimeTable.end(); ii ++)
		{
			if ( *ii > nSqrt )
				break;

			if ( nInt % *ii == 0 )
				return false;			
		}

		return true;
	}

	static void CalculatePrimeTable( int nIntMax )
	{
		if ( 0 == vecPrimeTable.size() )
			vecPrimeTable.push_back( 2 );
		int nIntMin = vecPrimeTable[ vecPrimeTable.size() - 1 ] + 1;

		if ( nIntMin % 2 == 0)
			nIntMin ++;

		for ( int i = nIntMin; i <= nIntMax; i += 2)
		{
			if ( IsPrime( i ))
				vecPrimeTable.push_back( i );
		}

		nPrimeTableMax = max( nPrimeTableMax, nIntMax );
	}


	static std::vector<int> OutputFirstNPrime( int nBegin, int nCount )
	{
		std::vector<int> vecResult;

		//CalculatePrimeTable( static_cast<int>( sqrt( nBegin * 1.1 ) ) );

		int nValue = nBegin;
		if ( 0 == nBegin % 2 )
			nValue ++;

		while ( nCount >= 0 )
		{
			if ( IsPrime( nValue ))
			{
				vecResult.push_back( nValue );
				nCount --;
			}
			nValue += 2;
		}

		return vecResult;
	}

	static void OutputArray( int A[], int n)
	{
		std::cout << n << std::endl;
		for ( int ii = 0; ii < n; ii ++ )
			if ( ii < n - 1 )
				std::cout << A[ii] << ",";	
			else
				std::cout << A[ii];	
		std::cout << std::endl;
	}
};


int _tmain(int argc, _TCHAR* argv[])
{
	std::vector<int> vecResult = Solution::OutputFirstNPrime(1000000000, 10);
	copy( vecResult.begin(), vecResult.end(), ostream_iterator<int>(cout, " "));
	_getch();

	return 0;
}

- slfeng July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Phoenix's answer is sound logic but we can also use the sieve of Eratosthenes to generate all primes up to 10,000,000,000 (11 digits), mind you primes up to 11 digits are considered very small primes in contrast to the primes used in current applications (such as cryptographic algorithms) so the sieve is a good and efficient way to generate the first 5, 10 digit primes in linear time.
Link for those interested: en.wikipedia.org/wiki/Sieve_of_Eratosthenes

- Anonymous July 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I recall seeing this before. The same link also says this:
"The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)" - that is only 7 0's or 8 total digits. It doesn't say anything about 11 digits.

Keeping this in mind, will the sieve really be that much better than Phoenix's method?

- Rohitraman2006 July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes Wikipedia says 10 million (7-8 digits) but mind you that small prime numbers in the real world are considered those numbers that are ~20 digits as most real-world applications use 100+ digit primes for their algorithms, so 11 digits is relatively small compared to what is being used today.

That being said, the sieve of eratosthenes is obviously not guaranteed to produce a better result than Phoenix's answer, but as some of the replies suggested to his answer not every number in the form of 6k -1 or 6k + 1 is prime (high chance you can get a false positive, i.e the number 49 = 48 + 1 = (6*8) + 1)

The sieve is guaranteed to generate all primes up to N, and with further optimizations it can do it in linear time. There are better and faster sieves one can use to generate primes but they are not as simple to understand as the sieve of eratosthenes like the sieve of Atkin.
All in all, I think this question is a good way to discuss different methods of generating primes and the trade-offs from using one method over the other. It's a good question that probes the logic of the candidate, but can also be considered a complete curve ball if the candidate is not aware that all primes after 3 are in the form of 6k+1 or 6k-1.
Anyways, I'm going off track :) Hope to see some more creative answers to this question

- Anonymous July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the key to this question is to use dynamic programming to save all the prime number as we calculate all the prime

import math

primelist = [2]

def isprimeinlist(input):
    mid = math.sqrt(input)

    for i in primelist:
        if i <= mid and input%i == 0:
            return False;
    return True;

def checkprime(input):
    mid = math.sqrt(input)

    start = 0
    for i in primelist:
        start = i
        if i <= mid and input%i == 0:
            return False

    while start <= mid:
        if (input % start) == 0:
            return False

        if start == 2:
            start += 1
        else:
            start +=2

        if isprimeinlist(start):
            primelist.append(start)

    return True


checking = 0
for i in range(1000000,10000000):
    if checkprime(i):
        print '{} is prime'.format(i)
        checking += 1
    if checking == 5:
        break

print primelist

- hc167 July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void firstKNDigitsPrime(int k, int n)
	{
		double power10n = Math.pow(10, n);
//		System.out.println("10^n: " + power10n);

		int minCoff = (int) ((power10n + 1) / 6);

		int number = 6 * minCoff + 1;

		int count = 1;
		for (int i = 2; i < Math.sqrt(number); i++)
		{
			if (number % i == 0)
			{
				count = 0;
				break;

			}
		}

		minCoff++;
		while (count < k)
		{

			int sixnminusone = minCoff * 6 - 1;
			int sixnplusone = minCoff * 6 + 1;

//			System.out.println("6n - 1: " + sixnminusone);
//			System.out.println("6n + 1: " + sixnminusone);
			boolean isSixNMinusOnePrime = true;
			boolean isSixNPlusOnePrime = true;
			for (int i = 2; i <= Math.sqrt(sixnminusone); i++)
			{
				if (sixnminusone % i == 0)
				{
					isSixNMinusOnePrime = false;
					break;
				}
			}

			for (int i = 2; i <= Math.sqrt(sixnplusone); i++)
			{
				if (sixnplusone % i == 0)
				{
					isSixNPlusOnePrime = false;
					break;
				}
			}

			if (isSixNMinusOnePrime && count < k)
			{
				System.out.println(count + 1 + ": " + sixnminusone);
				count++;
			}

			if (isSixNPlusOnePrime && count < k)
			{
				System.out.println(count + 1 + ": " + sixnplusone);
				count++;
			}
			
			minCoff++;
		}
	}

- Anonymous August 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1000000007
1000000009
1000000021
1000000033
1000000087

int i = 1000000000, j = 0, ct = 0, n = 0, cn = 5;
    
    while (n < cn){
        j = 1;
        ct = 0;
        while (j < i){
            if (i%j == 0){
                ct ++;
            }
            j ++;
            if (ct > 2){
                break;
            }
            
        }
        if (ct == 1){
            printf("%d\n", i);
            n++;
            
        }
        i ++;
    }

- OV August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from math import sqrt

def get_primes(n):
  primes = []
  i = 1
  while len(primes) < 10:
    if i == 1:
      primes.append(i)
    else:
      is_prime = True
      for j in range(2, int(sqrt(i))+1):
        if i % j == 0:
          is_prime = False
          break
      if is_prime:
        primes.append(i)
    i = i + 1
  return primes

print(get_primes(10))

- d.gabri3le September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is based on eratosthene's sieve. Algorithm is this
-Find all primes upto SQRT(1billion) using sieve.
-check divisibility of numbers starting after 1 billion with all the primes calculated above until 5 primes are found.

It ran in about 20 ms on my laptop.

**Edit - I ran the brute force solution and it is faster than the sieve method. I guess it is because brute force does not need any storage.

public static void find5PrimesfromN() {
		long IN = 1000000000l;
		int N = (int)Math.sqrt(IN)+1;
		boolean[] nonprime = new boolean[N];
		int d=2;
		while(d < (int)Math.sqrt(N)+1) {
			for(int i=d+1; i<=N; i++) {
				//System.out.println("compare");
				if(i%d == 0) {
					nonprime[i-1] = true;
				}
			}
			d++;
			for(int k=d; k<N; k++) {
				if(!nonprime[k-1]) {
					d = k;
					break;
				}
			}
		}
		List<Integer> primesUpSqRoot = new ArrayList<>();
		for(int k=2; k<N; k++) {
			if(!nonprime[k-1]) {
				primesUpSqRoot.add(k);
			}
		}
		long p = IN+1;
		int np = 0;
		while(np < 5) {
			boolean isP = true;
			for(int div : primesUpSqRoot) {
				if(p%div == 0) {
					isP = false;
					break;
				}
			}
			if(isP) {
				System.out.println("prime "+p);
				np++;
			}
			p++;
		}

	}

- javaspring7 April 08, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More