10 months ago

Rohit • 660

Hyderabad

Avg CTC: 20lpa

Application Link: Job List

Question 1

Original number

You are given an array A consisting of N continuous natural numbers denoting the seat numbers in a theater. The array values are as follows A = [1, 2, 3, ..., N].

You have to process Q queries of two different types:

• type = 1 and value = X:

  The current seat number X is occupied now (denoted by ), and the seat number of all the vacant seats that have current seat numbers greater than X is decreased by one.

  Thus, the enumeration of seats (i.e. current seat numbers at the theater) always remains continuous.

• type = 2 and value = X:

  Determine the original seat number (seat number before processing any query) of the current seat number X.

Task

Determine the original seat number for each type 2 query in the given order.

Notes

• All seats are vacant initially and current seat numbers are the same as original seat numbers.
• 1 based indexing is followed.
• Queries are dependent and processed in the given order.
• For each query of type 1, the current seat number X always exists.
• There is at least one query of type 2.
• N = 6
• Q=5
• Query = [[2 3], [1 3], [2 3], [1 2], [2 4]]

Approach

Initially, A = [1, 2, 3, 4, 5, 6] (all seats are vacant)

• In the 1st query, the original seat number at the current seat number 3 is 3.
• After processing the 2nd query, A = [1, 2, 0, 3, 4, 5] (O denotes an occupied seat).
• In the 3rd query, the original seat number at the current seat number 3 was 4.
• After processing the 4th query, A = [1, 0, 0, 2, 3, 4] (0 denotes an occupied seat).
• In the 5th query, the original seat number at the current seat number 4 was 6.

Therefore, the answer is [3, 4, 6].

Input format

• The first line contains a single integer N denoting the initial number of vacant seats.
• The second line contains a single integer Q denoting the number of queries.
• The next Q lines contain two space-separated integers denoting the type of query and seat number.

Output format

Print an integer array denoting the answer to the type 2 queries. Each value that is printed must be space-separated.

Constraints

• 1 <= N <= 10^5
• 1 <= Q <= 10^5
• 1 <= type <= 2
• 1 <= X <= 10^15

Sample Input

5
5
1  2
1  1
2  1
1  2
2  2

Sample Output

3  5

Explanation

Given

• N=5
• Q = 5
• Query = [[1 2], [1 1], [2 1], [1 2], [2 2]]

Approach

Initially, A = [1, 2, 3, 4, 5] (all seats are vacant)

• After processing the 1st query, A = [1, 0, 2, 3, 4] (0 denotes an occupied seat).
• After processing the 2nd query, A = [0, 0, 1, 2, 3] (O denotes an occupied seat).
• In the 3rd query, the original seat number at the current seat number 1 was 3.
• After processing the 4th query, A = [0, 0, 1, 0, 2] (O denotes an occupied seat).
• In the 5th query, the original seat number at the current seat number 2 was 5.

Therefore the answer is [3, 5].

Question 2

Find the total number of subsequences in an array whose elements are in GP with a common ratio of a prime number.

NOTE: The common ratio can by any prime number

Constraints:

• 1 <= array length = 10000
• 1 <= array elements <= 100000

Question 3

Find number of ways to divide array A of size N into two subsets such that sum of each subset is greater than K.

Constraints:

• 1 <= N <= 10^3
• 1 <= K <= 10^5
• 1 <= A[i] <= 10^9

Question 4

String Transformation

You are given two strings S and T of the same length. You need to determine if it's possible to transform string S into T with the following rule any number of times. You can map a character from string S to a character of String T and replace all the occurrences of that character in string S.

Notes:

• All occurrences of a character must be replaced with another character while preserving the order of characters
• No two characters may map to the same character, but a character may map to itself.

Input Format: The first line of input contains an integer N, the number of test cases.

For every test case:

• The first line contains string S.
• The second line contains string T.

Output Format:

For every test case, return a boolean in a new line, indicating if it's possible to transform S into T.

Question 5

Watchmen Trouble

A river has N checkpoints on left side and M checkpoints on the right side. P bridges are built connecting checkpoints across the river. Guards needs to be placed on checkpoints, a guard can protect all the bridges on which this checkpoint is present. There can be more than one guard to protect a single bridge.

Find the minimum number of guards required to protect all the bridges over the river.

Example:

If N = 4, M = 3, P = 4, bridge = [(1,3),(1,2),(2,2),(4,1)]

• If we place a guard on checkpoint 1 on left side, then we can guard the bridge 1 - 3 and 1 - 2.
• If we place a guard on checkpoint 2 on left side, then we can guard the bridge 2 - 2.
• If we place a guard on checkpoint 4 on left side, then we can guard the bridge 4 - 1.

Hence, minimum 3 guards are required to protect all the bridges.

2.4 years ago

Yash Sahijwani 960

Solution for Question 5 - Watchmen Trouble

Analysis

In the question, it is mentioned that we have N checkpoints on the left side of the river, and M checkpoints on the right side of the river, and there are P bridges which connect checkpoints on the left side to checkpoints on the right side. This means, that there is no bridge between checkpoints on the same side of the river. So, for each bridge, one endpoint is on the left side and one endpoint is on the right side.

We can visualize this using the following image:

Here, the red vertices can be seen as checkpoints on the left side of the river, and blue vertices as the checkpoints on the right side of the river, and the edges are the bridges connecting them. From the image it is clear that the graph is a Bipartite Graph. A Bipartite graph is a graph in which we can separate all the vertices in the graph into 2 disjoint sets, say U and V, such that for each edge - one endpoint is in U and the other edge is in V. i.e. both endpoints of the edge can't be in the same set U/V. You can read more about Bipartite Graphs here.

Now, we need to find the minimum number of guards needed to protect all the bridges. A guard at a checkpoint can protect all bridges which have an endpoint at that checkpoint. So for all bridges, we need that atleast one endpoint of the bridge is covered by a guard. This becomes the minimum vertex cover problem. A vertex cover is basically a set of vertices which cover atleast one endpoint of each edge in the graph. The minimum vertex cover is a vertex cover with the minimum possible number of vertices. You can read more about minimum vertex cover here.

Here are some examples of a minimum vertex cover, where the red vertices are the vertices in the minimum vertex cover:

Now, calculating minimum vertex cover for a graph is NP-hard, but since it is a Bipartite Graph it can be done in polynomial time. To calculate the minimum vertex cover of a Bipartite Graph, we will use Konig's Theorem, which uses Maximum Bipartite Matching.

Hence, I'll give a brief explanation of what Matching in Graphs is, but it is advised to go through Matching, Maximum Bipartite Matching and Flows (since Maximum Bipartite Matching is calculated using Flows).

A matching in a graph is a set of edges, such that no 2 edges share a vertex. This means, that if there is an edge in a matching, then for both the endpoints of that edge, there cannot be another edge starting from those endpoints. A maximum matching is such that we cannot add any other edge to the matching (otherwise it will break the condition for it being a matching) and it has the maximum number of edges possible.

Now Konig's theorem states that in a Bipartite Graph, the size of the minimum vertex cover is equal to the size of the Maximum Bipartite Matching of the graph, i.e. the number of vertices in the minimum vertex cover is equal to the number of edges in the maximum bipartite matching. There are multiple proofs of the algorithm here but I'll try and explain the constructive proof here.

Proof for Konig's Theorem

Given a bipartite graph G(U, V, E), where U and V are the disjoint sets of vertices (red and blue) and E is the set of edges, we need to find a vertex set S⊆U∪V of minimum size that covers all edges, i.e. every edge (u,v) has at least one endpoint in S, that is u∈S or v∈S or both.

Let us consider the bipartite graph given below, where the edges in the maximum bipartite matching are marked in blue. The nodes in the upper row represent the vertex set U, and the nodes in the lower row represent the vertex set V.

Now let us create a set Z which consists of all unmatched vertices in the vertex set U. By unmatched, I mean vertices which don't have a matching starting at them. From the image, we can see that r7 and r8 are the ones which will be in this set.

Then, to this set Z we add all vertices which are reachable using an alternating path from the vertices in Z. By alternating path, I mean a path in which the edges switch between edges in the matching and edges not in the matching (so for 2 adjacent edges, one should be in the matching and the other shouldn't). From this, we get the following (all vertices colored red are in the set Z)

So, if we look carefully, since the initial nodes in the set were unmatched, they can reach the nodes in the set V using an edge not in the matching, then the nodes in the set V reach nodes in the set U using edges in the matching, and then again they use edges not in the matching and so on. So in an alternating path, we will have

(edge not in matching, edge in matching, edge not in matching, edge in matching, .... )

Now, if we have an edge (u, v) (where u is from the set U, and v is from the set V) in the matching, say M, then if v is in the set Z, then u will also be in the set Z. This is because, the alternating path would have reached v in which the last edge would have been an edge not in the matching. So that alternating path can be extended by using an edge in the matching. Hence, if (u, v) belong to the matching M, and if v belongs to Z, then u also belongs to Z.

Now, we consider the reverse case. If (u, v) belong to M, and u belongs to the set Z, then v also belongs to the set Z. This is because, initially u was not in the set, (since only unmatched vertices were in the set). So there must be an alternating path to get from those initial vertices to this vertex. To get to the vertex u, the last edge in the alternating path would have been an edge in the matching, and since edges in the matching can't share vertices, there is only one unique matching with vertex u as endpoint and that is (u, v), so to get to u, the alternating path must have gone through v.

From the above two conclusions, we come to the fact that for each edge in the matching M, either both the endpoints are in the set Z, or none of them are.

We define another set now, S = (U - Z) union (V intersection Z), This means that we take nodes from the set U, which are not in the set Z, and nodes from the set V, which are in the set Z. Hence, for each edge of the matching, if the matching is in Z, we take it's node v, and if the matching is not in Z, then we take it's node u. So each matching in the graph, has one endpoint in the set S, and so |S| = number of edges in the matching.

Now, Konig's theorem says that this set S is the minimum vertex cover. Let us consider an edge (u, v). If u is not in Z, then it is covered by S, since that vertex will be in the set S. Let us consider the case when u is in Z. If (u, v) is in the matching M, then as proved above, since u is in Z, v will also be in Z. If v is in Z, then it will also be in S, and hence the edge (u, v) will be covered. We are left with the case when (u, v) is such that (u, v) is not in the matching and u is in Z. If u is in Z, it must have been reached using an alternating path in which the last edge was an edge in the matching (or there was no edge at all - it was in Z at the start), Then we can always extend the alternating path using an edge not in the matching which is (u, v). So v will also be in Z, and hence (u, v) will be covered.

Hence, we have proved Konig's theorem and our solution will know consist of finding the maximum bipartite matching and then the size of that will be our answer.

Implementation

ll bfs(ll s, ll t, vector < ll > &parent, vector < vector < ll > > &adj, vector < vector < ll > > &capacity)
{
     parent[s] = -2;
     ll n = parent.size();
     vector < bool > visited(n, false);
     visited[s] = true;
     queue < pair < ll,ll > > nodes;
     nodes.push({s, LLONG_MAX});
     while(!nodes.empty())
     {
          pair < ll,ll > node_flow = nodes.front();
          ll node = node_flow.fi;
          ll flow = node_flow.se;
          nodes.pop();
          for(ll i=0;i < (ll)adj[node].size();i++)
          {
                  ll next = adj[node][i];
                  if(visited[next] || capacity[node][i]==0)
                        continue;
                  visited[next] = true;
                  parent[next] = node;
                  int new_flow = min(flow, capacity[node][i]);
                  if(next==t)
                       return new_flow;
                  nodes.push({next, new_flow});
           }
     }
     ll flow = 0;
     return flow;
   }

   ll maxflow(ll s, ll t, vector < vector < ll > > &adj, vector < vector < ll > > &capacity)
   {
         ll flow = 0;
         ll n = adj.size();
         vector < ll > parent(n, -1);

         ll new_flow = 0;

        while(new_flow=bfs(s, t, parent, adj, capacity))
        {

               flow += new_flow;
               ll curr = t;
               while(curr!=s)
               {
                    ll prev = parent[curr];
                    ll idx = (find(adj[prev].begin(), adj[prev].end(), curr) - adj[prev].begin());
                    capacity[prev][idx] -= new_flow;
                    idx = (find(adj[curr].begin(), adj[curr].end(), prev) - adj[curr].begin());
                    capacity[curr][idx] += new_flow;
                    curr = prev;
               }
          }
          return flow;
        }

     ll maximum_bipartite_matching(ll n, ll m, vector < vector < ll > > &edges)
     {
                ll total = n+m+2;
                vector < vector < pair < ll,ll > > >  temp(total+1);
                vector < vector < ll > > adj(total+1);
                vector < vector < ll > > capacity(total+1);
                for(ll i=0;i < (ll)edges.size();i++)
                {
                          ll u = edges[i][0];
                          ll v = edges[i][1];
                          v = v+n;
                          temp[u].pb({v, 1});
                          temp[v].pb({u, 0});
                 }
                 for(ll i=1;i < = n;i++)
                 {
                       ll source = n+m+1;
                       temp[source].pb({i, 1});
                       temp[i].pb({source, 0});
                  }
                  for(ll i=1;i < = m;i++)
                 {
                         ll sink = n+m+2;
                         temp[i+n].pb({sink, 1});
                         temp[sink].pb({i+n, 0});
                  }
                 for(ll i=1;i < = total;i++)
                          sort(temp[i].begin(), temp[i].end());
                 for(ll i=1;i < = total;i++)
                {
                          for(ll j=0;j < (ll)temp[i].size();j++)
                          {
                                  adj[i].pb(temp[i][j].fi);
                                  capacity[i].pb(temp[i][j].se);
                          }
                }
                ll matchings = maxflow(n+m+1, n+m+2, adj, capacity);
                return matchings;
        }

      void solve()
     {         
         ll n,m;
         cin > > n > > m;
         ll p;
        cin > > p;
        vector < vector < ll > > edges;
        for(ll i=0;i<p;i++)
        {
            ll u,v;
           cin > > u > > v;
           edges.pb({u, v});
         }
         ll ans = maximum_bipartite_matching(n, m, edges);
        cout < < ans < < '\n';
        return;
     }           

16 months ago

Akshay Sharma 1.0k

Chandigarh

Question 3

Assumptiion

• I don't think there will be a solution existing for the given constraints. So my solution will work for the constraints less than 10^3for the value of N and K
  • Also there can possible that the number of subsets is too large so don't forget to take the modulo that is 10^9+7

Overview

• We are given an array and we need to create 2 subsets out of this array and return the number of possible ways such that we can choose so the sum of subsets is greater than K.
• Assumption we can skip elements from both sets

Solution

• Let cnt be the number of subsets of 𝐴 with sum at most 𝐾
• we know that each set should get at least a total of 𝐾+1. So, the sum of the array should be ≥2⋅(𝐾+1). If not, the answer is 0
• We can compute this by 𝑑𝑝𝑖,𝑗= number of subsets of 0..𝑖 with sum equal to K in 𝑂(𝑁𝐾)
• Then the answer would be max(0,2^N-2*Cnt).
• For the calculating part we will be using DP to count the number of subsets whose sum is greater than or equal to the given value K .
• Here we will be using a 2D array of size (Arr.size() + 1) x (target + 1) with integer type.
• We will create an array ‘Subset’,i.e., Subset[ ][ ] and have to fill it up in a bottom-up manner
• The return value of Subset[ i ][ j ] will be true if the subset of the set[ 0 … (j - 1)] is with a sum value equal to ‘i’, or else it will return false.

  If the current value of the element is greater than the current 
  value of sum then we will just copy the previous answer from 
   the  previous case, but if the current value of the sum is greater than the 
   'kth' element, then we will check if the previous state has the 
   ('sum' = 'l' and 'l - A[k]' which should fulfill our purpose).

   if(A[k] > l)
     matrix[k][l] = matrix[k - 1][l];
   else
      matrix[k][l] = matrix[k - 1][l] + matrix[k - 1][l - A[k]];

• Time Complexity: O(N*K)

Sample Code

for(int k = 1; k <= N; k++){
   for(int l = 1; l <= sum; l++){
       // If element value is greater than the sum value
       if(A[k - 1] > l)
           matrix[k][l] = matrix[k - 1][l];
       else{
           matrix[k][l] = matrix[k - 1][l] + matrix[k - 1][l - A[k - 1]];

        }
    }   
 }
 return max(0,int(pow(2,n))-2*matrix[N][sum]+1));

16 months ago

Akshay Sharma 1.0k

Chandigarh

QUESTION 4

Overview Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Solution

• First consider some base cases. If either str1 or str2 is null, return false.
• If str1 and str2 are the same, return true.
• Otherwise, if all lowercase letters occur in str2, return false since conversions will definitely cause duplicates in str1 and make it impossible to transform str1 into str2.
• Then loop over str1 and for each letter, store the indices in str1. If there exists two indices such that the letters at the two indices in str1 are the same but the letters at the two indices in str2 are different, return false since it is impossible to convert two same letters into two different letters.
• If no such indices exist, return true.
• Time Complexity: O(N)

Code

 if(str1 == str2) return true;
    if(str1.size() != str2.size()) return false;
    unordered_set<char> s(str2.begin(), str2.end());
    if(s.size() == 26) return false;

    unordered_map<char,char> mp;
    for(int i  = 0; i < str1.size(); i++) {
        if(mp.count(str1[i]) == 0) {
            mp[str1[i]] = str2[i];
        }
        else if(mp[str1[i]] != str2[i]) {
            return false;
        }
    }

    return true;

11 months ago

Ayush Gangwani 1.3k

New Delhi

Solution to Problem 1

Analysis

This problem can be solved simply using an Order Statistics Tree. C++ comes with a built in data structure called the policy based data structure which can perform the same operations. Java and python coders will need to implement such a structure on their own.

Lets first insert all natural numbers from 1 to N in the tree. Now,

• For a query of type 1, we simply have to find the x-th smallest element in the tree and delete it.
• For a query of type 2, we simply have to print the x-th smallest element in the tree.

Both the queries can be answered in O(logN) time, thereby giving the total time complexity of O(QlogN) and space complexity of O(N).

PseudoCode

solve(Queries, N):
    ds = new Order_Statistics_Tree<int>
    for i from 1 to N:
        ds.insert(i)
    ans = new int[]
    for query in queries:
        if(query.type == 1):
            ds.erase(ds.find_by_order(query.x))
        else:
            ans.append(ds.find_by_order(query.x)) 
    return ans

11 months ago

Ayush Gangwani 1.3k

New Delhi

Solution to Problem 2

Analysis

There can be infinitely many GPs of length 1 with prime common ratios (simply because there are infinite prime numbers and each element can be termed as a GP of length 1 with a prime common ratio), so we will only focus on finding the GPs of length >= 2 with prime common ratios.

Lets define dp[value][ratio] to be the number of GPs ending with value and having a common ratio of ratio. Now, notice that it only makes sense to define dp[value][ratio] if value is divisible by ratio, otherwise we would have a GP with a single element. Since ratio must be prime and there are only atmost log(value) distinct primes divisors of some value, we only need to define value*log(value) dp states. In the problem the max value of a_i is 1e5, which would fit in the time limit.

Now, for the transitions, we iterate through the array and If we encounter some value x, we should update dp[x][p] as follows:

• If dp[x/p][p] is defined we simply do dp[x][p] += dp[x/p][p]. This adds up all the GPs of length >= 3.
• But this does not account for the GPs of length 2 that can be formed by x/p and x, hence we also do dp[x][p] += count[x/p], where count[x/p] is the frequency of x/p so far.