SDE - Intern

You are given an integer ‘K’, and two numbers ‘A’ and ‘B’. You need to count the occurrences of the given digit ‘K’, in the range [A, B].

Note:

 You need to count occurrences at every place of the number. You also need to include the lower and higher limits of the given range

For example :

Given K = 3, A = 1, B = 15, then 3 occurs 2 times(3, 13) in the range [1, 15], so you need to print 2.

Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the wildcard pattern is matched with the text. The matching should cover the entire text not partial text.

The wildcard pattern can include the characters ‘?’ and ‘*’

 ‘?’ – matches any single character 
 ‘*’ – Matches any sequence of characters(sequence can be of length 0 or more)

Given a binary tree of integers, you need to print the binary tree in a 2-D array of string such that -

1. There should be ‘H’ number of rows in the matrix where ‘H’ is the binary tree’s height.

2. The column number should always be an odd value.

The unfilled cells should contain an empty string “ “.

If the parent node is placed at matrix[ row ][ column ], this cell will divide the rest space into two parts, i.e., left part and right part. You should print the left subtree of this parent node in the left part and the right subtree in the right part.

Note

If one of the left and right subtree is empty while the other is not, then for the empty part, you don’t have to print anything but have to leave the space as that of the nonempty size subtree.

For Example

For the given binary tree

Matrix will look like as

[ “ “,  “ “,  “ “,  “2”,  “ “,  “ “,  “ “ ] 
[ “ “,  “6 “,  “ “,  “ “,  “ “,  “4 “,  “ “ ] 
[ “ “,  “ “,  “8 “,  “ “,  “ “,  “ “,  “ “ ] 

You are given ‘n’ items with certain ‘profit’ and ‘weight’ and a knapsack with weight capacity ‘w’.

You need to fill the knapsack with the items in such a way that you get the maximum profit. You are allowed to take one item multiple times.

Example:

Input: 
'n' = 3, 'w' = 10, 
'profit' = [5, 11, 13]
'weight' = [2, 4, 6]

Output: 27

Explanation:
We can fill the knapsack as:

1 item of weight 6 and 1 item of weight 4.
1 item of weight 6 and 2 items of weight 2.
2 items of weight 4 and 1 item of weight 2.
5 items of weight 2.

The maximum profit will be from case 3 = 11 + 11 + 5 = 27. Therefore maximum profit = 27.

Ninja has been given a string ‘STR’ containing either ‘{’ or ‘}’. 'STR’ is called valid if all the brackets are balanced. Formally for each opening bracket, there must be a closing bracket right to it.

For Example:

“{}{}”, “{{}}”, “{{}{}}” are valid strings while “}{}”, “{}}{{}”, “{{}}}{“ are not valid strings.

Ninja wants to make ‘STR’ valid by performing some operations on it. In one operation, he can convert ‘{’ into ‘}’ or vice versa, and the cost of one such operation is 1.

Your task is to help Ninja determine the minimum cost to make ‘STR’ valid.

For Example:

Minimum operations to make ‘STR’ =  “{{“ valid is 1.

In one operation, we can convert ‘{’ at index ‘1’ (0-based indexing) to ‘}’. The ‘STR’ now becomes "{}" which is a valid string.

Note:

Return -1 if it is impossible to make ‘STR’ valid.