## Google Interview Question for Software Engineer / Developers

Country: United States

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

this is duplicate. please remove this question

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

``````if(n%prime==0)
return false;
if(prime>squareRoot)
break;``````

the previous code adds 9 to prime numbers small change

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

use sieve's algorithm, takes O(n) time

Comment hidden because of low score. Click to expand.
0

First of all, it's not O(n) time. Second of all, it's O(n) memory and the problem statement is clearly trying to hint that you shouldn't use sieve because of that.

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

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

can't you just use recursion to find the first 5 primes from 2 to 100? I believe the time complexity is O(n^2) because the for loop is calling a recursive function which is n/1

``````public ArrayList<Integer> first5Primes(){
ArrayList<Integer> primes = new ArrayList<Integer>();
for(int i = 2; i < 101; i++){
if(primes.size() == 5){
break;
}
if(primeHelper(i,i-1)){
}
}
return primes;
}

public boolean primeHelper(int i, int j){
if(j == 1)
return true;
else if(i % j == 0)
return false;
else
return primeHelper(i, j-1);
}``````

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

public class Prime {
public static void main(String[] args) {
int startnumber=1000000000;
int count=0;
while(count!=5){
boolean val=checkPrime(startnumber);
if(val==true){
count++;
System.out.println(startnumber);
}
startnumber++;
}
}
public static boolean checkPrime(int number){
for(int i=2;i<number/2;i++){
if(number%i==0)
return false;
}
return true;
}
}

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

public class Prime {
public static void main(String[] args) {
int startnumber=1000000000;
int count=0;
while(count!=5){
boolean val=checkPrime(startnumber);
if(val==true){
count++;
System.out.println(startnumber);
}
startnumber++;
}
}
public static boolean checkPrime(int number){
for(int i=2;i<number/2;i++){
if(number%i==0)
return false;
}
return true;
}
}

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

``````#include<iostream>

using namespace std;

bool checkPrime(int number){
for(int i=2;i<number/2;i++){
if(number%i==0)
return false;
}
return true;
}

int main() {
int startnumber=1000000001;
int count=0;
while(count!=5){
bool val=checkPrime(startnumber);
if(val==true){
count++;
cout<<startnumber<<endl;
}
startnumber++;
}
}``````

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

``````#include <iostream>

bool check(long	int x)
{
for (int i = 2; i * i	<= x; ++i)
if (x % i == 0) return false;
return true;
}

int main()
{
long int x = 10000000;
int nc = 0;
while (nc < 5)
if (check(++x )) {
std::cout	<< x <<	"\n";
nc ++;
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use the fact that if n is not prime, then n has at least one factor less or equal to the square root of n.

Keep a list of primes so you don't have to check if composite numbers factor n. Expand it as needed.

An implementation in Java:

``````List<Integer> firstFivePrimesWithTenDigits() {
List<Integer> knownPrimes = new ArrayList<Integer>();
List<Integer> bigPrimes = new ArrayList<Integer>();
for (int i = 1000000001; bigPrimes.size() < 5; i += 2) {
if (isPrime(i, knownPrimes)) {
}
}
return bigPrimes;
}

// Assumes "knownPrimes" is a list of the first k primes from some k >= 2
boolean isPrime(int n, List<Integer> knownPrimes) {
int squareRoot = (int) Math.sqrt(n);
while (knownPrimes.get(knownPrimes.size() - 1) < squareRoot) {
}
for (int i = 0; i < knownPrimes.size(); ++i) {
int prime = knownPrimes.get(i);
if (prime >= squareRoot) {
break;
}
if (n % prime == 0) {
return false;
}
}
return true;
}

// Takes in a list of the first k primes for some k >= 2 and makes it a list of the first k+1 primes.
for (int i = knownPrimes.get(knownPrimes.size() -1) + 2; true; i += 2) {
if (isPrime(i, knownPrimes)) {
return;
}
}
}``````

This is a simple approach. More sophisticated solutions can be found by looking up "primality test" online.

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.

### 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.