Question: PhonePe | 9th October | Online Assessments

Entering edit mode

Question 1

Bob gave Alex a string s consisting of lowercase English letters of length n. He then asked Alex to construct a new string s1 using the characters of s such that no two characters appear more than k times consecutively. It is not mandatory to use all characters from s.

Help Alex find the lexicographically largest possible string s1.

Input Format

First line letters integers n and k.

Second line contains string s of length n.

Output Format

Print the lexicographically largest string s1.

Sample Input 0

7     3
ddybydd

Sample Output 0

yydddbd

Explanation 0

No letter appears more than 3 times consecutively and also the string is lexicographically largest.

Question 2

Click here to Practice

There are N cities (1, 2,......., N) and M roads and the cities are connected to other cities by those roads. Terrorists have planted bombs in every city. Each bomb will explode one after the other. First bomb in city1 will explode, then city2 and so on.

Each explosion will destroy the city and the roads which are connected to it.

For every explosion, you need to return the number of connected components of cities.

Input Format

Input is given from Standard Input in the following format:

N       M
A1     B1
A2     B2
-
-
-
AM     BM
(Ai, Bi represents City number)

Constraints

1 <= N <= 200000

0 <= M <= min(200000,(N(N-1))/2)

1 <= Ai, All values are in input are integers

Output Format

Print N lines.

The i-th line should contain the number of connected components when a city is exploded.

Sample Input 0

Sample Output 0

Explanation 0

PhonePeimgExplanation

Question 3

Bonus Question Asked in the Onsite Round

You are given two arrays a and b. You draw lines by connecting a[i] with b[j] where a[i]==b[j]. You need to find maximum lines you can draw without crossing each other. You are expected to solve this problem in approximately O(n^2) time.

ADD COMMENT • link

Entering edit mode

Solution to Problem 2

Analysis

Most problems that require deleting edges or nodes from a graph can be solved simply by processing the queries offline in the reverse order. Suppose that we start with a graph having 0 nodes and 0 edges. Now we add the nodes (and the edges corresponding to them) in the reverse order of their deletion, i.e. starting from N down to 1. We can simply use a DSU or Union Find Data Structure to simulate this process and hence answer the queries in the reverse order.

Implementation

Maintain a DSU (Union Find Data Structure) for answering the queries.
Keep adding the nodes and their corresponding edges in the reverse order of their deletion, i.e. in the descending order.
Find the number of components after each addition and store them in some container.
Reverse the container and print the answers for the queries.

PseudoCode

class DSU:                                                       //DSU implemntation
    parent = [0]*N
    size = [0]*N
    components = 0

    make_node(x):                                                //function to create a new node   
        components++
        parent[x] = x
        size[x] = 1

    is_active(x):
        return size[x] != 0

    find(x):                                                     //find(x) returns the representative element of the set containing x
        return parent[x] = (parent[x] == x) ? x : find(parent[x])

    merge(a,b):                                                  
        a = find(a)
        b = find(b)
        if(a == b) return                                        //if the representative elements are same, these nodes are already connected, hence we return
        components--                                             //otherwise we have merged two components and hence the no of components reduces by 1
        if(size[b] &gt; size[a]) swap(a,b)
        size[a] += size[b]
        parent[b] = a 

solve(N, Edges)
    d = DSU(N)
    ans = []
    for node from N to 1:
        d.make_node(node)
        for nbr in Edges[node]:
            if(d.is_active(nbr)):
                d.merge(node,nbr)
        ans.append(d.components)
    ans.reverse()
    return ans

ADD COMMENT • link 2.2 years ago Ayush Gangwani 1.2k

Entering edit mode

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

class disjoint
{
private:
int nodes;
vector<int> parent,size;
public:
disjoint(int n)
{
nodes=n;
parent.resize(nodes);
for(int i=0;i<nodes;i++) parent[i]=i;
size.resize(nodes,1);
}
int findpar(int x)
{
if(x==parent[x]) return x;
return parent[x]=findpar(parent[x]);
}
void join(int x,int y)
{
int p1=parent[x],p2=parent[y];
if(size[p1]>size[p2])
{
size[p1]+=size[p2];
parent[p2]=parent[p1];
}
else
{
size[p2]+=size[p1];
parent[p1]=parent[p2];
}
}
};

int main() {

int n,m;
cin>>n>>m;
vector<vector<int>> graph(n);
disjoint dsu(n);
int components=0;

for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
//ensuring 0 based indexing.
if(x<y)
{
graph[x-1].push_back(y-1);
}
else
{
graph[y-1].push_back(x-1);
}
}

stack<int> st;
st.push(0);
for(int new_node=n-1;new_node>=0;new_node--)
{
components++;
for(auto exit_node: graph[new_node])
{
if(dsu.findpar(exit_node)!=dsu.findpar(new_node))
{
components--;
}
dsu.join(exit_node,new_node);
}
if(new_node!=0)
st.push(components);
}

while(!st.empty())
{
cout<<st.top()<<endl;
st.pop();
}
return 0;

}

ADD REPLY • link 12 months ago

Rahul Dev Gurjar • 10

Entering edit mode

For the 3rd question: We can just find the Longest Common Subsequence (Works in O(N^2)).

ADD COMMENT • link 15 months ago mananwrp • 10

Entering edit mode

Question 1

Overview

Given a string s and we need to form a new string s1 such that no two characters appear more than k times consecutively.
Also it is not mandatory to use all characters from s.
The string s1 should be lexicographically largest.

Solution

Initialize string s1 to empty string.
Store pair of {character, "frequency_of_character"} in a set.
Now pick the character from the end of the set, add it to string s1 and decrease its frequency by one and update it in the set.
Keep a counter lets cay cnt_char which gets incremented when we add a character to s1 and when it becomes equal to k we pick the second last character from the set if it's present in the set (else we exit) and repeat the 3rd step again and also do the value of cnt_char=0.
In this way, we ensure the string s1 formed is lexicographically largest.

Code

    ll n, k;
    cin &gt;&gt; n &gt;&gt; k;
    string s;
    cin &gt;&gt; s;
    vector&lt;ll&gt; freq(26, 0);
    for (ll i = 0; i &lt; n; i++)
    {
        freq[s[i] - 'a']++;
    }
    set&lt;pair&lt;char, ll&gt;&gt; se;
    char c = 'a';
    for (ll i = 0; i &lt; 26; i++)
    {
        if (freq[i])
        {
            se.insert({c, freq[i]});
        }
        c++;
    }
    string s1 = "";
    ll cnt_char = 0;
    while (se.size())
    {
        auto it = se.end();
        it--;
        if (cnt_char &lt; k)
        {
            s1 += (*it).ff;
            if ((*it).ss &gt; 1)
            {
                se.insert({(*it).ff, (*it).ss - 1});
                cnt_char++;
            }
            else
            {
                cnt_char = 0;
            }
            se.erase(it);
        }
        else
        {
            cnt_char = 0;
            if (se.size() &gt; 1)
            {
                it--;
                s1 += (*it).ff;
                if ((*it).ss &gt; 1)
                {
                    se.insert({(*it).ff, (*it).ss - 1});
                }
                se.erase(it);
            }
            else
            {
                break;
            }
        }
    }
    cout &lt;&lt; s1 &lt;&lt; endl;
    return;

ADD COMMENT • link 2.2 years ago Ujjwal Srivastava 320

Entering edit mode

SOLUTION TO Q2

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

#define int long long

vector<int> sz;
vector<int> par;

int comp = 0;

void node(int x)
{
    comp++;
    par[x] = x;
    sz[x] = 1;
}

bool active(int x)
{
    return sz[x] != 0;
}

int find(int x)
{
    if (par[x] == x)
        return x;

    else
        return find(par[x]);
}

void merge(int u, int v)
{

    int x = find(u);
    int y = find(v);

    if (x == y)
    {
        return;
    }

    comp--;
    if (sz[y] > sz[x])
        swap(x, y);

    sz[x] += sz[y];
    par[y] = x;

    return;
}

int32_t main()
{

    int n, m;
    cin >> n >> m;

    par.resize(n, 0);
    sz.resize(n, 0);

    vector<int> adj[n];
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> ans;
    for (int i = n - 1; i >= 0; i--)
    {
        ans.push_back(comp);

        node(i);

        for (auto it : adj[i])
        {
            if (active(it))
                merge(i, it);
        }
    }

    reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;

    return 0;
}

ADD COMMENT • link 14 months ago Syed Ateeb Shah • 0