Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

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 2.3 years 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 2.1 years 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 24 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 17 months ago Mayank Jain • 10
0
Entering edit mode

Problem 2

 

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {

    int n,k;
    cin>>n>>k;
    
    vector<int>arr(n);
    for(int i=0;i<n;i++){
      cin>>arr[i];
    }
    
    sort(arr.begin(),arr.end());
    
    int ans = 1;
    for(int i=0;i<n;i++)
    {
        int count = 0;
        int it = (arr.begin()+i) - upper_bound(arr.begin(),arr.begin()+i,arr[i]-k-1);
        count += it;
        it = upper_bound(arr.begin()+i,arr.end(),arr[i]+k) - (arr.begin()+i);
        count += it;
        ans = max(ans,count);
    }
    
    cout<<ans<<endl;
     
    return 0;

  }

 

Getting Wrong answer on 15th test case

ADD COMMENTlink 13 months ago Manpreet Singh Saluja • 0
0
Entering edit mode

Problem 1:

<code>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
   int n;
   cin >> n;
   string s;
   cin >> s;
   vector<pair<int, int>> pairs;
   stack<pair<char, int>> st;
   for (int i = 0; i < n; i++) {
       if (s[i] == '(') {
           st.push({'(', i});
       } else {
           auto p = st.top();
           st.pop();
           pairs.push_back({p.second, i});
       }
   }

   int ans = 100;

   auto check = [&](int l, int r, int mask) -> bool {
       for (int i = l + 1; i <= r; i++) {
           if (mask & (1 << i)) {
               return true;
           }
       }
       return false;
   };

   for (int mask = 0; mask < (1 << (n + 1)); mask++) {
       int bits = __builtin_popcount(mask);
       if (bits >= ans)
           continue;
       bool ok = true;
       for (const auto &[l, r] : pairs) {
           if (!check(l, r, mask)) {
               ok = false;
               break;
           }
       }
       if (ok)
           ans = bits;
   }

   cout << ans << "\n";
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int t;
   cin >> t;
   while (t--) {
       solve();
   }
}

</code>
 

Problem 3:
<code>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    int m = 2*n - 1;
    vector<ll> p(m + 1, 0);
    for (int i = 1; i <= m + 1 - i; i++) {
        p[i] = p[m + 1 - i] = i;
    }
    for (int i = 1; i <= m; i++) {
        p[i] = p[i - 1] + p[i];
    }

    while (q--) {
        ll x;
        cin >> x;
        int l = 1, r = m;
        while (l < r) {
            int mid = (l + r) / 2;
            if (p[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        cout << r << " ";
    }
    cout << "\n";
}

</code>

ADD COMMENTlink 3 months ago Sourav Mohapatra • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts