java coding

  

Instructions

1) You can use any coding language of your choice.

2) Please write appropriate test cases for your code. 

3) Please share the code and paste screenshots of your output(if available)

4) The code need not be complete. Feel free to inundate them with comments. We are trying to test only your thought process and algorithmic thinking

QUESTIONS

1. Sort a linked list using insertion sort.

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.

2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.

3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3

Output: 1->2->3->4

2. A subarray A[i], A[i+1], ..., A[m] of A is said to be composite if and only if:

• For i<= m<m,      A[m] > A[m+1] when m is odd, and A[m] < A[m+1] when m is even;
• OR,      for i<= m<m, A[m] > A[m+1] when m is even, and A[m] < A[m+1]      when m is odd.

That is, the subarray is composite if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size composite subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]

Output: 5

Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16]

Output: 2

Example 3:

Input: [100]

Output: 1

Note:

1. 1 <= LENGTH(A)<= 40000

2. 0 <= A[i] <= 10^9