Don't let the byte code bite you.

- 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

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.

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()
```

Tree is a non - linear Abstract Data Type.

Example of Tree:

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

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

A `root`

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

All participating elements that holds data are called nodes.

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

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]

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]

`G`

is called an ancestor of `K`

as it lies in the path from root to leaf [A, C, G]

`K`

is descensant of `G`

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

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.

- Skew Tree
- Left Skew tree
- Skew Tree
- Right Skew Tree

- Binary Tree
- Strict Binary tree
- Full Binary tree
- Complete Binary Tree

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

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

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

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

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
```

```
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__
```

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)
```

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
```

In [5]:

```
from IPython.display import IFrame
IFrame('http://podiff.com/pod/4', width='100%', height=950)
```

Out[5]:

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.

```
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
```

```
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.
```

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.

- 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 !

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)
```

In [71]:

```
from itertools import permutations, combinations
a = ['A', 'B', 'C', 'D', 'E']
print list(permutations(a, ))
```

In [1]:

```
# Using pure python
x = "haha wow chal gaya"
print " ".join(reversed(x.split(" ")))
```

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
```

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
```

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.

`__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()
```

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
```