Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

There are `n`

people numbered from `0`

to `n - 1`

. A list of meetings is given whose each entry is a tuple `[x`

, indicating that the person _{i}, y_{i}, time_{i}]`x`

and the person _{i}`y`

have a meeting at _{i}`time`

._{i}

Person `0`

has a secret and initially shares the secret with a given person at time `0`

. This secret is then shared every time a meeting takes place with the person that has the secret.

Return a list of all the people who have the secret after all the meetings have taken place.

```
{
"n": 6,
"meetings": [
[1, 2, 3],
[2, 3, 5],
[1, 5, 2],
[3, 5, 10]
],
"first_person": 2
}
```

Output:

```
[0, 1, 2, 3, 5]
```

At time 0, person 0 shares the secret with person 2.

At time 2, neither person 1 nor person 5 knows the secret.

At time 3, person 2 shares the secret with person 1.

At time 5, person 2 shares the secret with person 3.

At time 10, person 3 shares the secret with person 5.

Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

```
{
"n": 5,
"meetings": [
[2, 3, 1],
[2, 4, 1],
[1, 2, 1]
],
"first_person": 1
}
```

Output:

```
[0, 1, 2, 3, 4]
```

At time 0, person 0 shares the secret with person 1.

At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with persons 3 and 4.

Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

- A person may attend multiple meetings at the same time.
- The secrets are shared instantaneously, which means a person may receive the secret and share it with people in other meetings within the same time frame.
- Return the output list in any order.

Constraints:

- 2 <=
`n`

<= 10^{5} - 0 <= size of the input list <= 10
^{5} - 0 <=
`x`

,_{i}`y`

<=_{i}`n`

- 1 `x`

!=_{i}`y`

_{i}- 1 <=
`time`

<= 10_{i}^{5} - 1 <= first person with whom secret is shared at time
`0`

<=`n`

- 1

```
/*
Asymptotic complexity in terms of the number of meetings \`m\` and the number of people \`n\`:
* Time: O(m * log(m) + n).
* Auxiliary space: O(n + m).
* Total space: O(n + m).
*/
vector<int> find_all_people_with_secret(int n, vector<vector<int>> &meetings, int first_person) {
vector<vector<pair<int,int>>> graph(n);
for (int i = 0; i < meetings.size(); i++) {
graph[meetings[i][0]].push_back({meetings[i][1], meetings[i][2]});
graph[meetings[i][1]].push_back({meetings[i][0], meetings[i][2]});
}
// Min Heap which stores a pair of elements where the first entry denotes the current
// time and the second entry denotes the person who knows the secret.
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> is_secret_known(n, false);
pq.push({0, 0});
pq.push({0, first_person});
while (!pq.empty()) {
int current_time = pq.top().first;
int person_x = pq.top().second;
pq.pop();
if (is_secret_known[person_x]) {
continue;
}
is_secret_known[person_x] = true;
for (int i = 0; i < graph[person_x].size(); i++) {
int person_y = graph[person_x][i].first;
int meeting_time = graph[person_x][i].second;
if (is_secret_known[person_y]) {
continue;
}
if (meeting_time >= current_time) {
pq.push({meeting_time, person_y});
}
}
}
vector<int> people;
for (int i = 0; i < n; i++) {
if (is_secret_known[i]) {
people.push_back(i);
}
}
return people;
}
```

We hope that these solutions to the 4 sum problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

There are `n`

people numbered from `0`

to `n - 1`

. A list of meetings is given whose each entry is a tuple `[x`

, indicating that the person _{i}, y_{i}, time_{i}]`x`

and the person _{i}`y`

have a meeting at _{i}`time`

._{i}

Person `0`

has a secret and initially shares the secret with a given person at time `0`

. This secret is then shared every time a meeting takes place with the person that has the secret.

Return a list of all the people who have the secret after all the meetings have taken place.

```
{
"n": 6,
"meetings": [
[1, 2, 3],
[2, 3, 5],
[1, 5, 2],
[3, 5, 10]
],
"first_person": 2
}
```

Output:

```
[0, 1, 2, 3, 5]
```

At time 0, person 0 shares the secret with person 2.

At time 2, neither person 1 nor person 5 knows the secret.

At time 3, person 2 shares the secret with person 1.

At time 5, person 2 shares the secret with person 3.

At time 10, person 3 shares the secret with person 5.

Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

```
{
"n": 5,
"meetings": [
[2, 3, 1],
[2, 4, 1],
[1, 2, 1]
],
"first_person": 1
}
```

Output:

```
[0, 1, 2, 3, 4]
```

At time 0, person 0 shares the secret with person 1.

At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with persons 3 and 4.

Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

- A person may attend multiple meetings at the same time.
- The secrets are shared instantaneously, which means a person may receive the secret and share it with people in other meetings within the same time frame.
- Return the output list in any order.

Constraints:

- 2 <=
`n`

<= 10^{5} - 0 <= size of the input list <= 10
^{5} - 0 <=
`x`

,_{i}`y`

<=_{i}`n`

- 1 `x`

!=_{i}`y`

_{i}- 1 <=
`time`

<= 10_{i}^{5} - 1 <= first person with whom secret is shared at time
`0`

<=`n`

- 1

```
/*
Asymptotic complexity in terms of the number of meetings \`m\` and the number of people \`n\`:
* Time: O(m * log(m) + n).
* Auxiliary space: O(n + m).
* Total space: O(n + m).
*/
vector<int> find_all_people_with_secret(int n, vector<vector<int>> &meetings, int first_person) {
vector<vector<pair<int,int>>> graph(n);
for (int i = 0; i < meetings.size(); i++) {
graph[meetings[i][0]].push_back({meetings[i][1], meetings[i][2]});
graph[meetings[i][1]].push_back({meetings[i][0], meetings[i][2]});
}
// Min Heap which stores a pair of elements where the first entry denotes the current
// time and the second entry denotes the person who knows the secret.
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> is_secret_known(n, false);
pq.push({0, 0});
pq.push({0, first_person});
while (!pq.empty()) {
int current_time = pq.top().first;
int person_x = pq.top().second;
pq.pop();
if (is_secret_known[person_x]) {
continue;
}
is_secret_known[person_x] = true;
for (int i = 0; i < graph[person_x].size(); i++) {
int person_y = graph[person_x][i].first;
int meeting_time = graph[person_x][i].second;
if (is_secret_known[person_y]) {
continue;
}
if (meeting_time >= current_time) {
pq.push({meeting_time, person_y});
}
}
}
vector<int> people;
for (int i = 0; i < n; i++) {
if (is_secret_known[i]) {
people.push_back(i);
}
}
return people;
}
```

We hope that these solutions to the 4 sum problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart