Question: Google | L3 | 30th September

Entering edit mode

Question 1

There N runners and M reports. report i says that runner A beats runner B. Return the order of runners and how they finished There can be test cases like this: a->b, b->a

Example 1: A->B B->C A->C C->D E->D

Result: A,B,C,E,D

Example 2: a->b b->a

Result: Impossible

Question 2

Click here to Practice

Given a tree of N vertices and an edge E, calculate the number of vertices in each of the connected components remaining after removal of the edge.

Test case: image

1,3

Result: 3,8

Question 3

Click here to Practice

Given a string containing only parentheses, scan it to see if the parentheses are well-nested, then:

If they are, return the string as-is. If they are not, repair the string so that the parentheses are well nested and return the result action can be: deleting, adding, changing

You must do string well-nested with minimum number of actions

Example: Input: (() Output: (()), or () or ()()

Input: (()))) Output: ((()))

ADD COMMENT • link

3

Entering edit mode

Question 3

Assumption

Let the total length of the string would be less than 10^5.
We are not given that either we have to make the string balanced with the minimum number of moves or not
Also here we are given that we can do any operation like adding, deleting and modifying
So there arise lots of solutions for this problem like if we have at least one opening and one closing bracket simply delete all other elements
So we are taking certain assumptions and reframing our question

Overview of Question-Based on assumptions

Given a string of length less than 100100 the string only contains parenthesis.
Find if the given string is well nested with parenthesis or not
If not we are allowed to do some operations like add any parenthesis or modify the parenthesis
once we get the well-nested string print that string
Again we are not concerned about the minimum number of operations but we are more concerned to make the given string balanced -Length of the resulting string would be greater than equal to the length of the previous string of parenthesis.

Detailed Solution

we are going to use a simple approach to solve this question.
- Initialize some variable with 0 that says cnt=0, now we will be iterating over the string and checking for a few conditions.
- we are using cnt variable to check if our string is well nested or not, let when we encounter an opening bracket we will increase our cnt variable by one else decrease it by one. Starting from 0 if at any point it reduces to less than 0 then our string is not well nested which means that the point of time closing bracket is greater than the opening ones. So using this information we are modifying our answer
- if the current bracket is opening we will be inserting that array in our answer vector of character type and increase our cnt variable by 1
- else if the current bracket is closing one and the value of cnt is equal to zero in such case we will add the opening bracket to our answer vector and increase cnt by else if cnt is greater than 0 then we will push the closing bracket to our answer vector and decrease the cnt.
- once we reach the end of the loop we are going to check if the cnt is equal to zero or not. If cnt is not equal to zero we are going to add cnt times closing bracket to our answer vector.
- finally, print our answer vector without any spaces. -Time Complexity: O(N).

ADD COMMENT • link 2.2 years ago Akshay Sharma 990

2

Entering edit mode

Question 2

Assumptions

Let assumes the edges in a tree would be less than 1e5

prerequisite

Graph and tree theory and precomputation techniques

BreakDown/Overview

Given a tree with N nodes and N-1 edges
we are also given the vertex.
Question asked you if we remove the given vertex from the tree then how many connected components we are left with and return that number

Detailed Solution

Let's make a dummy tree to understand the solution clearly:
 : Nodes in tree =7
                                      0
                                   /  |  \
                                 1    2    3
                               /  \           \
                             4    5            6
 suppose we get node vertex 0 to be removed, Currently, we can see we have only 1 connected component in our tree
 If we remove the vertex 0 from the tree then all the edges that are connected with that vertex 
 are also get removed in this case edge {(0,1) (0,2)(0,3) } edges get removed from the tree
 So after removing the vertex 0 we get 3 connected component that is [(1,4,5) (2) (6) ]

Idea/Observation==&gt; 
The idea is to observe that in a Tree, whenever a node is deleted, the nodes which were connected together to that node get separated. So, the count of 
connected components become equal to the degree of the deleted node.
So the approach is to do some precomputation earlier.
the approach is to precompute and store the degree of each node in an array.
 For every vertex deleted, the count of the connected components is simply the degree of the corresponding node that is deleted
 Time Complexity: O(N).

ADD COMMENT • link 2.2 years ago Akshay Sharma 990

1

Entering edit mode

Question 2 can be done by 2 Approaches

1st Approach : This approach is vaild in graph also and for multiple deletions.

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

void dfs(vector<int> & visit,int node,vector<int> adj[]){
visit[node] = 1;

for(auto child : adj[node]){
if(visit[child] == 0){
dfs(visit,child,adj);
}
}
}

int main(){
int n;
cin>>n;

vector<pair<int,int>> edges;

for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
edges.push_back({x,y});
}

int already;

cin>>already;

vector<int> adj[n];

for(int i=0;i<n-1;i++){
int x = edges[i].first;
int y = edges[i].second;

if( x != already && y != already){
adj[x].push_back(y);
adj[y].push_back(x);
}
}

// for(int i=0;i<n;i++){
// for(int j =0;j<adj[i].size();j++){
// cout<<adj[i][j]<<" ";
// }
// cout<<"\n";
// }

vector<int> visit(n,0);
visit[already] = 1;
int count =0;

for(int i=0;i<n;i++){
if(visit[i] == 0){
dfs(visit,i,adj);
count++;
}
}
cout<<count<<"\n";

}

2nd Approach is count the neigbouring of delete node

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

void dfs(int i,vector<int> & visit,vector<int> adj[]){
visit[i] = 1;

for(auto child : adj[i]){
if(visit[child] == 0){
dfs(child,visit,adj);
}
}
}

int main(){
int n;
cin>>n;

vector<int> adj[n];

for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}

int already;
cin>>already;

cout<<adj[already].size()<<"\n";

}

ADD COMMENT • link 16 months ago piyush • 50

1

Entering edit mode

Question 2

import java.util.*;
public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] adj = new int[n];
      
      for(int i=0; i<n-1; ++i){
        int a = sc.nextInt();
        int b = sc.nextInt();
        ++adj[a];
        ++adj[b];
      }
      
      int d = sc.nextInt();
      System.out.println(adj[d]);
    }
}

ADD COMMENT • link 6 months ago lebron • 10

0

Entering edit mode

Question 1

Assumptions

we are not given the number of players participating or we are given char from a to z or there can be more characters like aa bb etc
- So we assume that N people are participating in the race from [0 to N-1] and the value of each person will be an integer
- For simplicity let's assume the number of participants is less than 10^4.
- we are also given M results.
- M are in form of two integers which states that the left person wins and the right loses

What question wants to say

N people race against each other in a pair of 2. During prize distribution, they are arranged in such a way that on the left side of that person is a person whom the player lost to and on the right side is a person whom he won. Write an algorithm to arrange the players in that order.

Prerequisites

It's hardly recommended to know the basic knowledge of graph theory.
Topology shorting in the graph
Directed and Undirected graphs
DAG(Directed acyclic graph)

Solution

Question revolves around topology shorting
let's assume if results are given like this 1>2 , 1>3 and 3>1 the 1st person wins over the second and third person in the race and on the other hand we are also given that the 3rd person wins from the first. Isn't the statement contradicting ?? Assume this result in form of a graph where 1 is the directed edge towards 2 and 3 and 3 is the directed edge towards 1.
`
```
Let's visualise our graph for the above results :

                                                           1
                                                         /  | \
                                                       /    |   \
                                                       |    |     \
                                                       2   3______\
 Here we can see that our graph is forming a Cycle If we analyse more such cases we get to know 
 that whenever our graph is forming a cycle.
 it's not possible to give the winning sequence or our results are a contradiction.
  So in such cases, we return NO. (Sry for the bad image )
```
`
- otherwise, if the graph is not a DAG (Direct acyclic graph ) we return No else if our graph is a DAG we can construct the topology short in the graph using BFS or DFS and return the sequence that is being asked.
- Remember the first vertex of our topology short is the vertex that has in-degree 0
- It's recommended to go threw the graph theory mentioned above.
- Time complexity (O(V+E))

ADD COMMENT • link 2.2 years ago Akshay Sharma 990

0

Entering edit mode

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

int main() {

int n;
cin>>n;
string s;
cin>>s;
int depth=0;
vector<bool>pos(n,true);
for(int i=0;i<n;i++)
{
if(s[i]=='(')
depth++;
else
depth--;
if(depth<0) //is pos pe ek opening bracket dalna pdega
{
pos[i]=false;
depth=0;
}
}

string ans="";
for(int i=0;i<n;i++)
{
if(pos[i]==true)
ans+=s[i];
else //balance it
ans+="()";
}
while(depth>0) //means end me bhi closing bracket dalne pdege
{
ans+=')';
depth--;
}
cout<<ans<<endl;

return 0;