Fullstack Developer

You are given two strings named str1 and str2 of length N and M respectively. Find whether string str2 contains one of the permutations of string str1 as its substring. In other words, whether there exists any permutation of string str1 that is a substring of str2.

For Example :

Input: str1 = “ab” , str2 = “aoba”
Output: True
Explanation : Permutations of first-string str1 i.e. “ab” are [ “ab”, “ba” ].
The substrings of str2 i.e. “aoba” are [ “a”, “o”, “b”, “a”, “ao”, “ob”, “ba”, “aob”, “oba”, “aoba” ].
The string “ba” is present in the list of substrings of string str2.

There are ‘N’ junctions connected by ‘M’ bi-directional roads. At most, one road is present between any pair of junctions. There is no road connecting a junction to itself. The travel time for a road is the same in both directions.

A vehicle at a junction can start moving along a road only when the light at the current junction flashes green. If a vehicle arrives at a junction between green flashes, it must wait for the next green flash before continuing in any direction. If it arrives at a junction exactly when the light flashes green, it can immediately proceed along any road originating from that junction.

You are given a city map that shows travel times for all roads. For each junction ‘i’, you are given ‘P[i]’, the time period between green flashes of the light at that junction. The light at junction ‘i’ flashes green at times 0, P[i], 2P[i], 3P[i] and so on.

Your task is to return the minimum time taken from a given source junction ‘src’ to a given destination junction ’des’ for a vehicle when the traffic starts. The junctions are identified by integers ‘0’ through ‘N - 1’. If we cannot reach the destination junction, then return -1.

For example:

Consider if ‘N’ = 3 and edges are 
[[0, 1, 2],
 [1, 2, 4]]
'P' = [2, 3, 4], and we have to reach from junction 0 to 2.
The time consumed from junction 0 to 1 is 2. We have to wait for 1 for the next green flash at junction 1. The time consumed from junction 1 to 2 is 4. The path 0 -> 1 -> 2 takes time 2 + 1 (wait till 3) + 4 = 7. Hence, the answer is 7.

You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note:

Here, sorted paths mean that the expected output should be in alphabetical order.

For Example:

Given a square matrix of size 4*4 (i.e. here 'N' = 4):
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1 
Expected Output:
DDRDRR DRDDRR 
i.e. Path-1: DDRDRR and Path-2: DRDDRR

The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.