Need Help to Practice Interview Question

Hello Everyone.

I just completed one interview Process. I was able to give the approach but was not able to solve fully. I need all of yours help in finding the questions of the interview so I can practice them.

First Question was as
You have one input m. You will be having list of m pairs and you need to print the correct order of their builds.

It will be more clear with example.

eg. if m = 3. then pairs are [A,B], [B,C] [C,D];
[A,B] means for building A you need to build B first.

Now one more input is x = A (You need to build this)

So the output is D C B A (Since A will require B which requires C which requires D. so D then C then B then A will be build.)

I was giving a topological sorting based approach but in case of more connected nodes dry run was giving wrong ans.
Provide me the link if you have solved something similar.

Other was a more simple one, But I was not able to pass dry run.

You are given list of names (First and Last). You need to find the largest cluster of connected names.

n = 5
Dev Singh
Vipul Kumar
Vipul Sharma
Kapil Dev
Rahul Singh

So the ans of largest cluster is 3.

Because Dev Singh -> Kapil Dev -> Rahul Singh is one cluster (Size 3). (Dev is repeated and then Singh is repeated)
and Vipul Sharma ->Vipul Kumar is one cluster (Size 2)

So the ans is 3.

I knew that it will be done using map and pair only. But somehow I was not able to explain the approach well and dry run it as this was my first Interview.

Help me to find these or similar to them. Second one I have solved somewhere but don’t remember exactly where I did. Hope anyone will figure out.

For the first question, the Topological sort is approach is correct. Refer to this problem . As for the second question, you are basically asked to return the size of the largest connected component in a graph with the names as nodes having an edge between two nodes if they have at least one word in common. I believe it can be done using DSU.

1 Like

@harsaroorsohal. Thanks for the first first one. Can you point the link for second something similar. Also map approach is wrong or it might be good to go with.

Just learn about DSU. Later you’ll realize the question is trivial. As for your approach, I can’t think of anything with map and pairs of strings.