Rebrained!

Puzzle – 4 Bugs chasing each other

Say there are four bugs standing at the corners of an imaginary 1m * 1m square.  Each of the bugs is facing the bug that is on the adjacent, clockwise corner from where they are.

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

Posted in puzzles | No Comments »

Puzzle – Liars and Truthtellers

This is another probability question that seems straightforward but can be deceptive…

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

Posted in puzzles | No Comments »

Puzzle – shortest road system

Let’s say you’re contracted to build roads to connect four towns that are at the corners of an imaginary square with sides 1 mile. What’s the shortest length of road system you can build so that every town can get to every other town?

Answer

Posted in puzzles | 2 Comments »

Puzzle – Clock

It’s 3 O’Clock. What will be the time when the minute and hour hands are next in the same position (coincident)?

Answer

Posted in puzzles | 5 Comments »

More puzzles…

A few more brainteasers..

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

Posted in puzzles | 2 Comments »

Dice puzzle – redux

I’d blogged previously about rolling a die and being given whatever you roll in dollars. You get given two more chances if you don’t like what you get the first time, or the second time, for a max of 3 rolls. What’s your strategy? You can see the answer in my previous post.

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.

Posted in puzzles | 2 Comments »

Mth to last – a recursive approach

A collegue of mine was pondering the mthToLast problem for a LinkedList I’d blogged about previously and sent me the following IM message:

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

Posted in programming | No Comments »

Reverse a string using recursion

Very basic – take a string and reverse it using simple recursion. I’m sure there’s a bunch of ways to do it, but like the fibonacci you should aim to be able to code this in about 30 seconds…

>>> def reverseString(str,loc=0):
	if loc>=len(str): return ''
	return reverseString(str,loc+1)+str[loc]

>>> reverseString("hello")
'olleh'

Ok, a little more interesting: let’s say we wanted to reverse the strings within words, but keep the words in the original order. An ugly implementation, again using recursion:

>>> def reverseWithinWords(str,loc=0):
	if loc>=len(str): return ('','')
	(revstr,revwords)=reverseWithinWords(str,loc+1)
	revstr=revstr+str[loc]
	if (str[loc]==" ")|(loc==0):
		revwords=revstr+' '+revwords
		revstr=''
	if loc==0: return revwords.strip()
	return (revstr,revwords)

>>> reverseWithinWords("hello my lovely")
'olleh ym  ylevol'

Here’s the punch line: given that, let’s say you were now asked to reverse the words, but keep the letter order the same – so for example “yes dark lord” becomes “lord dark yes”. What’s the quickest way to do this?
Answer

>>> reverseWithinWords(reverseString("yes dark lord"))
'lord dark  yes'
>>>

Posted in programming | No Comments »

Deep copy and recursive references

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.

Posted in programming | 1 Comment »

Bootstrapping Zero Curves

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.

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.

Posted in finance | 2 Comments »

The “Mathematical Constant” and Continuously Compouding Interest

One of the (many) aspects of the ”Mathematical Constant” is that:

This property makes 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):

In the formula above represents the number of compounding periods. Given normal conventions, this is typical represented as 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 (or rate) above is normally quoted in years, so we should divide this by the months: .

So now we have:

We can make use of the formula above if we want continuously compounding interest – that is where is as high as possible, converging on .

Let’s start by making and we would get:

We can now drop this into our formula for given that we want m (or x, which is effectively our proxy for m) to approach :

We can write this simply as:

So if we invest $100 at 6.5% continuously compounding interest for a year, we will end up with:

Posted in finance | No Comments »

Probability Puzzles…

Some probability questions/puzzles:

1. I have two children. One of my children is a girl. What are the chances I have two girls?
Answer

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?
Answer

3. I guess I have to put the old three door problem in here. 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?
Answer

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

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

Posted in puzzles | 5 Comments »

BinaryTree – Lowest Common Ancestor – Python

The last problem in the Trees chapter of Programming Interviews Exposed was about finding the lowest common ancestor between two nodes of a binary 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(node1,node5,node5).value
    5
    commonAncestor(node1,node4,node5).value
    3
    """
    if head==None: return
    if (node1.value<=head.value)&(node2.value>=head.value):
            return head
    if (node1.value<=head.value)&(node2.value<=head.value):
            return commonAncestor(node1,node2,head.left)
    if (node1.value>=head.value)&(node2.value>=head.value):
            return commonAncestor(node1,node2,head.right)

class Node:
    def __init__(self,value,left=None,right=None):
        self.value=value;self.left=left;self.right=right

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

Posted in programming | 1 Comment »

Binary Search – Python

Further to my previous post, a simple binary search O(log n) algorithm:

def binarySearch(node,value):
    """
    >>> node1=Node(1)
    >>> node4=Node(4)
    >>> node3=Node(3,node1,node4)
    >>> node7=Node(7)
    >>> node5=Node(5,node3,node7)
    >>> binarySearch(node5,4)
    5 3 4
    >>> binarySearch(node5,5)
    5
    """
    print node.value,
    if value==node.value: return
    if value<node.value:
        binarySearch(node.left,value)
    else:
        binarySearch(node.right,value)
    return None

class Node:
    def __init__(self,value,left=None,right=None):
    	self.value=value;self.left=left;self.right=right

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

Posted in programming | No Comments »

Tree Traversal – Python

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:

>>> class Node:
	def __init__(self,value,left=None,right=None):
		self.value=value;self.left=left;self.right=right

>>> node1=Node(1)
>>> node2=Node(2)
>>> node3=Node(3,node1,node2)
>>> node4=Node(4)
>>> node5=Node(5,node3,node4)

>>> def traverse(node):
	if node==None: return
	print node.value
	traverse(node.left)
	traverse(node.right)

>>> traverse(node5)
5
3
1
2
4
>>>

The trick is how to implement this without recursion – thinking caps on! Well, using a stack may be the best way (see earlier post), though it’s amazing how much more convoluted it gets. I’m sure it can be done more efficiently, though I like my algorithm better than the one in the book. Anyone have something better?

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=Lifo()
    while True:
        print node.value
        if node.left!=None:
            lifo.push(node)
            node=node.left
        else:
            node=lifo.pop()
            if node==None: return
            node=node.right

class Node:
    def __init__(self,value,left=None,right=None):
    	self.value=value;self.left=left;self.right=right

class Lifo:
    def __init__(self):
        self.lifo = ()
    def push(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        if len(self.lifo)==0: return None
        ret, self.lifo = self.lifo
        return ret

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

Posted in programming | 2 Comments »

Fibonacci – Python

Ok so if you’re interviewing for a programming job you have to be able to whip out a quick Fibonacci sequence at the drop of a hat, even if inelegant. This prints the fib series for n terms:

>>> def fib(n):
	a,b=0,1
	for i in range(n):
		print a,
		a,b=b,b+a

>>> fib(10)
0 1 1 2 3 5 8 13 21 34
>>>
>>>

There’s a recursive approach as well:

>>> def fib(n,a=0,b=1,counter=0):
	print a,
	if counter<(n-1): fib(n,b,a+b,counter+1)

>>> fib(10)
0 1 1 2 3 5 8 13 21 34
>>>

Python has a nice concept called iterators which can be used as well. Basically you implement an __iter__ method, and then code a next method, and then you can use your class in a for loop.

>>> class fib():
	def __init__(self):
		self.a,self.b=0,1
	def __iter__(self):
		return self
	def next(self):
		ret=self.a
		self.a,self.b=self.b,self.a+self.b
		return ret

>>> for i in fib():
	print i,
	if i>10: break

0 1 1 2 3 5 8 13
>>>

You can get the benefit of an iterator in Python without the __iter__ and next methods – you just have to invoke yield somewhere in your function and you have a Generator – which will generate an iterator.

>>> def fib(a=0,b=1):
	while True:
		yield a
		a,b=b,a+b

>>> fib=fib()
>>> for i in range(10): print fib.next(),

0 1 1 2 3 5 8 13 21 34
>>>

Here’s some recursion on steroids, generating the nth fib term (though starting at 1). Somewhat of a brainstretcher to think through what’s going on in this recursion though. And I think something like O(2^n) time.

>>> def fib(n):
	    if n<=1: return n
	    return fib(n-1)+fib(n-2)

>>> fib(10)
55

Anybody have another favorite fib implementation?

Posted in programming | No Comments »

More Linked Lists – Acyclic or not?

Another problem in the Programming Interviews Exposed book (see previous post) is to determine whether a Linked List is Acyclic 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

This is an O(n squared) solution. There’s a better way, of course, and here I’ll admit I needed a hint from the book. As soon as I saw something about fast and slow pointers it clicked – it’s quite a clever solution. 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 isAcyclic2(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
    >>> isAcyclic2(e1)
    True
    >>> e5.next=e3
    >>> isAcyclic2(e1)
    False
    >>> e5.next=e4
    >>> isAcyclic2(e1)
    False
    >>> e5.next=e2
    >>> isAcyclic2(e1)
    False
    """
    slow=head
    fast=head.next
    while fast!=None:
        if fast.next==None:
            return True
        if (fast==slow)|(fast.next==slow):
            return False
        fast=fast.next.next
        slow=slow.next
    return  True

Posted in programming | No Comments »

More on Linked Lists – flattening and unflattening

More from the Programming Interviews Exposed book (see last post). In this problem you take a double linked list (where each node knows its previous and next nodes) with child elements, and flatten it. Then unflatten it back to its original structure. It took me a few minutes to get the AHA moment around using recursion for unflattening.

class Node:
    def __init__(self,data,prev=None,next=None,child=None):
        self.data=data
        self.prev=prev
        self.next=next
        self.child=child

class ListFlattener:
    """
    >>> node1=Node(1)
    >>> node5=Node(5)
    >>> node1.child=node5
    >>> node2=Node(2)
    >>> node3=Node(3,node1,None,node2)
    >>> node1.next=node3
    >>> node4=Node(4,node2)
    >>> node2.next=node4
    >>> ListFlattener.listAsArray(node1)
    [1, 3]
    >>> ListFlattener.flattenList(node1)
    >>> ListFlattener.listAsArray(node1)
    [1, 3, 5, 2, 4]
    >>> ListFlattener.unflattenList(node1)
    >>> ListFlattener.listAsArray(node1)
    [1, 3]
    >>> ListFlattener.flattenList(node1)
    >>> ListFlattener.listAsArray(node1)
    [1, 3, 5, 2, 4]
    >>> ListFlattener.listAsArray(ListFlattener.findTail(node1),False)
    [4, 2, 5, 3, 1]
    """
    @staticmethod
    def flattenList(head):
        curr=head
        tail=ListFlattener.findTail(head)
        while curr!=None:
            if curr.child!=None:
                tail=ListFlattener.appendChildToEnd(curr,curr.child,tail)
            curr=curr.next

    @staticmethod
    def unflattenList(head):
        curr=head
        while curr!=None:
            if curr.child!=None:
                curr.child.prev.next=None
                curr.child.prev=None
                ListFlattener.unflattenList(curr.child)
            curr=curr.next

    @staticmethod
    def appendChildToEnd(node,child,tail):
        tail.next=child
        child.prev=tail
        return ListFlattener.findTail(child)

    @staticmethod
    def findTail(node):
        while node.next!=None:
            node=node.next
        return node

    @staticmethod
    def listAsArray(node,forward=True):
        list=[]
        while node!=None:
            list.append(node.data)
            if forward:
                node=node.next
            else:
                node=node.prev
        return list

Posted in programming | No Comments »

Linked List Interview questions…

I hadn’t done much programming for a while so I thought I’d brush up on some basic stuff. I bought Programming Interviews Exposed.

I did some of the Linked List stuff in the first section in Python. The code came out pretty close to the solutions in the book, though that was mainly in C++. I did like the problem of finding the Mth to last and needing to keep the lagging pointer – once you know it the answer is obvious, but it took a few minutes before it dawned on me.

class Stack:
    """
    Adapted from Programming Interviews Exposed problems
    LinkedList implementation that keeps track of head and tail

    Basic tests - push,pop,remove
    >>> s=Stack()
    >>> s.push(1)
    >>> s.push(2)
    >>> s.push(3)
    >>> s.push(4)
    >>> s.pop()
    4
    >>> e=s.head.next
    >>> s.remove(e)
    True
    >>> s.head.data
    3
    >>> s.tail.data
    1
    >>> e=s.head.next
    >>> s.remove(e)
    True
    >>> s.head.data
    3
    >>> s.tail.data
    3
    >>> e=s.head
    >>> s.remove(e)
    True
    >>> s.head
    >>> s.tail
    """

    def __init__(self):
        self.head=None
        self.tail=None

    def push(self,data):
        if self.head==None:
            self.head=Element(data,None)
            self.tail=self.head
        else:
            self.head=Element(data,self.head)

    def pop(self):
        oldhead=self.head
        if oldhead==None:
            return None
        self.head=oldhead.next
        if self.head==None:
            self.tail=None
        return oldhead.data

    def remove(self,element):
        if self.head==None:
            return False
        if self.head==element:
            self.head=self.head.next
            if self.head==None:
                self.tail=None
            return True
        curr=self.head
        while curr!=None:
            if curr.next==element:
                curr.next=curr.next.next
                if curr.next==None:
                    self.tail=curr
                return True
            else:
                curr=curr.next
        return False

    def insertAfter(self,element,data):
        """
        >>> s=Stack()
        >>> s.insertAfter(None,1)
        True
        >>> s.head.data
        1
        >>> s.tail.data
        1
        >>> s.insertAfter(None,2)
        True
        >>> s.head.data
        2
        >>> s.tail.data
        1
        >>> e=s.head
        >>> s.insertAfter(e,3)
        True
        >>> s.head.data
        2
        >>> s.tail.data
        1
        >>> s.head.next.data
        3
        >>> e=s.tail
        >>> s.insertAfter(e,4)
        True
        >>> s.head.data
        2
        >>> s.tail.data
        4
        """
        if (element==None)|(self.head==None):
            self.head=Element(data,self.head)
            if self.head.next==None:
                self.tail=self.head
            return True
        curr=self.head
        while curr!=None:
            if curr==element:
                curr.next=Element(data,curr.next)
                if curr.next.next==None:
                    self.tail=curr.next
                return True
            curr=curr.next
        return False

    def removeHead(self):
        """
        >>> s=Stack()
        >>> s.removeHead()
        >>> s.head
        >>> s.tail
        >>> s.push(1)
        >>> s.removeHead()
        >>> s.head
        >>> s.tail
        >>> s.push(1)
        >>> s.push(2)
        >>> s.removeHead()
        >>> s.head.data
        1
        >>> s.tail.data
        1
        """
        if self.head!=None:
            self.head=self.head.next
            if self.head==None:
                self.tail=None

    def findMToLastElement(self,m):
        """
        >>> s=Stack()
        >>> s.push(1)
        >>> s.push(2)
        >>> s.push(3)
        >>> s.findMToLastElement(1).data
        1
        >>> s.findMToLastElement(2).data
        2
        >>> s.findMToLastElement(3).data
        3
        >>> s.findMToLastElement(4)
        """
        mToLast=None
        curr=self.head
        count=0
        while curr!=None:
            count+=1
            if count==m:
                mToLast=self.head
            if count>m:
                mToLast=mToLast.next
                if mToLast==None:
                    return None
            curr=curr.next
        return mToLast

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

Posted in programming | No Comments »

Python – gotta love it

I’ve programmed in lots of languages (have on past occasion considered myself a Smalltalk, Java, Ruby… aficionado.) But I really like Python and the mindset of the community – a smart, no-nonsense efficiency. Something simple like unit testing – you can do it by having Python execute your docstrings, which you can cut and past straight from the shell. Nice!

<pre name="code" class="python:showcolumns">
def largestArrayCompareToMax(array):
    """
    Prints largest value in array by comparing to max - O(n) solution
    >>> largestArrayCompareToMax([1,5,9,2,4,6,8,3,7])
    9
    """
    max = array[0]
    for i in range(len(array)):
        if array[i] > max:
            max = array[i]
    print max

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

Posted in programming | 1 Comment »

Python LIFO implementation

I like this Python LIFO implementation – it’s very Pythonesque, using tuples (which are insanely fast to unpack, apparently.) I implemented a Lifo myself using some weird array thing which, after seeing this, I won’t post here…

class Lifo:
    """
    From http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436
    >>> lifo=Lifo()
    >>> lifo.append(1)
    >>> lifo.append(2)
    >>> print lifo.pop()
    2
    >>> print lifo.pop()
    1
    >>> print lifo.pop()
    Traceback (most recent call last):
        ...
    ValueError: need more than 0 values to unpack
    """
    def __init__(self):
        self.lifo = ()
    def append(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        # Use tuple unpacking - popping an empty Lifo will
        # raise a ValueError, which is OK
        ret, self.lifo = self.lifo
        return ret

Posted in programming | No Comments »

Weighing oranges

Posted in puzzles | 1 Comment »