SDE - 1

Ninja went to an amusement park and visited a maze. Now, he is stuck in the maze. He can go in any direction(Up, Down, Left, or Right) from this point, but he cannot change his direction of motion until he comes across a wall in its path. Once he stops, he can choose his new direction.

Now, you are given Ninja’s starting point, the destination he wants to reach, and the maze in the form of a 2D matrix. You need to find out if Ninja can reach the destination from the starting point or not.

The maze is represented by a 2D array. ‘1’ means Ninja came across a wall and he needs to stop. ‘0’ means that it is an empty space and he can keep moving.

The coordinates of starting point and destination are represented by row and column numbers.

For Example

Given maze: {[0, 0, 1], [1, 0, 0], [1, 0, 0]} 
Starting point: [2, 2]
Destination: [0, 0]

For the above example maze will look like this:

So, we can see there are 2 ways for Ninja to reach destination(D), from the starting point(SP). They are: [left -> up -> left] and [up -> left -> up -> left].
So, you need to print true.

In Ninja Land there are ‘N’ cities numbered from 0 to ‘N’-1. The distance between each pair of cities is given by N * N matrix ‘DIST’ where ‘DIST[i][j]’ denotes the distance between city ‘i’ and ‘j’.

Ninja wants to select ‘K’ (‘K’ <= ‘N’) cities and install Coding Ninjas Server in these cities. He wants to select ‘K’ cities in such a way that the maximum distance of a city from the Coding Ninjas Server is minimized.

Can you help Ninja in finding this maximum distance if he selects ‘K’ cities optimally? You should return this distance.

Note :

1. DIST[i][j] = DIST[j][i].
2. DIST[i][i] = 0.

Example :

Consider that there are 4 cities i.e. ‘N’ = 4, and the distance between each pair of cities is given by the following matrix ‘DIST’:  
             [0, 10, 7, 6]
             [10, 0, 8, 5]
             [7, 8, 0, 12]
             [6, 5, 12, 0]

Graphically, cities can be represented as -:

Assume Ninjas wants to install a server in 2 cities i.e ‘K’ = 2.  Then one optimal choice is to select cities 2 and 3.
After that, the minimum distance of city 0 from the server is  6  (i.e from city 2).
The minimum distance of city 1 from the server is 5  (i.e from city 3).
The minimum distance of cities 2 and 3 from the server is 0, as the server is installed in these cities.
Thus the maximum distance of the city from the server is max (6, 5, 0, 0) = 6.
So, we should return 6.
No selection of two cities can give a maximum distance which is less than 6.

Given an input string 'S' and a pattern 'P', implement a regular expression matching with the support of two special characters ‘.’ (dot) and ‘*’(asterisk) where

1. ‘.’ matches to any single character.
2. ‘*’ matches to zero or more of the preceding element.

If the input string 'S' matches the pattern 'P', then return true else, return false.

Note:

1. You have to match the entire string with the pattern given.

2. Both the strings, 'S' and 'P' contain only lower-case alphabets.

3. Only the pattern will contain additional characters ‘*’ and ‘.’ along with alphabets.

You're given a string 'S' consisting of "{", "}", "(", ")", "[" and "]" .

Return true if the given string 'S' is balanced, else return false.

For example:

'S' = "{}()".

There is always an opening brace before a closing brace i.e. '{' before '}', '(' before ').
So the 'S' is Balanced.

There is an array 'JUMP' of size 'N' which is 1-indexed and you are currently at index 1. Your goal is to reach index 'N' (end).

When you are at index 'i', you can jump a maximum length of 'JUMP[i]' which means you can make a jump of size 1 to JUMP[i]. Return true if you can reach the end otherwise false.

Example:-

N = 5
JUMP = [1,2,3,4,5]

ANSWER:- The answer should be YES as you can jump from 1st index to 2nd index, from 2nd index to 4th index, and from 4th index to 5th index.

You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.