Interview question: Potato Spies


29 June 2011, by

In our initial phone interviews, we like to ask candidates a question based on a real-world scenario, that requires algorithmic or mathematical thinking in order to solve.

Below is just such a test that we wrote but never got round to using. My colleague Kenny and I also presented it to a room full of Oxford Mathematicians in February 2011. Kenny used to work as a teacher, so he grabbed the chalk with relish, while I amused myself throwing new potatoes at the audience whenever they got a question right. That was one careers event they didn’t forget in a hurry!

Question

Two spies are in the business of communicating with each other through a very primitive communication channel. In fact, they send each other bags of potatoes.

On receiving a bag of potatoes the recipient spy counts how many potatoes he has received and looks up the number in his secret code book in order to decipher the message. He then returns the sack with a different number of potatoes in to reply.

By and large this works very well. No-one is interested in intercepting large bags of potatoes and their conversations go undetected. However, it is noticed that on occasion it would be very useful to be able to send two messages at once. In a brief get-together the spies may be able to agree on a scheme to encode two messages in one bag of potatoes. What could you suggest?

photograph by Thom Quine

Discussion

OK. It’s a shaky story at best. What we’re really interested in here is a method of encoding 2 numbers in one. We could of course also send a number of potatoes equal to the higher message and take a bite out of a number of them equal to the smaller message. If the candidate suggests that, we tell them that the potatoes must arrive in pristine condition because the spies sell them to make a living. And smart-arses who point out that you can make invisible ink out of potato juice get binned straight away :-)

There are a number of possible methods outlined below, and the bulk of the interview will be taken up with a comparison of the various methods. The most interesting properties of an encoding method for discussion are the following

  • the number of potatoes needed to encode the message
  • the ease of and feasibility of encoding and decoding
  • the behaviour of the approach with weighted messages (i.e. whether it matters which message comes first)
  • extensibility to more than 2 messages.

Prime decomposition

The Mathematics students among you will probably be tempted to make use of the fact that every number has a unique decomposition into prime factors – so we can encode a and b as 2^a3^b.

This would work in theory, although in fact it is rather a poor method. Of the methods mentioned here it is the only method which fails to map message pairs 1-1 onto the natural numbers, which means that it’s likely to require more potatoes than the other methods.

To illustrate how bad this method really is, consider that the poor spy wanting to encode 345 and 21 would need approximately 7.497 x 10113 potatoes. Although the more modest 9 and 12 can be encoded in around a quarter of a (US) billion potatoes.

Concatenation

If we assume that each message is less than a fixed number k, then we can encode a and b as ktimes a + b. Decoding is a simple process of dividing by k; a is the quotient and b the remainder.

If we adopt an appropriate based number system, this process amounts to simple concatenation of the digits of a and the digits of b (assuming zero padding where necessary).

For this to be the case, we must adopt a number system with base m where k is a power of m.

For example, if k is 1000, the above method is simply a concatenation of a and b in decimal with zeros added at the left of each to make them each up to n digits.

345 and 21 become 345021

9 and 12 become 9012

The number of digits required is log_m k + lfloorlog_m arfloor.

Interleaving

Concatenation requires us to assume that each message is less than a fixed number k. If we cannot make such an assumption, we can still find a solution by “digit manipulation” by interleaving the digits of a and b (ababababab…).

For instance:

345 and 21 become 304251

9 and 12 become 192

The number of digits is 2 log_m a if a geq b and 2 log_m b + 1 otherwise.

Plotting

Leaving aside digit manipulation methods we can also view a and b as co-ordinates on a graph. After plotting (a,b) we can count outwards from the origin in any of several ways, one obvious one being

(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3)…

i.e counting upwards along each of the x+y = k diagonals in turn.

Using the above method, a and b are encoded as a and b become:

[

frac{1}{2}(a+b)(a+b+1)

]

…which is obtained from the formula for triangular numbers plus the remainder left to count on the next diagonal which is the y component +1.

The encode process is just counting until you reach the plotted point. The decode process is just counting out the number, plotting the point and reading off the co-ordinates. Of course, for large numbers you’d want to calculate rather than count.

Using this method,

345 and 21 become 67183

9 and 12 become 244

When we presented this at the Oxford Mathematics Institute, we managed to convince ourselves that this method is more efficient than concatenation. However, since we failed to keep a record of the proof, we’ll have to leave that as an exercise to the reader!

Tags: , , ,

Categories: Recruitment, Softwire, Technical

«
»

13 Responses to “Interview question: Potato Spies”

  1. Joey says:

    This question is effectively asking for ways to enumerate NxN. Therefore there is no ‘best’ way as how ‘good’ a method is depends on the expected values of a & b.

    For example, if a&b were normally in the area (100,900) -> (200,1000) then a method which counted the pairs in this area first would be the ‘best’, however it would no longer be the ‘best’ if a&b were normally in a different area.

  2. Chris Harris says:

    Fair point – as with many of our interview questions, although it starts as a real-world problem, we’ll eventually want to abstract from any of the practicalities. If there was any doubt as to what “best” meant I would explain to the interviewee that we want the answer that becomes best as a and b tend to infinity.

  3. Sean says:

    It seems like the plotting solution has a direct one to one mapping from the concatenated number to a point so I’m not sure whether it can be more efficient, can it?

    From the plotting equation if a->infinity and b <infinity and b->inifinity then it the number of digits logm(2a^2) which is worse.

    As for an alternate method: if the order of the messages doesn’t matter then we can force a > b and we then only have to map the (roughly) half the possible combinations. I.e. we don’t have to map any point where b > a. So we can map just map everything below and including the line x = y. One example mapping would be b+a(a+1)/2. In this case as a->infinity the number of digits becomes logm((a^2)/2) regardless of b, which is always as good as the previous plotting methods best case. And if the order does matter we can choose to use the first bit to encode whether b is the first message or not and have the rest of the message start after that bit.

  4. Sean says:

    Sorry, I meant interleaving not concatenation. And the second line should be (before the text was processed as a special character sequence):

    From the plotting equation if a->infinity and b is much less than a then the number of digits tends to logm((a^2)/2) which is better than interleaving but if a and b tend to infinity then the number of digits become logm(2a^2) which is worse than interleaving.

    Also adding an extra bit to identify whether b is the first message then doubles the number of potatoes making it the same as interleaving again. So there’s no advantage unless we don’t care about the order of the messages.

  5. Chris Harris says:

    Good point Sean. I guess it does make sense that plotting works best when one number is a lot bigger than the other, as in this case interleaving feels a little inefficient (e.g. 1234 and 1 -> 10203041). But if both numbers are of similar size then it’s hard to see how we can improve on interleaving.

  6. Tanjilul says:

    Why not use different kinds of potatoes? Red for one message and yellow for the other.

  7. Chris Harris says:

    Thanks Tanjilul, I think that falls into the category of being too clever for your own good!

  8. Grocer says:

    Weigh the spuds. Messages = number above and number below the modal weight.
    Weighted messages : skew to the left or skew to the right.
    Extensibility : bimodal, trimodal etc distributions.

    As an aside : this problem illustrates the differences between mathematicians and engineers. With a sack of potatoes of the allowable handling weight of 25kg your example ‘code’ of 345021 would give a load of potatoes of average weight 72mg – hardly saleable. An engineer might have chosen a bag of rice grains or poppy seeds.
    My weight distribution method would need an average potato weight of less than 68g, ie a sackful of smallish new potatoes.

  9. Chris Harris says:

    Hi Grocer,

    You’re right, our method will fall foul of all but the most accommodating airline :-)

    I’d be interested in hearing more about your weight-based solution. Does it require you to have control over the potatoes’ weight distribution?

  10. Grocer says:

    Yes, the spies need to weigh all the potatoes in the sack and plot the weights as a histogram. The size of the cells or the resoution of the balances used might need to be pre-agreed (balances do naturally set their own minimum cell size). Also, whether the modal cell is counted to the left or to the right must be pre-agreed.

    Count out random spuds equal to the sum of the two message numbers (a+b) and plot the histogram – I guess it will be a classic bell-shaped normal distribution. Sum the cells to the left and to the right of the modal cell. If a>b then take out large spuds and replace them with small spuds – skews the distibution to the right – continue until the sums are correct.

    Three or more messages will be a bit more difficult to ‘encode’ – creating histograms having n-1 peaks.

    It will take a while to weigh the sackful and plot the histogram, but only a+b (555) spuds will be handled – this is likely to be quicker than having to count a*k+b (eg: 304,251) spuds.

    For maximum security against discovery of the method the spuds should be graded within a small weight range and a small cell size chosen.

  11. Chris Harris says:

    Ooh, nice! You’d definitely get some marks for this in our interview, although we’d also ask you to think about options that don’t require weighing scales so we could have a discussion around the efficiency of different methods

  12. Dave Milne says:

    Can you not do this as a sum of multiples of 2 and then you can transmit an unlimited number of messages?
    i.e. 6 potatoes can only be 2+4
    20 potatoes can be 16 + 4

    disadvantages are you run into very big numbers very quickly and I suspect that someone more mathematically minded than me might point out without ordering you couldn’t guarantee uniqueness

  13. Chris Harris says:

    Hi Dave,

    That’s a nice solution and is similar to the “Prime decomposition” solution I discuss above, which uses powers of 2 and 3 instead of just 2. Your version requires fewer potatoes but has the ordering issue that you have identified. And it still requires more potatoes than the other solutions discussed above.


Leave a Reply

* Mandatory fields


2 + seven =

Submit Comment