Software Engineer Intern

You are given a 'M' x 'N' matrix of characters, 'CHARACTER_MATRIX' and a string 'WORD'. Your task is to find and print all occurrences of the string in the given character matrix. You are allowed to search the string in all eight possible directions, i.e. North, South, East, West, North-East, North-West, South-East, South-West.

Note: There should not be any cycle in the output path. The entire string must lie inside the matrix boundary. You should not jump across boundaries, i.e. from row 'N' - 1 to 0 or column 'N' - 1 to 0 or vice versa.

Example:

Consider below matrix of characters,
[ 'D', 'E', 'X', 'X', 'X' ]
[ 'X', 'O', 'E', 'X', 'E' ] 
[ 'D', 'D', 'C', 'O', 'D' ]
[ 'E', 'X', 'E', 'D', 'X' ]
[ 'C', 'X', 'X', 'E', 'X' ]

If the given string is "CODE", below are all its occurrences in the matrix:

'C'(2, 2) 'O'(1, 1) 'D'(0, 0) 'E'(0, 1)
'C'(2, 2) 'O'(1, 1) 'D'(2, 0) 'E'(3, 0)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(1, 2)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(3, 0)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(3, 2)
'C'(2, 2) 'O'(2, 3) 'D'(2, 4) 'E'(1, 4)
'C'(2, 2) 'O'(2, 3) 'D'(3, 3) 'E'(3, 2)
'C'(2, 2) 'O'(2, 3) 'D'(3, 3) 'E'(4, 3)

You are given a string ‘S’ of length ‘N’.

You must return the longest palindromic substring in ‘S’.

Note: Return any of them in case of multiple substrings with the same length.

Example:

Input: ‘S’ =’badam’

Output: ‘ada’

‘ada’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

Example:

Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6

In the given input, the number of vertices is 4, and the number of edges is 5.

In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’.

As per the input, there is an edge between node 0 and node 1 and the distance between them is 5.

The vertices 0 and 2 have an edge between them and the distance between them is 8.
The vertices 1 and 2 have an edge between them and the distance between them is 9.
The vertices 1 and 3 have an edge between them and the distance between them is 2.
The vertices 2 and 3 have an edge between them and the distance between them is 6.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There can be parallel edges i.e. two vertices can be directly connected by more than 1 edge.

You have been given a sorted array/list 'arr' consisting of ‘n’ elements. You are also given an integer ‘k’.

Now the array is rotated at some pivot point unknown to you.

For example, if 'arr' = [ 1, 3, 5, 7, 8], then after rotating 'arr' at index 3, the array will be 'arr' = [7, 8, 1, 3, 5].

Now, your task is to find the index at which ‘k’ is present in 'arr'.

Note :

1. If ‘k’ is not present in 'arr', then print -1.
2. There are no duplicate elements present in 'arr'. 
3. 'arr' can be rotated only in the right direction.

Example:

Input: 'arr' = [12, 15, 18, 2, 4] , 'k' = 2

Output: 3

Explanation:
If 'arr' = [12, 15, 18, 2, 4] and 'k' = 2, then the position at which 'k' is present in the array is 3 (0-indexed).

You have been given a root node of the binary search tree and a positive integer value. You need to perform an insertion operation i.e. inserting a new node with the given value in the given binary search tree such that the resultant tree is also a binary search tree.

If there can be more than one possible tree, then you can return any.

Note :

A binary search tree is a binary tree data structure, with the following properties :

    a. The left subtree of any node contains nodes with a value less than the node’s value.

    b. The right subtree of any node contains nodes with a value equal to or greater than the node’s value.

    c. Right, and left subtrees are also binary search trees.
It is guaranteed that,

    d. All nodes in the given tree are distinct positive integers.

    e. The given BST does not contain any node with a given integer value.

Example, below the tree, is a binary search tree.

Below the tree is not a BST as node ‘2’ is less than node ‘3’ but ‘2’ is the right child of ‘3’, and node ‘6’ is greater than node ‘5’ but it is in the left subtree of node ‘5’.

You have been given a Snake and Ladder Board with 'N' rows and 'N' columns with the numbers written from 1 to (N*N) starting from the bottom left of the board, and alternating direction each row.

For example

For a (6 x 6) board, the numbers are written as follows:

You start from square 1 of the board (which is always in the last row and first column). On each square say 'X', you can throw a dice which can have six outcomes and you have total control over the outcome of dice throw and you want to find out the minimum number of throws required to reach the last cell.
Some of the squares contain Snakes and Ladders, and these are possibilities of a throw at square 'X':
You choose a destination square 'S' with number 'X+1', 'X+2', 'X+3', 'X+4', 'X+5', or 'X+6', provided this number is <= N*N.
If 'S' has a snake or ladder, you move to the destination of that snake or ladder.  Otherwise, you move to S.
A board square on row 'i' and column 'j' has a "Snake or Ladder" if board[i][j] != -1. The destination of that snake or ladder is board[i][j].

Note :

You can only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving - you have to ignore the snake or ladder present on that square.

For example, if the board is:
-1 1 -1
-1 -1 9
-1 4 -1
Let's say on the first move your destination square is 2  [at row 2, column 1], then you finish your first move at 4 [at row 1, column 2] because you do not continue moving to 9 [at row 0, column 0] by taking the ladder from 4.

A square can also have a Snake or Ladder which will end at the same cell.
For example, if the board is:
-1 3 -1
-1 5 -1
-1 -1 9
Here we can see Snake/Ladder on square 5 [at row 1, column 1] will end on the same square 5.