Question

Provide the optimal Solution to the problems below using java code and include Time Complexity Analysis!

1. Peaks and Valleys

In an Array of integers, a “peak” is an element which is greater than or equal to the adjacent integers and a “valley” is an element which is less than or equal to the adjacent integers. For example, the array {5, 8, 6, 2, 3, 4, 6}, {8, 6} are peaks and {5, 2} are valleys. Give an array of integers, sort the array into an alternating sequence of peaks and valleys.

EXAMPLE

INPUT:

                                {5, 3, 1, 2, 3}

                OUTPUT:

{5, 1, 3, 2, 3}

2. Build Order

You are given a list of projects and a list of dependencies (Which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

EXAMPLE

                INPUT:

                                Projects: a, b, c, d, e, f

                                Dependencies: (a, d), (f ,b), (b, d), (f, a), (d, c)

                OUTPUT:

f, e, a, b, d, c

(I need java code with explanation of algorithms and time complexity)

Answer 1

Peaks and Valleys

The explanation of the codes and the idea to solve is written in the codes in comments. Please go through it.

public class Tester {
        /* Here what we are going to do is that we will first sort the array we receive into ascending
        order using the quick sort since its complexity is n log n. Then we will create a new array of
        same size as old array and then we have two idealogies to implement we assign i=0,j=n-1 and k=n-2.
        1. If the array is even:
                If the array is even we will run a while loop, we will take a toggle variable assigned values as 0.
                if the toggle value will be 0 then we will take last element of the old array and place it at the
                first place of the new array ,i.e. the 0th index. And then we will take the first element of the
                 old array and put it into the last element of the new array. Then we will assign the value 0 to
                 toggle. Then we increment the value of i and decrement the value of j. And if the toggle value
                 is 1 then we take the next ith element of the old array and put it into the ith element of the
                 new array. Then we take the jth value of the old array and put it into the jth value of the
                 new array. and we continue this till we traverse half of the array from both sides.
        2. If the array is of odd length:
                we do same as we did in even just we leave the last element as it is and do the same we did above.
                finally we will always end up will values as peak and valley.
        */

        int partitioning(int oldArray[], int start, int end)
        {
                int pivot = oldArray[end];
                int i = (start-1);
                for (int j=start; j<end; j++)
                {
                        if (oldArray[j] < pivot)
                        {
                                i++;
                                int temp = oldArray[i];
                                oldArray[i] = oldArray[j];
                                oldArray[j] = temp;
                        }
                }
                int temp = oldArray[i+1];
                oldArray[i+1] = oldArray[end];
                oldArray[end] = temp;

                return i+1;
        }

        //This is the function where we are implementing the Quicksort
        void sorting(int oldArray[], int start, int end)
        {
                if (start < end)
                {
                        int piv = partitioning(oldArray, start, end);
                        sorting(oldArray, start, piv-1);
                        sorting(oldArray, piv+1, end);
                }
        }

        // we used a function to print the array
        static void displayArray(int newArray[])
        {
                int n = newArray.length;
                for (int i=0; i<n; ++i)
                        System.out.print(newArray[i]+" ");
                System.out.println();
        }
        public static void main(String[] args){
                // we take an array.. An array with odd number of elements
                int oldArray[] = {23, 27, 18, 9, 2, 5 ,33 ,54 ,73 ,65 ,12};
                int n = oldArray.length;

                // we take new array with same length as old array
                int newArray[] = new int[n];
                Tester ob = new Tester();

                //we sort the array using quick sort
                ob.sorting(oldArray, 0, n-1);

                /* we took i = 0 and j= n-1 so that we can refer to the start and end of the array  we took
                        k = n-2 so that if we have odd number of elements we leave the last element as it is
                 and we perform the functioning on n-2 number of element. As it is the largest element since the
                 array is sorted, hence we will end up with a peak at the end and always there will be a valley
                 before that peak. Also we used a variable toggle to toggle between the two idealogies we are using*/
                int i=0;
                int j =n-1;
                int k= n-2;
                int toggle = 0;

                // if old array has even number of elements
                if(n%2==0){
                        while(i<=j){
                                if(toggle==0){
                                        newArray[i]=oldArray[j];
                                        newArray[j]=oldArray[i];
                                        toggle=1;
                                }
                                else if(toggle==1){
                                        newArray[i]=oldArray[i];
                                        newArray[j]=oldArray[j];
                                        toggle=0;
                                }
                                i++;
                                j--;
                        }
                }
                //if old array has odd number of elements
                else if(n%2!=0){
                        while(i<=k){
                                if(toggle==0){
                                        newArray[i]=oldArray[k];
                                        newArray[k]=oldArray[i];
                                        toggle=1;
                                }
                                else if(toggle==1){
                                        newArray[i]=oldArray[i];
                                        newArray[k]=oldArray[k];
                                        toggle=0;
                                }
                                newArray[j]=oldArray[j];
                                i++;
                                k--;
                        }
                }
                System.out.println("******************************************************************************");
                System.out.println("The peak and valley result is: ");
                displayArray(newArray);
                System.out.println("******************************************************************************");

        }
}

The Output of the code is:

Now talking about the time complexities:

1. We used quick sort which has a time complexity of N Log N .
2. We directly selected the elements to put it into new array , hence N number of elements took N times to compute.So the complexity to do this was N.
3. Hence the over all complexity is N + N Log N which is equal to N Log N.