I’ve always found recursion somewhat unnatural to think about, but somehow satisfying when I can see it unfolding in my mind – this simple exercise in reversing a string using recursion is a case in point…
>>> def reverse(str):
if len(str)==1:
return str
else:
return reverse(str[1:])+str[0]
>>> reverse('hello')
'olleh'
>>>
Of course, this is just a thought experiment. In real-world Python, you’d do this:
>>> 'abcdef'[::-1] 'fedcba' >>>
Quick one about coding a deep copy and avoiding recursive references…
Let’s say we have an instance a which has a reference to an instance b and we have to do a deep copy of a. To do this, we need a deep copy of b as well.
But let’s say b had a reference back to a.
Here it is in Python (I know Python has its own __deepcopy__() method but the below is for illustrative purposes).
class A:
def __init__(self,b=None):
self.b=b
def deepcopy(self):
newA=A()
newA.b=self.b.deepcopy()
return newA
class B:
def __init__(self,a=None):
self.a=a
def deepcopy(self):
newB=B()
newB.a=self.a.deepcopy()
return newB
Now let’s execute this:
>>> a=A() >>> b=B() >>> a.b=b >>> b.a=a >>> newA=a.deepcopy()
What happens? Not pretty – a recursion limit error.
To fix this, we can keep track in a as to whether that instance has already created a copy of itself, so when it is called back from b it can just return that instance. This is sometimes called the “memo” copy. See amended code below.
class A:
def __init__(self,b=None):
self.b=b
self.memo=None
def deepcopy(self):
if self.memo==None:
newA=A()
self.memo=newA
newA.b=self.b.deepcopy()
self.memo=None
return newA
else:
return self.memo
class B:
def __init__(self,a=None):
self.a=a
def deepcopy(self):
newB=B()
newB.a=self.a.deepcopy()
return newB
Now when we execute:
>>> a=A() >>> b=B() >>> a.b=b >>> b.a=a >>> newA=a.deepcopy() >>> newA <__main__.A instance at 0x00D53A30> >>> newA.b.a <__main__.A instance at 0x00D53A30> >>> newA2=a.deepcopy() >>> newA2 <__main__.A instance at 0x00D53AF8> >>> newA2.b.a <__main__.A instance at 0x00D53AF8> >>>
Note that the memo is removed just before the copy is handed back so that if you call deepcopy again you’ll get a new copy of a.
What is a yield curve
A yield curve is a representation of what interest rates you could lock in today for investments over different periods. It’s effectively a set of yields for securities of different maturities (typically cash rates at the short end, futures and then swaps at the longer maturities – see the wikipedia entry). These yields are typically calculated from market prices using standard price/yield formulas.
Why yield curves can’t directly be used in PV calculations
The problem is that the quoted rates are from coupon paying securities and tell us the value of a series of cash flows, but they don’t tell us the rate for a cash flow at the maturity point independently of the other cash flows. So these rates don’t directly imply the present value of a dollar to be received at the maturity points – that is, they cant be used directly as discount rates.
The Zero curve to the rescue
A zero curve represents the set of interest rates assuming that there are no periodic cash flows – as though the rate reflects a single payment of interest and principal made at that maturity point on the curve. As such, the rate can directly provide the present value of a dollar received at these maturity points.
Let’s take a very simple example:
A yield curve with 3 points:
Year 1: 5%
Year 2: 6%
Year 3: 7%
This means if you invest $1:
The key point here is that the 2 and 3 year rates effectively represent a coupon paying security. In the 2 year rate, $1 invested now for two years represents the combined PV of two cash flows. But what is the PV of just the second cash flow? If we can work this out, we’ll have a zero (or discount) rate at 2 years, enabling us to PV any money received 2 years in the future.
Deriving Zero curves
We know the PV of $1 received at the end of the first year using our basic time value of money formula:
PV = \frac{FV}{(1 + r)^n} = \frac{1}{(1 + .05)^1} = \frac{1}{1.05}This is effectively the 1 year discount factor. So any monies received at the end of 1 year can be multiplied by this to get the PV. Building (or “bootstrapping”) the zero curve is obtaining these discount factors for all maturity points.
To get the zero rate, or discount factor, for the 2 year point, we can say that $1 invested today will equal the PV of 1st payment plus the PV of 2nd payment. So:
PV = 1 = (\frac{.06}{1.05}) + (\frac{1.06}{(1+r)^2})(where r equals the 2 year discount factor)
Working this out, we end up with:
r_{\tiny{Z2}}=.0603or 6.03%
For the 3rd year zero rate, we build on the above:
PV = 1 = (\frac{.07}{1.05}) + (\frac{.07}{(1+.0603)^2}) + (\frac{1.07}{(1+r)^3})(where r equals the 3 year discount factor)
This gives us:
r_{\tiny{Z3}}=.07097or 7.097%
Now we have our zero curve that we can used as discount rates for cash flows at the corresponding
maturities.
So the corresponding zero curve:
Year 1: 5%
Year 2: 6.03%
Year 3: 7.097%
An observation
It’s interesting to note that the zero rates are slightly higher than the yield curve rates when the curve is sloping upwards. If you have trouble seeing why think of an extreme case of a yield curve with 0% rate in year 1 and 100% rate in year 2.
Implied forward rates
Another concept worth touching on here are the implied forward rates from these zero rates. Let’s say we invest $1 for 2 years under our zero rate, which is 6.03%. This would give us a return of:
FV = 1 * (1 + .0603)^2 = 1.124236We could also have invested for 1 year, then take that return and lock in a forward rate for the second year (the rate at the end of year 1 for investing for year 2). Under the rules of arbitrage, this forward rate for year 2 needs to give us the same return as investing for 2 years using the 2 year zero rate. So:
FV = 1.124236 = 1.05 * (1 + r_{\tiny{1,2}})where r_{\tiny{1,2}} is the forward rate for the second year
This gives an implied forward rate r_{\tiny{1,2}} = .070707 = 7.07%
You can keep building these implied forward rates for all future years using this technique.
One of the (many) aspects of the “Mathematical Constant” e is that:
\lim_{x\to\infty} (1+\frac{1}{x})^x = eThis property makes e very useful for working on compounding interest problems. How so?
Let’s start with the basic time value of money formula giving the relationship between the PV (present value) and FV (future value) given R (the rate of interest):
FV = PV * (1 + R)^nIn the formula above n represents the number of compounding periods. Given normal conventions, this is typical represented as m * Y where m is months (or other periods – it represents how many chunks we divide the year into for receiving interest payments) and Y is years. Also, the R (or rate) above is normally quoted in years, so we should divide this by the months: R/m.
So now we have:
FV = PV * (1 + \frac{R}{m})^{mY}We can make use of the e formula above if we want continuously compounding interest – that is where m is as high as possible, converging on \infty.
Let’s start by making x=\frac{m}{R} and we would get:
FV = PV * (1 + \frac{1}{x})^{x * YR}We can now drop this into our formula for e given that we want m (or x, which is effectively our proxy for m) to approach \infty:
FV = PV * [\lim_{x\to\infty} (1+\frac{1}{x})^{x}]^{RY}We can write this simply as:
FV = PV * e^{RY}So if we invest $100 at 6.5% continuously compounding interest for a year, we will end up with:
FV = 100 * e^{.065*1} FV = \$106.72A really simple problem, but needs a trick or two to solve quickly.
Question: You take it in turns tossing a coin with a friend – you having the first toss – and keep going until one of you tosses heads and wins. What are the chances you’re the winner?
Answer: The chances of me winning are the sum of my chances at each toss which is: 1/2 + 1/8 + 1/32… The chances of my friend winning are 1/4 + 1/16 + 1/64…
It may be immediately obvious to you that I’ll have twice my friend’s chances of winning. So that would mean I have a 2/3 chance, and my friend a 1/3 chance.
Let’s also think about this in terms of geometric progressions. First, some basics:
when r<1:
\sum_{n=0}^\infty cr^n = \frac{c}{1-r}
and:
\sum_{n=1}^\infty cr^{n-1} = \frac{c}{1-r}
So if you can get your progression into one of the two forms above, you can just apply the formula on the right hand side.
Now start looking at this from the point of view of the guy starting second. His first toss has a probability of \small(1/2)^2, his second toss \small(1/2)^4, his third \small(1/2)^6. So we can see that on his nth toss, his probability will be \small(1/2)^{2n} with n starting at 1.
We see from the above formulas that when we have n starting at 1 we need to get our progression into the form: {\small}cr^{n-1}. So we need to expand as such: (\frac{1}{2})^{2n} = (\frac{1}{4})^n = \frac{1}{4} * (\frac{1}{4})^{n-1}. Now we have c=1/4 and r=1/4 to plug in: \frac{c}{1-r} = \frac{\frac{1}{4}} {1 - \frac{1}{4}} = \frac{1}{3}.
So of course, since someone has to win, the probability for the starter is 2/3. But let’s work this out. The starter’s probability at toss n is \small(1/2)^{2n+1} with n starting at 0. Since n starts at 0, we need to get this into the form: {\small}cr^{n}. Expanding as above: (\frac{1}{2})^{2n+1} = \frac{1}{2} * (\frac{1}{4})^{n}. Now we have c=1/2 and r=1/4 to plug in: \frac{c}{1-r} = \frac{\frac{1}{2}} {1 - \frac{1}{4}} = \frac{2}{3}.
This is an interesting puzzle in that it shows a basic technique used in solving these kinds of probability puzzles, as well as in models for some derivatives pricing, without the need for conditional probability calculations. Hint: start with the last event where we know the expected winnings, and work backwards.
Question: It’s your birthday, and a generous uncle tells you that he’ll give you in dollars whatever number comes up when you roll a die – so you will win between $1 and $6. He makes it more interesting – if you don’t like what you roll the first time, you can roll again. And if you don’t like that, you can roll one more time – for a maximum of three rolls. Note that if you choose to throw again, you can’t go back to an earlier better roll. What’s your strategy to maximize your winnings?
Answer: The trick here is to realize that on the third roll (if you get that far) you’re really stuck with whatever comes up, and that on average on your third roll you’ll win $3.50. So on your second roll, you should stick with anything 4 or higher, anything less you go on to the third roll. So, on average, your winnings on the second roll are ($6 + $5 + $4 + $3.50 + $3.50 + $3.50)/6 which equals $4.25. So then on your first roll, you should stick with a 5 or a 6, but go on to your second roll with anything less. On average, your winnings overall if you stick with this strategy will be ($6 + $5 + $4.25 + $4.25 + $4.25 + $4.25) /6 which equals $4.67.
1. I have two children. One of my children is a girl. What are the chances I have two girls?
The answer to this question is not 50/50. After being told that one of your children is a girl, you know there are 3 options (with equal probability each): GB, BG & GG. So the answer is a 1/3 chance. Counterintuitive perhaps because people assume the question has stated that the first child is a girl – in which case it would be 50/50.
2. There is a sixgun with two bullets in consecutive chambers pointed at your head. The bad guy spins it, then pulls the trigger. It clicks on an empty chamber. He then tells you that you have a choice: he pulls the trigger again or spins it first before pulling the trigger. Which to choose?
My immediate intuition was to spin again – it would seem that if you were lucky enough for it not to fire once, you’re pushing your luck pulling the trigger again straight away. But now let’s think about it.
The probability of getting shot if you spin again is clearly 2/6, or 1/3. What if you don’t spin? The only way you’re going to get shot is if the you had landed on the one empty chamber just before the bullets – a 1/4 chance. So, perhaps counterintuitively, you’re better off just having the trigger pulled again with no spin.
3. OK, this is a really hoary old chestnut – the Monty Hall problem. You’re at a game show, and the host tells you the car is behind one of the three closed doors – and to choose a door. Before he opens your chosen door, he opens one of the two remaining doors that he tells you he knows the car is not behind, and then gives you the choice of sticking with your original pick or switching to the other unopened door. Which do you do?
It’s not 50/50, even though there’s two doors left (although the probability across both equals 1). There’s many ways to think about it, but to me the one that makes the most sense is that no matter what, the probability that you picked the door in the first place remains 1 in 3. So if you were to pick out of a million doors, the host opening 1 million minus 2 doors leaving your pick and one remaining unopened door doesn’t suddenly up your chances of having picked the door from 1 in a million to 1 in 2. In the 3 door case, if your pick still has a 1/3 chance of having the car, the other door must have a 2/3 chance – so you in effect double your chances by switching doors.
The last problem in the Trees chapter of Programming Interviews Exposed was about finding the lowest common ancestor between two nodes of a binary search tree. Starting from the head, if you find that the nodes that you’re looking for straddle the node you’re on, then you’ve found your lowest common ancestor. If they’re both on one side or the other, grab your child on that side, and recurse. The key is realizing that when you go left (for example) there will be no result on the left branch bigger than the right’s universe.
def commonAncestor(node1,node2,head):
"""
>>> node1=Node(1)
>>> node4=Node(4)
>>> node3=Node(3,node1,node4)
>>> node7=Node(7)
>>> node5=Node(5,node3,node7)
>>> commonAncestor(node1,node7,node5).value
5
>>> commonAncestor(node7,node1,node5).value
5
>>> commonAncestor(node1,node5,node5).value
5
>>> commonAncestor(node1,node4,node5).value
3
>>> commonAncestor(node7,node7,node5).value
7
"""
maxNode=max([node1,node2], key=lambda item: item.value)
minNode=min([node1,node2], key=lambda item: item.value)
if head==None: return
if (minNode.value <= head.value) & (maxNode.value >= head.value):
return head
if (minNode.value <= head.value) & (maxNode.value <= head.value):
return commonAncestor(node1,node2,head.left)
if (minNode.value >= head.value) & (maxNode.value >=head.value):
return commonAncestor(minNode,maxNode,head.right)
class Node:
def __init__(self,value,left=None,right=None):
self.value=value
self.left=left
self.right=right
import doctest
doctest.testmod()
Another question posed in the Programming Interviews Exposed book. A pre-ordered traversal of a binary tree (counterclockwise starting at root, printing nodes as you encounter them) is pretty straight forward, and a very natural thing to implement with recursion:
def traverse(node):
"""
>>> node1=Node(1)
>>> node2=Node(2)
>>> node3=Node(3,node1,node2)
>>> node4=Node(4)
>>> node5=Node(5,node3,node4)
>>> traverse(node5)
5
3
1
2
4
"""
if node==None: return
print node.value
traverse(node.left)
traverse(node.right)
class Node:
def __init__(self,value,left=None,right=None):
self.value=value;self.left=left;self.right=right
import doctest
doctest.testmod()
A little trickier is an implementation without recursion:
def treeWalker(node):
"""
>>> node1=Node(1)
>>> node2=Node(2)
>>> node3=Node(3,node1,node2)
>>> node4=Node(4)
>>> node5=Node(5,node3,node4)
>>> treeWalker(node5)
5
3
1
2
4
"""
lifo=[]
while True:
print node.value
if node.left!=None:
lifo.append(node)
node=node.left
else:
try:
node=lifo.pop()
except:
return None
node=node.right
class Node:
def __init__(self,value,left=None,right=None):
self.value=value;self.left=left;self.right=right
import doctest
doctest.testmod()
Another problem in the Programming Interviews Exposed book (see previous post) is to determine whether a Linked List is cyclic or not.
The most obvious way to do this is to iterate over the list, checking whether the next element is one that you’ve seen before. So as you get to an element, you sweep back from head to current.
def isAcyclic1(head):
"""
>>> e1=Element(1)
>>> e2=Element(2)
>>> e3=Element(3)
>>> e4=Element(4)
>>> e5=Element(5)
>>> e1.next=e2
>>> e2.next=e3
>>> e3.next=e4
>>> e4.next=e5
>>> isAcyclic1(e1)
True
>>> e5.next=e3
>>> isAcyclic1(e1)
False
>>> e5.next=e4
>>> isAcyclic1(e1)
False
>>> e5.next=e2
>>> isAcyclic1(e1)
False
"""
curr=head
while curr!=None:
sweeper=head
while sweeper!=curr:
if curr.next==sweeper:
return False
sweeper=sweeper.next
curr=curr.next
return True
class Element:
def __init__(self,data,next=None):
self.data=data
self.next=next
if __name__ == "__main__":
import doctest
doctest.testmod()
This is an O(n squared) solution. There’s a better way, of course. You start a fast pointer, skipping elements, which if acyclic will get to the end quickly. If cyclic, it will eventually trip over the slow pointer. It turns out to be an O(n) solution. Smart.
def isAcyclic(head):
"""
>>> e1=Element(1)
>>> e2=Element(2)
>>> e3=Element(3)
>>> e4=Element(4)
>>> e5=Element(5)
>>> e1.next=e2
>>> isAcyclic(e1)
True
>>> e2.next=e3
>>> e3.next=e4
>>> e4.next=e5
>>> isAcyclic(e1)
True
>>> e5.next=e3
>>> isAcyclic(e1)
False
>>> e5.next=e4
>>> isAcyclic(e1)
False
>>> e5.next=e2
>>> isAcyclic(e1)
False
"""
slow=head
fast=head
while fast!=None and fast.next!=None:
slow=slow.next
fast=fast.next.next
if (fast==slow):
return False
return True
class Element:
def __init__(self,data,next=None):
self.data=data
self.next=next
if __name__ == "__main__":
import doctest
doctest.testmod()