Two problems I had to solve in my Oxford interview (2013) | Hacker News Reader

Two problems I had to solve in my Oxford interview (2013)

blog.jgc.org

64 pointsjgrahamc40 comments

Was this for entrance into the undergraduate program? Question 1 would have been extraordinarily difficult for me, having no formal computer education at all before entering undergrad. Maybe it's different in the UK.

Yes. These were the two questions that I recall being asked when I was interviewing to be an undergraduate.

As someone else who went to University in the UK to do CS in the 1980s I think I'd have enjoyed trying to answer these questions. What would have made it very difficult for me would have been doing something like that in an interview!

It is for entrance to Oxford, not Random State University. Aren't Oxford students expected to be elite?

The problem 1 is more of a logical puzzle and may not be categorized as CompSci problem.

Linked below is what Oxford currently lists as sample interview questions.

http://www.ox.ac.uk/admissions/undergraduate/applying-to-oxf...

Well, here is my non-zero-handling answer to the first

  Z2
  I2  <-+
  J0,2 -+
  Z3
  I2  <-+
  I3    |
  J1,3 -+

And with zero handling (maybe)

    Z4
    I4
    Z2
    J0,2 -+
  +-J0,4  |
  | I2  <=+ 
  | J0,2 -+ 
  +>Z3    
    J1,3 -+
  +-J1,4  |
  | I2  <=+
  | I3    |
  | J1,3 -+ 
  +>exit

Edit * 2nd try

My solution, looks pretty similar to your second.
I think this should work:
0 Z2 1 Z3 2 I4 3 J0,3 -> 5 // If r0 != 0, jump to add it to r2 4 J3,4 -> 9 // r0 == 0, force jump to check r1 5 I2 // add r0 6 I3 7 J0,3 -> 5 8 Z3 9 J1,3 -> 11 // If r1 != 0, jump to add it to r2 10 J3,4 -> exit // r1 == 0, force jump to exit 11 I2 // add r1 12 I3 13 J1,3 -> 11 14 exit
Phew that took a while. The simple case was easy enough. I guess exceptional candidates would be able to crack that out in an interview, otherwise they'd move you onto the balls.
Edited!

Couple corrections I think: - Register 4 should be set to zero before incrementing in instruction 2.
- inst. 4 should compare 0,4 , register 1 is unknown at this pt.
- inst. 3 should jump to 5

Yep 3->5 is a typo.
r4 could be zeroed, but I was lazy and assumed that as long as it's greater than zero it doesn't matter (since it's always compared to zero).
Instruction 4 should be cmp(3,4) to force a jump to 9.
EDIT: Although thinking about it, it doesn't make much difference. It has the same effect as doing cmp(0,4) since you know r4 > 0 and r0 == 0.
Thanks!

In your zero-handling program, you seem to suppose the first "J0,2" and "J1,3" commands take the arrow on equality, while the second "J0,2" and "J1,3" commands instead take the arrow on inequality.

oops! I changed it but I'm not sure if this is the right way to do it

My solution:
0: Z 2 1: Z 3 2: J 0 2 -> 4 3: J 1 3 -> 7 4: I 2 5: J 0 2 -> 4 6: J 1 3 -> 7 7: I 2 8: I 3 9: J 1 3 -> 7
Handles the zero case. Only uses 4 cells total.

Instruction 6 is a nop? if mem. 1 not-equals mem. 3, jump to 7, or else fall thru to 7?
I don't think you can depend on jumping in instruction 3, because you don't control the value of mem. 1, it's input. So if mem. 3 = 0, instructions 2 and 3 will always lead to instruction four.

Sure "only allowed to examine each ball once" should be "only allowed to examine each bucket once"? Otherwise you have to keep track of which balls you've looked at already after swapping. Also, I can't figure out how to do it that way :)

Descriptively, scan through the slots in order, stacking reds up on the left, and blues up on the right, leaving greens in the middle. You only need to remember how many reds & blues you've stacked up.
Programmatically:
LastRed = -1, LastBlue = numSlots
- If the observed ball is red, swap with ++LastRed. Move the observing arm forward, as you've already observed the one swapped in.
- If the observed ball is blue, swap with --LastBlue.
- If the observed ball is green, leave it there. It might get swapped with a red later as LastRed grows. Move the observing arm forward.
If the observing arm is at LastBlue, we're done.
Loop.

Thanks! I managed to work it out in the end, after the other comment said it was possible :)

It's highly unlikely that a candidate would recognize this as Dijkstra's Dutch National Flag problem ( http://www.drdobbs.com/cpp/a-classic-example-that-off-the-en... ).

Well, the correct solution means you never want to examine each ball more than once anyway. It's the kind of constraint you can consider as existing 'outside' of the algorithm.

Seems like the key insight into solving problem 1 is constructing the unconditional jump operation.
From what I remember of my Cambridge interview, the questions they asked weren't anywhere near as interesting as these.

Why would there be an unconditional jump?
- Initialize locations 2 & 3 to zero. (solution & scratch register, leaving 0 & 1 unmodified)
- While loc 2 is not equal to loc 0, increment loc 2. (Copy, just a conditional jump)
- While loc 3 is not equal to loc 1, increment locs 2 and 3. (Still just a conditional jump)
In the end, 2 holds the solution, 3 holds a copy of 1, and there are no unconditional jumps.

Your pseudo-code misses that there must be two branches in each loop. In a high-level language, it looks like there is a single branching construct:
while (condition) { do_something }
But in assembly, which is what we are writing, there are two branches: The loop test and the loop back. If you could guarantee that the two numbers were not zero, you could do it without an entry check, but since that isn't stated in the problem, you need to check.
Z2 // zero 2. This will hold the answer // Branch to "add element zero" loop if element zero is not zero J 0, 2, Handle_element_zero Z4 // unconditional branch to Handle_element_one I4 J 3, 4, Handle_element_one Handle_element_zero: I2 // increment answer J2, 0, Handle_element_zero // loop if we haven't iterated enough Z3 // zero loop counter Handle_element_one: J 1, 3, End // branch if there are no elements C: I3 I2 J3, 1, C End

The followup question was "Under what circumstances does this program fail?" so it seems they didn't want fancy input-checking, just a simple algorithm that assumed positive integers. After all, your algorithm doesn't handle fractional numbers, does it? "6.2" is displayed in the example!

Given the supplied instructions, it is not possible to write a program that handles floating point correctly, so my guess is that the failure conditions are non-integer numbers in locations 0 or 1.
My code also doesn't handle negative integers correctly, but I'm pretty sure there is a way to do it.
However, given that it is possible to write a program that works for all integers, and that this is an entry question for Oxford, "As correct as possible given the constraints of the problem" would be the right answer.

> My code also doesn't handle negative integers correctly, but I'm pretty sure there is a way to do it.
It's pretty easy to show by induction that you can't handle negative numbers in the general case. Consider: if memory locations 0 and 1 are both negative, so is their sum. But the only operations available to you are setting a value to 0, and incrementing it. You can't produce a negative number that way.

This is true. But if you are clever, you can handle the case where you have 2 arbitrary integers whose sum is non-negative!
The trick is to zero out a counter, then increment it until it is one of the two starting values. Then start a second counter and increment it together with the other starting value until the second counter reaches the first and the other contains the sum of the two. Finally start a counter at location 2 and increment it until it reaches the value of the register that has the sum.

Problem 1 could be made clearer by specifying that only non-negative integers could be stored on the tape. The example image doesn't help either... :(

Oh yeah. Note that one can never do anything to a memory location but write 0 to it or add 1 to it, so one couldn't possibly write into an uninitialized location anything but a non-negative integer.
Note that the "For example, here's a loop that keeps adding one to memory location 4 until it equals memory location 20" code only works for positive integers, at that! (It could be fixed to handle zero (at the cost of clobbering an extra memory location, in the process of constructing a "branch if equal" command from the "branch if not equal" command), but that's as far as we can go)
This may all be part of why one is asked "Under what circumstances does this program fail?" at the end.

The real question he was asked is: "Did you have access to computer science materials before applying. Prove it by solving these trivia."

No. I knew nothing about computer science when I got that interview. I had programmed (self-taught) but knew nothing of Big O and had never heard of Dijkstra or the Dutch National Flag problem.
These questions were less about testing my knowledge more about testing my ability to figure stuff out. The latter is highly prized in my experience by Oxford.

Yes I went up to Oxford in 1983 to read Natural Science and although I was mad on computers that meant simply that I had done some z80 and BASIC programming and read a few books on e.g. PL/1 programming and AI (i.e. lisp) from the local library. There was no internet then :-)

The second problem would be clearer if we knew how much scratch space we had. Is it zero? Is it O(1)? Is it O(n)?

You just need a constant number of pointers. This requires O(log n) scratch space because a pointer can be stored in O(log n) space.

Not if N=1 ;)
(A constant amount is of course independent of N anyway!)

> Not if N=1 ;)
> (A constant amount is of course independent of N anyway!)
When using O notation, we're doing asymptotic analysis and n can be arbitrarily large. If you have an arbitrarily large pointer, you cannot store the pointer in a constant number of bits. If your pointer is 64-bits long, you're cannot handle n > 2^64. That is why I said you need O(log n) rather than O(1).

A common implicit assumption in complexity analysis is that machine words can hold O(lg n) bits, and that those words can be operated on in constant time.
Lots and lots of algorithms gain an extra lg(n) factor if you drop that assumption.
e.g. http://blog.computationalcomplexity.org/2009/05/shaving-logs...

Well, that's certainly an unusual way of looking at it! Pointers are usually assumed to be "large enough" when you do this sort of analysis, with the data being assumed to fit into the available address space (if you're even thinking about such issues). But I see your thinking now!

Can be solved with no extra storage just three ints or pointers.

Here's a python script for the simple machine and a 9 instruction solution program. It won't work if the addends are zero. The 0 case can be handled by checking for 0 and jumping ahead of the increment loop.
class VM(object): memory = [] ip = 0 while len(memory) < 1000: memory.append(0) memory[0] = 3 memory[1] = 4 def z(idx): VM.memory[idx] = 0 VM.ip += 1 def i(idx): VM.memory[idx] += 1 VM.ip += 1 def j(idx, cmp, goto): if VM.memory[idx] == VM.memory[cmp]: VM.ip += 1 else: VM.ip = goto program = ( (z, (2,)), #0 INITIALIZE USED MEMORY (z, (3,)), #1 (z, (4,)), #2 (i, (2,)), #3 BEGIN LOOP, INCREMENT m[2] (i, (3,)), #4 INCREMENT m[3] (j, (3, 0, 3)), #5 LOOP UNTIL memory[3] == memory[0] (i, (2,)), #6 SIM. (i, (4,)), #7 (j, (4, 1, 6)) #8
)
def run(): while VM.ip < len(program): func, args = program[VM.ip] func(*args) run() print VM.memory[2]

Answer to question 1: My program is simply Z2; I2; I2; I2
Answer to question 2: My program fails under the circumstances that the values in locations 0 and 1 do not sum to 3.
(I mean, as long as we're expected to give answers with significant failure conditions...)

Reply on news.ycombinator.com