OA for meesho sde 1

Round 1

Questions:

Question: Connected People in a Social Media Network

You are given a social media network represented as an undirected graph, where each person is a node, and a connection (friendship) between two people is an edge. Your task is to find the size of the connected component (direct and indirect connections) for each person in the network.

Question: Vertical Paths with Divisible Sum

You are given a tree with n nodes, where each node has a cost. A vertical path in the tree is defined as a path starting from any node and moving downwards through its child nodes (it does not go back up). Your task is to count the total number of vertical paths such that the sum of the costs of nodes in the path is divisible by a given integer k.

Question: Infection Timeline with Vaccinations

You are tasked with modeling the spread of an infection in a population over time. The spread of infection is influenced by two events: contact between individuals and vaccination. Given a series of events and an initial list of infected individuals, your goal is to determine the time at which each person becomes infected or if they remain uninfected.

Problem Description

You are given the following:

• An integer n (1 ≤ n ≤ 10^5) — the number of people labeled from 1 to n.
• An integer m (1 ≤ m ≤ 10^5) — the number of events in the timeline.
• An array of m events where each event is of one of the following types:
  • (1, a, b) — Person a and b came into contact. This means that all people who have been in contact with a are now also in contact with b (and vice versa).
  • (2, a) — Person a was vaccinated at this time. If a person is vaccinated before coming into contact with an infected person, they will not get infected.
• An array infected[] of integers — the initial list of infected people.

Your task is to return an array of size n where the i-th element represents the time (1-based index of the event) at which person i becomes infected. If a person does not get infected, return -1 for that person.