interview practice questions

[CodeCake]

So, from previous interviews and online interview questions, I made a list of possible questions that may appear in an interview. it's been frustrating when ive tried to memorise algorithms i found online but i really dont understand them to explain them when asked to do so

I've been trying to figure out a divide and conquer algorithm to find the minimum element in an array with O(N) complexity.

this code i found on stackoverflow but dont understand at all:

private static int smallest(int[] array, int from, int to) {
    if (from == to) {
        return array[from];
    }
    int middle = from + (to - from) / 2;
    return Math.min(smallest(array, from, middle), smallest(array, middle + 1, to));
}

public static int smallest(int[] array){
    return smallest(array, 0, array.length - 1);
}

I'm sure this would be O(NlogN) complexity... please correct me if i'm wrong?
If so, I should note this, also.

Would an approach where the first element of the array that isn't null is removed then set to null and compared to the next element of the array being set to null, by the recursive call of the function be considered a divide and conquer algorithm ? i believe this would be done in O(n) time complexity.

could someone explain to me please?

[CodeCake]

I also just thought of another brute force solution... but not sure of the time complexity as I want it to be-

private static int smallest(int[] array) {
    int middle = (arr.length-1)/2
    int[]arr=Arrays.CopyOfRange(array,0,middle);
    int[]arr2=Arrays.CopyOfRange(array,middle+1,arr.length);
    return Math.min(smallest(arr),smallest(arr2));
}

although unsure how i could explain this.. i hate recursive algorithms

thanks in advanc






}

[wolle]

I'm sure this would be O(NlogN) complexity... please correct me if i'm wrong?

Well, I have a feeling it's rather O(N).

The divide-and-conquer algorithm to find the minimum element of an array builds an implicit binary tree of min-function calls recursively.

This recursive tree will be balanced and almost complete so approximately half of the nodes will be leaf-level nodes. When the number of elements in the array is increased the number of min-function calls at leaf-level will increase in direct proportion to the change and, in keeping with the half/half ratio, so will also the number of higher level min-function calls.

It means the total number of min-function calls increases linearly with the number of array elements (N) and that's O(N) behavior.