Skip to main content

The two problems I had to solve in my Oxford interview

Back in the 1980s I went to Oxford University and studied Mathematics and Computation (this was almost the entire Mathematics course plus Computer Science added on; the degrees offered today are a little different).  Having sat the mathematics entrance exam and gone through all the mathematics interviews I had interviews in the Programming Research Group (now the Department of Computer Science). During those interviews two specific programming/algorithm design questions were posed. Here they are (I made up names for them).

The Z Machine

A computer is constructed with a simple memory layout. It has an unlimited amount of memory and each memory location is numbered so that a program can refer to it. Each memory location can store a single number or be uninitialized. In the following diagram memory locations that are blank are uninitialized some other memory locations have numbers in them.

The computer's CPU only has three instructions Z, I and J as follows:

Z. This instruction zeroes a memory location. For example, Z2 sets memory location 2 to 0, Z42 sets memory location 42 to 0.

I. This instruction adds one to the contents of a memory location. For example, I3 adds 1 to whatever is currently stored in location 3.

J. This instruction examines the contents of two memory locations and branches if the contents are different. For example J18,19 would compare the contents of memory locations 18 and 19, if they are the same the program continues with the next instruction, if different it branches. The branch destination is just specified by drawing an arrow to the instruction you want to go to.

When there are no more instructions the program stops.

For example, here's a loop that keeps adding one to memory location 4 until it equals memory location 20.
1. The operator of the machine places two numbers (one each) in memory locations 0 and 1. Here, for example, the operator has put 3 in location 0 and 4 in location 1. Write a program using the Z, I and J instructions to add those (arbitrary) numbers together and put the result in memory location 2.

2. Under what circumstances does this program fail?

The One-eyed Robot

(If you've studied computer science you may recognize this problem)

On the ground along Keble Road there are a line of n buckets, in each bucket is a single ball. The balls are red, green and blue. A robot is to be programming to sort the balls so that there's one ball in each bucket still but the colours are now in the order red, green, blue. So, working from left to right an observer will see all the red balls in buckets, then all the green balls in buckets, and finally all the blue balls.
The robot is only allowed to examine one ball at a time by peering into its bucket and is only allowed to examine each ball once. When it looks at a ball it must decide what to do with it. The robot has two arms and the only ball manipulation it can do is swap the balls in two buckets.

1. Program the robot to sort the balls.

2. Write out a proof that the proposed algorithm works.


Of course, a whole load of other questions were asked about program running time, correctness and what I later realized was the lambda calculus. But these were the two main 'programming' tasks.


CoachDom said…
1 z3
2 z2
3 i2
4 i3
5 j3-0 ->3
6 z3
7 i3
8 i2
9 j3-1 ->7

It fails when either [0] or [1] contain 0
CoachDom said…
1 z3
2 z2
3 i2
4 i3
5 j3-0 ->3
6 z3
7 i3
8 i2
9 j3-1 ->7

It fails when either [0] or [1] contain 0
CoachDom said…
1 z3
2 j3-0 ->8·
3 z2
4 i2
5 i3
6 j3-0 ->4
7 z3
8 j3-1 ->12
9 i3
10 i2
11 j3-1 ->9
12 z3

Solution with managing zero case !
CoachDom said…
Damn in the last solution i forgot to initialise [2]
So insert Z2 command at second line, and add +1 to all memory address for jmp ! :)
@CoachDom: the first solution is good, but the one handling the zero case is not.
phil said…
This ought to work if the two numbers are non-negative integers (and not too large, obviously):

0001: Z2
0002: Z3
0003: I3
0004: J0,2 0006
0005: J2,3 0008
0006: I2
0007: J0,2 0006
0008: Z4
0009: J1,4 0011
0010: J3,4 0014
0011: I2
0012: I4
0013: J1,4 0011
0014: Z3

The second problem's impossible, isn't it? Perhaps I'm mis-reading it.

Suppose there are 3 red balls, 1 green and 2 blue. If the first ball you come across is green, it needs to go into the third bucket from the right. But you don't know that until you've examined all the other balls. That would break the rule about deciding what to do with a ball immediately after examining it.
@Unknown: the second problem is not impossible.
phil said…
Oh, I think I got it now.

left = -1;
right = num_buckets;
loc = 0;
while (loc<right) {
  switch (buckets[loc]) {
    case RED:
      swap(buckets[loc], buckets[left]);
    case BLUE:
      swap(buckets[loc], buckets[right]);
    case GREEN:
Dave O said…
Here's my online implementation of the ball sorting algorithm:
Pascal said…
1 z2
2 z3
3 i2
4 j0,2 --> 3
5 i3
6 i2
7 j1,3 --> 5
Will enter an infinite loop if either [0] or [1] = zero

b = ["g", "b", "r", "b", "b", "g", "b", "r", "g", "r", "b", "r", "b", "b", "r", "g", "g", "b", "r", "r"]
pos = 0
for c in ["r", "g", "b"]:
    for i in range(pos, len(b), 1):
        if b[i] == c:
            b[i], b[pos] = b[pos], b[i]    # python swap
            pos += 1
print b
Josh said…
I think this should work:

0 Z2
1 Z3
2 I4 //holds 1, use to force jump to exit

3 J0,3 -> 6 // r0 != 0, r1 == ?
4 J1,3 -> 12 // r0 == 0, r1 != 0
5 J3,4 -> 16

6 I2 // add r0
7 I3
8 J0,2 -> 9
9 Z3

10 J1,3 -> 11 // r0 != 0, r1 != 0
11 J3,4 -> 16 // r0 != 0, r1 == 0

12 Z3 // add r1
13 I2
14 I3
15 J1,2 -> 12

16 exit
Josh said…
EDIT: made a couple of typos in the summation loops.

I think this should work:

0 Z2
1 Z3
2 I4 //holds 1, use to force jump to exit

3 J0,3 -> 6 // r0 != 0, r1 == ?
4 J1,3 -> 12 // r0 == 0, r1 != 0
5 J3,4 -> 16

6 I2 // add r0
7 I3
8 J0,2 -> 6
9 Z3

10 J1,3 -> 11 // r0 != 0, r1 != 0
11 J3,4 -> 16 // r0 != 0, r1 == 0

12 Z3 // add r1
13 I2
14 I3
15 J1,2 -> 13

16 exit
Josh said…
Blergh typos and some shrinkage, try three.

0 Z2
1 Z3
2 I4
3 J0,3 -> 6 // r0 != 0
4 J1,3 -> 10 // r0 == 0
5 I2 // add r0
6 I3
7 J0,3 -> 5
8 Z3
9 J1,3 -> 11 // r1 != 0
10 J3,4 -> exit // r1 == 0
11 I2 // add r1
12 I3
13 J1,3 -> 11
14 exit
vivekseth said…
0000: Z 2
0001: I 2
0002: J 2, 0 (0001)
0003: I 2
0004: J 2, 1 (0003)
Unknown said…

I got the exact same answer as you for the first question.

However, for your solution to the second problem, i don't think it satisfies the condition that the robot is only allowed to examine each ball once. Phil's solution looks like it should work and meets this criteria.
Unknown said…
01 z2 -- additive accumulator
02 z3 -- reference 0
03 z4 -- reference 1
04 i4 -- reference 1
05 z5 -- accumulator
06 j3,4 => 08 -- if false
07 i2
08 j2,0 => 07 -- add 1 until true
09 j3,4 => 12 -- if false
10 i5
11 i2
12 j5,1 => 10 -- using #5

This program will enter an infinite loop if any location has a negative number (as per the example).
Anatoly Vorobey said…
It's a little tricky to take care of the case when both numbers are 0.

I managed with 17 instructions, I think this works provided 0 and 1 are integers >=0. I first check explicitly for the "both 0" case. Register 10 stays zero throughout (except in that first check).

J0, 10 -> first
J1, 10 -> first
J0, 10 -> end

J2, 0 -> first_loop


J3, 1 -> second_loop
J3, 10 -> end

J2, 10 -> first

J3, 10 -> second

end: Z10
MEC said…
2 i1
3 i2
4 j0,2 --> 2
5 i2
6 j1,2 --> 2

1 z2
2 j0,2 --> 6
3 i1
4 i2
5 j0,2 --> 3
6 j1,2 --> 9
7 i2
8 j1,2 --> 7
9 z1

First listing works for non-zero values (it may work for 0 depending upon what occurs when i command is run on max-int values).

Second listing works for values including 0.

Both may work on negative values depending again upon what occurs when i command is run on max-int values.

Both require only memory locations 0,1,and 2. Preservation of inputs was not a requirement.
Unknown said…
Your 'Z-machine' is a Turing machine I believe from memory.
Unknown said…
I made a couple of python 2.7.8 programs to implement my solutions.
1. Could account for zero but didn't because it makes the program not as nice looking. Negative numbers would only work if you have two of them and you interpret a positive output as negative.
s = [
l = [9,5,'','']
x = 0
while True:
if s[x][0] == 'z':
l[s[x][1]] = 0
elif s[x][0] == 'i':
l[s[x][1]] += 1
if l[s[x][1]] != l[s[x][2]]:
x = s[x][3] - 1
x += 1
if x >= len(s):

b = [2,3,1,3,3,2,3,1,2,1,3,1,3,3,1,2,2,3,1,1]
c1 = 0
c3 = 0
x = 0
while x < len(b):
if b[x] == 1:
b[x] = b[c1]
b[c1] = 1
c1 += 1
if b[x] ==1 or b[x] ==2:
x += 1
if x >= len(b)-c3:
if b[x] == 3:
b[x] = b[len(b)-c3 -1]
b[len(b)-c3 -1] = 3
c3 += 1
In short it works because balls of type 1 or 3 are put to their respective sides and 2 has no place to be except the middle. I wonder if I broke the rules.
Haran said…
For problem 1:
01. Z 2
02. Z 4
03. I 4
04. Z 3
05. J 3 0 07
06. J 4 0 09
07. I 2
08. J 0 2 07
09. J 3 1 11
10. J 4 1 13
11. I 3
12. I 2
13. J 3 1 11

Just 13 line. It doesn't consider Any number less than 0. Seems like no one noted down there is a floating point number mentioned in the system example. So I can say my code considers only positive integers and zeros.
Unknown said…
Has anyone solved this in under 13 OPS

0001 Z2
0002 Z3
0003 Z4
0004 I4
0005 J0,2 0007
0006 J3,4 0009
0007 I2
0008 J0,2 0007
0009 J1,3 0011
0010 J3,4 #END
0011 I2
0012 I3
0013 J1,3 0011

This only works for positive intgers
0utdacious said…

0: z2
1: j0,2 -> 5
2: j0,3 -> 8
3: i2
4: j0,3 -> 8
5: i1
6: i2
7: j0,2 -> 5
8: j1,2 -> 3

Handles the 0 case and doesn't use any additional memory.
Assumes that uninitialized memory will never equal 0, thus `j0,3 -> x` acts as an unconditional jump to `x`

Popular posts from this blog

How to write a successful blog post

First, a quick clarification of 'successful'. In this instance, I mean a blog post that receives a large number of page views. For my, little blog the most successful post ever got almost 57,000 page views. Not a lot by some other standards, but I was pretty happy about it. Looking at the top 10 blog posts (by page views) on my site, I've tried to distill some wisdom about what made them successful. Your blog posting mileage may vary. 1. Avoid using the passive voice The Microsoft Word grammar checker has probably been telling you this for years, but the passive voice excludes the people involved in your blog post. And that includes you, the author, and the reader. By using personal pronouns like I, you and we, you will include the reader in your blog post. When I first started this blog I avoid using "I" because I thought I was being narcissistic. But we all like to read about other people, people help anchor a story in reality. Without people your bl

Your last name contains invalid characters

My last name is "Graham-Cumming". But here's a typical form response when I enter it: Does the web site have any idea how rude it is to claim that my last name contains invalid characters? Clearly not. What they actually meant is: our web site will not accept that hyphen in your last name. But do they say that? No, of course not. They decide to shove in my face the claim that there's something wrong with my name. There's nothing wrong with my name, just as there's nothing wrong with someone whose first name is Jean-Marie, or someone whose last name is O'Reilly. What is wrong is that way this is being handled. If the system can't cope with non-letters and spaces it needs to say that. How about the following error message: Our system is unable to process last names that contain non-letters, please replace them with spaces. Don't blame me for having a last name that your system doesn't like, whose fault is that? Saying "Your

The Elevator Button Problem

User interface design is hard. It's hard because people perceive apparently simple things very differently. For example, take a look at this interface to an elevator: From flickr Now imagine the following situation. You are on the third floor of this building and you wish to go to the tenth. The elevator is on the fifth floor and there's an indicator that tells you where it is. Which button do you press? Most people probably say: "press up" since they want to go up. Not long ago I watched someone do the opposite and questioned them about their behavior. They said: "well the elevator is on the fifth floor and I am on the third, so I want it to come down to me". Much can be learnt about the design of user interfaces by considering this, apparently, simple interface. If you think about the elevator button problem you'll find that something so simple has hidden depths. How do people learn about elevator calling? What's the right amount of