2 days ago

Sarthak • 0

Hyderabad

Question 1: Linked a Linked List

Problem Statement:

You are given an array of size n. You have to create a new linked list with exactly n/2 nodes such that the first node of the new linked list will have a mean of largest and smallest value in the given array/LinkedList. The second node will have the mean of the second largest and second smallest value of the LinkedList and so on.

Mean of two integers a, b is (a + b) / 2. (floor division)

Input Format:

• First-line will contain an integer n, denoting the size of the array.
• The next n lines will contain an integer each.

Constraints:

• 1 <= n <10^5
• n will always be even.

Output Format:

• Return the head of the newly created LinkedList.

Question 2: Partial Sorting

Problem Statement:

You are given an array A of N numbers. You can perform the following operation:

• swap any two adjacent numbers in A.

Your task is to print the minimum number of operations to be performed such that A satisfies the following property:

• The maximum number in A should occupy the first position.
• The minimum number in A should occupy the last position.
• The order of other numbers doesn't matter.
• A necessarily does not contain distinct elements. That is, A might contain more than one occurrence of a number. (Note: If there are multiple maximums/minimums, you must optimize for the minimum swaps).

Input Format:

• The first line of input consists of a single integer N, denoting the size of A.

The next N lines contain the integers denoting the elements of A.