> (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).
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!
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.
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 :)
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.
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.
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.
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.
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.
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!
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.
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.
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.
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.
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 :-)
44 comments
[ 4.7 ms ] story [ 105 ms ] thread(A constant amount is of course independent of N anyway!)
> (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).
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...
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.
From what I remember of my Cambridge interview, the questions they asked weren't anywhere near as interesting as these.
- 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.
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.
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.
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.
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.
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.
I think this should work:
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!
- inst. 4 should compare 0,4 , register 1 is unknown at this pt.
- inst. 3 should jump to 5
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!
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.
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...)
http://www.ox.ac.uk/admissions/undergraduate/applying-to-oxf...
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.