## Ebay Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

I guess following is optimized code for finding prime..which is certainly not O(N^2)

``````import java.util.ArrayList;
import java.util.List;

public class PrimeFinder {
public int findNthPrime(int n) {
if (n < 0) {
throw new RuntimeException("Invalid argument :" + n);
}
List<Integer> primeNoList = new ArrayList<Integer>();
int primeNo = 2;
boolean iterateOverPrimeNoList = true;
int primeListCnt = 0;
int num = primeNo + 1;
int denominator = primeNo;
int primeCnt = 0;
while (primeCnt < n) {
System.out.println("main loop interation cnt : " + primeCnt);
primeListCnt = 0;
iterateOverPrimeNoList = true;
// check if next num is not divisible by all prime numbers which are
// less than equal to sqrt of num
while (primeListCnt < primeNoList.size() && iterateOverPrimeNoList) {
denominator = primeNoList.get(primeListCnt);
System.out.println("check num :" + num + " divisible by : " + denominator);
if (num % denominator == 0) {
num++;
primeListCnt = 0;
} else {
denominator = (primeListCnt + 1) < primeNoList.size() ? primeNoList.get(primeListCnt + 1) : denominator;
if (denominator <= Math.sqrt(num)) {
primeListCnt++;
} else {
iterateOverPrimeNoList = false;
}
}

}

primeCnt++;
primeNo = num;
System.out.println(primeCnt + " nth Prime no:" + num + " found ");
num++;

}
System.out.println(primeNoList);
return primeNo;
}

public static void main(String[] args) {
System.out.println(new PrimeFinder().findNthPrime(10));
}
}``````

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

This code seems optimized. Can anyone tell me what is the time complexity of above code?

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

When you are increasing the count for prime no. you can increase it by 2, to avoid checking for even numbers

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

this is the most optimized code i could think of....

am a fresher so would like a review
thank you

``````public class nth_prime_no {

public static void main(String... args){
int n = 0;

int j =3;
int count=0;

Scanner s=new Scanner(System.in);
System.out.println("enter the position of prime no");
n=s.nextInt();
int pn[] =new int[n];
pn[0]=2;
for(int i=1;i<n;i++){
while(j>=3){
for(int k=0;k<i;k++)
if(j%pn[k]==0)
count++;

if(count==0){
pn[i]=j;
break;
}
j++;
count=0;
}

}
System.out.println("nth prime no is"+pn[n-1]);
}``````

}

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

thats me

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

Stop upvoting yourself in public.

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

i am not upvoting
i need a review
please if you can guide me do so

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

try to find 10000th or more prime no for comparison with other algos
e.g.
long start = System.currentTimeMillis();
System.out.println(new PrimeFinder().findNthPrime(10000));
long end = System.currentTimeMillis();
System.out.println(" time 1: " + (end - start));

start = System.currentTimeMillis();
prime(10000); /*assuming ur code is in prime method*/
end = System.currentTimeMillis();
System.out.println(" time 2: " + (end - start));

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

#include<stdio.h>
#include<conio.h>

int main()
{
int n=0,i=0,j=0,count=0,flag=0;

printf("\nwhich prime number you want ?? ");
scanf("%d",&n);

i=1;
do
{
i++;
flag=0;
for(j=2;j<i;j++)
{
if(i%j == 0)
{
flag=1;
break;
}
}

if(flag == 0)
count++;
}while(count != n);

printf("%d is prime number you wanted !! ",i);
getch();
return 0;
}

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

``````package PractiseApps;
import java.util.*;
import java.lang.*;
public class NthPrime {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int i=3;
N--;
boolean flag = true;
if (N<0){
System.out.print(2);
}
else{
while(true){
int j=2;
while(j<=Math.sqrt(i)){
if(i%j==0)
{
flag=false;
break;
}
j++;
}
if(flag)
{
N--;
if (N<0){
System.out.print(i);
break;
}
}
i++;
flag = true;
}
}
}

}``````

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

One way would be the using the sieve of eratosthenes and then simply looking up the number in the result. The algorithm can run in O(N), but the naive implementation runs in O(N^2) I think.

Another way (wwwDOTpaul-scottDOTcomSLASHnth-primeDOTphp) would be to actually count all the primes. For every odd number n (since evens can't be prime after 2) iterate through all primes up until sqrt(n) and see if they are a factor of the new number, if you find one the number is not prime, else it is so increment your count and keep looking until you've found enough primes. Since there are approximately logN prime numbers (I think?) that would involve N*logN calculations (since you try to divide every number by the logN primes you've found so far).

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

Use trial division rather than the sieve. This is due to the fact that you don't know the value N will be and you cant know the number of values you will need to mark in order to find it so this is infinitely large. Rather find the primes in order till you get to N. Use the previous primes to help you find future primes by trial division.

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

I think the following algo should work.

1. Compute the primes using sieve of Eratosthenes, upto m. Set m initially to a small number as 2 or 3.
2. If n < m then return the nth prime else set m = m^2 and repeat steps 1 & 2, each time re-using the previously computed sieve.

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

The following optimizations can be done
1> Prime numbers apart from 2 are all odd numbers
2> To check whether a number is prime it suffices to check numbers from 2 to sqrt of number
3> Any number can be broken down to product of prime factors

So while iterating to find nth prime number over the range of numbers, we need to consider only odd numbers greater than 2 and also for any number to check if its prime we need to check if its divisible without remainder by all prime numbers less equal to square root of the number.

Please suggest if we can have further improvement.

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

Assuming same function called multiple times

``````import java.util.Vector;

/*
* To get the nth prime number , say if n=0, return 2, n=1, return 3 and so on
*
*  Here i am using the scenario where same function might be called multiple times during single execution
*  Not handled Exception is range of int
*/

public class PrimeTester {
private static Vector<Integer> objVector = new Vector<Integer>();

public static int getnthPrime(int n)
{

if( n < 0 )
throw new IllegalArgumentException("Illegal Arument = " + n);

//Now check if the objVector has already the prime number. Consider the scenario when same call is made multiple times
if( objVector == null || objVector.size()==0)
{
}

int intVectorSize = objVector.size();
if ( intVectorSize > n )
return objVector.get(n);

//Keep on finding prime numbers till n is meet
//Find next prime
int item = objVector.get(intVectorSize-1);
while ( intVectorSize <= n )
{
item = item + 2;
if(isPrime(item))
{
intVectorSize++;
}
}

return objVector.get(intVectorSize-1);
}

private static boolean isPrime(int item)
{
for (int i=0 ; i < objVector.size(); i++)
{
if( (item%(objVector.get(i))) == 0 )
return false;
}
return true;
}

}``````

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

Another optimization can be in isPrime. We need to iterate for loop till item /2 > objVector.get(i)

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

``````import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
* CALCULATE THE NTH PRIME NUMBER
*
* @author Jeyabarani K S
*
*/
public class Prime {

public static Map<Integer, Boolean> table = new TreeMap<Integer, Boolean>();

public boolean isNumberPrime(int number) {

if (number<2) {
return false;
} else if (number==2) {
return true;
} else if (number%2==0) {
return false;
} else {

if(checkIfNumberPresentInTable(number)) {
return table.get(number);
} else {
// only need to check till its square root ... since atleast one divisor (if exist) should be less than the square root of the number
int tmp = (int) Math.sqrt(number);

while(tmp>2) {

if(tmp%2==0)
tmp--;

if(number%tmp==0) {
table.put(number, false);
return false;
}

tmp = tmp -2;

}

table.put(number, true);
return true;
}
}

}

if (n>1) {
while(n>0) {
n--;
}
}
}

}

private boolean checkIfNumberPresentInTable(int number){
if (table.containsKey(number))
return true;
else
return false;
}

public static void main(String args[]) {
Prime prime = new Prime();

// calculate nth prime number

System.out.println();
System.out.println();

// prints the primes less than 100
for(int i=0; i<100; i++) {
if(prime.isNumberPrime(i))
System.out.print(" " + i);
}

}

}``````

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

The most optimized code I can think of.

The key point is establish a list of primes and fill it until the size increase to n.
And I add 2 to num at a time as odd numbers can't be prime numbers.

``````int findNthPrime( int N ){

int prime = 2;
int num = 3;

list<int> primes;
primes.push_back(2);

while( primes.size() < N){

for( list<int>::iterator it = primes.begin(); it != primes.end() && *it <= (int) sqrt( num ); it++ ){

if( num%(*it) == 0 ){
num += 2;
it = primes.begin();
}
}

primes.push_back(num);

num += 2;
}

return primes[N];
}``````

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

Time Complexity O(n2) and Space Complexity O(n) but very few computations.
Basic Logic: Prime No greater than 3 are of the form (6n-1) or (6n+1) and
The given number is a prime number if it is not divisible by any prime number less than its square root

``````public int findNthPrime(int N){
// Prime No greater than 3 are of the form (6n-1) or (6n+1)
// Cover base case of 2 and 3
if(N < 0){
return -1;
}if(N == 0){
return 2;
}else if(N == 1){
return 3;
}

int count = 2;
// The given number is a prime number if it is not divisible by
// any prime number less than its square root
int lastIndex = 0;
while(count <= N){
int n = (6*(lastIndex+1)-1);
int m  = n +2;
int sqrt = (int) Math.sqrt(n);
if(i > sqrt){
count++;
break;	// Prime number found!
}
if(n%i == 0){
break;  // Not a prime number
}
}
if(count <= N) {
sqrt = (int) Math.sqrt(m);
if(i > sqrt){
count++;
break;	// Prime number found!
}
if((m)%i == 0){
break;  // Not a prime number
}
}
}
lastIndex++;
}
}``````

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

``````public static int nthPrime(int n) {
if(n == 0)
return 2;
if(n == 1)
return 3;
if(n == 2)
return 5;
boolean[] a = new boolean[n*n];

a[2] = true;

int k = 0;
int i = 2;
while(i < a.length) {
if(!a[i])  {
k++;
}
if(k == n)
return i;
for(int j = 2; j <= i && j*i < a.length; j++)
a[i * j] = true;
i++;
}
return i - 1;
}``````

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

package interv.eBay;

import java.util.ArrayList;

public static void main(String[] args) {
ArrayList<Integer> output = fpN.findNprimes(7);
for(int i: output)
System.out.print(i+" ");
}

private ArrayList<Integer> findNprimes(int n) {
// TODO Auto-generated method stub
if (n <= 0)
return null;
else {
ArrayList<Integer> output = new ArrayList<Integer>();
n--;
boolean isPrime =true;
int currentTestNumber = 3;
while (n > 0) {
for (int i : output) {
isPrime = true;
if (i > Math.sqrt(currentTestNumber))
break;
else if (currentTestNumber % i == 0) {
isPrime = false;
break;
}
}
if(isPrime)
currentTestNumber +=2;
n--;
}
return output;
}

}

}

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.