Big O notation on algorithms

everdead.ie

Hey, I'm just looking at some coding questions that google have asked before in their interviews and trying them out etc.

Basically there are a few questions where they ask you to do an algorithm to solve in O(n) or O(log(n)) etc.

But it has been so long since I did this in college I can't remember how to get the correct Notation to see if my algorithm is correct.

Anyway I have the question below

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output will be equal to multiplication of all the elements of A[N] except A. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

I implemented this in a couple of minutes and I am just wondering if someone could help me figure out how to convert the complexity into Big O notation.

Thanks

     private ArrayList setArray(ArrayList input) {
        
        ArrayList output= new ArrayList();
        float full=1;
        for (int i = 0; i<input.size(); i++) {
            full = full*Integer.parseInt(input.get(i).toString());
        }
        for (int i = 0; i<input.size(); i++) {
            output.set(i, divide(full,Integer.parseInt(input.get(i).toString())));
        }
        return output;
        
    }
    
    private float divide(float whole, float divider) {
        
        float targetRemainder = whole%divider, currentRemainder=whole;
        float result=0;
        
        while (currentRemainder!=targetRemainder) {
            currentRemainder = currentRemainder-divider;
        result ++;
        }
        
        result=result + currentRemainder;
        return result;
        
    }

Jonny Blaze

everdead.ie wrote: »

Hey, I'm just looking at some coding questions that google have asked before in their interviews and trying them out etc.

Basically there are a few questions where they ask you to do an algorithm to solve in O(n) or O(log(n)) etc.

But it has been so long since I did this in college I can't remember how to get the correct Notation to see if my algorithm is correct.

Anyway I have the question below
I implemented this in a couple of minutes and I am just wondering if someone could help me figure out how to convert the complexity into Big O notation.

Thanks

     private ArrayList setArray(ArrayList input) {
        
        ArrayList output= new ArrayList();
        float full=1;
        for (int i = 0; i<input.size(); i++) {
            full = full*Integer.parseInt(input.get(i).toString());
        }
        for (int i = 0; i<input.size(); i++) {
            output.set(i, divide(full,Integer.parseInt(input.get(i).toString())));
        }
        return output;
        
    }
    
    private float divide(float whole, float divider) {
        
        float targetRemainder = whole%divider, currentRemainder=whole;
        float result=0;
        
        while (currentRemainder!=targetRemainder) {
            currentRemainder = currentRemainder-divider;
        result ++;
        }
        
        result=result + currentRemainder;
        return result;
        
    }

Not sure exactly how you'd go about it, but to start you would probably sum those array traversals. If memory serves, iterating through an array is in constant time O(n) for n elements, so if you have two full array iterations that would be O(n2) time (I think!). Also, the while loop in your function will add overhead.

Here's a good link I remember from college about some basic big O stuff.

Good luck with it anyway!

everdead.ie

Jonny Blaze wrote: »

Not sure exactly how you'd go about it, but to start you would probably sum those array traversals. If memory serves, iterating through an array is in constant time O(n) for n elements, so if you have two full array iterations that would be O(n2) time (I think!). Also, the while loop in your function will add overhead.

Here's a good link I remember from college about some basic big O stuff.

Good luck with it anyway!

Thanks that's very helpful.

Jonny Blaze

No problem! I'm probably wrong in the post above but hope it helps anyway!

GreeBo

Jonny Blaze wrote: »

Not sure exactly how you'd go about it, but to start you would probably sum those array traversals. If memory serves, iterating through an array is in constant time O(n) for n elements, so if you have two full array iterations that would be O(n2) time (I think!). Also, the while loop in your function will add overhead.

Here's a good link I remember from college about some basic big O stuff.

Good luck with it anyway!

Unless they are inner loops, wouldnt that be O (2n) = O(n)?
(the 2N being insignificant)

The while loops is essentially causing an inner loop of effectively n-1
so that would give you O(n2) (n Squared)

That said, this stuff always messes me up!

Procasinator

Your divide operation doesn't seem like it would work unless the the numbers divide evenly.

I would agree with GreenBo's assessment that it's O(n^2), because of the divide operation is O(n) (worst case) being nested in an O(n) for-loop.

fergalr

GreeBo wrote: »

Unless they are inner loops, wouldnt that be O (2n) = O(n)?
(the 2N being insignificant)

The while loops is essentially causing an inner loop of effectively n-1
so that would give you O(n2) (n Squared)

That said, this stuff always messes me up!

Procasinator wrote: »

Your divide operation doesn't seem like it would work unless the the numbers divide evenly.

I would agree with GreenBo's assessment that it's O(n^2), because of the divide operation is O(n) (worst case) being nested in an O(n) for-loop.

A couple of things: O notation can be used to refer to a lot of things: best case, worst case, average case. If its not said, then I'd assume average case. Plenty of algorithms have a different average case vs. worst case. In these situations, we might care about the typical input the algorithm will have (e.g. a sorting algorithm), or how the algorithm will respond under attack (e.g. an attacker doing denial-of-service by forcing hash collisions).

In the question above, I'd assume they care about average case.

As such, I don't think the 'worst case' arguments made against the divide operation are valid? I would say they are not - but it depends on how you implement your operator exactly - wasn't sure what the OP was doing.


But anyway, the complexity of the divide operator is irrelevant to the question because of the bigger point:


The question is asked in the spirit of "don't use the divide operator". Now, I haven't understood your code implementation, but if you do that in an interview, the interviewer will maybe let you finish it (maybe with a discussion about integer vs. floats, or precision etc.) but will then say:

"Well, thats one solution, but what we were really looking for you to do is to solve the problem without any use of any division operator at all - including one you've implemented yourself" (alternatively: "modulus operator [insert other 'division with direct use of division operator' trick here (e.g. exp to fractional power)] is wasting our time, thats clearly not how we meant the question *angry*.").


And then you'll be back to addressing the question as its stands.

Its a tricky question. I'm proud I managed to figure out a solution; it took me a bit of thinking.

Try think it out a bit more before you look at the solution, if you haven't given it further thought:

Then here are a bunch of solutions:
http://stackoverflow.com/questions/2680548/given-an-array-of-numbers-return-array-of-products-of-all-other-numbers-no-div

Probably the two answers in the first 'reply' there (by 'michael anderson') are what they are looking for. The second one does it without using extra space which is probably the gold standard.


Its tricky to come up with. I'm not sure whether its a good interview question - seems to me like there's going to be a good bit of randomness about whether someone gets the answer or not in an interview. I guess that you learn a lot by guiding someone to the answer and seeing how much of it they 'get'.

Thats always the controversy around this kind of interview question; thats what you get when you take your practice questions from google.