CISCO | Online Round - Coding Test | Mail Rooms for Office Buildings

Appeared for OA of Cisco for New Grad Role (2022) on HackerRank Platform in August 2022.

Here's the question description for Problem -1 :

Problem :
Company ABC has corporate campus with multiple buildings. These buildings may or may not be connected to one other.

Goal :
Please help Alisa determine the least number of mail rooms to be setup so that all buildings are serviced with the following considerations.

Constraints :

1. A building can host only 1 mail room
2. A building having a mail room will also service buildings directly connected to it. Hence those directly connected buildings may not host a mail room unless required otherwise.
3. A building may or may not be connected to other buildings. In such a case, it would need its own mail room.
4. The number of each building X is a random integer where 0 <= X <= 10ˆ4
5. Total number of buildings is P where 0 <= P <= 10ˆ4
6. Number of connections is N such that 0 <= N <= 1000

Inputs :
First line contains integer P i.e. total number of buildings in Campus.
Second line contains integer N i.e numbers of connections. Here each connection is represented as "X Y" eg "10 20" i.e. link between Bldg 10 and Bldg 20
Next N lines contain the first building connected by the link i.e. 10. The other endpoint would be at index of current line + N.
Next N lines contain the second building connected by the link i.e. 20

Output :
Number indicating minimum number of mail rooms needed.

Example 1 :

Input :
3
2
1
2
2
3

Output :
1

Explanation :

The 3 (line 1) buildings are connected over 2 (line 2) links as follows. Bldg 1 (line 3) is connected to bldg 2 (line 5) and Bldg 2 (line 4) is connected to Bldg 3 (line 6). In this case, placing mail room in Building 2 serves all three. So, answer is 1.

Example 2 :

Input :
6
5
1
2
2
4
5
2
3
5
5
6

Output :
2

Explanation :
The buildings are connected as follows. In this case, minimum mail rooms needed would be 2 i.e. at 2 and 5.

My takeaway - I thought this was gonna be a graph problem which I could do by DFS but I was unable to understand the second example.

My request to you the reader - Kindly upvote so that other readers can also benefit. And please comment down the solution if you could solve the problem. Will upload and link second problem soon.

EDIT : Here's the link to Problem - 2