dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: interview practice questions

  1. #1
    Join Date
    Nov 2017
    Posts
    18

    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 03:39 AM.

  2. #2
    Join Date
    Nov 2017
    Posts
    18

    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.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






    }
    Last edited by 2kaud; November 10th, 2017 at 03:41 AM.

  3. #3
    Join Date
    Feb 2017
    Posts
    370

    Re: interview practice questions

    Quote Originally Posted by CodeCake View Post
    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.
    Last edited by wolle; November 27th, 2017 at 08: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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)