6 ms·
Two problems I had to solve in my Oxford interview (2013)
- elevensies 12y agoWell, 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
- deleted 12y ago[deleted]
- Chinjut 12y agoIn 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.
- elevensies 12y agooops! I changed it but I'm not sure if this is the right way to do it
- joshvm 12y agoMy 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!
- elevensies 12y agoCouple 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
- joshvm 12y agoYep 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!
- corruptio 12y agoMy 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.
- elevensies 12y agoInstruction 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.
- sharth 12y agoThe 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)?
- jgrahamc 12y agoCan be solved with no extra storage just three ints or pointers.
- kspiteri 12y agoYou 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.
- to3m 12y agoNot if N=1 ;) (A constant amount is of course independent of N anyway!)
- deleted 12y ago[deleted]
- kspiteri 12y ago> 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).
- Strilanc 12y agoA 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-with-unit-cost.html http://blog.computationalcomplexity.org/2009/05/shaving-logs...
- to3m 12y agoSure "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 :)
- seabee 12y agoWell, 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.
- white-flame 12y agoDescriptively, 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.
- to3m 12y agoThanks! I managed to work it out in the end, after the other comment said it was possible :)
- maxlybbert 12y agoIt'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-end-itera/240168707 http://www.drdobbs.com/cpp/a-classic-example-that-off-the-en... ).
- seabee 12y agoSeems 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.
- white-flame 12y agoWhy 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.
- compiler-guy 12y agoYour 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
- jessaustin 12y agoThe 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!
- hm8 12y agoProblem 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... :(
- Chinjut 12y agoOh 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.
- brianpgordon 12y agoWas 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.
- jgrahamc 12y agoYes. These were the two questions that I recall being asked when I was interviewing to be an undergraduate.
- arethuza 12y agoAs 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!
- myth_buster 12y agoThe problem 1 is more of a logical puzzle and may not be categorized as CompSci problem.
- vampirechicken 12y agoIt is for entrance to Oxford, not Random State University. Aren't Oxford students expected to be elite?
- asanagi 12y agoHere'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]
- Chinjut 12y agoAnswer 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...)
- foobarqux 12y agoLinked below is what Oxford currently lists as sample interview questions. http://www.ox.ac.uk/admissions/undergraduate/applying-to-oxford/interviews/sample-interview-questions http://www.ox.ac.uk/admissions/undergraduate/applying-to-oxf...
- deleted 12y ago[deleted]
- m3talridl3y 12y agoThe real question he was asked is: "Did you have access to computer science materials before applying. Prove it by solving these trivia."
- jgrahamc 12y agoNo. 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.
- abdulhaq 12y agoYes 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 :-)