SDE - Intern

Given two binary trees T and S, check whether tree S has exactly the same structure and node values with a subtree of T, i.e., check if tree S is a subtree of the tree T.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List rather for each node in the original Linked List, a new node is created.

For example,

Random pointers are shown in red and next pointers in black.

Ninjas are often known for their stealth execution and accuracy to get the job done right. While honing their art of moving through dense forests stealthily, they need the maximum number of continuous trees one after the other for practicing.

Trees are represented by 1s and empty places by 0s (basically a binary representation of a given integer). You are also given an extra tree which you can plant at any empty place (i.e. you can flip one of the zeroes in the binary representation to 1). The tree should be planted such that the maximum number of consecutive trees is maximized.

Your task is to report the maximum number of consecutive trees after plantation.

Note:

You may also choose not to plant that extra tree at all.

For Example:

Input: 54
Output: 5

The binary representation of 54 is 110110.
After flipping the third bit from the left, we get consecutive 5 bits. i.e. 111110.

Ninja likes to travel a lot, but at the same time, he wants to save as much money as possible.

There are ‘N’ Stations connected by ‘M’ Trains. Each train that he boards starts from station ‘A’ and reaches destination station ‘B’ with a ticket price ‘P’.

Your task is to return the cheapest price from the given ‘source’ to ‘destination’ with up to ‘K’ stops. If there is no such route, return ‘-1’.

For example:

Input:
5 6
0 1 10
0 2 10
0 3 40
1 4 10
2 4 20
4 3 5
0 3 40 

There are three ways to reach station ‘3’ from station ‘0’. The first path is 0->1->4->3, which will cost us 10+ 10+ 5= 25 and the second path 0->2->4->3 will cost us, 10+ 20+ 5 = 35, and the third path 0->3 will cost us 40. 

We can’t take the first path since K = 1 and in this path, we are taking 2 stops, at station ‘1’ and station ‘4’. 

Similarly, there are 2 stops in the second path. Hence we’ll finally choose the 3rd path i.e. 0->3, which is colored in blue.

You have been given a non-empty grid ‘mat’ with 'n' rows and 'm' columns consisting of only 0s and 1s. All the rows are sorted in ascending order.

Your task is to find the index of the row with the maximum number of ones.

Note: If two rows have the same number of ones, consider the one with a smaller index. If there's no row with at least 1 zero, return -1.

Example:

Input: 'n' = 3, 'm' = 3, 'mat' = [[1, 1, 1], [0, 0, 1], [0, 0, 0]]

Output: 0

Explanation: The row with the maximum number of ones is 0 (0 - indexed).

You are given an N x N chessboard and a knight. On a chessboard, the knight can supposedly move in 8 different positions from its original position i.e. if the knight is originally at (i,j) then it can move to (i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), (i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), (i - 1, j - 2).

The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N - 1, N - 1).

(X is the Knight’s current position, O is the position Knight can visit in 1 move)

You have to make K such moves from the initial position of the knight and tell the probability of the knight being within the boundaries of the chessboard i.e you have to consider all possibilities of K moves and determine the probability that after these moves the knight will remain within the chess grid.

Note:

Print output up to 6 decimal places.