
November 9th, 2017, 05:12 PM
#1
interview practice questions
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:
Code:
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?
Last edited by 2kaud; November 10th, 2017 at 02:39 AM.

November 9th, 2017, 05:19 PM
#2
Re: interview practice questions
I also just thought of another brute force solution... but not sure of the time complexity as I want it to be
Code:
private static int smallest(int[] array) {
int middle = (arr.length1)/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
}
Last edited by 2kaud; November 10th, 2017 at 02:41 AM.

November 26th, 2017, 09:05 AM
#3
Re: interview practice questions
Originally Posted by CodeCake
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 divideandconquer algorithm to find the minimum element of an array builds an implicit binary tree of minfunction calls recursively.
This recursive tree will be balanced and almost complete so approximately half of the nodes will be leaflevel nodes. When the number of elements in the array is increased the number of minfunction calls at leaflevel will increase in direct proportion to the change and, in keeping with the half/half ratio, so will also the number of higher level minfunction calls.
It means the total number of minfunction calls increases linearly with the number of array elements (N) and that's O(N) behavior.
Last edited by wolle; November 27th, 2017 at 07:56 AM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
