Software Developer

Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses:
1. All open brackets must be closed by the closing brackets.

2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses.
)()()( is not a valid parentheses.

Tiny URL is an online URL shortening service, where you get a short version of a given URL as a substitute.

Your task is to design encode the original URL “S”, into a tiny URL and decode the previously encoded tiny URL into the original URL.

Example:

S= “https://youtu.be/dQw4w9WgXcQ”, can be encoded to TinyUrl “http://tinyurl.com/abcdef”, then in future queries “http://tinyurl.com/abcdef”  can be decoded into “https://youtu.be/dQw4w9WgXcQ”

Note:

The URL given to you for decoding will always be one of the URLs you have already returned after encoding in the past.

The encoded URL should strictly be of the format “http://tinyurl.com/abcdef”, where instead of “abcdef” you can have any alphanumeric code of length 6.

You are given an array ‘arr’ of size ‘N’. Your task is to maximize your score by doing the following operation at most ‘K’ – times.

1. Choose an element from the start or end of the array and the value of the element to your score.
2. Remove the element from the array you have chosen in step – 1.

Note:

Initially, you have a score of zero.

You are given an integer ‘N’. Your task is to find out the ‘N’th Tribonacci Number. ‘N’th number in the Tribonacci sequence is defined as T_n = T _{n - 1} + T_{n - 2} + T_{n - 3}. Where T₀ = 0, T₁ = 1, T₂= 1. Return the answer in mod of 10⁹ + 7.

For Example :

You are given ‘N’ = 5, Here we know 0th, 1st and 2nd Tribonacci numbers are 0, 1 and 1 respectively. Therefore we can calculate the 3rd number as 0 + 1 + 1 = 2 and 4th number as 1 + 1 + 2 = 4 and 5th number as 1 + 2 + 4 = 7. Hence the answer is 7.

Follow Up :

Can you solve it in logarithmic time?

You are given ‘N’ binary tree nodes numbered from 0 to N - 1 where node ‘i’ has two children LEFT_CHILD[i] and RIGHT_CODE[i]. Return ‘True’ if and only if all the given nodes form exactly one valid binary tree. If node ‘i’ has no left child then 'LEFT_CHILD[i]' will equal -1, similarly for the right child.

Example:

Let’s say we have n=4 nodes, 'LEFT_CHILD' = {1, -1, 3, -1} and 
RIGHT_CHILD = {2, -1, -1, -1}. So the resulting tree will look like this:

It will return True as there is only one valid binary tree and each node has only one parent and there is only one root.

Ninja and his friend are playing a game of subarrays. They have an array ‘NUMS’ of length ‘N’. Ninja’s friend gives him an arbitrary integer ‘K’ and asks him to find the length of the longest subarray in which the sum of elements is equal to ‘K’.

Ninjas asks for your help to win this game. Find the length of the longest subarray in which the sum of elements is equal to ‘K’.

If there is no subarray whose sum is ‘K’ then you should return 0.

Example:

Input: ‘N’ = 5,  ‘K’ = 4, ‘NUMS’ = [ 1, 2, 1, 0, 1 ]

Output: 4

There are two subarrays with sum = 4, [1, 2, 1] and [2, 1, 0, 1]. Hence the length of the longest subarray with sum = 4 is 4.