What's the most insidious way to pose this problem?

Question

My best shot so far:

A delivery vehicle needs to make a series of deliveries (d₁,d₂,...d_n), and can do so in any order--in other words, all the possible permutations of the set D = {d₁,d₂,...d_n} are valid solutions--but the particular solution needs to be determined before it leaves the base station at one end of the route (imagine that the packages need to be loaded in the vehicle LIFO, for example).

Further, the cost of the various permutations is not the same. It can be computed as the sum of the squares of distance traveled between d_{i -1} and d_i, where d₀ is taken to be the base station, with the caveat that any segment that involves a change of direction costs 3 times as much (imagine this is going on on a railroad or a pneumatic tube, and backing up disrupts other traffic).

Given the set of deliveries D represented as their distance from the base station (so abs(d_i-d_j) is the distance between two deliveries) and an iterator permutations(D) which will produce each permutation in succession, find a permutation which has a cost less than or equal to that of any other permutation.

Now, a direct implementation from this description might lead to code like this:

function Cost(D) ...

function Best_order(D)
    for D1 in permutations(D)
        Found = true
        for D2 in permutations(D)
            Found = false if cost(D2) > cost(D1)
        return D1 if Found

Which is O(n*n!^2), e.g. pretty awful--especially compared to the O(n log(n)) someone with insight would find, by simply sorting D.

My question: can you come up with a plausible problem description which would naturally lead the unwary into a worse (or differently awful) implementation of a sorting algorithm?

Answer 1

I assume you're using this question for an interview to see if the applicant can notice a simple solution in a seemingly complex question.

[This assumption is incorrect -- MarkusQ]

You give too much information.

The key to solving this is realizing that the points are in one dimension and that a sort is all that is required. To make this question more difficult hide this fact as much as possible.

The biggest clue is the distance formula. It introduces a penalty for changing directions. The first thing an that comes to my mind is minimizing this penalty. To remove the penalty I have to order them in a certain direction, this ordering is the natural sort order.

I would remove the penalty for changing directions, it's too much of a give away.

Another major clue is the input values to the algorithm: a list of integers. Give them a list of permutations, or even all permutations. That sets them up to thinking that a O(n!) algorithm might actually be expected.

I would phrase it as:

Given a list of all possible permutations of n delivery locations, where each permutation of deliveries (d₁, d₂, ..., d_n) has a cost defined by:

Return permutation P such that the cost of P is less than or equal to any other permutation.

All that really needs to be done is read in the first permutation and sort it.

If they construct a single loop to compare the costs ask them what the big-o runtime of their algorithm is where n is the number of delivery locations (Another trap).

Answer 2

This isn't a direct answer, but I think more clarification is needed.

Is d_i allowed to be negative? If so, sorting alone is not enough, as far as I can see.

For example:

d₀ = 0

deliveries = (-1,1,1,2)

It seems the optimal path in this case would be 1 > 2 > 1 > -1.

Edit: This might not actually be the optimal path, but it illustrates the point.

Answer 3

YOu could rephrase it, having first found the optimal solution, as

"Give me a proof that the following convination is the most optimal for the following set of rules, where optimal means the smallest number results from the sum of all stage costs, taking into account that all stages (A..Z) need to be present once and once only.

Convination:

A->C->D->Y->P->...->N

Stage costs:

A->B = 5,
B->A = 3,
A->C = 2,
C->A = 4,
...
...
...
Y->Z = 7,
Z->Y = 24."

That ought to keep someone busy for a while.

Answer 4

This reminds me of the Knapsack problem, more than the Traveling Salesman. But the Knapsack is also an NP-Hard problem, so you might be able to fool people to think up an over complex solution using dynamic programming if they correlate your problem with the Knapsack. Where the basic problem is:

can a value of at least V be achieved without exceeding the weight W?

Now the problem is a fairly good solution can be found when V is unique, your distances, as such:

The knapsack problem with each type of item j having a distinct value per unit of weight (vj = pj/wj) is considered one of the easiest NP-complete problems. Indeed empirical complexity is of the order of O((log n)2) and very large problems can be solved very quickly, e.g. in 2003 the average time required to solve instances with n = 10,000 was below 14 milliseconds using commodity personal computers1.

So you might want to state that several stops/packages might share the same vj, inviting people to think about the really hard solution to:

However in the degenerate case of multiple items sharing the same value vj it becomes much more difficult with the extreme case where vj = constant being the subset sum problem with a complexity of O(2N/2N).

So if you replace the weight per value to distance per value, and state that several distances might actually share the same values, degenerate, some folk might fall in this trap.

Answer 5

Isn't this just the (NP-Hard) Travelling Salesman Problem? It doesn't seem likely that you're going to make it much harder.

Maybe phrasing the problem so that the actual algorithm is unclear - e.g. by describing the paths as single-rail railway lines so the person would have to infer from domain knowledge that backtracking is more costly.

What about describing the question in such a way that someone is tempted to do recursive comparisions - e.g. "can you speed up the algorithm by using the optimum max subset of your best (so far) results"?

BTW, what's the purpose of this - it sounds like the intent is to torture interviewees.

Answer 6

You need to be clearer on whether the delivery truck has to return to base (making it a round trip), or not. If the truck does return, then a simple sort does not produce the shortest route, because the square of the return from the furthest point to base costs so much. Missing some hops on the way 'out' and using them on the way back turns out to be cheaper.

If you trick someone into a bad answer (for example, by not giving them all the information) then is it their foolishness or your deception that has caused it?

How great is the wisdom of the wise, if they heed not their ego's lies?