questions.py

def linkedlist1():
    """
    How do you reverse a singly linked list? How do you reverse a doubly linked list? Write a
    program to do the same.
    """
    
    class NodeSingle(object):
        def __init__(self, n,v):
            self.next = n
            self.value = v
            
    def print_list(start):
        tmp = start
        while tmp:
            print tmp.value
            tmp = tmp.next
    
    start = False
    tmp = False
    for v in (0,1,2,3,4,5,6,7,8,9):
        if not start:
            start = NodeSingle(None,v)
            tmp = start
        else:
            tmp.next = NodeSingle(None,v)
            tmp = tmp.next
    print 'original:'
    print_list(start)
    
    def reverse_list_single_iter(start):
        tmp = start
        start = None
        while tmp:
            next = tmp.next
            tmp.next = start
            start = tmp
            tmp = next
        return start

    start = reverse_list_single_iter(start)
    print 'reversed iter:'
    print_list(start)
    
    def reverse_list_single_recursive(prev, node):
        if node:
            next = node.next
            node.next = prev
            return reverse_list_single_recursive(node, next)
        else:
            return prev
        
    start = reverse_list_single_recursive(None,start)   
    print 'reversed recursive:'
    print_list(start)    
    
    def print_list_with_links(start):
        tmp = start
        print 'value,prev,next:'
        while tmp:
            next = None
            prev = None
            if tmp.next:
                next = tmp.next.value
            if tmp.prev:
                prev = tmp.prev.value
            print tmp.value, prev, next
            tmp = tmp.next
    
    class NodeDouble(object):
        def __init__(self,p,n,v):
            self.next = n
            self.value = v
            self.prev = p

    start = False
    tmp = False
    prev = None
    for v in (0,1,2,3,4,5,6,7,8,9):
        if not start:
            start = NodeDouble(prev,None,v)
            tmp = start
        else:
            tmp.next = NodeDouble(prev,None,v)
            tmp = tmp.next
        prev = tmp
    print 'original:'
    print_list_with_links(start)
    
    def reverse_list_double_iter(start):
        while True:
            tmp = start.next
            start.next = start.prev
            start.prev = tmp 
            if not tmp:
                break
            else:
                start = tmp
        return start
        
    start = reverse_list_double_iter(start)
    print 'reversed iter:'
    print_list_with_links(start)
    
    def reverse_list_double_recursive(node):
        next = node.next
        node.next = node.prev
        node.prev = next
        if next:
            return reverse_list_double_recursive(next)
        else:
            return node
        
    start = reverse_list_double_recursive(start)   
    print 'reversed recursive:'
    print_list_with_links(start)
    
    pass
def strings():
    """
    Reverse a string
    """
    def reverse(s,pos=0):
        s = list(s)
        tmp = s[pos]
        s[pos] = s[len(s)-pos-1]
        s[len(s)-pos-1] = tmp
        pos+=1
        if pos >= len(s)/2:
            return ''.join(s)
        return reverse(s,pos)
    print reverse('hola como estas')
        
def graphs():
    """
    find longest path from X node, max depth from X node, deepst node from x node, all paths
    
    """
    graphA = {'1' : ['2','3'],
              '2' : ['1','4','5'],
              '3' : ['1'],
              '4' : ['2','6','7'],
              '5' : ['2','8'],
              '6' : ['4'],
              '7' : ['4','9','a'],
              '8' : ['5','b'],
              '9' : ['7'],
              'a' : ['7'],
              'b' : ['8']
    }
    """ *all links are bidirectional
          1
         / \
        2   3
       / \
      4   5
     / \   \
    6   7   8
       / \   \
      9   a   b
    """
    
    graphB ={'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D', 'B'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']
            }
    """  *this graph has unidirectional links
          A
         / \
        B - C
         \ / \
          D   F
             /
            E
    """
    def longestPath(graph,start, path=[]):
        nodes = {}
        path=path+[start]
        for node in graph[start]:
            if node not in path:
                deepestNode,maxdepth,maxpath = longestPath(graph,node,path)
                nodes[node] = (deepestNode,maxdepth,maxpath)
        maxdepth = -1
        deepestNode = start
        maxpath = []
        for k,v in nodes.iteritems():
            if v[1] > maxdepth:
                deepestNode = v[0]
                maxdepth = v[1]
                maxpath = v[2]
        return deepestNode,maxdepth +1,maxpath+[start]
    print longestPath(graphB,'A')
    
if __name__ == '__main__':
    graphs()