The Amit Yadav Blog

Don't let the byte code bite you.

Unordered Singly Linked List implementation in Python

Unordered Singly Linked List implementation in Python¶

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.

Why Linked List?¶

Arrays can be used to store linear data of similar types, but arrays have following limitations.

  • The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
  • Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.
For example, in a system if we maintain a sorted list of IDs in an array id[].¶
id[] = [1000, 1010, 1050, 2000, 2040].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

Advantages over arrays¶

  • Dynamic size
  • Ease of insertion/deletion

Drawbacks:¶

  • Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
  • Extra memory space for a pointer is required with each element of the list.
In [1]:
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next_node = None

    def __str__(self):
        return "Node [%s]" % self.data if self.data else ""


class UnorderedSinglyLinkedList(object):
    def __init__(self):
        self.head = None

    def insert(self, data):
        node = Node(data)
        if self.head is not None:
            current = self.head
            self.head = node
            self.head.next_node = current
        else:
            self.head = node

    def delete(self, data):
        previous = None
        current = self.head
        while current is not None:
            if current.data == data:
                if previous is None:
                    if current.next_node is None:
                        del current
                        self.head = None  # because previous and next both are None
                        return True
                    else:
                        self.head = current.next_node
                else:
                    previous.next_node = current.next_node
                    del current
                    return True
            previous = current
            current = current.next_node
        return False

    def search(self, data):
        current = self.head
        if current is not None:
            while current.next_node is not None:
                if current.data == data:
                    return True
                else:
                    current = current.next_node
            if current.data == data:
                return True
        return False

    def __str__(self):
        if self.head is not None:
            current = self.head
            out = "UnorderedSinglyLinkedList [(HEAD) Node(%s)" % current.data
            while current.next_node is not None:
                current = current.next_node
                out += " ==> Node(%s)" % current.data
            out += " (TAIL)]"
            return out
        else:
            return "UnorderedSinglyLinkedList []"


if __name__ == '__main__':
    ull = UnorderedSinglyLinkedList()
    ull.insert(10)
    ull.insert(20)
    ull.insert(30)
    ull.insert(3)
    ull.insert(8)
    print ull
    print ull.search(37)
    ull.delete(8)
    print ull
    ull.delete(20)
    print ull
    ull.delete(10)
    print ull
    ull.delete(3)
    print ull
    ull.delete(30)
    print ull
UnorderedSinglyLinkedList [(HEAD) Node(8) ==> Node(3) ==> Node(30) ==> Node(20) ==> Node(10) (TAIL)]
False
UnorderedSinglyLinkedList [(HEAD) Node(3) ==> Node(30) ==> Node(20) ==> Node(10) (TAIL)]
UnorderedSinglyLinkedList [(HEAD) Node(3) ==> Node(30) ==> Node(10) (TAIL)]
UnorderedSinglyLinkedList [(HEAD) Node(3) ==> Node(30) (TAIL)]
UnorderedSinglyLinkedList [(HEAD) Node(30) (TAIL)]
UnorderedSinglyLinkedList []

Doubly Linked List Implementation in Python

Doubly Linked List implementation in python¶

A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Following are advantages/disadvantages of doubly linked list over singly linked list.¶

Advantages over singly linked list¶
  • A DLL can be traversed in both forward and backward direction.
  • The delete operation in DLL is more efficient if pointer to the node to be deleted is given. In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.
Disadvantages over singly linked list¶
  • Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though (See this and this).
  • All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.

Insertion¶

A node can be added in four ways

  • At the front of the DLL
  • After a given node.
  • At the end of the DLL
  • Before a given node.
In [2]:
class Node(object):
    def __init__(self, data):
        self.data = data
        self.previous_node = None
        self.next_node = None

    def __str__(self):
        return "Node [%s]" % self.data


class DoublyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_after(self, node, new_node):
        assert self.head and node and self.tail is not None
        if node.next_node is None:
            self.tail = new_node
        else:
            new_node.next_node = node.next_node
            node.next_node.previous_node = new_node
        node.next_node = new_node
        new_node.previous_node = node
        return new_node

    def insert_before(self, node, new_node):
        assert self.head and node and self.tail is not None
        if node.previous_node is None:
            self.head = new_node
        else:
            new_node.previous_node = node.previous_node
            node.previous_node.next_node = new_node
        new_node.next_node = node
        node.previous_node = new_node
        return new_node

    def prepend(self, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return self.head
        else:
            return self.insert_before(self.head, new_node)

    def append(self, new_node):
        if self.tail is None:
            return self.prepend(new_node)
        else:
            return self.insert_after(self.tail, new_node)

    def delete(self, node):
        # It assumes that `node` DO exists in DoublyLinkedList
        if node.previous_node is None:
            # Then this is head
            self.head = node.next_node
        else:
            node.previous_node.next_node = node.next_node

        if node.next_node is None:
            self.tail = node.previous_node
        else:
            node.next_node.previous_node = node.previous_node
        del node

    def __str__(self):
        if self.head and self.tail:
            current = self.head
            out = "DoublyLinkedList [(HEAD) Node(%s)" % current.data
            while current.next_node is not None:
                current = current.next_node
                out += " <==> Node(%s)" % current.data
            out += " (TAIL)]"
            return out
        else:
            return "DoublyLinkedList []"


if __name__ == '__main__':
    ddl = DoublyLinkedList()
    node_10 = ddl.append(Node(10))
    print ddl
    node_11 = ddl.append(Node(11))
    print ddl
    node_12 = ddl.append(Node(12))
    print ddl
    node_13 = ddl.prepend(Node(13))
    print ddl
    node_14 = ddl.append(Node(14))
    print ddl
    node_9 = ddl.insert_after(node_11, Node(9))
    print ddl
    ddl.delete(node_14)
    print ddl
    ddl.delete(node_13)
    print ddl
DoublyLinkedList [(HEAD) Node(10) (TAIL)]
DoublyLinkedList [(HEAD) Node(10) <==> Node(11) (TAIL)]
DoublyLinkedList [(HEAD) Node(10) <==> Node(11) <==> Node(12) (TAIL)]
DoublyLinkedList [(HEAD) Node(13) <==> Node(10) <==> Node(11) <==> Node(12) (TAIL)]
DoublyLinkedList [(HEAD) Node(13) <==> Node(10) <==> Node(11) <==> Node(12) <==> Node(14) (TAIL)]
DoublyLinkedList [(HEAD) Node(13) <==> Node(10) <==> Node(11) <==> Node(9) <==> Node(12) <==> Node(14) (TAIL)]
DoublyLinkedList [(HEAD) Node(13) <==> Node(10) <==> Node(11) <==> Node(9) <==> Node(12) (TAIL)]
DoublyLinkedList [(HEAD) Node(10) <==> Node(11) <==> Node(9) <==> Node(12) (TAIL)]

Design Patterns and Strategies

Design Patterns and Strategies¶

What this means?¶

  • Define a family of algorithms by encapsulating each algorithm such that they are interchangeable by the consumers that use them.
  • Abstraction is captured in interfaces, and the implementation goes in derieved classes

What problem does this solve?¶

Client are only meant to deal with the "the things done". They are not supposed to know what is going below the hood. Strategy provides us this concept i.e. encapsulate the concept in interface and put all the logic in derived classes. Client then can use only the interface and then they don't have to deal with changes in strategy or implementations.

A generic value of the software community for years has been, "maximize cohesion and minimize coupling". The object-oriented design approach shown in figure is all about minimizing coupling. Since the client is coupled only to an abstraction (i.e. a useful fiction), and not a particular realization of that abstraction, the client could be said to be practicing "abstract coupling" . an object-oriented variant of the more generic exhortation "minimize coupling".

A more popular characterization of this "abstract coupling" principle is "Program to an interface, not an implementation".

Clients should prefer the "additional level of indirection" that an interface (or an abstract base class) affords. The interface captures the abstraction (i.e. the "useful fiction") the client wants to exercise, and the implementations of that interface are effectively hidden.

Strategy in python¶

In [20]:
"""
Define a family of algorithms, encapsulate each one, and make them
interchangeable. Strategy lets the algorithm vary independently from
clients that use it.
"""

import abc


class Discount(object):
    """
    Define the interface of interest to clients.
    Maintain a reference to a Strategy object.
    """
    def __init__(self, strategy):
        self._strategy = strategy
        
    def get_discount(self):
        return self._strategy.get_discount()
        
    
class DiscountStrategy(object):
    """
    Declare an interface common to all supported algorithms. Context
    uses this interface to call the algorithm defined by a
    ConcreteStrategy.
    """
    __metaclass__ = abc.ABCMeta
    @abc.abstractmethod
    def get_discount(self):
        pass


class BuyTwoGetOneDiscountStrategy(DiscountStrategy):
    """
    Implement the algorithm using the Strategy interface.
    """

    def get_discount(self):
        return 10.00


class BuyTwoGetTwoDiscountStrategy(DiscountStrategy):
    """
    Implement the algorithm using the Strategy interface.
    """

    def get_discount(self):
        return 12.90
    

def main():
    strategy = BuyTwoGetTwoDiscountStrategy()
    discount = Discount(strategy)
    print discount.get_discount()


if __name__ == "__main__":
    main()
    
12.9

Trees

Trees¶

Tree is a non - linear Abstract Data Type.

Example of Tree:

           1    <-- root
         /   \
        2     3  <-- Nodes
       /  \ 
      4    5

Keywords in trees¶

  • Root
  • Nodes
  • Leaf
  • Height
  • Depth
  • Ancestors
  • Descendants
  • Level
  • Size

Referal Image of a Tree¶

Root¶

A root is the top node of any tree. It does not have any parent.

Nodes¶

All participating elements that holds data are called nodes.

Leaf¶

Leaf is the last node in the tree. It does not have any children

Height¶

The height of a node is the length of the path from that node to the deepest node.

  • A rooted tree with only one node has height zero
  • Height of B is 2 -> [B, F, J]

Depth¶

The depth of a node is the length of the path from the root to that node.

  • Depth of G is 2 -> [A, C, G]

Ancestors¶

G is called an ancestor of K as it lies in the path from root to leaf [A, C, G]

Descendants¶

K is descensant of G

Level¶

Set of all nodes at a given depth is called level of a tree.

  • [B, C, D] all are at same level 1
  • Root node is at level 0

Size¶

The size of a node is the number of descendants it has including itself.

Height of a tree is the maximum height among all the nodes and depth of the tree is the maximum depth among all the nodes. So for a given tree, depth and height return the same value, but for individual nodes we may get different results.

Types of Trees:¶

  • Skew Tree
    • Left Skew tree
    • Skew Tree
    • Right Skew Tree
  • Binary Tree
    • Strict Binary tree
    • Full Binary tree
    • Complete Binary Tree

Skew Tree¶

A tree is called a skew tree if every node has exactly one child node

Example of left skew tree¶

          1    <-- root
         /   
        2     
       /  
      4   

Example of right skew tree¶

          1    <-- root
           \
            2
             \
              3

Example of a skew tree¶

          1    <-- root
         /   
        2     
         \ 
          5
         /
        6

Binary Tree¶

A tree where each node has either 0, 1, or 2 children. A empty tree is also a valid binary tree.

Strict binary tree¶

A tree where each node has either 0, or 2 children

Full binary tree¶

Each node has exactly 2 children and all leaf nodes are at the same level

Complete binary tree¶

A tree is called a complete bainary tree if every level, except possibly the last, is completely filled and all nodes are as far as left as possible

Properties of a binary tree¶

For the following properties, let us assume that the height of the tree is h. Also assume that the root node is at height 0

  • The number of nodes in a full binary tree is 2^(h+1) - 1
  • Number of nodes at any level (h) is 2^h
  • Height of a tree = height of root node
In [ ]:
class Node(object):
    def __init__(self, data):
        self.right = None
        self.left = None
        self.data = data

Example of Binary Tree¶

           1    <-- root
         /   \
        2     3  
       /   
      4
In [2]:
class Node(object):
    def __init__(self, data):
        self.right = None
        self.left = None
        self.data = data
        
root = Node(1)
root.left = Node(2)
root.left = Node(3)

root.left.left = Node(4)
print root.__dict__
{'right': None, 'val': 1, 'left': <__main__.Node object at 0x10cadc9d0>}

Traversal¶

Tree example¶

        1
     /     \
    2        3
  /   \     /  \
 4    5    6    7 

1: Pre Order Traversaal

2: In Order Traversal

3: Post Order Traversal

Using recursion¶

In [ ]:
class Node(object):
    def __init__(self, data):
        self.right = None
        self.left = None
        self.data = data
        
    def __str__(self):
        return self.data
        
def preorder_traversal(root, result):
    if not root:
        return
    result.append(root.data)
    preorder_traversal(root.left, result)
    preorder_traversal(root.right, result)
    
def inorder_traversal(root, result):
    if not root:
        return
    preorder_traversal(root.left, result)
    result.append(root.data)
    preorder_traversal(root.right, result)
    
def postorder_traversal(root, result):
    if not root:
        return
    preorder_traversal(root.left, result)
    preorder_traversal(root.right, result)
    result.append(root.data)

    

Using iterative way¶

In [ ]:
class Node(object):
    def __init__(self, data):
        self.right = None
        self.left = None
        self.data = data
        
def preorder_traversal(root, result):
    if not root:
        return 
    stack = []
    stack.append(root)
    while stack:
        node = stack.pop()
        result.append(node.data)
        # Appending first right because, we know we will be poping the right most element
        # and we know the right most element should be left DLR
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
            
def inorder_traversal(root, result):
    if not root:
        return
    stack, node = [], root
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            result.append(node.data)
            node = node.right
            
def postorder_traversal(root, result):
    if not root:
        return 
    visited, stack, node = set(), [], root
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            if node.right and not node.right in visited():
                stack.appaned(node)
                node = node.right
            else:
                visited.add(node)
                result.append(node.data)
                node = None

Difference between Binary Tree and Binary Search Tree¶

In [5]:
from IPython.display import IFrame
IFrame('http://podiff.com/pod/4', width='100%', height=950)
Out[5]:

Find valid paths

Coding question

The diagram below represents 5 cities - A, B, C, D and E with roads connecting them. In some cases, there are two or more roads connecting two cities. Note that all the roads are bi-directional. A route is defined as a string of letters such that they have a road connecting 2 adjacent letters in the string. A valid route is one where the same path is not taken twice.

Some valid routes:

AB - Simplest route between A and B
ABDE - take one of the large loops between B and D
ABCDBCDBCDE - takes every line on the system exactly once

Some invalid routes:

ABA: the road connecting A and B is taken twice
ABE : There is no direct route from B to E
ABDBDE: There are only 2 valid direct routes between B and D, hence "BDBD" is not possible.


Image

Problem Statement

Write a program such that given a string of letters as input, it returns as output the following:

Line 1: "true" if the given string of letters describes a valid route and "false" if not.

Line 2: the total number of valid routes possible between the two end points of the string, without passing either of the end points more than once.

Note that even if the given route is invalid, you can still find the total number of valid routes between the end points. For example, ABE is an invalid route, but there are 2501 valid routes connecting A and E.

The input has to be received from STDIN and the output has to be written to STDOUT. Here are some sample inputs and their corresponding outputs.

Samples:

  • Sample INPUT 1:
    AB
  • Sample OUTPUT 1:
    true
    1
  • Sample INPUT 2:
    ABCDBCDBCDE
  • Sample OUTPUT 2:
    true
    2501
  • Sample INPUT 3:
    ABDBDE
  • Sample OUTPUT 3:
    false
    2501

Please note that the focus would be on how your solution works, approach is and how you design the solution to be optimal and performant.

All the best !

Answer

In [72]:
from collections import defaultdict

all_destination = ['A', 'B', 'C', 'D', 'E']
road_map = {
    'A': {
        'B': [1]
    },
    'B': {
        'A': [1],
        'C': [3, 5, 7],
        'D': [2, 9]
    },
    'C': {
        'B': [3, 5, 7],
        'D': [4, 6, 8]
    },
    'D': {
        'B': [2, 9],
        'C': [4, 6, 8],
        'E': [10]
    },
    'E': {
        'D': [10]
    }
}


class Path(object):
    def __init__(self):
        self.all_visited_roads_from_given_s_to_e = defaultdict(list)
        self.check_dict = defaultdict(list)

    @staticmethod
    def get_all_roads_that_connect_s_to_e(s, e):
        return list(road_map.get(s, {}).get(e, []))

    def visit_a_road(self, s, e, road):
        s_e_key = "%s%s" % (s, e)
        e_s_key = "%s%s" % (e, s)
        if road in self.all_visited_roads_from_given_s_to_e.get(s_e_key, []) or \
                        road in self.all_visited_roads_from_given_s_to_e.get(e_s_key, []):
            raise Exception("Can not visit an already visited road")
        else:
            self.all_visited_roads_from_given_s_to_e[s_e_key].append(road)
            self.check_dict[s_e_key].append(road)

    def is_valid_path(self, path):
        len_path = len(path)
        path_found = True
        for i in range(len_path):
            # checking for only one node passed
            if len_path == 1:
                raise Exception("Path value must be greater than 1")

            # Checking if element is last
            if i == len_path - 1:
                continue

            s, e = path[i], path[i + 1]
            s_to_e_possible_roads = self.get_all_roads_that_connect_s_to_e(s, e)

            retry = True
            while s_to_e_possible_roads and retry:
                try:
                    self.visit_a_road(s, e, s_to_e_possible_roads.pop())
                    retry = False
                except:
                    retry = True

            s_e_key = "%s%s" % (s, e,)
            if s_e_key not in self.check_dict.keys():
                path_found = False
                break
            else:
                self.check_dict.pop(s_e_key)
        return path_found


class FindPath(object):
    def __init__(self, s, e):
        self.start = s
        self.end = e
        self.all_possible_paths = []
        self.single_path = [self.start]

    def get_all_valid_paths_for_s_to_e(self):

        p = road_map.get(self.start)

        for np in p.keys():
            self.single_path.append(np)
            pp = "".join(self.single_path)
            if Path().is_valid_path(pp):
                if np == self.end:
                    self.all_possible_paths.append(pp)
                    self.single_path.pop()
                    continue
                self.start = np
                self.get_all_valid_paths_for_s_to_e()
            else:
                self.single_path.pop()
                continue


if __name__ == "__main__":
    try_times = int(raw_input())
    all_q_paths = []
    for i in range(try_times):
        my_path = raw_input()
        all_q_paths.append(my_path)

    for my_path in all_q_paths:
        if Path().is_valid_path(my_path):
            print my_path, 'true'
        else:
            print my_path, 'false'

        fp = FindPath(s=my_path[0], e=my_path[-1])
        fp.get_all_valid_paths_for_s_to_e()
        print 'all possible paths: ', set(fp.all_possible_paths)
1
ABC
ABC true
all possible paths:  set(['ABDC', 'ABC', 'ABDBC'])
In [71]:
from itertools import permutations, combinations
a = ['A', 'B', 'C', 'D', 'E']
print list(permutations(a, ))
first time
0
1
2
3
second time

Reverse indexes of all words in a given string

Reverse all words in a given string with using an extra array and without using any extra array.

Example:

  • input
    this is my string
  • output:
    string my is this

Write algo for both the cases

P.S. Dont use any python functions

Using pure python

In [1]:
# Using pure python
x = "haha wow chal gaya"
print " ".join(reversed(x.split(" ")))
gaya chal wow haha

Not using pure python and using an array

In [2]:
# Not using pure python
# Using an auxilliary space
x = "haha wow chal gaya"
s, e, arr = 0, 0, []

for i in range(len(x)):
    if x[i] == " ":
        e = i
        arr.append(x[s:e])
        s = i+1
    last = len(x) - 1
    if i == last:
        arr.append(x[e+1:])
            
my_str = ""
for i in xrange(len(arr)-1, -1, -1):
    my_str += arr[i] + " "

print my_str
gaya chal wow haha 

Not using pure python and also not using array

In [3]:
# Without using any auxilliary space
x = "my name is amit yadav"
s = ""
current_word = ""
for i in range(len(x)):
    current_word += x[i]
    if x[i] == " ":
        s = current_word + s
        current_word = ""
    last = len(x) - 1
    if i == last:
        s = current_word + " " + s
print s
yadav amit is name my 

Magic Functions in Python

Magic functions

Magic functions/methods starts with double underscore and ends with double underscore.

Some examples:

  • __init__()
  • __new__()
  • __len__()

and many more.

The whole list can be found here.

Difference between __init__() and __new__()

Use __new__ when you need to control the creation of a new instance. Use __init__ when you need to control initialization of a new instance.

__new__ is the first step of instance creation. It's called first, and is responsible for returning a new instance of your class. In contrast, __init__ doesn't return anything; it's only responsible for initializing the instance after it's been created.

In general, you shouldn't need to override __new__ unless you're subclassing an immutable type like str, int, unicode or tuple.

In [10]:
class Foo(object):
    def __init__(self):
        print "__init__ is called"

foo = Foo()
__init__ is called
In [14]:
class A(object):
    def __getattr__(self, att):
        """
        If your class defines a __getattr__() method, 
        Python will call it only after looking for the attribute in 
        all the normal places. If an instance x defines an attribute color, 
        x.color will not call x.__getattr__('color'); 
        it will simply return the already-defined value of x.color.
        """
        print '__getattr__ is called'

    def __getattribute__(self, att):
        """
        If your class defines a __getattribute__() method, 
        Python will call it on every reference to any attribute or method name 
        (except special method names, since that would cause an unpleasant infinite loop).
        """
        print '__getattribute__ is called'
        return super(A, self).__getattribute__(att)


a = A()
a.time = 'machine'
print a.time
print a.wow
__getattribute__ is called
machine
__getattribute__ is called
__getattr__ is called
None