import numpy
import math
def prime(upto=100):
    return filter(lambda num: (num % numpy.arange(2,1+int(math.sqrt(num)))).all(), range(2,upto+1))

>>> prime()
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>>

Similiar code that uses a for loop runs about 5 times longer for 100K primes, about 7 secs:

import numpy
import math
def prime2(upto=100):
    return filter(lambda num: numpy.array([num % factor for factor in range(2,1+int(math.sqrt(num)))]).all(), range(2,upto+1))

By not including even numbers, the original code can be optimized to run in half the time again, about .7 secs for 100K primes.

import numpy
import math
def prime3(upto=100):
    return [2]+filter(lambda num: (num % numpy.arange(3,1+int(math.sqrt(num)),2)).all(), range(3,upto+1,2))

The above code is not the fastest implementation, but illustrative of using the element-wise operations in Numpy arrays rather than looping through a list.

We can write faster code by breaking after finding the first modulo equal zero condition. The code below runs in about .4 seconds for 100K primes:

import numpy
import math
def prime4(upto=100):
    primes=[2]
    for num in range(3,upto+1,2):
        isprime=True
        for factor in range(3,1+int(math.sqrt(num)),2):
            if not num % factor: isprime=False; break
        if isprime: primes.append(num)
    return primes

Ok Scruffy Pete has laid down the challenge in the comments section so I need to get serious about optimization. The code below uses a few Numpy tricks for a zippy implementation and generates 1 million primes in about .03 secs, about 6X faster than Scruffy Pete’s.

import math
import numpy
def prime5(upto):
    primes=numpy.arange(2,upto+1)
    isprime=numpy.ones(upto-1,dtype=bool)
    for factor in primes[:int(math.sqrt(upto))]:
        if isprime[factor-2]: isprime[factor*2-2::factor]=0
    return primes[isprime]

Scruffy Pete… Ball’s in your court matey!

UPDATE 9/3 – did a half sieve style implementation of the above (see comments) which runs a little faster – under .02 secs for 1 million primes:

import math
import numpy
def prime6(upto):
    primes=numpy.arange(3,upto+1,2)
    isprime=numpy.ones((upto-1)/2,dtype=bool)
    for factor in primes[:int(math.sqrt(upto))]:
        if isprime[(factor-2)/2]: isprime[(factor*3-2)/2::factor]=0
    return numpy.insert(primes[isprime],0,2)

I posted this on the stack overflow site (see comments section). They run timings which you can see on:
http://ideone.com/oDg2Y

My impl is there listed under nolfonzo_prime6

The following code generates birthday samples for a given number of people, then works out the proportion of these samples that contain at least one shared birthday:

import numpy
def sharedbday1(people,simulations=50000):
    samples = numpy.random.random_integers(0,365, size=(simulations, people))
    hasnoshared=map(lambda x: len(x)==len(set(x)),samples)
    return 1-float(sum(hasnoshared))/simulations

Timing this in IPython on my laptop for 50k simulations takes about .5 secs to run:

In [579]: time sharedbday1(23)
CPU times: user 0.56 s, sys: 0.00 s, total: 0.56 s
Wall time: 0.56 s
Out[580]: 0.50678000000000001

Since we’re using Numpy, there’s a cleverer way to see if there’s a shared birthday in each sample. We can sort the array, then compare it element-wise against a slice of itself offset by one – if we find any equivalent elements we’ve found a sample with a shared birthday. With Numpy arrays this is achieved very neatly as operations in Numpy are performed element-wise by default:

import numpy
def sharedbday2(people, simulations=50000):
    samples = numpy.random.random_integers(0,365, size=(simulations, people))
    samples.sort()
    hasshared  = ((sample[1:]==sample[:-1]).any() for sample in samples)
    return float(sum(hasshared))/simulations

Unfortunately this runs at about half the speed of my original code:

In [582]: time sharedbday2(23)
CPU times: user 1.01 s, sys: 0.00 s, total: 1.01 s
Wall time: 1.02 s
Out[583]: 0.50988

I exchanged some emails with Travis Oliphant of Numpy fame, who suggested the following code which is really neat and I think shows off the power of Numpy in a simple and elegant way:

import numpy
def sharedbday3(people, simulations=50000):
    samples = numpy.random.random_integers(0,365, size=(simulations, people))
    samples.sort(axis=-1)
    hasshared = (samples[:,1:] == samples[:,:-1]).any(axis=-1)
    return float(sum(hasshared))/simulations

This is fast and shows a speed-up of least 5X on my original code – with a wall time of .09s:

In [585]: time sharedbday3(23)
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.09 s
Out[586]: 0.50119999999999998

As Travis explains it:
You create a 2-d array up-front with the simulations along one axis (i.e. every row of the 2-d array is a separate simulation). Then you can use the sample approach used above, but this time letting NumPy do the loop over the rows (down in C). The sort and any methods on NumPy arrays take an axis keyword which determines the dimension over which the operation works. The operation is then repeated implicitly over the other dimensions. So, in the 3rd version shared birthday there are no for loops. The penalty paid is memory usage: a 2-d array instead of throw-away 1-d arrays. But, of course, less memory management is also a major reason for the speed gain.

For completeness, I made some minor modifications to the original code above to simulate the probability that at least one person in a group shares your birthday (rather than of finding a shared birthday between them).

import numpy
def sharemybday(people,simulations=50000):
    mybday=0
    samples = numpy.random.random_integers(0,365, size=(simulations, people))
    hasshared=map(lambda x: mybday in x,samples)
    return float(sum(hasshared))/simulations

In [1509]: sharemybday(253)
Out[1509]: 0.50431999999999999

The implementation below sticks pretty closely to the algorithm description in the wikipedia entry, which I turned into something a little more pseudo-code-ish to help me implement it:

Initial state:

1. give nodes two properties – node.visited and node.distance
2. set node.distance = infinity for all nodes except the start node which is set to zero.
3. set node.visited = false for all nodes
4. set current node = start node.

Current node loop:

1. if current node = end node, finish and return current.distance & path
2. for all unvisited neighbors, calc their tentative distance (current.distance + edge to neighbor).
3. if tentative distance < neighbor's set distance, overwrite it.
4. set current.isvisited = true.
5. set current = remaining unvisited node with smallest node.distance

Here’s my implementation – it’s recursive, as suggested by the algorithm description:

import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
    """Find the shortest path between start and end nodes in a graph"""
    # we've found our end node, now find the path to it, and return
    if start==end:
        path=[]
        while end != None:
            path.append(end)
            end=predecessors.get(end,None)
        return distances[start], path[::-1]
    # detect if it's the first time through, set current distance to zero
    if not visited: distances[start]=0
    # process neighbors as per algorithm, keep track of predecessors
    for neighbor in graph[start]:
        if neighbor not in visited:
            neighbordist = distances.get(neighbor,sys.maxint)
            tentativedist = distances[start] + graph[start][neighbor]
            if tentativedist < neighbordist:
                distances[neighbor] = tentativedist
                predecessors[neighbor]=start
    # neighbors processed, now mark the current node as visited
    visited.append(start)
    # finds the closest unvisited node to the start
    unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited)
    closestnode = min(unvisiteds, key=unvisiteds.get)
    # now we can take the closest node and recurse, making it current
    return shortestpath(graph,closestnode,end,visited,distances,predecessors)

if __name__ == "__main__":
    graph = {'a': {'w': 14, 'x': 7, 'y': 9},
            'b': {'w': 9, 'z': 6},
            'w': {'a': 14, 'b': 9, 'y': 2},
            'x': {'a': 7, 'y': 10, 'z': 15},
            'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
            'z': {'b': 6, 'x': 15, 'y': 11}}
    print shortestpath(graph,'a','b')

    """
    Result:
        (20, ['a', 'y', 'w', 'b'])
        """

You’ll see I turned the example in wikipedia into a graph for the test case in the code above.

I found this useful about how to represent and process graphs in python: http://www.python.org/doc/essays/graphs.html. I think this was written by Guido himself.

There’s a bunch of interesting implementations on the web, including two here. More elegant, but it took me a while to understand them.

Problem: Given the head node of a cyclic (or circular) linked list, write a function to return the node that is at the start of the loop.

A cyclic linked list would look something like this:

A->B->C->D->E->F->C

In the case above, A is the head node, and C is the node at the start of the loop.

My Solution

Let’s call x the distance from the head to the start of the loop, and c the number of nodes in the loop.

We kick off a fast and a slow pointer from the head, with the fast pointer going twice as fast as the slow pointer (skipping every other node). By the time the slow pointer gets to the start of the loop, the fast pointer will have a head start of x (the fast pointer is always the same distance from the slow pointer as the slow pointer is from the head).

Given its head start of x, when will the fast pointer catch up to the slow pointer? The fast pointer always needs twice the initial distance from the slow pointer to catch up. Moving forward in the loop, the fast pointer is c-x nodes from the slow pointer, so it needs 2(c-x) nodes to catch up. In that time, the slow pointer will have managed to move c-x nodes away from the start (half what the fast pointer travelled).

The key thing to note here is that both pointers are now x nodes away from the start of the loop looking in a forwards direction. So you’ll see that to find the start of the loop the code below gets the fast and slow pointer to meet in the loop, then walks the slow pointer forward x nodes – the distance from the head to the start.

def startOfCyclicLoop(head):

    """
    >>> e1=Element(1)
    >>> e2=Element(2)
    >>> e3=Element(3)
    >>> e4=Element(4)
    >>> e5=Element(5)
    >>> e1.next=e2
    >>> print startOfCyclicLoop(e1)
    None
    >>> e2.next=e3
    >>> e3.next=e4
    >>> e4.next=e5
    >>> print startOfCyclicLoop(e1)
    None
    >>> e5.next=e3
    >>> print startOfCyclicLoop(e1)
    3
    >>> e5.next=e4
    >>> print startOfCyclicLoop(e1)
    4
    >>> e5.next=e2
    >>> print startOfCyclicLoop(e1)
    2
    """
    slow=head
    fast=head
    while fast!=None and fast.next!=None:
        slow=slow.next
        fast=fast.next.next
        if (fast==slow):
            slow=head
            while (fast!=slow):
                slow=slow.next
                fast=fast.next
            return fast
    return  None

class Element:
    def __init__(self,data,next=None):
        self.data=data
        self.next=next
    def __str__(self):
        return str(self.data)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

Answer

>>> for group in anagrams(['dog','cat','horse']):
...     print group
...
['dog', 'god']
['act', 'cat']
['horse', 'shoer', 'shore']

When called without a parameter, make the function return a list of all the anagram groups in the word dictionary, ordered by the group of anagrams with the most words:

>>> for group in anagrams():
...     if len(group)>6: print len(group), group
...
9 ['ester', 'estre', 'reest', 'reset', 'steer', 'stere', 'stree', 'terse', 'tsere']
9 ['angor', 'argon', 'goran', 'grano', 'groan', 'nagor', 'orang', 'organ', 'rogan']
9 ['caret', 'carte', 'cater', 'crate', 'creat', 'creta', 'react', 'recta', 'trace']
8 ['leapt', 'palet', 'patel', 'pelta', 'petal', 'plate', 'pleat', 'tepal']
8 ['laster', 'lastre', 'rastle', 'relast', 'resalt', 'salter', 'slater', 'stelar']
7 ['dater', 'derat', 'detar', 'drate', 'rated', 'trade', 'tread']
7 ['easting', 'gainset', 'genista', 'ingesta', 'seating', 'signate', 'teasing']
7 ['darter', 'dartre', 'redart', 'retard', 'retrad', 'tarred', 'trader']
7 ['least', 'setal', 'slate', 'stale', 'steal', 'stela', 'tales']
7 ['atle', 'laet', 'late', 'leat', 'tael', 'tale', 'teal']
7 ['alem', 'alme', 'lame', 'leam', 'male', 'meal', 'mela']
7 ['lapse', 'salep', 'saple', 'sepal', 'slape', 'spale', 'speal']
7 ['armet', 'mater', 'metra', 'ramet', 'tamer', 'terma', 'trame']
7 ['argel', 'ergal', 'garle', 'glare', 'lager', 'large', 'regal']
7 ['aldern', 'darnel', 'enlard', 'lander', 'lenard', 'randle', 'reland']
7 ['alert', 'alter', 'artel', 'later', 'ratel', 'taler', 'telar']
7 ['arist', 'astir', 'sitar', 'stair', 'stria', 'tarsi', 'tisar']
7 ['aril', 'lair', 'lari', 'liar', 'lira', 'rail', 'rial']
7 ['asteer', 'easter', 'reseat', 'saeter', 'seater', 'staree', 'teaser']
7 ['arpent', 'enrapt', 'entrap', 'panter', 'parent', 'pretan', 'trepan']
>>>

Can you think of an elegant (dare I say pythonic?) way to implement the anagrams function?

Here’s my attempt:

def anagrams(wordsin=None):
    f=open('/usr/share/dict/words')
    ana=dict()
    for word in f.readlines():
        ana.setdefault(''.join(sorted(word.rstrip())),[]).append(word.rstrip())
    if wordsin!=None:
        return [ana.get(''.join(sorted(wordin)),[]) for wordin in wordsin]
    else:
        return sorted(ana.values(), key=lambda(v): (len(v)),reverse=True)

How many people do you need in a room to have a better than 50% chance of finding at least one shared birthday among them?

Answer

How many people do you need in a room with you to have a better than 50% chance of finding someone who shares your birthday?

Answer

Answer

You take a bold approach and decide to wager your entire $10 on the first toss. You have a 50/50 chance of doubling your money, and whether you do or go bust will be determined on the first toss.

Would it have been better to take a more patient approach and only bet $1 on each toss?

Answer

Now let’s say you start with $10 and want to get to $20, but this time the coin is weighted in your favor and you have a 2/3 chance of rolling heads. Similarly, let’s say you’re betting on even/odd in roulette where you have an 18/38 chance – slightly less than half – of winning on each roll. In these cases, is it better to be a bold gambler or a patient gambler?

Answer

Answer

What if you started with $2 – what are the chances you’ll eventually go bust?

Answer

If you just had one egg with which to conduct your experiment, you’d have to start at floor one, and go up floor by floor looking for the first floor at which your egg broke until you reached floor 100. So your maxim number of drops would be 100.

What would be the worst case number of drops if you could use two eggs?

Answer

You play a game where you alternate tossing a coin with a friend, and the first person to toss heads wins. But let’s make it a little more interesting by making the coin weighted, or biased, so that it lands heads only 25% of the time. If you were to start, what would be your chances of winning?

Answer

Let’s call the probability of tossing heads and the probability of tossing tails .

On the starter’s first toss, his chances of tossing heads are . The chances he’ll toss heads on his second toss are . On his 4th toss it’s and so on.

So his chances of winning the game is the sum of the geometric progression …

Let’s use the shifting approach to solve this. The idea is to subtract out the first element, and then shift the rest of the elements to the left. So first subtract:
…

Now to shift the terms to the left, we need to divide by
…

So…

This gives us a general solution to the alternating coin toss problem. If we plug in the unweighted coin probabilities, we get which is what we’d worked out before. For the case where the probability of tossing a head is 1/4, then we get , which is the probability of winning for the starter.

Answer

Answer

Answer

At the same instant, each of the four bugs starts walking directly towards the bug they are facing at 1m per hour, and keeps walking directly towards that bug as that bug itself starts moving.  So the four bugs spiral towards the center of the square in a clockwise direction.

How long does it take for the four bugs to meet?

Answer

There’s a way to arrive at the answer to this problem instantly and with no calculations – but does require somewhat of an a-ha moment.

A-ha Moment Answer

What if the 3 bugs were in an equilateral triangles with sides 1m?

You’re an FBI agent and have been monitoring a large gang, and you know that 1/4 of its members always tell the truth, the rest always lie.  Then you get taken hostage by the gang, and two gang members are assigned to guard you.  You ask the first: ”Am I going to live?”  He answers “Yes.”  Then you ask the second the same question.  He also answers “Yes.”  What are your odds of living?

Answer

So – what would your chances of living be if the first guard told you that you would live, but the second that you would die?

Answer

Answer

Answer

Some of these are from Heard on the Street – a book of interview questions for Quants I’m trying to get through. Well worth a read if you’re into this sort of thing – or if you ever want to pretend you’re a Quant at parties (oh yeah, that will really attract the ladies!)

1. Two ropes of different lengths, and you know that if you were to light either of them at one end it burns through in an hour. How can use use them to measure 45 mins?
Answer

2. Two identical jugs, one with water, one with vodka. You pour a bit of vodka into the water, mix it, then pour the mix back to get the jugs to their original volumes. What’s the relationship between the new concentration of vodka in the vodka jug and water in the water jug?
Answer

3. Imagine you’re an ant (you can walk on walls but not fly) and you want to get from a bottom corner of a cubic room (1*1*1) to the extreme opposite corner (farthest from you). What’s your shortest path to get there?
Answer

4. Let’s say you have a bunch of 1*1*1 mini-cubes that you’ve assembled into a 10*10*10 big cube. Now let’s say the whole outer layer of the big cube becomes damaged and has to be replaced – how many new mini-cubes do you need?
Answer

5. Say there are 100 lights with switches (initially off), and 100 people. The first person goes through and flips every switch (so all the lights are on). The second person flips every second switch, so at this point half the lights are off again. The third person every third switch, and so on. By the time the 100th person goes through he just flips switch #100. At the end, how many light bulbs are turned on?
Answer

A couple of people have asked – what if there’s a pair of dice?

It’s the same principle. You could write all 36 permutations (but you’d live in fear you’ll be asked for a 3 dice solution). You know you can only roll a sum from 2 to a 12, and that you can get these sums from more than one combination of numbers on the dice.

You’ll see in the table below we again start by looking at the last throw. The expected payoff on the third throw is 7 (as you may have figured given the expected payoff for 1 die is 3.5). Following the same strategy as for the 1 die problem, for the second roll we pretend anything less than 7 is 7 for the purposes of figuring the expected payoff, which for roll 2 is 7.97. And so on for roll 1 which has an expected payoff of 8.54 (this is what you’d expect to win on average from this game).

So the strategy to maximize the expected payoff: on roll 1, stick with 8 or higher. On roll 2, stick with 7 or higher.

just a guess - but can you use  recursion to solve your link list m problem?
a method to track through the list which calls itself,
then when you get to the end start incrementing a counter,
and when it equals M return the value?

I think this is what he meant – it seems to work. Not as scalable as the trailing pointer approach in the previous post, but an interesting excerise in recursion. You find the size at the end, and return it all the way back. The code is a little messy with the 1 element case…anyone have a neater implementation?

class Element:
    def __init__(self,value,next=None):
        self.value=value
        self.next=next

def findMToLast(element,m,counter=1):
        """
        >>> e1=Element(1)
        >>> e2=Element(2)
        >>> e3=Element(3)
        >>> e4=Element(4)
        >>> e1.next=e2
        >>> e2.next=e3
        >>> e3.next=e4
        >>> findMToLast(e1,1).value
        4
        >>> findMToLast(e1,2).value
        3
        >>> findMToLast(e1,3).value
        2
        >>> findMToLast(e1,4).value
        1
        """
        if element.next==None:
            if m==1: mtolast=element
            else: mtolast=None
            if counter ==1: return mtolast
            return (counter,mtolast)
        (size,mtolast)=findMToLast(element.next,m,counter+1)
        if size-counter+1==m: mtolast=element
        if counter==1: return mtolast
        return (size,mtolast)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

>>> def reverse(str):
    if len(str)==1:
        return str
    else:
        return reverse(str[1:])+str[0]

>>> reverse('hello')
'olleh'
>>>

Without using recursion, the simplest way to reverse a string is to use the slice function:

>>> 'abcdef'[::-1]
'fedcba'
>>>

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.

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.

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:

• For 1 year, you’ll receive 5% interest plus your principal – $1.05 – at the end of year 1.
• For 2 years, you’ll get 6% annually, with your principal included at the end of year 2. So you will get $.06 at the end of year 1, and $1.06 at the end of year 2.
• For 3 years, you’ll get $.07 at the end of year 1, $.07 at the end of year 2 and $1.07 at the end of year 3.

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.

We know the PV of $1 received at the end of the first year using our basic time value of money formula:

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:

(where r equals the 2 year discount factor)

Working this out, we end up with or 6.03%

For the 3rd year zero rate, we build on the above:

(where r equals the 3 year discount factor)

This gives us or 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%

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 1 and 100% rate in year 2.

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:

We 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:

where is the forward rate for the second year

This gives an implied forward rate

You can keep building these implied forward rates for all future years using this technique.