SDE - 1

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 two strings ‘S1’ and ‘S2’. Your task is to find the smallest substring of ‘S1’ which contains all the characters of ‘S2’. The characters of ‘S2’ need not be present in the same order in S1. That is, we need a substring that contains all characters of ‘S2’ irrespective of the order.

A substring is a contiguous sequence of characters within a string.

Example

Let ‘S1’ be “ABBCD” and ‘S2’ be “ABC”, so the smallest substring of ‘S1’ which contains all the characters of S1 is “ABBA”.

Ninja is learning tree data structure these days. While learning, she came across learn about the Binary Search tree. She found BST quite interesting. She decided to make her own Binary Search Tree. Being a newbie, she made a mistake and swap two nodes of the Binary Search Tree.

Your responsibility being an expert and a good friend is to correct the Binary Search Tree made by Ninja and recover the correct Binary Search Tree.

A binary search tree (BST) is a binary tree data structure with the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Example

This is the binary search tree made by Ninja. But here, the left node of 8 is greater, and the right node is smaller.
If we swap the right and the left node of 8 Ninja’s Binary Search Tree will become correct.

This is the correct binary Search Tree.

Ninja is planning to organize an exhibition in which ‘2N’ peoples are coming. The hall’s capacity in which the exhibition is going to take place is only ‘N’. So, ninja thinks of organizing two exhibitions in 2 different cities, ‘CITY_A’ and ‘CITY_B’, each of capacity ‘N’. All ‘2N’ people will come to the exhibition but in the group of ‘N’ in two different cities. Ninja wants your help in organizing this event.

You are given an array ‘COST’ where “COST[i] = [COST_TO_Ai, COST_TO_Bi]”, in which ‘COST_TO_Ai’ is the cost of the ith person to fly to the city A, and ‘COST_TO_Bi’ is the cost of the ith person to fly to the city B. Your task is to find the minimum cost of organizing the exhibition in which every person flies to a city such that exactly ‘N’ people arrive in each city.

Note:

The intersection of the set of the persons who go to ‘CITY_A’ to those going to ‘CITY_B’ is to be disjoint set, whereas the union must be the ‘2N’.

You are given a string 'S' containing only digits. Your task is to find all possible IP addresses that can be obtained from string 'S' in lexicographical order.

Note:

A valid IP address consists of exactly four integers, each integer is between 0 and 255 separated by single dots, and cannot have leading zeros except in the case of zero itself.

For example:

The following are valid IP addresses:
0.1.24.255
18.5.244.1

Following are invalid IP addresses:
0.01.24.255  (as  01  contains one leading zero).
18.312.244.1 (as 312 not lies between 0 and 255).