Facebook Interview Question for Developer Program Engineers


Country: India




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

That's a pretty ambiguous question. Could you please elaborate more? What is it meant by any of them not prime? I think you can find 2n+1 prime numbers for any value of n>0.

- Anonymous April 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

public class PrimeFactors {

public PrimeFactors(int n) {
this.run(n);
}

private void run(int n) {
int m = 2 * n + 1;
for (int i = 2; i <= m; i++) {
if (this.isPrime(i))
System.out.println(i);
else
System.out.println(this.primeFactors(i));
}
}

private List<Integer> primeFactors(int numbers) {
int n = numbers;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}

private boolean isPrime(int n) {
for (int i = 2; i <= (int) Math.sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}

public static void main(String[] args) {
new PrimeFactors(10);
}

}

- Thiago Genez May 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code works good...

- kiran May 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

He might be asking you to pick up the prime numbers from 1...2n+1 numbers.
Which are not prime, just print out factors.
Sieve's method might work well here.

// Let's print only the factors >1
void print(int n) {
vector<int>numbers [2*n+1];
int M = 1 + 2 * n;
for (int j=2;j<=M;j++) {
if (numbers[j].size() == 0) // it's prime and print it.
else // Traverse the list and print all the factors
for (int k=j+j;k<=M;k+=j) {
numbers[k].push_back(j);
}
}
}

- IAMBACK May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int num = 10734;
		PrimeCalc pc = new PrimeCalc();
		boolean res = pc.primeCalcMethod(num);
		System.out.println(res);
		// Factorize
		if(!res){
			FactorCalc fc = new FactorCalc();
			fc.factorCalcMethod(num);
		}
		else
		{
			System.out.println(num);
		}
		
	}
public Boolean primeCalcMethod(int num){
		if(num%2 == 0){
			return false;
		}
		else
		{
			for(int i=3;i<13;i++){
				if(num % i == 0 && num != i){
					return false;
				}
			}
		}
		return true;
	}
public void factorCalcMethod(int num){
		while(num != 1){
			if(num % 2 == 0){
				System.out.println(2);
				num = num / 2;
			}
			else{
				for(int i=3;i<=num;i=i+2){
					if(num % i == 0){
						System.out.println(i);
						num = num / i;
						break;	
					}
				}
			}
		}
	}

- To check whether number is prime or not and find it's factors June 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A composite number(a number that has only 2 prime numbers as its factors) is not a prime number, but it will return as a prime number with the code you provided

- juicifruitolic August 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thiago
this section is not clear where n is divided by i..
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;

- nutcracker July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This will do it in O(n^2) using a hashtable using so called Sieve algorithm

#include <iostream>
#include <iomanip>
using namespace std;

#define N 100000

class factors {
    public:
        int value;
        factors * next;
};

void insert(factors **head,int value) {
    factors * myFactor = new factors();
    myFactor -> value = value;
    myFactor -> next = *head;
    * head = myFactor; 
    };  

void printFactors(factors **head, int i){ 
    factors * f = *head;
    cout << i << ": " << setw(2);
    if(f==0) cout << " prime";
    while(f) {
        cout << f->value;
        if(f->next) cout << ",";
        f=f->next;
    }   
    cout << endl;   
};

main()
{
    factors **f = new factors * [2*N+1];
        
    for(int i=2; i < 2*N+1 ; i++) {
        for(int mul=2; (mul*i) < 2*N+1 ; mul++) {
            insert(&(f[i*mul]),i);
        }   
    }   
        
    for(int i=1; i < 2*N+1; i++) {
        printFactors(&f[i],i);
    }   
    }

- mohammad rahimi July 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] a){
for(int i=1; i <= 2*(Integer.parseInt(a[0]))+1; i++){
primeFactor(i);
}
}
static void primeFactor(int n){
if(n==1){
System.out.println("Number 1 is prime");
return;
}

List<Integer> factors = new ArrayList<Integer>();
for(int i = 2; i<= n/2; i++){
if(n%i == 0){
factors.add(i);
}
}
if(factors.isEmpty()){
System.out.println("\nNumber "+n+" is prime");
return;
}
factors.add(1);
factors.add(n);
System.out.print(n+" is not prime factors are:");
for(int factor : factors){
System.out.print(factor+",");
}

}

- BS August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I suppose I found a method work with better time approach(I think this comes from Eratosthenes sieve):

void find_prime_and_print_factors(std::std::vector<int> _return,int n)
{
	int range = 2*n+1;
	std::std::vector<int> num[range];
	for(int i=1;i<range;i++)
	{
		int calnum = i+1;
		if(num[i].isEmpty())
		{
			for(int j=2;j*calnum<=range;j++)
				num[j*calnum-1].push_back(calnum);
			_return.push_back(calnum);
		}else{
			std::cout<<calnum<<": ";
			std::std::vector<int>::iterator itr;
			for(itr=num[i].begin();itr!=num[i].end();++itr)
				std::cout<<*itr<<" ";
			std::cout<<std::endl;
		}
	}
}

- cdtsgsz October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void two_n_1_primes(unsigned n)
{
   unsigned m = (n << 1) + 1;
   for (unsigned p = 2; p <= m; ++p) {
	   unsigned x = p;
	   printf ("%d =", p);
	   for (unsigned j = 2; j * j <= x; ++j) {
		   while (x % j == 0) {
			   printf (" %d ", j);
			   x /= j;
		   }
	   }

	   if (x == p) {
		   printf(" is prime");
	   } else if (x != 1){
		   printf (" %d", x);
	   }
	   printf("\n");
   }
}

- Anonymous October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is not the best one but a normal approach
PrimeFactor(n)
{
int flag=0,i;
for(i=2;i<sqrt(n);i++)
{
if((n%i)==0)
{
print i
flag=1
}
}
if(flag==0) print n
}

void main()
{

for(int i=1;i<2*n+1;i++)
PrimeFactor(i);
}

- brittu April 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brittu,

It seems like this would only find the prime numbers in the interval [1, 2n+1]. We want to find the first 2n+1 primes. Correct me if I'm wrong.

- Anonymous April 30, 2012 | Flag


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