SDE - 1

Ninja was solving questions on the array where he came across a question in which Ninja has an array ‘ARR’ of ‘N’ integers in which he has to perform the following operations to get the result.

1- In one successful operation, Ninja can remove two positive integers, ‘A’ and ‘B’, and insert their sum, i.e., ‘A’ + ‘B’ into the position of either ‘A’ or ‘B’.

2- To insert sum in the position of element ‘A’, the condition 2 * ’A’ >= ‘B’ should be satisfied. Similarly, to insert the sum in the position of element ‘B’, the condition 2 * ‘B’ >= A should be satisfied.

3- We will insert the sum at one position, and the value at the other position should be changed to -1.

4- The resultant array should contain only 1 positive element.

Your task is to find the count of distinct combinations possible for the array.

Note:

A combination is different if they lead to a different position of the element that remains positive at the end of all successful operations for that combination.

For example:

Let ‘ARR’ be: {2, 1}
Combination 1: 
Pick 2 and 1 and insert their sum at the position of 2: [3, -1]

Combination 2:
Pick 2 and 1 and insert their sum at the position of 1: [-1, 3]

So total combinations are 2.

Given a string "pattern", which contains only two types of characters ‘(’, ‘)’.

Your task is to find the minimum number of parentheses either ‘(’, ‘)’ we must add the parentheses in string ‘pattern’ and the resulted string is valid.

Condition for valid string-

Every opening parenthesis ‘(’ must have a correct closing parenthesis ‘)’.

Example - ‘(()(()))’, ‘()()()’, ‘((()))’ are valid string, and ‘(((’, ‘(()’, ‘)(())’ are invalid string.

Note:

1. You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the minimum number of parentheses required to make a string valid.

You are given a binary tree with ‘N’ nodes.

Your task is to find the “Maximum Path Sum” for any path.

Note :

1. A ‘path’ is a sequence of adjacent pair nodes with an edge between them in the binary tree.
2. The ‘path’ doesn’t need to pass through the root.
3. The ‘path sum’ is the sum of the node’s data in that path. 

Given a singly linked list of 'N' nodes. The objective is to determine the middle node of a singly linked list. However, if the list has an even number of nodes, we return the second middle node.

Note:

1. If the list is empty, the function immediately returns None because there is no middle node to find.
2. If the list has only one node, then the only node in the list is trivially the middle node, and the function returns that node.

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false.