SDE - 2

Given an undirected graph of V vertices and E edges. Your task is to find all the bridges in the given undirected graph. A bridge in any graph is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph).

For Example :

If the given graph is :

Then the edge between 0 and 4 is the bridge because if the edge between 0 and 4 is removed, then there will be no path left to reach from 0 to 4.and makes the graph disconnected, and increases the number of connected components.

Note :

There are no self-loops(an edge connecting the vertex to itself) in the given graph.

There are no parallel edges i.e no two vertices are directly connected by more than 1 edge.

Ninja is very fond of strings so he is creating a new type of string, help him in creating his new magical string.

You are given a string ‘S’ of length |S| and an integer ‘N’. Now, you need to find a string 'STR' of length at most ‘N’ such that if you add this string ‘X’ number of times(STR + STR +... X times) let's say it as 'XSTR' then the frequency of each character in 'XSTR' string should be greater than or equal to the frequency of the same character in the string ‘S’. 'XSTR' should cover all the characters of string S.

Help Ninja in finding the minimum possible value of ‘X’.

For example:

Given S = "aaabbc" and N = 4.
Frequency of each character is 'a' = 3, 'b' = 2, and 'c' = 1.

If we take ‘STR’ = "aabc" and add this 2 times i.e "aabcaabc" the frequency of each character will be 'a' = 4, 'b' = 2, 'c' = 2. Here the frequency of each character is greater or equal to that of string ‘S’. i.e for 'a' 4 >= 3, 'b' 2 >= 2 and 'c' 2 >= 1.
Hence X = 2.
We can't find any other string 'STR' of length N such that X < 2.

A sequence is called nice by a coding ninja if the following conditions are met:

0 <= ‘ARR’[k] <= k 
‘ARR’[k] = ‘ARR’[m] mod k, for all pairs of k,m such that k divides m.

You are given a sequence of integers ‘ARR’ where some numbers may be -1. Find and print the number of nice sequences you can create by changing each -1 to a non-negative integer. As this number can be quite large, your answer must be modulo it by 10 ^ 9 + 7.

For example:

Given ‘N’ = 3, 
'A' = {0, -1, -1} 
Then the answer is 6 because following sequences are possible:[0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 0, 1], [0, 0, 2].

There are ‘N’ cities in ninja Kingdom and Mayer of the city wants to connect all the cities using roads by performing the following operations ‘N - 1’ times. Initially, there are no edges between any cities.

At every operation, you are given two cities, ‘A’ and ‘B’, and you have to connect the city if they are not already connected.

Connected component is that part of the graph in which we have at least two city and we can reach one city to other cities and no two connected components share a common city.

After every input edge, there can be multiple connected components.

Component is good if the number of cities of that component is even; otherwise, it is a bad component.

You need to find the absolute difference between total good and bad components after adding each edge.

You are given a string of length ‘N’ containing only the following characters: ‘[’, ‘{’, ‘(’, ‘)’, ‘}’, ‘]’. At some places, there is ‘X’ in place of any bracket. Your task is to determine that if you replace all the X’s with appropriate brackets, is it possible to get a valid balanced sequence or not.

For example:

For the given string “[X)](X”, the possible replacement for the first X is ‘(‘ and the second X is ‘)’, which makes the sequence “[()]()”, which is a valid balanced sequence. 

For the given string “[XX{”, there is no possible replacement for X which can make it a valid bracket sequence.  

Describe your responsibilities at your current job. 

What type of teams have you worked with? 

What was your role? 

Describe a time when you experienced conflict with a coworker. How did you handle it? 

How does this job compare to others you might be interviewing for?