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).