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.addConnection(1,2);
c.addConnection(2,3);
c.addConnection(1,3);
c.addConnection(3,4);
c.addConnection(5,6);

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

TC: 🌰

comments

Want to comment? LOG IN or SIGN UP
TOP 16 Comments
  • 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
    Adjacencies list?
    Nov 11 1
  • Google PCBro
    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
  • Google foony
    Macho Man Randy Savage's algorithm for disjoint sets
    Nov 11 0
  • Google / Eng sadnoogler
    Union-find
    Nov 11 0
  • Google The Old Nite
    Union find
    Nov 11 0

Salary
Comparison

    Real time salary information from verified employees