Goldman Sachs Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

The first answer in this thread can be optimised further .
Here is the code

#include<iostream.h>

int power(int a,int b)
{
int temp;
if(b==0)
return 1;
temp=power(a,b/2);
if(b%2==0)
return(temp*temp);
else
return(temp*temp*a);
}

void main()
{
	int a,b;
cout<<"\nenter no.\n";
cin>>a;
cout<<"\nEnter power\n";
cin>>b;
cout<<a<<"^"<<b<<"="<<power(a,b)<<endl;
}

- Mahendra Pratap Singh June 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is great..

- amnesiac June 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one..

- Vignesh June 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well your code doesn't work when the power is negative (i.e for negative b). You just have to change it a little bit. Add two lines to the code and everything will be ok.

if(b%2==0)
          return(temp*temp);
else {
     if(b > 1) {
          return(temp*temp*a);
     }
     else {
          return ((temp * temp)/a);
     }
}

- Spock July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

With those two lines it will work only when the power is negative even, not for odd.
What about this code to fix it?

#include <iostream>

double power(int a,int b)
{
  std::cout<<a<<"^"<<b<<";";
  double temp;
  bool signedExp(b<0?true:false);

  b=abs(b);
  if(b==0)
  {
    return 1;
  }
  temp=power(a,b/2);
  if (!signedExp)
  {
    if(b%2==0)
    {
      return(temp*temp);
    }
    else
    {
      return(temp*temp*a);
    }
  }
  else
  {
    if(b%2==0)
    {
      return(1/(temp*temp));
    }
    else
    {
      return (1/(temp*temp*a));
    }
  }
}

int main()
{
  int a(5),b(-5);
  std::cout<<a<<"^"<<b<<"="<<power(a,b)<<std::endl;
}

- juan.jose.martin.marcos.gomez August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think we have to deal with negative power. For a^b, We deal with the absolute value of the power |b|. After we calculating c = a^|b|, if b > 0 then return c else return 1/c.

- wenbinzhjl October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

lets take example
2^10 --> 2^9 * 2 ^1 --> 2^3 * 2^3 * 2^3 * 2^1
Algo:
1. Find nearest square root of power and remainder.
2. Calculate number ^ square root using multiplication and store it. Here 2^3 using multiplication.
3. Again find stored number ^ square root power. Here 2^3 is 8. So get 8 ^3 using multiplication that is 8 *8 *8.
4. Now multiply result with remainder of power. Here it is 512 * 2^1

- sanjay.kr.maurya June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think we can do it using divide and conqueror algorithm ( O(log(n)) ).
If n is odd then
func(n/2)*func(n/2)*n;
else
func(n/2)*func(n/2);

- Pranay Singhania June 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

HashMap<Integer, Long> hmap=new HashMap<Integer, Long>();
	 long power(int a, int b) {
		if (b == 0)
			return 1;
		if (b == 1)
			return a;
		if(hmap.containsKey(b))
			return hmap.get(b);
		long p = power(a, b / 2) * power(a, b / 2);
		if (b % 2 == 1)
			 p=p*a;
		hmap.put(b, p);
		return p;
	}

uses DP also

- salvo4u June 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I just saw Hashmaps and DP and stopped right there.

- eugene.yarovoi June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hmmm...well, I guess that makes sense. If you want to do it using pure recursion + memorization...still, check out some of the other solutions, they do it much more simply. You also could have just used long p = power (power(a, b / 2), 2), and there would have been no need for DP.

- eugene.yarovoi June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution has a bug. A small fix can resolve this.
Try calling the following two one after the other,
power(2,3);
power(3,3);
both will give you 8 as the answer.

- IC June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@IC i get ur point
i am assuming u clear the map for every new a u get.
a small check can be done.

@eugene ur solution is very elegant .. :)
I just use maps for memoization in java
Is this practice wrong.

- salvo4u June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@salvo4u: It's not wrong; sometimes, I use it too. There are different ways to implement memorization and the best way depends on the structure of your problem. Sometimes an array is best; a map might be better when the array would be very sparse. A map is really more general. It's just that using memorization in this problem is not necessary.

- eugene.yarovoi June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what makes this function "optimal" instead of simple loop multiplying 'base' 'power' number of times ?

- spa March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Below code is writen in VS2008:

#include "stdafx.h"
#include "stdio.h"
#include "conio.h"

int power(int a, int b);

int _tmain(int argc, _TCHAR* argv[])
{
int exp = 0;
int pow = 0;
printf("Enter the base: ");
scanf("%d", &exp);
printf("\nEnter the power: ");
scanf("%d",&pow);
printf("2^3 : %d", power(exp,pow));
getch();
return 0;
}

int power(int a, int b){

return b == 0? 1: a*power(a,b-1);

}

- Arup Halder June 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//An O(log(n)) Non Recursive C# for unsigned ints.
//get the b th power of a
public static ulong Power(uint a, uint b)
{
  ulong power = 1;
  if (b > 0)
  {
    power = power * a;
    if (b > 1)
    {
      uint largestBit = GetLargestBit(b);
      uint position = 2;
      uint rem = largestBit >> 1;
      do
      {
        power = power * power;
        if ((b & rem) > 0)
        {
          power = power * a;
        }
        rem = rem >> 1;
        position = position << 1;
      } while (b >= position);
    }
  }
  return power;
}

//Get the max bit of a number
public static uint GetLargestBit(uint b)
{
  uint largestBit = 1;
  while (largestBit <= b)
  {
    largestBit = largestBit << 1;
  }
  largestBit = largestBit >> 1;
  return largestBit;
}

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

#include<iostream.h>
#include<conio.h>
void main()
{
int a,b,i,c=1;
cout<<"enter no";
cin>>a;
cout<<"enter power";
cin>>b;
if(b==0)
cout<<c;
else
{
for(i=1;i<=b;i++)
{
c=a*c;
}
cout<<c;
}

getch();
}

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

#include<iostream.h>
#include<conio.h>
void main()
{
int a,b,i,c=1;
cout<<"enter no";
cin>>a;
cout<<"enter power";
cin>>b;
if(b==0)
cout<<c;
else
{
for(i=1;i<=b;i++)
{
c=a*c;
}
cout<<c;
}

getch();
}

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

public int ppp(int a, int b) {
		if (b == 1) {
			return a;
		} else if (b == 0) {
			return 1;
		}
		return a * ppp(a, b - 1);

}

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

power (int a, int b){
int cnt = 0;
while (2 * cnt < b){
cnt ++;
}
int rem = b - 2 * cnt;
int result = a;
for (int i = 0 ; i < cnt ; i++){
result = result*result;
}
if (rem == 1){
return result*a;
}else{
return result;
}


}

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

#include<iostream.h>
#include<conio.h>
#define basevalue 5
#define powr 5
int power[powr];
void initilise() {
for(int i=0; i<powr; i++)
power[i] = 0;
}
int findPower(int value, int pow){
int num = pow;
power[0] = 1;
power[1] = value;
if(num == 0)
return power[num];
else if(pow == 1 || (power[num] != 0))
return power[num];
else {
if(pow % 2 == 0) {
if(power[num/2] != 0)
power[num] = power[num/2] * power[num/2];
else {
power[num/2] = findPower(value, num/2);
power[num] = power[num/2] * power[num/2];
}
}
else {
if(power[num/2] != 0 && power[num/2 + 1] != 0) {
power[num] = power[num/2] * power[num/2+1];
}
else {
power[num/2] = findPower(value, num/2);
power[num/2+1] = findPower(value, num/2+1);
power[num] = power[num/2] * power[num/2+1];
}
}
}
return power[pow];
}
int main()
{
int result;
initilise();
result = findPower(basevalue, powr);
cout<<"\n result = "<<result;
getch();
return 0;
}

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

Not optimal but workable solution :

class Power{

public int calculatePower(int x, int y)
{
int z =1;

for(int w=1;w<=y;w++)
{
z=z*w;
}
return z;
}}

public class SampleProgram extends Power{

public static void main(String[] args) {
Power p = new Power();
System.out.println("O/P Is:"+p.calculatePower(2,4));

}

}

- Approacjh December 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Function to calculate x raised to the power y in O(logn)*/
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}

- Putta June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Function to calculate x raised to the power y in O(logn)*/
int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

- Putta June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#python


#converts to binary
def bin(b):
	rem = [ ]
	i = 0
	while b !=0:
		rem.append(i)
		rem[i] =  b % 2
		b= b/2
		i = i+1
	rem.reverse()
	return rem

#square and multiply	
def power(a,b):
	binary = bin(b)
	ans = 1
	for i in range(len(binary)):
		ans = ans * ans 
		if binary[i] == 1:
			ans = ans * a 
	return ans 

power(2,3)

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

How about this approach?

While finding x^y, break down the radix to binary format.

For example, 35 can be broken down as

32 16 8 4 2 1
1 0 0 0 1 1

Then take x, since value in above array is 1, answer will contain x.
Find x*x=x^2, since value in above array is 1, answer will contain x*x^2
Find x^2*x^2=x^4, since value in above array is 0, answer will contain x*x^2
.
.
.
Find x^16*x^16=x^32, since value in above array is 1, answer will contain x*x^2*x^32

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

int pow(int base, int exp)
{
int result = 1;
while (exp > 0) {
if (exp & 1) result = result * base;
base = (base * base);
exp >>= 1;
}
return result;
}

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

As far as I know its NP complete .yea u may use binary number system to make it log(n) , but even for smaller exponents sometimes triple number system uses fewer multiplications.

- Anonymous June 17, 2012 | 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