Interview: Efficiently implement x^y for positive integers using basic operators.

There are three solutions that come to mind..

public static int PowerOfY_0(int x, int y)
 {
     int result = 1;
     for (int i = 0; i < y; i++)
         result *= x;
     return result;
 }

The second solution is a bit of fun, because you are not using the power function but other math functions. Definitely efficient in terms of lines of code.

 

public static int PowerOfY_1(int x, int y)
     {
         return (int) Math.Round( Math.Exp(y* Math.Log(x, Math.E)));
     }

The expected function is something like this:


public static int PowerOfY(int x, int y)
{
    int result = 1;
    while (y > 0)
    {
        if (y % 2 == 1)
            result *= x;
        y = y / 2;
        x *= x;
    }
    return result;
}
Of course, this is a bad question – you are really testing if the person can remember prior canned solutions and not their ability to think.  IMHO, the interviewer asking the question is suspect on their ability to think. It has no relationship to any job function.

Comments

  1. Hi Ken,

    I enjoy reading your interview questions.

    I think this kind of a question could be more about how someone comes to an answer than about knowing the canned solution. If the interviewer just wanted the final answer, and not the process to get to it, that is revealing. If the candidate doesn't know how to discover/ask quesitons to get to the solution, that is revealing. The interview process is a tense situation which may mimick real working conditions (ha ha) of daily life in the company. So while the question is suspect, the question may not have been the point.

    ReplyDelete

Post a Comment

Popular posts from this blog

Yet once more into the breech (of altered programming logic)

How to convert SVG data to a Png Image file Using InkScape

Simple WP7 Mango App for Background Tasks, Toast, and Tiles: Code Explanation