Posts Tagged ‘Data Structures’

Q: You are given an array of integers. For each element x find a suitable y such that
1. Val(Y) < Val(x)
2. Position(Y) < Position(X)
3. Position of Y should be maximum as possible
4. If there is no such Y, set it to null

Try to achieve complexity better than O(n^2).

A: Use a doubly linked list with following insertion and maintenance rules –
1. Linked starts with null and at any point, parent node is the value of Y for operational element. The prints of Y happens at the time of element insertion.
2. For each element X, Start with the tail of the linked list.
> If its null node, add a node X as its successor.
> If linked list node element is less than X, add a new node as its successor.
> If node element is greater equals X, delete that node(including its tail) and re-do comparison with its parent.

Sample run
Say for array 7, 1, 4, 8, 5, 6, 2

Operational Element Linked List Operation taken Printed Result (X, Y)
7 null -> 7 Added node 7 7, Null
1 null -> 1 Deleted node 7 and added node 1 1, Null
4 null -> 1 -> 4 Added node 4 4,1
8 null -> 1 -> 4 -> 8 Added node 8 8,4
5 null -> 1 -> 4 -> 5 Deleted 8 and added 5 5,4
6 null -> 1 -> 4 -> 5 -> 6 Added Node 6 6,5
2 null -> 1 -> 2 Deleted 6, then 5, then 4 while traversal from tail and added 2 2,1

 

PS: We do complete traversal of linked list from right to left. We can have a step further by maintaining the linked list in such a manner, that we can do binary search on it (by storing position index separately). It can be more optimized by using binary search as linked list is always sorted.

Advertisements