SDE - Intern

You are given a string ‘st’, Your task is to find the length of the longest repeating subsequence such that two subsequences don’t have the same character at the same position.

For Example :

The given string st = AABCBDC.

As you can see there are two repeating longest subsequences “ABC” with the same character but different position. Therefore the required answer is ‘3’ as the length of “ABC” is 3.

You are given an array 'a' of size 'n'.

Print the Next Greater Element(NGE) for every element.

The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.

If no greater elements exist to the right of 'x', consider the next greater element as -1.

For example:

Input: 'a' = [7, 12, 1, 20]

Output: NGE = [12, 20, 20, -1]

Explanation: For the given array,

- The next greater element for 7 is 12.

- The next greater element for 12 is 20. 

- The next greater element for 1 is 20. 

- There is no greater element for 20 on the right side. So we consider NGE as -1.

Ninja lives in a 2D plane where each location is represented with integer coordinates ‘[X, Y]’. You are given an array ‘POINTS’ containing ‘N’ such points. Ninja lives at the location ‘POINTS[0]’ and wants to visit all the remaining ‘N-1’ points in the order given by the ‘POINTS’ array. Your task is to help ninja find the minimum time (in seconds) required to visit all the points in the given order (starting from ‘POINTS[0]’).

The ninja can travel according to the following rules :

• In one second, the ninja can either:
  • Move vertically by one unit, i.e., along the y-direction.
  • Move horizontally by one unit, i.e., along the x-direction.
  • Move diagonally by ‘sqrt(2)’ units, i.e., move one unit horizontally then one unit vertically.
• The ninja must visit the points in the exact order as they are given the ‘POINTS’ array.
• The ninja is allowed to pass through points that may be given later in the order, but these points will not be counted as visited.

For Example :

‘POINTS = [ [3, 1], [-1, 3], [2, 0] ]’, ‘N = 3’

The path with minimum time is: ‘[3,1] -> [2,2] -> [1,3] - > [0,3] -> [-1,3] -> [0,2] -> [1,1] -> [2,0]’.

Time taken from [3,1] to [-1,3] = 4 seconds.
Time taken from [-1,3] to [2,0] = 3 seconds.

Total time = 7 seconds. Thus, you should return ‘7’ as the answer.

Given a binary tree and the value of two nodes, find the distance between the given two nodes of the Binary Tree.

Distance between two nodes is defined as the minimum number of edges in the path from one node to another.