Question: Google | OA | 2022 | Balanced brackets | Maximize equal numbers | Diagonal number
1
Entering edit mode

# Question 1

## Balanced brackets

You are given a string S of length M. It consists of only two
characters;

• (: Opening bracket
• ): Closing bracket

S is a balanced bracket sequence. Formally, a sequence of brackets is balanced-if the following conditions are met:

• It contains no unmatched brackets.
• The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

You are required to insert the character '+' in S such that there exists at least one '+'  enclosed within each pair of matched
bracket sequence. Find the minimum number of ' characters to be inserted in S to satisfy the provided condition.

### Input format

• The first line contains an integer T denoting the number of test cases. For each test case :-
• The of first line of each test case contains an integer -N denoting the length of string S
• The next line of each test case contains a string S.

### 1 ≤ T < 10 1≤ N ≤ 10 N is even

`````` Sample Input          Sample Output
1                            2
6
()(())``````

# Question 2

## Maximize equal numbers

You are given the following:

• An array a consisting of n elements
• Integer k

For each (1 ≤ i ≤ n), perform the following operation exactly one
time:

• Replace a, by a, + x where z € [-k, k) which denotes should lie in the range of -k and k, both inclusive.

Determine the maximum length of the subsequence of array a, such that all numbers in that subsequence are equal after applying the given operation.

### Notes

•  A subsequence of array a is an array that can be derived from array a by removing some elements from it. (maybenone or all of them)
• Assume 1 based indexing

### Assumptions

• n = 4
• k = 1
• Array a = [2, 5, 1, 2]

### Approach

Applying one operation on indices 1, 2, and 4, with x = 0 to get
array a as [2, 5, 1, 2].

Applying one operation on index 3, with x = 1 to get array a as [2, 5, 2, 2]

Therefore, the maximum length of the subsequence with equal numbers is 3.

### Function description

Complete the Maximize qualNumbers function provided in the editor. This function takes the following 3 parameters and returns the maximum length of the subsequence:

• n. Represents the size of array a
• k. Represents the integer k
• a. Represents the array a of length n

### Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

0 ≤ k ≤ 109

1 ≤ a≤ 109

``````Sample Input              Sample Output
2                               2
4 0                             2
2 2 5 6
3 2
1 5 6
``````

### Explanation

The first line represents the number of test cases
For test case 1:

Applying one operation with x - 0 on index 1, 2, 3, and 4 to get array
as [2, 2,5, 6]

# Question 3

## Diagonal number

Consider a square matrix of size N sorted diagonally (bottom left to the top right). The diagonals in the matrix are numbered and filled with integer values from 1 to Nas given below.
For example, consider a square matrix of size N = 3 then we have the following matrix.                                            You are given Q queries

and each query has an Integer x.

Determine the diagonal number to which x belongs.

### Notes

• The matrix is filled diagonally (bottom left to the top right). A diagonal is filled only all the previous diagonals are filled

• The diagonals are filled starting with integer value 1 and so on

### Input Format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).
• The first line contains an integer N denoting the size of the matrix.
• The next line contains an integer Q denoting the number queries.
• The next line contains Q space-separated integers denoting x for each query.

### Output format

For each query, print a single integer in a new line representing
the diagonal number to which x belongs.

### Constraints

•   N   106
•   Q   106
•   X   N2

``````Sample Input             Sample Output

5                              1
3                              6
1 16 25                        9``````

### Explanation

Consider a square matrix of size N = 5

For Query 1,1  occurs in the diagonal numbered 1

For Query 2,16  occurs in the diagonal numbered 6

For Query 3,25  occurs in the diagonal numbered 9

2
Entering edit mode

## Problem 2

### Approach

Since every element can be from a{i}-k to a{i}+k we will calculate the range of numbers an element can be and then calculate the maximum overlapping range.

Then

• The idea is to store coordinates in a new vector of pair mapped with characters ‘x’ and ‘y’, to identify coordinates.
• Sort the vector.
• Traverse the vector, if an 'x' coordinate is encountered it means a new range is added, so update count and if 'y' coordinate is encountered that means a range is subtracted.
• Update the value of the count for every new coordinate and take the maximum.

### Code

``````void solve() {
int n, k;
cin >> n >> k;
int ans = 0;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
/*since every element can be from a{i}-k to a{i}+k we will
calculate the range of numbers an element can be and then
calculate the maximum overlapping range */
vector<pair<int, char>> v;
for (int i = 0; i < n; i++) {
v.push_back({a[i] - k, 'x'});
v.push_back({a[i] + k, 'y'});
}
sort(v.begin(), v.end());
int count = 0;
for (int i = 0; i < v.size(); i++) {
// if x occur it means a new range
// is added so we increase count
if (v[i].second == 'x')
count++;
// if y occur it means a range
// is ended so we decrease count
if (v[i].second == 'y')
count--;
// updating the value of ans
// after every traversal
ans = max(ans, count);
}
cout << ans << endl;
return;

}``````

### Complexity

O(n log n) n is the size of the array.

Entering edit mode
0

A vector of pair is not required I believe, You can just sort the given array and use a sliding window approach to maximise the overlapping intervals.

``````#include <bits/stdc++.h>
using namespace std;

int main() {

int n,k;
cin>>n>>k;
vector<int> v(n);
for(int i=0; i<n; i++){
cin>>v[i];
}
sort(v.begin(),v.end());

int left = 0;
int maxlen = 1;
for(int right = 0; right<n;){
if(v[left]+k >= v[right]-k){
if(maxlen <= (right-left+1)) maxlen = right - left + 1;
right++;
}
else {
left++;
}
}
// if(maxlen <= int(right-left+1)) maxlen = right - left + 1;
cout << maxlen << "\n";

return 0;

}`````` Similar Posts