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

21–30 of 45 posts

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

#21

Post by Chinjut »

hm8 wrote: post #16

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.

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

#23

Post by Strilanc »

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

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

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

#25

Post by thaumasiotes »

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

Earlier quoted context omitted.

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

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

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

#26

Post by asanagi »

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

  def run():
	while VM.ip

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

#27

Post by Chinjut »

elevensies wrote: post #22

Well, here is my non-zero-handling answer to the first Z2 I2 And with zero handling (maybe) Z4 I4 Z2 J0,2 -+ +-J0,4 | | I2 Z3 J1,3 -+ +-J1,4 | | I2 exit Edit * 2nd try

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.

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

#28

Post by Chinjut »

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

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

#29

Post by elevensies »

Chinjut wrote: post #27
elevensies wrote: post #22

Well, here is my non-zero-handling answer to the first Z2 I2 And with zero handling (maybe) Z4 I4 Z2 J0,2 -+ +-J0,4 | | I2 Z3 J1,3 -+ +-J1,4 | | I2 exit Edit * 2nd try

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

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

#30

Post by to3m »

white-flame wrote: post #14
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, swa…

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