Associate Software Engineer

Ninjaland is a country consisting of ‘N’ states and ‘M’ paths. There are two types of paths that connect any two states. One is the normal path, and the other is a special path. Both paths have their respective lengths. You can use either of the paths to travel between two states. Your task is to determine the shortest distance between the two given states such that at most, one(possibly zero) special path is included in this path.

Note:

1. All the paths are directed.

2. Multiple paths can be present between two states.

3. All the states are connected with each other.

4. It does not have any self-loop.

5. At least one path always exists between the two given states.

For Example:

If ‘N’ = 3, ‘M’ = 2, and given values of paths are 
[ [1, 2, 2, 3],
  [2, 3, 4, 2] ]
You have to calculate the shortest distance between ‘X’ = 1 and ‘Y’ = 3

In the diagram, we can observe no direct edge from state 1 to state, 3 but we can go from state 1 to state 2 using the normal path of length 2 and then from state 2 to state 3 using the special path of length 2. So the total length will be 4, and we can clearly see that no other path can be smaller than this. Hence, the answer is 4.

Given a 2D grid having N Rows and M Columns. Each cell of the grid has a character among [ 'U', 'L', 'D', 'R' ] written on it, denoting Up, Left, Down, and Right respectively and indicating the direction in which it is permitted to move from that cell to its neighbor. Your task is to find the minimum number of cells whose direction value is required to be changed so that there exists a path from Top-Left to the Bottom-Right cell by following the directions written on the cells.

For example,

Consider the 2 * 2 grid

Let's call the four cells in the grid as A,B,C,D. In this grid, it is allowed to move from Cell A to Cell B, Cell B to Cell D, Cell C to Cell D and Cell D to Cell C. There are two paths that start from A and ends at D:

1) A->C->D
To follow this path we need to change the value of cell A to “D” and do not need to change the value of cell C. Therefore, the total change for this path is 1.

2) A->B->D
To follow this path we need not to change any of the cell values. Therefore the total changes for this path is 0.

As we can see the minimum changes required to reach the bottom-right cell is Zero therefore the answer is 0 in this case.

You are given an integer 'N'. For a given 'N' x 'N' chessboard, find a way to place 'N' queens such that no queen can attack any other queen on the chessboard.

A queen can be killed when it lies in the same row, or same column, or the same diagonal of any of the other queens. You have to print all such configurations.

Given a string (STR) of length N, you have to create a new string by performing the following operation:

Take the smallest character from the first 'K' characters of STR, remove it from STR and append it to the new string.

You have to perform this operation until STR is empty.

 Note:

The input string(STR) will not contain any spaces.

Assume that all characters in STR are lower case letters.

If characters less than 'K' remain, then append them in a sorted way to the new string.

Example:

Let the input string be "edcba" with K = 4.

Let the new string to be formed is initially empty, newString = "".
The first set of 4 characters are, ('e', 'd', 'c', 'b')
Out of these 4 characters, the smallest one is 'b' and hence we add it to the newString and it becomes, 
newString = "b"

The next set of 4 characters are, ('e', 'd', 'c', 'a')
Out of these 4 characters, the smallest one is 'a' and hence we add it to the newString and it becomes, 
newString = "ba"

Now we are left with "edc" and since we can't get a window of size 4, we sort them in the increasing order and append them to the newString.

Hence, newString thus formed will be "bacde".

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given index twice.

Follow Up:

Try to do this problem in O(N) time complexity.