Question: Google | OA | 2022 | Balanced brackets | Maximize equal numbers | Diagonal number
2
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. 


Output format


For each test case. print the minimum number of characters that must be be inserted in string S in a new line.


Constraints


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

 

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

 



Question 2

Maximize equal numbers

Click here to Practice


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.

Task


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

Example

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.


Task


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

 

 

3
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.

ADD COMMENTlink 12 months ago Akash 240
Entering edit mode
2

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;

  }

 

ADD REPLYlink 10 months ago
Spark
• 20
Entering edit mode
0

# problem description : https://thejoboverflow.com/p/p1198/#p1199


[n, k] = [int(i) for i in input().split(" ")]
a = [ int(i) for i in input().split(" ")]

l = []
for i in range(n):
    l.append([a[i]-k, 'S'])
    l.append([a[i]+k, 'E'])
l.sort()
ans = 0
current = 0
for i in range(len(l)) :
    if l[i][1] == "S" :
        current += 1
    else :
        current -= 1
    ans = max(ans, current)
    
print(ans)
       

 

Hi I am getting Wrong answer in test case 1 itself. Can you help in find out the error. Thanks in advance.

ADD REPLYlink 8 months ago
Haritha Kallamadi
• 0
1
Entering edit mode

Problem 2

Used a Sliding window kind of approach

import java.util.*;
public class Main {
    public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      int k=sc.nextInt();
      int[] arr=new int[n];
      for(int i=0;i<n;i++)
        arr[i]=sc.nextInt();
      Arrays.sort(arr);
      int idx=1;
      int ans=1;
      int l=0, r=1;
      while(r<n){
        while(idx<n&&arr[l]==arr[idx]){
          idx++;
        } 
        if(r<n&&arr[l]+k>=arr[r]-k){ 
          r++;
          ans=Math.max(ans,r-l);
        }
        else{
          l=idx;
        }
        
      }
      System.out.println(ans);
    }
  }

 

ADD COMMENTlink 12 weeks ago Mayank Jain • 10

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts