Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: Algorithm test question

  1. #1
    Junior Member
    Join Date
    Mar 2013
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Algorithm test question

    Here is the question: Given an array of 1000 elements in sorted order what is the
    largest possible value that will be printed when the array is
    passed to method mystery?


    And here is the mystery code
    public int mystery(int[] v, int t) { 
     
     int w = 0; 
     int h = v.length - 1; 
     int c = 0; 
     while(w <= h)
     { 
     
    c++; 
     int m = (w + h) >>> 1; 
            if(v[m] < t) {h = m - 1}; 
     
         else if(v[m] > t) {w = m + 1}; 
     
        else { 
     
    System.out.print(c); 
     
    return m; 
     } 
     } 
     
     System.out.print(c); 
     
    return -(w + 1); 
    }

    Could someone explain it to me how this is 9? It would be greatly appreciated.
    Last edited by javapava; March 16th, 2013 at 14:49. Reason: make code more readable and understandable


  2. #2
    Administrator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    24,848
    Thanks
    64
    Thanked 2,645 Times in 2,615 Posts

    Default Re: Algorithm test question

    Please edit the code and properly format it. Its poor formatting makes it hard to read and understand.
    Nested statements should be indented
    Statements inside of if statement control should be enclosed in {}s
    }s should not be in the same column.

  3. #3
    Junior Member
    Join Date
    Mar 2013
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Algorithm test question

    Norm, I tried to make the code more easier to read and understandable. I tried working it out a few times, but I am still confused.

  4. #4
    Administrator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    24,848
    Thanks
    64
    Thanked 2,645 Times in 2,615 Posts

    Default Re: Algorithm test question

    The formatting is different, but I can't say its formatting is better.
    There are {}s on the same line with the if and else
    There are }s one beneath the other.

    To see what the code is doing, add some printlns to print out the values of the variables as they are changed and used.

  5. #5
    Junior Member
    Join Date
    Mar 2013
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Algorithm test question

    Here is the proper formatted code to help you out:

    public static int mystery (int[] v, int t)
        {
     
            int w = 0;
            int h = v.length - 1;
            int c = 0;
            while (w <= h)
            {
                c++; // 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
                int m = (w + h) >>> 1; // 499 | 294 | 124 | 61 | 30 | 14 | 6 | 2
                if (v [m] < t) // if v[499] < 1000 | if v[294] < 1000 | if v[124] < 1000 | if v[61] < 1000 | if v[30] < 1000 | if v[14] < 1000 | if v[6] < 1000 | if v[2] < 1000
                {
                    h = m - 1; // h = 499 - 1 = 498 | h = 249 - 1 = 248 | h = 124 - 1 = 123 | h = 61 - 1 = 60 | h = 30 - 1 = 29 | h = 14 - 1 = 13 | h = 6 - 1 = 5 | h = 2 - 1 = 1
                }
     
                else if (v [m] > t)
                {
                    w = m + 1;
                }
     
                else
                {
     
                    System.out.print (c);
     
                    return m;
                }
            }
     
     
            System.out.print (c);
     
            return -(w + 1);
        }

    Code with syntax highlighting:


    9 is the total number of loops it does when the method is called.

    *TIP*
    Debugger is always helpful in this sort of problem

  6. #6
    Member
    Join Date
    Sep 2012
    Posts
    128
    Thanks
    1
    Thanked 15 Times in 15 Posts

    Default Re: Algorithm test question

    The code has some syntax errors.

    If you test this class, try using t = -1 and see what value is printed out.

Similar Threads

  1. Test Question(Introduction Course)
    By Daler in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 19th, 2012, 22:10
  2. algorithm question
    By amandu in forum Java Theory & Questions
    Replies: 2
    Last Post: October 11th, 2012, 08:20
  3. Challenging Java Question: Test your Java skill by grouping these terms
    By karthickk3 in forum Java Theory & Questions
    Replies: 3
    Last Post: July 18th, 2012, 22:10
  4. Exception in JUnit test (easy question)
    By opium in forum Exceptions
    Replies: 1
    Last Post: February 14th, 2012, 08:09