Facebook Puzzles : Liar, Liar

I have been meaning to write this post for some time. I had some time on my hands last year and decided to try and solve the Facebook Puzzle Liar Liar (spec here). The solution was accepted by the Facebook Robot.

The first thing to realise is that (like most of these Computer Science related challenges) this problem can be translated into a graph traversal problem. We have 2 distinct groups of people, liars and truth tellers. The problem can be represented using a bipartite graph as truth tellers give the names of liars and vice versa.

So the first step of the solution is to go through the input specification and create a graph with each person connected to the list of people they are accusing. At the time of solving this problem my strongest language was Java, hence the solution is in Java as well.

I used a HashMap of Strings (people’s names) as the key and the value was a set of strings (accusers of the particular key).

When this is done, we can use breadth first search to traverse the graph (as the graph is fully connected) and we can create two sets, one of liars and one of truth tellers (we will never know which one is the liars though) and output the size of both.

The solution is here, feel free to send me feedback.