Two problems I had to solve in my Oxford interview (2013)
1–10 of 45 posts
Re: Two problems I had to solve in my Oxford interview (2013)
#2The 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)?
Re: Two problems I had to solve in my Oxford interview (2013)
#3The 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)?
Can be solved with no extra storage just three ints or pointers.
Re: Two problems I had to solve in my Oxford interview (2013)
#4The 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.
Re: Two problems I had to solve in my Oxford interview (2013)
#5The 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!)
Re: Two problems I had to solve in my Oxford interview (2013)
#6Re: Two problems I had to solve in my Oxford interview (2013)
#7Re: Two problems I had to solve in my Oxford interview (2013)
#8Earlier quoted context omitted.
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).
Re: Two problems I had to solve in my Oxford interview (2013)
#9Sure "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 :)
Re: Two problems I had to solve in my Oxford interview (2013)
#10Seems 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.