Facebook | Phone | Connected Components in Graph

My Background - 16 years of programming experience, includes 9 years specializing in Android, seeking potentially E6 roles.

Given information about the links between various data centers, find the groups of isolated but connected data centers. For example --> Input : {A<->B, B<->C, D<->E}, Output : {A, B, C}, {D, E}

Clarifying questions -

  1. appears undirected-graph structure. Do we also assume A <-> A ? Interviewer suggested self-edges need not be taken into consideration.
  2. I was also unclear about <-> notation to begin with. Clearly the problem statement did not have the method signature that I was expected to solve. I asked for some hints / help regarding the full method signature, particularly input representation. Interviewer suggested it is all up to me.

Of course, I was familiar with BFS and DFS to some degree, but not a whole lot in Graphs.
My first though about the solution was -

class Node { 
    Character value; // representing each character.
    List<Node> edges = new ArrayList<>(); //  representing it's connections.
}

Therefore, method signature was -

public Set<Set<Node>> disjointSets(List<Node> input);

Then I went ahead and implemented a naive DFS, something like backtracking, that appears to have solved the problem.

Biggest issue - no compiler. This is entirely plain text-editor, and I was expected to walk-through the solution conceptually. My solution did seem to work correctly. Only I noticed the glaring recursive stack-overflow issue, but never mentioned that.


Follow-up:
Apparently, Input : {A<->B, B<->C, D<->E, E <-> A}, Output : {A, B, C}, {D, E}.
Threw me off-guard, because based on my signature and DFS, output is the universal set.
I'd imagine, the interviewer's expected output is based on an Adjacency-Matrix. As you may notice, E <--> A probably has no significance ?

image

I did not know LC-323 previously.
Although, after noticing LC-323, I have more questions, based of some clarifying questions that I had discussed with the interviewer.

  1. LC-323 does not have a solution, but it's not necessarily an unsolvable problem. plenty in the discussion.
  2. There's a distinct size-limit, and input are Int types, unlike the interview question with char types ?
  3. Suppose if char types are the representation, then what is the last expected character in the interview question ?
  4. For LC-323, i'd imagine Undirected-graph Adjacency-matrix can help convert the problem into Number of islands, also based of the expected output, particuarly for given size-limit N, the matrix would be a N X N.
  5. In the interview question, no size-limit or last possible character is represented, which makes the interview-question slightly different and definitely not exactly the same as LC-323 ? Are we going to create a Adjacency-matrix of 26 X 26 ?
  6. Also notice the expected output between the two problems ?

In all, did the interviewer ask a bad / incomplete question ? Why do they ask bad questions ?
Was I expected / supposed to correct the interviewer ? Suggest correct inputs, input-types etc ?
Should i have practiced LC-323 previously, and recalled exactly how this interview question is possibly incomplete ?

I reached out to the recruiter regarding the interviewer's conflicting points-of-view, see clarifying question-2, and follow-up output, that my DFS approach apparently failed in the interviewer's expected output. I will have to do another phone-screen round. If it is going to be just as hard, is it all worth it ?

Edit - Upon popular demand in the discussions below, I've included a potential Adjacency-matrix, that might explain the follow-up expected output. Please bear in mind, this is only based of my understanding of the problem, the clarifying questions, potential solution approaches etc. I do not know what was going-on in the interviewer's mind. I cannot guess that.

Comments (13)