SDE - 1

You are given two arbitrary rectangles on a 2-D coordinate plane, which may have an intersecting area. You have to find the net area covered by both the rectangles on the cartesian plane.

The orange area depicted in the above figure is the net area covered by both rectangles on the cartesian plane.

Note:

1. For a rectangle, its top left and bottom right coordinates are given.

2. Coordinates of the rectangles are integer values.

3. Edges of the given rectangles will always be parallel to the X and Y coordinate axes of the cartesian plane.

4. It is guaranteed that both the rectangles will have at least a unit area.

You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.

Note :

Try to solve the problem in 'Single Scan'. ' Single Scan' refers to iterating over the array/list just once or to put it in other words, you will be visiting each element in the array/list just once.

You are given a linked list containing 'n' 'head' nodes, where every node in the linked list contains two pointers:

(1) ‘next’ which points to the next node in the list

(2) ‘child’ pointer to a linked list where the current node is the head.

Each of these child linked lists is in sorted order and connected by 'child' pointer.

Your task is to flatten this linked such that all nodes appear in a single layer or level in a 'sorted order'.

Input: Given linked list is:

Output:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 12 → 20 → null.


Explanation:
The returned linked list should be in a sorted order. All the elements in this returned linked list are connected by 'child' pointers and 'next' pointers point to null.