Solution to Array/Celebrity Problem

[evilegg]

trafficstars

I wrote a solution to the celebrity problem based on the description that I've run into. It's in python and not cpp, but it might be useful. It's got two solutions: the straightforward one and the clever one.

Running it results in the following (numbers in parens is number of times HaveAcquaintance() is called):

$ python problem/Array/CelebrityProblem.py

D_IS_THE_CELEBRITY {'a': ('b', 'c', 'd'), 'c': ('a', 'd'), 'b': ('c', 'd'), 'e': ('b', 'd'), 'd': ()}
PASS NSquaredSolution(40): d
PASS TwoPointersSolution(12): d

NO_CELEBRITY {'a': ('b', 'c', 'd'), 'c': ('a', 'd'), 'b': ('c', 'd'), 'e': ('b', 'd'), 'd': 'e'}
PASS NSquaredSolution(40): None
PASS TwoPointersSolution(11): None

ALMOST_A_CELEBRITY {'a': ('b', 'c', 'd'), 'c': ('a', 'd'), 'b': ('c', 'd'), 'e': 'b', 'd': ()}
PASS NSquaredSolution(40): None
PASS TwoPointersSolution(6): None