Microsoft Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
public static int improvePowCompute(int obj,int times){
HashMap<Integer,Integer> result_hold=new HashMap<Integer,Integer>();
result_hold.put(0, 1);
result_hold.put(1, obj);
return compute_process(obj,times,result_hold);
}
public static int compute_process(int obj,int times,HashMap<Integer,Integer> result_hold){
if(times<0){
return Integer.MIN_VALUE;
}
if(times%2==0){
if(result_hold.containsKey(times/2)){
int tmp=result_hold.get(times/2);
result_hold.put(times, tmp*tmp);
return tmp*tmp;
}
else{
int tmp=compute_process(obj,times/2,result_hold);
result_hold.put(times, tmp);
return tmp*tmp;
}
}
else{
if(result_hold.containsKey((times-1)/2)){
int tmp=result_hold.get((times-1)/2);
result_hold.put(times, tmp*tmp*obj);
return tmp*tmp*obj;
}
else{
int tmp=compute_process(obj,(times-1)/2,result_hold);
result_hold.put(times, tmp*tmp*obj);
return tmp*tmp*obj;
}
}
}
expressing the power as a sum of powers of two, evaluating each of the terms by left shift and then multiplying them would be a better option.
For example, 5^6=5^(2+4)=(5^2)*(5^4)
These two operations can be done by simple left shift.
How abt this idea??
ideone.com/n5aqx
import java.util.*;
import java.lang.*;
class Main
{
public static void pow(int a, int b)
{
double val1 = 1, val2 = 1;
if (b!=0)
{
int counter = Math.abs(b);
while(counter>0)
{
if (b<0)
{
val1 /= a;
}
else
{
val1 *= a;
}
counter--;
}
for(int i=0;i<a;i++)
{
val2 *= b;
}
}
else
{
val1 = 0;
val2 = 0;
}
System.out.println("Val1: "+val1);
System.out.println("Val2: "+Math.ceil(val2));
}
public static void main (String[] args) throws java.lang.Exception
{
pow(2, -4);
}
}
Do not really get the point, anyway, here is the power function.
- hao.liu0708 August 24, 2012