# Daily Algo Challgenge #6

Nov 11 16 Comments

Welcome! ☕️

A network is made out of n machines that are numbered from 1 to n. This network has a set of connections, which can be used to send information to both directions between two machines. Create the following functions:

void addConnection(int a, int b)
- adds connection between machines a and b.

boolean checkConnection(int x, int y)
- returns true if there is a connection between machines x and y, otherwise it returns false.

Limits:
1 <= n <= 5000 where for every n the runtime should be < 1000ms.

Example inputs and outputs:
Communications c = new Communications(6);

c.checkConnection(1,4); // true
c.checkConnection(2,5); // false
c.checkConnection(5,6); // true

TC: 🌰

• Guys can we get some working code so that I can check this as a successful challenge? 😂

Otherwise, I’ll get depressed and have to cancel the show 😭
Nov 11 2
• Airbnb avqx65
Lmfao nobody is gonna code on their phone while they’re taking a shit
Nov 11
• Apple ghahue120
^ lol this person blinds
Nov 11
• WeWork RPvk36
Nov 11 1
Union find
Nov 11 0
• Oracle aimlds
Isn’t it a simple graph problem where connects adds an edge , and the second question can be done by using BFS/DFS ?
Nov 11 3
• Yup, I just want to try easier problems and see how the answers differ. Tomorrow I’ll post a really hard one.
Nov 11
• Netflix aWGe33
BFS. Use memo to avoid cycles.
Nov 11
• BAE Systems Xpsz80
Essentially. There is also a data structure called union find that you can use to make checkConnection faster. Check out William Fiset's lectures on union find for a pretty good introduction if interested.
Nov 12
• New arv1
4 / 4 Googlers said Disjoint Set / Union-Find. There you have the solution. 😆
Nov 11 0
• BAE Systems Xpsz80
Looks like pretty straightforward union find. See https://leetcode.com/problems/critical-connections-in-a-network/ for an interesting follow up. Was asked a variant of this in an Amazon Online Assessment.
Nov 12 0
• Bloomberg MBloomberg
Last time I interviewed with google, I got a union find problem. What’s with googlers and Union find?
Nov 12 0