The Social Network

Problem Statement

A student in a college is planning to start a new social networking website for his college community. In this social network, initially, all people belong to different communities. Then, if X connects with Y, the result is the merger of the communities to which X and Y belong to. Suppose, person X and Y connected and later Y and Z connected, then X,Y and Z will belong to the same community.

Input Format

The first line will contain 2 integers U and V, separated by single space denoting number of persons and number of queries respectively. The next U lines will denote each person's details with each detail separated by a single space. The details are : "id of the person" "name of the person" "age of the person". The next V lines will contain V queries. There are 4 types of queries for this problem:-

1. M id1 id2 : This query will merge the 2 communities to which person with id1 and id2 belong to. If both of them belong to same community, then no need to merge.
2. F id1 id2 : This query will find whether person with id1 and person with id2 belong to the same community or not. Your answer has to be “YES” or “NO”.
3. W id1 : This query will return the number of persons in a community to which a person with id1 belongs to.
4. P id1 : This query will print the details of the person with id1.

Output Format

The output of the queries.

Sample Input

6 12
1 Harish 25
2 Anurag 24
3 Gaurav 25
4 Shaifali 22
5 Ranjana 23
6 Krishana 29
F 3 6
M 1 2
M 4 6
W 4
P 4
M 3 5
M 5 4
M 3 6
F 1 6
M 1 6
F 1 6
W 5

Sample Output

NO
2
4 Shaifali 22
NO
YES
6

Solution

Greedy Algorithms : Implementing Lecture Scheduling : Coding Interview

Problem Statement

In a conference, N people from a company XYZ are present to attend maximum number of presentations. Each presentation is scheduled between 8:00 and 8:00. Here the second 8:00 means 8:00 pm. Our task is to assign people to presentations such that the number of unique presentations attended by XYZ as a company is maximised.

Input Format

Input is provided in the form a file (taken as command line argument). The first line contains N i.e # of people. Second line contains M i.e # of presentation on that day. M lines follow each containing start and end time of presentation. Time will be in format of HH:MM.

Output Format

Output : The maximum number of presentations that can be attended.

Sample Input

3 
5 
08:00 08:00 
08:00 08:00 
08:00 08:00 
08:00 08:00 
08:00 08:00

Sample Output

3

Explanation

3 people can attend max 3 presentations for the given timings.

Solution

Interview Coding Problems : Solved

Hereon afterwards, I will be posting Java Code, for various problem sets, which are generally given during placement exams and interviews. These problems are well known and I certainly do not claim that these are most optimum, but I in the spirit of open source want to make my code available to those who might benefit from it.

If you feel this code helped you at all, just drop me a mail or comment, so that it keeps me motivated to keep doing it for more and more problem sets.

Thank you.

Today's problem : Based on Maxflow. 

Problem Statement

After succeeding to the British crown, you inherit a 16th-century Scottish castle with an elaborate plumbing system that has accumulated pipes and junctions over four centuries. You'd like to know if it is safe to install a modern American overHead Tank , or if this will eventually overflow the historic bathtub of James VI/James I.

Input Format

The first line of input consist of two integers N (no of junctions) and M (no of pipes) , separated by a single space.

Then, M lines follow. Each of these lines consist of three integers X, Y, Cxy separated by a single space. It means that there is a pipe between the junction X and the junction Y with a capacity of pipe equal to Cxy.

Assume junction 1 will be Source and junction N represents Sink.

Constraints:

3≤N≤500

3≤M≤500

1≤capacity of pipe ≤100

The junctions are indexed from 1 to N. its implicit that 1 is source and N is sink

Output Format

A yes or no, that represent to install new American overhead tank or not. A Integer representing maximum flow allowed my network into sink.

Sample Input

6 10

1 2 16

1 3 13

2 3 10

3 2 4

2 4 12

3 5 14

4 3 9

5 4 7

4 6 20

5 6 4

Sample Output

Yes

23

Explanation

The max flow of the network is 23 which is lesser than maximum input capacity of sink(bathtub) i.e 24.

Solution