Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.jgc.org

Post reply on HN
Print view View original

11–20 of 45 posts

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

#11

Post by to3m »

kspiteri wrote: post #8
to3m wrote: post #5

Earlier quoted context omitted.

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).

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!

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

#12

Post by seabee »

to3m wrote: post #9

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.

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

#13

Post by white-flame »

seabee wrote: post #10

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.

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

#14

Post by white-flame »

to3m wrote: post #9

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.

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

#15

Post by compiler-guy »

white-flame wrote: post #13
seabee wrote: post #10

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

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

#18

Post by jgrahamc »

brianpgordon wrote: post #17

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.

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

#19

Post by jessaustin »

compiler-guy wrote: post #15
white-flame wrote: post #13

Earlier quoted context omitted.

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 th…

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!

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

#20

Post by compiler-guy »

jessaustin wrote: post #19
compiler-guy wrote: post #15

Earlier quoted context omitted.

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 th…

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.

Post reply on HN