Facebook
4.6 of 5 637 reviews
www.facebook.com Menlo Park, CA 5000+ Employees

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 Flag Question

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

Answers & Comments

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

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.

Glassdoor is your free inside look at Facebook interview questions and advice. All interview reviews posted anonymously by Facebook employees and interview candidates.