SDE - Intern

You have been given an array/list ARR consisting of ‘N’ integers. You are also given a positive integer ‘K’.

Your task is to find the lexicographically smallest ARR that can be obtained by swapping at most K consecutive elements.

An array/list P is lexicographically smaller than its permutation Q if and only if, for the earliest index at which P and Q differ, P's element at that index is smaller than Q's element at that index. Example, P = [1, 12, 4, 7, 8] is lexicographically smaller than Q = [1, 12, 8, 4, 7].

For example, if ARR = [70, 60, 90, 21, 11] and K = 3, then-

Swap 1: We swap adjacent elements 90 and 21. So, ARR after one swap is [70, 60, 21, 90, 11].
Swap 2: We swap adjacent elements 60 and 21. So, ARR after one swap is [70, 21, 60, 90, 11].
Swap 3: We swap adjacent elements 70 and 21. So, ARR after one swap is [21, 70, 60, 90, 11].
The lexicographically smallest ARR after K = 3 swaps is [21, 70, 60, 90, 11].

Ninja has recently learnt about the heirarchial structure of Binary trees. Now, he wants to find the inorder successor of each node in a Binary Tree and want to implement that in a well mannered code.

Ninja is stucked in the problem and he is asking for your help. Help Ninja!

Note:

The Inorder Successor of a node in a binary tree is the next node in Inorder traversal of the Binary Tree. It is supposed to be NULL for the last node in Inorder traversal, for which suppose it to be ‘-1’.

For example :

For the given binary tree:

The inorder traversal of the tree will be: 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
Hence, the inorder successor of each node will be: 4 -> 2 2 -> 5 5 -> 1 1 -> 6 6 -> 3 3 -> 7 7 -> -1

There are 25 horses, and 5 race tracks, find minimum number of races required to find the top 3 fastest horses.

You have been given an N*M matrix where there are 'N' rows and 'M' columns filled with '0s' and '1s'.

'1' means you can use the cell, and '0' means the cell is blocked. You can move in the 4 following directions from a particular position (i, j):

1. Left - (i, j-1)
2. Right - (i, j+1)
3. Up - (i-1, j)
4. Down - (i+1, j)

Now, for moving in the up and down directions, it costs you $1, and moving to the left and right directions are free of cost.

You have to calculate the minimum cost to reach (X, Y) from (0, 0) where 'X' is the row number and 'Y' is the column number of the destination cell. If it is impossible to reach the destination, print -1.