Tuesday, August 24th, 2010
Problem: Write a python function to calculate the shortest path given a start node (or vertex), an end node and a graph. Use Dijkstra's algorithm. Return the distance from the start node to the end node, as well as the path taken to get there.
The implementation ...
Posted in programming | 7 Comments »
Sunday, July 18th, 2010
I'd blogged previously about writing a python function to find out whether a linked list is acyclic or not - it's worth a read before tackling this one.
Problem: Given the head node of a cyclic (or circular) linked list, write a function to return the node that is at ...
Posted in programming | No Comments »
Sunday, June 1st, 2008
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 ...
Posted in programming | 1 Comment »
Sunday, June 1st, 2008
Further to my previous post, a simple binary search O(log n) algorithm:
[sourcecode language="python"]
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)
...
Posted in programming | No Comments »
Saturday, May 31st, 2008
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 ...
Posted in programming | 4 Comments »
Friday, May 30th, 2008
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 ...
Posted in programming | 1 Comment »
Friday, May 30th, 2008
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 ...
Posted in programming | No Comments »
Thursday, May 29th, 2008
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 ...
Posted in programming | 2 Comments »
Tuesday, May 27th, 2008
I like this Python LIFO implementation:
[sourcecode language="python"]
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()
...
Posted in programming | No Comments »