The Amit Yadav Blog

Don't let the byte code bite you.

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