Hacker News Reader

Comment by pmiller2 | Hacker News Reader

The complexity of the forwarded message problem is wrong. Any algorithm solving this can be used to answer whether a graph of order n is Hamiltonian by simply asking if the longest forwarding path is of length n-1. Thus, either the complexity is nonpolynomial or the interviewee has just won the million dollar prize for solving an NP-complete problem in polynomial time.

View on HN

A linear solution for this problem is possible under the assumptions that the graph is directed and acyclic. The directed nature of the graph in this particular example is very clear, and because an individual doesn’t forward a message more than once, there are “basically” no cycles.

Had to Google what a Hamiltonian graph was though. I’ve been listening to the musical too much.

The stated problem does not produce an acyclic graph. For instance, if A has B in their contacts, then B is not forbidden from having A in their contacts. In fact, by ensuring that for all A, if A has B as a contact, then B has A as a contact, we can eliminate directedness from the graph and, via isomorphism, pretend we are operating on an undirected graph.

The requirement that no actor forward a message twice is merely equivalent to finding a simple path through the graph. It does not “basically” mean there are no cycles.

I see what you mean, but it just boils down to how you interpret the problem. Specifically, if you focus on the actual forwarding paths instead of the contact lists, the tree structure that enables the linear solution becomes more clear.

As I’m guessing was intended, this problem is particularly well-suited for engineering interviews because you can start with an easy example (the DAG one could derive in this specific interview) then ask the applicant how the solution would change given the additional constraints you’ve described.

That’s simply not correct. Do an example. What graph do you draw? That’s the underlying graph that has to be acyclic. Where is this supposed tree structure coming from? Try a dense graph, like with n=5, and every actor having at least 3 contacts.

Reply on news.ycombinator.com