Expedia Interview Question for Software Engineer / Developers






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

isnumberprime(int x)
for (int i = 0; i < x; i++)
for (int j = 0; j < x; j++)
if (i * j == x)
return false;
return true;

- Trooper December 15, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why you need to caculate gcd here. Just take mod.

- Noname January 07, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Your gcd doesn't work...it will always return n. You could use mod, but you'd still have to mod by all numbers 1->sqrt(n). So it's no less brute force.

But just an update for those who don't know, primes is in P.

- Anonymous February 18, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something like this:

bool is_prime(int num){
    if(num<=3)return true;
    if(num%2==0)return false;
    for(int i=9;i<num;i+=2)
        if(num%i==0)return false;
    return true;
}

- zzz100 February 25, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Apply your algorithm for 15.

- Sanjay June 04, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something like this:


bool is_prime(int num){
if(num<=3)return true;
if(num%2==0)return false;
for(int i=9; i < n;i+=2)
if(num%i==0)return false;
return true;
}

- zzz100 February 25, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool is_prime(int num)
{
if(num<=3)return true;
if(num%2==0)return false;
for(int i=5; i <=num/2;i+=2)
{

if(num%i==0)return false;
}
return true;


}

- This should work: February 28, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it can be made more efficient:
bool is_prime(int num){
if(num<=3)return true;
if(num%2==0)return false;
for(int i=5; i < sqrt(n);i+=2) //beyond sqrt(n)
if(num%i==0)return false; //no num can
return true; //divide n
}

- Ravi Kant Pandey April 09, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code snippet is highly inefficient:

Dont call sqrt(n) in for loop, because is possible to store the value for sqrt(n) in the local variable and then compare it with i.

There is multi exit point in the function, so it is good practice to have sigle exit point in the funtion and that should be at the end of the program. The reason for this is that for bigger functions it is difficult to debug the multi exit function.

The code should be:

bool isPrime(int n)
{
bool flag = true;
int temp = sqrt(n);
if(n <= 3)
{
flag = false;
}
else if( n % 2 == 0)
{
flag = false;
}
else
{
for(int i = 5; i< temp; i+=2)
{
if(n % i) == 0)
{
flag = false;
break;
}
}
}
return flag;
}

- sanjay June 04, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

good talks in the site guys.

- Trooper April 12, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

to test if a number is prime divide it by all the primes smaller than its square root

- Sunaina May 22, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But to find all smaller prime number less than sqrt(n) is in efficient.

Its time complexity will be:
O(sqrt(n)) + O(sqrt(n-1)) + ......

But yes u can build a program that can learn from experience, the more u use the program the more it becomes efficient, but this too is space inefficent.

I mean to say that u can build a program that can memorize all the prime factor less than n. Now suppose if the function is called for value less than n, then the function already have all the prime factor less than n, but if the function is called for greater than n, then it will first find all the remaining prime factor and memorize it for the further references.

- Sanjay June 04, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a=2038074743;
int n=1;
int low,high;
low = (6*n)-1;
high = (6*n)+1;
if(a<=3) cout<<"Prime"<<endl;
else
{
while(low<=a)
{
if((a-low) == 0)
{
cout<<"Prime"<<endl;
break;
}
if(high<=a)
{
if((a-high) == 0)
{
cout<<"Prime"<<endl;
break;
}
}
n++;
low = (6*n)-1;
high = (6*n)+1;
}
}
if(low>a)
cout<<"Not Prime"<<endl;

- goku October 28, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does not work....try 25

- goku December 03, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool IsPrime(int number)
{
if (number < 2) return false;

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

- Sathvik February 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isPrime1(int num) {
boolean prime = true;
System.out.println(num);
int limit = (int) Math.sqrt(num);
for (int i = 2; i <= limit; i++) {
if (num % i == 0) {
prime = false;
break;
}
}

- Barani February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

///
int temp = n;
for(int i=2;i<temp;i++){
if(n%i == 0)


}
\\\

- Cracker June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

///
int temp = n;
for(int i=2;i<temp;i++){
if(n%i == 0)


}
\\\

- Cracker June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

///
int temp = n;
for(int i=2;i<temp;i++){
if(n%i == 0)
return false;
temp = n/i;
}
\\\

Will this work? someone please look at it.

- Cracker June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean isPrime(int value){

for(int i=2; i<= value/2 ; i++){
if(value%i == 0){
return false;
}
}


return true;
}

- javaGirl April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

A slightly less brute-forced way would be to use Euclid's algorithm, and recognize that n is never divisible by m if m > sqrt(n):

int gcd(int a, int b)
{
if (b == 0)
return a;

return gcd(a, a % b);
}

int isPrime(int n)
{
int sqrt_n = sqrt(n);
int i;
for (i = 2; i < sqrt_n; i++)
{
if (gcd(n, i) > 1)
return FALSE;
}

return TRUE;
}

I'm sure there are better ways to do it than that, too.

- Nex3 December 16, 2006 | 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