How to crack Amazon.com technical interview?

First of all I would like to add a disclaimer that the article is my personal view and this is not an official statement from Amazon. But having taken more than 100 interviews in Amazon, I think this would help anyone who wants to join amazon or similar company.

In this article, I am going to write about how to think about amazon technical interview questions. It is a process framework that I think can be applied to other problems as well. The question would target problem solving and coding as the competency. These competencies are related to SDE 1 and 2 job profile. There are other competencies as well which I would cover in another blog.

The question is:
    Implement power function. The function should take two numbers as input (e.g. 2,3) and return 8 as output.




Before discussing about the solution, I would like to take a step back and talk about the problem itself. In any company the problem, the problem varies around 2 dimensions, depth and breadth (scale).  In general the interview process is a mimic of these two dimension. If the problem is very tough, then the expectation would be to provide a good solution not necessarily the most optimal one while if the problem is comparatively easy, the expectation would be to provide a solid answer that covers all the edge cases and is most optimal in time complexity. The former is an equivalent of an open book exam, which might appear to be easy but is very far from it.

I guess by now you must have figured out that the question is from the latter category and therefore its important to think about solving the questions in the most awesome way possible.




What are the steps to solution?
Whenever I think about a problem, I solve them using the following steps:

1. Define the input 
2. Based on type of input, define all the use cases
3. Write down examples of the above use cases. Be comprehensive
4. Write down the time and space complexity of the first solution that pops up in your mind
5. Write an algo and dry run all your use cases
6. If the algo succeeds, then start thinking about space and time optimization. If you don't succeed, then think about the algo again
7. Discuss your optimized solution with interviewer
8. If there is an agreement, the code it

I have found the above framework to be very effective and has helped me solve complex problems in the past. In the context of the problem give, let try to write some of the points

1. Input - you can define input as integers or decimal numbers. It might be tough to handle decimal power, so I think it will be good to consider base as floating and exponent as integer. Making exponent as integer and potentially be a step 2. Discuss this with your interviewer and make sure he is on the same page withe respect to the input assumptions
2. Define all use cases and write down examples. A few would be 0^0, 0^-1,0^1, -2^2, -5000^-9999. I have give few examples but its really important to be comprehensive here
3. The first easy solution would be a for loop and you multiply base  exponent times
4. Write an algo of this and make sure that all the above test case would pass. if you are able to do so, you have one solid answer
5. Now the time complexity of for loop solution is O(n). This can be further improved.
6. I am sharing a solution below which has log(n) time complexity but the solution can still be improved further using this framework and I would like to hear about it in comments

I hope that this thinking framework helps in solving problems in a structured way. One another byproduct of this structured way is that it would force you to be more vocal and generally you would be on the same page withe the interviewer.

All the best for your interview !!





   
    public double power (int base, int exponent) throws Exception{
        if(base ==0 && exponent <0){
            throw new Exception("Can't calculate number");
        }
        if(exponent<= 0){
            return 1.0/(double)positivePower(base, -exponent);
        }else{
            return positivePower(base, exponent);
        }
    }
   
    private int positivePower(int base, int exponent) throws Exception{
        if(exponent == 0){
            return base;
        }else if(exponent == 1){
            return base;
        }
        int power =  positivePower(base, exponent/2);
        int finalNumber =0;
        if(exponent%2 ==0){
            finalNumber =  power*power;
            if(finalNumber/power != power){
                throw new Exception ("Sorry cant calculate");
            }
        }else{
            finalNumber =  base * power * power;
            if(finalNumber/(base*power) != power){
                throw new Exception ("Sorry cant calculate");
            }
        }
        return finalNumber;
    }