Work in HR? Unlock Free Profile

Facebook Software Engineer Intern Interview Question (student candidate)

I interviewed in Kraków (Poland) and was asked:
"Find the center of graph(vertex, that is connected with every other vertex, but edges are directed to the center of graph)."
Add Tags [?]

Part of a Software Engineer Intern Interview Review - one of 1,071 Facebook Interview Reviews

Answers & Comments

of 0
intersection of each node's (neighbors plus itself).
- Yang on Mar 4, 2012
of 0
i guess it is very similar to finding the sink in a graph, there is a cute solution in O(n)
- light on Apr 22, 2012
of 0
Assume that the graph has N vertex.

Then just do DFS and counts array IN (IN[i] - how many edges directed to vertex i)
Then just go through array IN and check condition : IN[V] = N - 1
If such V found then it's an answer.

Complexity: O(N)
Aux.memory: O(N)
- ZuZu on Jun 28, 2013

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.