Archive for May, 2008
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 »
Saturday, May 31st, 2008
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 ...
Posted in programming | No 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'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 ...
Posted in programming | 1 Comment »
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 »
Sunday, May 18th, 2008
The puzzle
You have 8 oranges - one is heavier than the others. How many weighings on a justice scale do you need to determine which one it is?
Answer
It's tempting to split the oranges in the middle, and weigh 4 and 4, which would take 3 weighings. But you ...
Posted in puzzles | 1 Comment »