Facebook

  www.facebook.com
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 [?]
Answer

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

Answers & Comments

0
of 0
votes
intersection of each node's (neighbors plus itself).
- Yang on Mar 4, 2012
0
of 0
votes
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
0
of 0
votes
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.