#codingexercise

A turning number is the maximum number in a unimodal array that increases and then decreases. Please write a function (or a method) that finds the index of the turning number in a unimodal array.

For example, the turning number in the array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

Int getTurningIndex(int[] numbers)

{

If (numbers.length < 2)

      Return -1;

Int left = 0;

Int right = numbers.length -1;

While (right >= left+1) {

                Int mid = (left+right)/2;

               If (mid == left ) {

                     If (numbers[left] > numbers[right])        

                      Return left;

                     Return -1;

              }

        

                If (numbers[mid] > numbers[mid -1] && numbers[mid] > numbers[mid+1])

                       Return mid;

               Else if (numbers[mid] > numbers[mid-1] &&

                                Numbers[mid] < numbers[mid+1])

                                Left = mid;

               Else

                                Right = mid;

                               

}

Return  -1;

}
The above function assumes a decreasing order means the turning number is the first number and a strictly increasing order has no turning number.
This could be modified to detect the presence of an increasing sequence  or return -1.
Also we use a binary search because the numbers are mostly ordered.
#codingexercise

here is a stair with n levels. A frog can jump up one level or two levels at one time on the stair. How many ways are there for the frog to jump from the bottom of the stairs to the top?

For example, there are three choices for the frog to jump up a stair with three levels: (1) it jumps in three steps, one level for each jump; (2) it jumps in two steps, one level for the first jump and two levels for the second jump or (3) it jumps with two steps, two levels for the first step and one level for the last jump.
Can we do tail recursion here ?
If the last set was a single step, then we have a subproblem of n-1
If the last set was a two step, then we have a subproblem of n-2
we define the recursion as :
f(n) = f(n-1)+ f(n-2);
f(0) = 1
f(1) = 1
f(2) = 2
f(3) = 3
and this is a Fibonacci series

Another one:

Rectangles with size 2 x 1 are utilized to cover other rectangles, horizontally or vertically. How many approaches are available to cover a 2 x 8 rectangle with eight 2 x1 rectangles ?

Again using a similar argument as above, if we keep the 2 x 1 vertically to cover the leftmost vertical then we have sub-problem of 2 x 7
If we keep two horizontal 2 x 1 one on top of the other over the leftmost, we have a subproblem of 2 x 6 rectangle.
Let f(n) denote the number of choices to lay the smaller rectangle over a 2 x n rectangle.
Then the recursion is f(n) = f(n-1) + f(n-2) which is again a Fibonacci series.