Question d'entretien d'embauche FactSet: Given a graph and an online s... | Glassdoor.fr

Question d'entretien d'embauche

Entretien de Software Engineer Norwalk, CT (États-Unis)

Given a graph and an online stream of its edges (like a

  social network, where edges are the friendships built at that given instant), find the first incoming edge at which the graph is fully connected!
Répondre

Réponse de l'entretien

1 réponse

0

Represent each connected component by a disjoint set. The algorithm is O(mn^2), for m edges and n vertices. I thought it was O(mnlog n) because of AVL, not sure though.

Candidat à l'entretien, le 7 juil. 2014

Ajouter des réponses ou des commentaires

Pour commenter ceci, se connecter ou s'inscrire