SDE - Intern

For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array/list when the following two conditions are met.

A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:

1. 'ARR[i] > 'ARR[j]' 
2. 'i' < 'j'

Where 'i' and 'j' denote the indices ranging from [0, 'N').

You have been given a singly linked list in which nodes are present in increasing order. Your task is to construct a Balanced Binary Search Tree with the same data elements as the given Linked List.

A Balanced BST is defined as a BST in which the height of two subtrees of every node differs no more than 1.

Stack is a data structure that follows the LIFO (Last in First out) principle. Design and implement a stack to implement the following functions:

1. Push(num): Push the given number in the stack if the stack is not full.

2. Pop: Remove and print the top element from the stack if present, else print -1.

3. Top: Print the top element of the stack if present, else print -1.

4. isEmpty: Print 1 if the stack is empty, else print 0.

5. isFull: Print 1 if the stack is full, else print 0.

You have been given ‘m’ operations which you need to perform in the stack. Your task is to implement all the functions of the stack.

Example:

We perform the following operations on an empty stack which has capacity 2:

When operation 1 1 is performed, we insert 1 in the stack.

When operation 1 2  is performed, we insert 2 in the stack. 

When operation 2 is performed, we remove the top element from the stack and print 2.

When operation 3 is performed, we print the top element of the stack, i.e., 3.

When operation 4 is performed, we print 0 because the stack is not empty.

When operation 5 is performed, we print 0 because the stack is size 1, which is not equal to its capacity.