Amazon Interview Question for Interns


Country: India




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

I know the question was for C, but for simplicity, I coded up in ruby. Should be similar in C

def sqrt_with_accuracy(x,init_guess,accuracy)

  next_guess = 0.5*(init_guess + x/init_guess)
  if (init_guess - next_guess).abs <= accuracy
    return next_guess
  else
    sqrt_with_accuracy(x, next_guess, accuracy)
  end
  
end
puts sqrt_with_accuracy(30, 5, 0.01)

Based on newton raphson method.
How fast it produces an answer, depends on your initial guess. One can use a lookup table for that or simply default the init_guess to 1. If one does not want to pass arguments except for x, one can write a wrapper around this code.
For more on NR method, check out this video:
http://mathforcollege.com/nm/videos/youtube/03nle/newtonraphson/newtonraphson_03nle_squarerootnewtonraphson.html

- swap1712 August 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
5
of 5 vote

Newton-Raphson method

def sqr3(n):
...     k = 1.0
...     while((k*k - n) > 0.0000000001 or (n - k * k) > 0.0000000001):
...             k = (k + n / k) / 2
...     return k

- xiang.zh August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

say you want to find the square root of 2:

1)(1+2/1)/2=1.5;
2)(1.5+2/1.5)/2=1.4xyz,
3)(1.4xyz+2/1.4xyz)/2=1.4abc,
4).......
5)you will get 1.414..

- Charles January 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

#include <stdio.h>

int main()
{
	int n;
	printf("Enter your number:");
	scanf("%d", &n);
	
	int s;
	for(s = 1; s*s <= n; s++);
	s--;
	
	double x;
	for(double d = 0.001; d < 1.0; d+= 0.001)
	{
		x = (double)s + d;
		if((x*x > (double)n))
		{
			x -= 0.001;
			break;
		}
	}
	
	printf("square root is %.3lf\n", x);
	
	return 0;
}

- Sunny Mitra August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please the code whats the logic behind ..?

- rinku August 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

please explain the code whats the logic behind the program..?

- rinku August 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Below is a code that computes the square root of an integer and only returns the integer part. However this can be generalized to return floating point also ( by defining some error margin) . I just wanted to discuss about the idea. The idea I used is binary search. The squares of the natural numbers are already sorted , for example, 1,4,9,16.. and so on. So initially low = 1, and high = n. And in every iteration calculate mid = (low+high)/2 and check if (mid*mid) is less than , greater than or equal to the given element and update the mid value accordingly.

#include<stdio.h>
int square_root_binary_search(int elt)
{
    int low,high,mid;
    low=1;
    high=elt;
    while(low<=high)
    {
        mid = (low+high)>>1;
        if(mid*mid == elt) return mid;
        if(mid*mid > elt)
            high = mid -1 ;
        else
            low = mid + 1;
    }
    return high;
}
int main()
{
    int elt;
    printf("Enter the number");
    scanf("%d",&elt);
    printf("The square root is %d\n",square_root_binary_search(elt));
    return 0;
}

- Anonymous August 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above code has a compilation error in the statement mid = (low+high)>>;1;
an extra semicolon is there. The rest is fine. The complexity of this code in O(logn). However if you want to return the exact square root then you need to define some error margin, say "e". In that case the complexity will be O(log(n/e)).

- rajdeepgupta20 August 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u plz tell me the logic

- nk May 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You can use binary search. having low=1 and high = n initially. The idea of binary search works because the squares of natural numbers are sorted ( like, 1^2, 2^2, 3^2 , and so on)

- Anonymous August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sqrt(x)=sqrt(s)+(x-s)/2sqrt(s)
s is the closest no sq
suppose x=75 so s=81 we the result

- anjali August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

float sqrrt( int a) // for a>3
{
int b;
float temp,temp2=0;
cout<<"Enter the number of decimal precision :";
cin>>b;
for(int i=1; i<=a/2;i++)
{
if(i*i>a)
{
temp=i-1;
break;
}
temp2=temp;
for(i=1;i<=b;i++)
{
for(float j=0;(temp2*temp2)<a;j++)
{
temp2=temp1;
temp2=temp2+ (j/(10^i));


}
temp2=temp;
temp2=temp2+ ((j-1)/(10^i));

temp=temp2;
}

return temp;
}

- HerCules August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can anyone explain your method briefly with time complexity?? pl....

- saran August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

float i,n;
n is number 4 which v want square root
for(i=0;i*i<n;i=i+0.0001){}
printf("%.4f",i);
i will be d square root

- krishnan August 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be done in an other way too
when given a number, start subtracting all the odd numbers from it sequentially
if we get a 0 in the end, the number is a perfect square, and the number of times the subtraction is performed, is the square root of the number
even though this approach is not good for very big integers, it will work fine for small ones

e.g 25
25-1=24
24-3=21
21-5=16
16-7=9
9-9=0

this means that 25 is a perfect square and 5 is the square root

- akansha jain August 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I really liked your solution can you please tell me what is the logic

- Rajesh September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please explain the above logic for 36 ?

- vamsha November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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


void main()
{
float a,b,n=47;
clrscr();
a=n;
do
{
b=a;
a=(a+n/a)/2;

}while(a!=b);
printf("%f",a);
getch();
}

- vinay singh September 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good wrk

- anu October 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use NEWTON RAPSON METHOD

- ATUL September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
void main(){
	int num,i,c=0;
	clrscr();
	printf("\nEnter the number \t:");
	scanf("%d",&num);
	for(i=1;num>0;i+=2){
		num-=i;
		c++;
	}
	if(num==0){
		printf("\nSQRT(%d)=%d",c*c,c);
	}
	else{
		printf("\nGIVEN NUMBER IS NOT A PERFECT SQUARE");
	}
	getch();
}

- vishnu s soman October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Note: Java Code & running for all cases:
Case 1: Negative number
Case 2: 0<=n<=1
Case 3: n>1

public static double sqrtMethod3(double a)
    {
        //firstly check if a is non-negative value
    if(a<0)
        return -1;
    
    //also check if a==0 or a==1 because in these two cases sqrt(a) = a
    if(a==0 || a==1) return a;

    //now start the core part of the code
    double precision = 0.0000000000001;//define the precision, so we stop when precision is achieved
    
    double start = 0;
    double end = a;
    
    //we define these two start/end values because usually 0<sqrt(a)<a
    //however, if a<1; then 0<a<sqrt(a)
    if(a<1)
        end = 1;

    //define a loop to continue if the precision is not yet achieved
    while(end-start>precision)
    {
       // System.out.println("end-start = "+(end-start));
      //  System.out.println("precision = "+precision);

    double mid = (start+end)/2;
    double midSqr = mid*mid;
    
    if(midSqr==a)
        return mid;//we find the exact sqrt value!
    else if(midSqr<a)
        start = mid;//we shift our focus to bigger half
    else 
        end = mid;//shift focus to smaller half
    }

    
    //if we did not find exact sqrt value, we return the approxiated value with the defined precision
    return (start+end)/2;
   
  }

- codeAddict January 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* i is integer entered for squaring */
int Root(int i)
{
int Square, c=1, Temp=1, Temp2=1;
do
{
Temp=Temp+1;
Temp2=Temp*Temp;

}
while (Temp2!=i);
Square=Temp;
return Square;
}

- Using INTEGER. February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ok

- maddy June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is update to my previouus commenrt dated 14 july



int main()
{


int t;
scanf("%d",&t);
int input[10001];
char temp_s[25];
for(int k=0;k<t;k++) {
int n,query;
LL temp_res=0,x_ll;
double x_d;
scanf("%d%d",&n,&query);

for(int i=0; i<n; i++) {
scanf("%d",&input[i]);
if(input[i]<0) input[i]+=MOD;
temp_res = (temp_res+input[i])%MOD;
}
for(int i=0; i<query; i++) {
scanf("%lld",&x_ll);
sprintf(temp_s,"%lld",x_ll);
sscanf(temp_s,"%lf",&x_d);
LL ans=temp_res,temp_ans;
int index=1;

while(1) {
if(x_ll == 1) break;
if(index == 1) temp_ans=x_ll;
else {
temp_ans=pow(x_d,1.0/index)+1e-7;
if(pow(temp_ans,index)>x_d) temp_ans--;
}
if(temp_ans == 1) break ;
temp_ans--;
temp_ans=temp_ans%MOD;
ans = (ans+(input[index-1]*temp_ans)%MOD)%MOD;
index++;
}
cout<<ans<<" ";
}
cout<<endl;
}
return 0;
}

- maddy June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Update to code helpful to solve maxpr problem in codechef
for(int i=1; i<n; i++) {
for(int d=0; d<=a[i]; d++) {
dp1[a[i]][d] = (dp1[a[i]][d] + dp1[a[i]-d][d])%M;
if(!d) dp1[a[i]][d] = (dp1[a[i]][d]+1)%M;
if(d) dp1[a[i]][d] = (dp1[a[i]][d]+freq[a[i]-d])%M;
}
for(int d=1; d+a[i]<=100; d++) {
dp2[a[i]][d] = (dp2[a[i]][d] + dp2[a[i]+d][d])%M;
dp2[a[i]][d] = (dp2[a[i]][d]+freq[a[i]+d])%M;
}
freq[a[i]]++;
total = (2*total)%M;


/*for(int k=0; k<=4; k++) {
for(int j=0; j<=3; j++)
cout<<dp1[k][j]<<" ";
cout<<endl;
}
}
int ans=total-1;
int ans1=0,ans2=0;
for(int i=0; i<=100; i++)
for(int d=0; d<=100; d++) {
ans1 = (ans1+dp1[i][d])%M;
ans2 = (ans2+dp2[i][d])%M;
}

ans = ans-ans1; if(ans<0) ans += M;
ans = ans-ans2; if(ans<0) ans += M;

- saurabh June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<stdio.h>

using namespace::std;

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n;
scanf("%d",&n);
int temp=0,max=0;
for(int i=0; i<n; i++) {
int a;
scanf("%d",&a);
if(a) temp++;
else {
if(max<temp) max=temp;
temp=0;
}
}
if(max<temp)
max=temp;
printf("%d",max);
return 0;
}

- CHEF problem June 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void main()
{
float num,temp=0,sq;
clrscr();
printf("enter value for n");
scanf("%f",&num);
sq=num/2;
while(sq!=temp)
{
temp=sq;
sq=(num/sq+sq)/2;
}
printf("square root of %f is %f",num,sq);
}

- Prasad s bhat September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thnx for programs

- Anjali February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void main()
{
float num,temp=0,sq;
clrscr();
printf("enter value for n");
scanf("%f",&num);
sq=num/2;
while(sq!=temp)
{
temp=sq;
sq=(num/sq+sq)/2;
}
printf("square root of %f is %f",num,sq);
}

- Anonymous April 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i wrote code in Ruby.

def sqrt(num)
    k = 0
    s = 1.0
    kmax = 10000
    while k < kmax
        prev = s.to_f
        s = (s + num/s) / 2
        if prev == s
            break
        end
    end
    puts "#{s}"
end

sqrt(67476767668888989898989)

- prem.patel3105 July 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can I get a program for sunny numbers.
A number is said to be sunny when root of n+1 is an integer i.e.,example 3+1=4 which is the root of 2.Therefore 4 is a sunny number

- Redbug September 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>


/*Returns the square root of n. Note that the function */
float squareRoot(float n)
{
/*We are using n itself as initial approximation
This can definitely be improved */
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;
printf("%f == %f\n",x,y);
}
return x;
}


void main(){

float ab;
printf("enter the number\n");
scanf("%f",&ab);
printf("%lf this is the float vallues\n",squareRoot(ab));
printf("original values==%lf\n",squareRoot(ab)*squareRoot(ab));
}

- Kasim Hyderabad December 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <math.h>
main()
{
//Input
double x,y;
printf("Please input a real number:");
scanf(“%lf”,&x);
//Process
y = sqrt(x); //Output
printf("The square root of %lf is %lf.\n",x,y);

- Apon March 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can use Babylonian Method..
#include<iostream>
using namespace std;
float squareroot(float n)
{
float x = n;
float y = 1;//can be other constant
float e = 0.000001;
while(x-y>e){
x =(x+y)/2;
y = n/x;

}
return x;
}
int main()
{
int n;
cout<<"Enter the number"<<endl;
cin>>n;
cout<<squareroot(n)<<endl;
return 0;
}

- Tanim Ahmed May 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
float squareroot(float n)
{
    float x = n;
    float y = 1;//can be other constant
    float e = 0.000001;
    while(x-y>e){
        x =(x+y)/2;
        y = n/x;

    }
    return x;
}
int main()
{
    int n;
    cout<<"Enter the number"<<endl;
    cin>>n;
    cout<<squareroot(n)<<endl;
    return 0;
}

- Tanim Ahmed May 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
float squareroot(float n)
{
    float x = n;
    float y = 1;//can be other constant
    float e = 0.000001;
    while(x-y>e){
        x =(x+y)/2;
        y = n/x;

    }
    return x;
}
int main()
{
    int n;
    cout<<"Enter the number"<<endl;
    cin>>n;
    cout<<squareroot(n)<<endl;
    return 0;
}

- Tanim Ahmed May 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

for(i=0;i<n/2;i++)
check if any number sq is that number

- mani 4m sklm August 12, 2013 | 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