## Microsoft Interview Question for SDETs

• 0

Country: United States

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

``````#include <limits>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cmath>

/*
That's the story (took roughly more than 45 minutes...)

result = base ^ exponent, where the exponent is double (meaning e.g. 2.14 ^ 10.1241 or -2.14 ^ -1.42
which is a complex number)

I can't cover all the special cases, such as -inf + inf, NaN, negative base and negative exponent,
so I just assume base and exponent are positivie... it's complicated enough

1) if the exponent is an integer it's easy base^8 = ((base^2)^2)^2 (note 3 instead 8 multiplications,
roughly lg(exp) multiplications

2) if the exponent has a decimal part e.g. base^8.5 we can write: base^(8+1/2) = base^8 * base^(1/2)
(base^1/2 is the square-root of base, base^1/4 is the 4-th root of base etc...)
so after powering the integer part, we multiply it with the power of the decimal part.

powering the decimal part rquires us to have a root. root can be self-made by using newton method.
newton method requires a good guess to converge and to not take long. a good guess can be done using
binary search in the number range.

note we can write the decimal part of the power as base^dec_exponent = base^0.33333 (e.g.)
which is base^(0.25 + 0.0625 + 0.015625 + ...)
which is base^(1/4 + 1/16 + 1/64)
*/

// power with integer exponent
double mypow(double base, unsigned int exp)
{
if (exp == 0) return 1;
if (exp == 1) return base;
if (exp == 2) return base*base;
double result = mypow(base, static_cast<unsigned int>(exp / 2));
result *= result;
if (exp % 2 == 1) result *= base;
return result;
}

// takes the square root based on binary search (could use newton method, too)
double mysqrt(double value)
{
if (value == 0) return value;

// guess x using "binary search" to get close
double lo = 0.0; // root of something never get's below 0
double hi = value;
double x = (hi + lo) / 2;
while (abs(hi - lo) > 0.001)
{
x = (hi + lo) / 2;
double res = x * x;
if (res > value) hi = x;
else lo = x;
}

// with the reasonable accurate guess perform newton methode
for(int i = 0; i < 20; i++)
{
x = x - ((x*x - value) / (2 * x));
}

return x;
}

// powerfunction as desired by the question
double mypow(double base, double exp)
{
if ((exp < 0) && (base < 0) && (exp - static_cast<int>(exp) > 0.0)) throw "no support for complex numbers";
if (exp < 0) return 1.0 / mypow(base, -exp); // negative exponent is just 1/pow(base, -exp)

double result = mypow(base, static_cast<unsigned int>(exp)); // power integer part
double expdec = exp - static_cast<unsigned int>(exp); // remove integer part from exponent: 0 <= expdec < 1
if (expdec >= 1.0) throw "exponent too high";

if (expdec > 0.0)
{
double epsilon = 0.000000000000001;
double currentRs = 1.0;
double currentRt = mysqrt(base);
double currentExp = 0.5;
double remainingExp = expdec;

while (remainingExp > epsilon && currentExp > epsilon)
{
if (remainingExp >= currentExp)
{
currentRs *= currentRt;
remainingExp -= currentExp;
}
currentRt = mysqrt(currentRt);
currentExp /= 2;
}

result *= currentRs;
}
return result;
}

// test helper function
void testMyPow(double base, double exp)
{
double myresult = mypow(base, exp);
double result = pow(base, exp);
double error = abs(myresult - result);
std::cout << "tested " << base << "^" << exp << " mypow returned " << myresult << " pow returned " << result << " error " << error << std::endl;
}

int main()
{
testMyPow(2.0, 20.0);
testMyPow(2.0, -5.0);
testMyPow(2, 1.5);
testMyPow(0.212, 91.231);
testMyPow(891.212, 0.33333333333);
return 0;
/* output
tested 2^20 mypow returned 1.04858e+06 pow returned 1.04858e+06 error 0
tested 2^-5 mypow returned 0.03125 pow returned 0.03125 error 0
tested 2^1.5 mypow returned 2.82843 pow returned 2.82843 error 0
tested 0.212^91.231 mypow returned 3.47494e-62 pow returned 3.47494e-62 error 2.59085e-77
tested 891.212^0.333333 mypow returned 9.62337 pow returned 9.62337 error 3.55271e-15
*/
}``````

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

``````double ans = 1;
for (int i=1; i<=power; i++)
ans = ans * x;``````

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

``double ans = 1;``

``for (int i=1; i<=power; i++)``

``ans = ans * x;``

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

``double ans = 1;for (int i=1; i<=p; i++)	ans = ans * x; System.out.println("Ans : " + ans);``

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

``double ans = 1; for (int i=1; i<=p; i++) ans = ans * x;System.out.println("Ans : " + ans);``

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.