## Ebay Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

If you cannot use floating point approximations, do binary search.

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

This is O(log n), better than the sqrt(n) solutions.

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

Correct! I would use binary search. Here it goes:

``````public bool IsPerfectSquare(int n)
{
if (n == 1) return true;
if (n < 4) return false;

int min = 2;
int max = n / 2;
do
{
int div = (max + min) / 2;
int res = n / div;
if (res * res == n) return true;

if (res < div)
{
min = res;
max = div;
}
else
{
min = div;
max = res;
}
} while (max > (min + 1));
return false;
}``````

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

0+1=1
1+3=4 etc etc
-------------------

``````int count  = 0;
int oddInteger = 1; //So, odd integer will be 1, then 3, then 5, then 7, etc etc

while(count <= N){
if(count == N){
return true;
}

count = count + oddInteger;
oddInteger = oddInteger + 2;
}``````

Runs in O(Sqrt(n)) time I believe.

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

oh and return false if execution goes outside of the while loop.

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

This is an intelligent solution, but still executes N/2 additions. Then, it runs in O(N). I would do a binary search (I posted the code on another answer).

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

the time complexity is o(sqrt(logn)).
for 25
1+3+5+7+9 only sqrt(n) additions will be needed.

Comment hidden because of low score. Click to expand.
2
of 4 vote

``````bool isPerfectSquare(int N)
{
for(int i=0; i*i <= N; i++)
if(i*i == N)
return true;
return false;
}``````

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

This works, but I think they wouldn't accept a solution that runs in O(n). For N==2^31-1, this would take too long.

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

This solution is sqrt(n) not n, :)

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

Right! I was wrong.

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

binary search of (0, x / 2)

``````bool is_sqrt_helper(int x, int from, int to)
{
if (to < from) return false;

int mid = (from + to) / 2;

int r = mid * mid;

if (from == to)
return r == x;

if (r > x)
{
return is_sqrt_helper(x, from, mid - 1);
}
else if (r < x)
{
return is_sqrt_helper(x, mid + 1, to);
}
else
{
return true;
}
}

bool is_sqrt(int x)
{
if (x == 0 || x == 1) return true;
return is_sqrt_helper(x, 0, x / 2);
}``````

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

Here is what I would do in python

``````i = int(raw_input())

sq = int(i ** 0.5)

if sq*sq == i:
print i
print "It is a perfect Square"
else:
print i
print "It is not a perfect Square"``````

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

{ float x = n;
float y = 1;
float e = 0.000001; /* e decides the accuracy level*/
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
}
return x; }

it is Babylonian method for fiinding square root

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

I believe not all integer numbers can be correctly represented as floating point numbers. There are digit-by-digit methods to calculate square root of an integer number (see "Methods of computing square roots" article in wikipedia)

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

/*code in C*/
for(i=1;i<n;i++)
{ if (i*i==n)
{ printf("perfect square");}
else
{ printf("Not a perfect square");}
}

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

Here is code in C#.. I have used uint to make sure N is not negative as square can never be negative. Also if N is 0 return false

``````private static bool isSquare(uint N)
{
if (N == 0)
{
return false;
}
for (int i = 1; i * i <= N; i++)
{
if (i * i == N)
{
return true;
}
}
return false;
}``````

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

int main()
{
int k=0,n,i=1;
cout<<"enter any number:\n";
cin>>n;
if(n==0||n==1)
cout<<"squre root of entered number:"<<n;
else
{
for(i=1;i*i<=n;i++)
{
if(i*i==n)
cout<<"squre root of entered number:"<<i;
k=1;
}
}
if(k==0)
cout<<"entered number dont have perfect squre root:";
return 0;

}

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

int main()
{
int k=0,n,i=1;
cout<<"enter any number:\n";
cin>>n;
if(n==0||n==1)
cout<<"squre root of entered number:"<<n;
else
{
for(i=1;i*i<=n;i++)
{
if(i*i==n)
cout<<"squre root of entered number:"<<i;
k=1;
}
}
if(k==0)
cout<<"entered number dont have perfect squre root:";
return 0;

}

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

Forgot to mention the constraint. solution should work in O(N) time.

This junk site not allowing to edit existing questions. Sorry for the late clarifications.

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

log(N) time. sorry again.

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

``````/*
This will run in logarithmic time.
*/
public boolean isPerfectSquare(Integer input) {

// note - this method ignores the possibility of integer overflwo.
boolean flag = false;
int value = 1;

// the number we multiply the upperlimit with as we search for the
// limits that bound the input from above and from below.
int factor = 2;

// the limits that bound the input from above and below
int lowerLimit = 0;
int upperLimit = 1;

// determine the limits within which binary search is to be done.
while (input > upperLimit * upperLimit) {
lowerLimit = upperLimit;
upperLimit = upperLimit * factor;
}

// the do th binary search
if (!flag) {
while (lowerLimit < upperLimit) {
value = (lowerLimit + upperLimit) / 2;
int valueSquare = value * value;
if (valueSquare > input) {
upperLimit = value-1;
}
else if (valueSquare < input) {
lowerLimit = value+1;
}
else {
flag = true;
break;
}
}
}

return (flag);
}``````

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

The below code runs in O(logN) time.

``````bool isSqrRoot(int n)
{
for(int i=1;i<n/2;i++)
{
if((i*i)==n)
return true;
}
return false;

}``````

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

I guess this is O(n^0.5), what do you think?

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

This needs n/2 multiplications, so it's O(N)

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

log base 2(N) is O(root(n)) .so it log base 2.however generic representation is O(n^0.5).

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

#include<stdlib.h>
#include<stdio.h>
void main()
{
int a,i;
printf("enter number:--");
scanf("%d",&a);
for(i=0;i*i>a;i=i/2);
for(;;)
{
if(i*i==a)
{
printf("perfect square\n");
exit(0);
}
if(i*i>a)
break;
i++;
}
printf("not perfect square\n");
}

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

Couldn't you find the fast inverse square root and then find the reciprocal of that?

www . codemaestro . com / reviews / 9

Single function, called once. O(1).

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

#include<stdio.h>
#include<conio.h>
int main()
{
int i,N;
printf("enter the number you want to check.\n");
scanf("%d",&N);
for(i=1;i<=N;i++)
{
if(N=i*i)
printf("the number is a perfect square.");
else
printf("the number entered is not a perfect square.");
}
return (0);
}

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

public class PerfectSquare {

public static void main(String[] args) {
int n= 144;
PerfectSquare ins = new PerfectSquare();
System.out.println("is "+n+" is perfect square : "+ins.isPerfectSquare(n));
}

public boolean isPerfectSquare(int n){
for(int i=0;i*i <=n;i++){
if(i*i == n){
return true;
}
}
return false;
}

}

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

``````#!/bin/python3

def perfect_square(n):
square = n ** 0.5
return square * square == n``````

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

static void Main(string[] args)
{
Console.WriteLine("Result = " + calcSQRT(2)); //Test Call;
Console.WriteLine("End");
}

static Double calcSQRT(int square, int overAllPrecision = 32)
{

int[] pairArray = getPairsArray(square);
String resultBuffer = "";

int currentIndex = 0;
BigInteger A = new BigInteger(pairArray[pairArray.Length - currentIndex - 1]);//BigInteger is from the System.Numerics
BigInteger y = new BigInteger(0);
while (true)
{
int i = 0;
while ((A - (10 * y + 2 * (i + 1) - 1)) >= 0)
{
i++;
A = A - (10 * y + 2 * i - 1);

}

if (currentIndex == pairArray.Length)
resultBuffer = resultBuffer + ".";

resultBuffer = resultBuffer + i;
currentIndex++;

if (currentIndex > overAllPrecision) break;

if (A == 0)
if (currentIndex >= pairArray.Length)
break;
A = 100 * A;
if (currentIndex < pairArray.Length)
A = A + pairArray[pairArray.Length - currentIndex - 1];

if (currentIndex == 1)
y = 2 * i;
else
y = 10 * y + 2 * i;
}

return Double.Parse(resultBuffer);

}

private static int[] getPairsArray(int square)
{
int[] pair = new int[1];
int count = 0;
while(square > 0)
{

int digit = square % 10;
square = square / 10;
if(square > 0)
{
digit = (square % 10) * 10 + digit;
square = square / 10;
}
if (count > 0)
Array.Resize(ref pair, count + 1);
pair[count] = digit;
count++;
}
return pair;
}

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

``````static void Main(string[] args)
{
Console.WriteLine("Result = " + calcSQRT(2)); //Test Call;
Console.WriteLine("End");
}

static Double calcSQRT(int square, int overAllPrecision = 32)
{

int[] pairArray = getPairsArray(square);
String resultBuffer = "";

int currentIndex = 0;
BigInteger A = new BigInteger(pairArray[pairArray.Length - currentIndex - 1]);//BigInteger is from the System.Numerics
BigInteger y = new BigInteger(0);
while (true)
{
int i = 0;
while ((A - (10 * y + 2 * (i + 1) - 1)) >= 0)
{
i++;
A = A - (10 * y + 2 * i - 1);

}

if (currentIndex == pairArray.Length)
resultBuffer = resultBuffer + ".";

resultBuffer = resultBuffer + i;
currentIndex++;

if (currentIndex > overAllPrecision) break;

if (A == 0)
if (currentIndex >= pairArray.Length)
break;
A = 100 * A;
if (currentIndex < pairArray.Length)
A = A + pairArray[pairArray.Length - currentIndex - 1];

if (currentIndex == 1)
y = 2 * i;
else
y = 10 * y + 2 * i;
}

return Double.Parse(resultBuffer);

}

private static int[] getPairsArray(int square)
{
int[] pair = new int[1];
int count = 0;
while(square > 0)
{

int digit = square % 10;
square = square / 10;
if(square > 0)
{
digit = (square % 10) * 10 + digit;
square = square / 10;
}
if (count > 0)
Array.Resize(ref pair, count + 1);
pair[count] = digit;
count++;
}
return pair;
}``````

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

``````public boolean isPerfectSquare(int n) {
int sum = 0;
if(n == 0 || n<0) {
return false;
}
else if(n ==1){
return true;
}
else {
for(int i=1;i<n;i+=2){
sum = sum+i;
if(sum == n)
{
return true;
}
}
return false;
}
}``````

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.