In Java. Please implement in given code below

Code I have so far:

import java.io.*; import java.util.*; public class Lab2 { /** * Problem 1: Arrange the given array such that all even numbers are in increasing * order at even indices and all odd numbers are in decreasing order at odd indices. */ private static void problem1(int[] arr) { // Implement me! } /** * Problem 2: Determines for each entry its position in the sorted array. */ private static int[] problem2(int[] arr) { // Implement me! return new int[] { }; } // --------------------------------------------------------------------- // Do not change any of the code below! static class IntKVPair implements Comparable { public int key; public int value; public IntKVPair(int key, int value) { this.key = key; this.value = value; } public int compareTo(IntKVPair other) { return this.key - other.key; } } private static final int LabNo = 2; private static final Random rng = new Random(654321); private static boolean testProblem1(int[][] testCase) { int[] arr = testCase[0]; int[] answer = arr.clone(); problem1(answer); if (answer == null) return false; if (answer.length != arr.length) return false;

for (int i = 2; i answer[i - 2]) return false; } Arrays.sort(arr); Arrays.sort(answer); for (int i = 0; i

for (int i = 1; i

{ int rndInd = rng.nextInt(size - i) + i; int tmp = numbers[i]; numbers[i] = numbers[rndInd]; numbers[rndInd] = tmp; } return new int[][] { numbers }; } private static int[][] createProblem2(int lineNo) { int maxSize = Math.min(lineNo, 500); int size = rng.nextInt(maxSize) + 2; int[] numbers = getUniqueRandomNumbers(size); Arrays.sort(numbers); int[] solution = new int[size]; for (int i = 0; i

int[] integers = new int[maxSize]; for (int i = 0; i

Problem 1 You are given an unsorted array A of non-negative integers. It contains the same number of even and of odd numbers. Implement an algorithm such that all odd numbers in A are at odd indices and all even numbers are at even indices. Additionally, even numbers should be sorted in increasing order and odd numbers should be sorted in decreasing order. Your algorithm should run in O(n log n) time. Problem 2 You are given an array A with n distinct elements. Implement an O(n log n)-time algorithm that creates an array B where all elements are in range from 0 to n - 1 and where the order of elements is the same as in A. That is, 0 has the same index in B as the smallest element in A, 1 has the same index in B as the second smallest element in A, and so on. For example, if A = [4,9,1,5), then B = [1,3,0,2]. Hint: Use key-value pairs where the key is the original element in A and the value is its index in A. The given file contains a class IntkVPair. It represents a key-value pair of integers and an IntKVPair-array can be sorted by their keys. Implementation You are given a file Lab2.java (which you can download from canvas). The file contains a class Lab2 with the two functions problem1 and problem2. Implement your solutions in the corresponding functions. Do not make any changes outside of these two functions (e.g. by adding helper functions); such changes will be undone. Do not output anything to the terminal. The program already implemented in the file Lab2.java randomly generates test cases. The seed of the random number generator is set to ensure the same test cases whenever to program is executed. Note that the purpose of the tests is for you to avoid major mistakes. Passing all given tests does not imply that your algorithm is correct, especially that is has the expected runtime. You may use the function java.util.Arrays.sort() to sort arrays; you can assume it runs in O(n log n) time. Do not use hash tables or similar data structures