Don't let the byte code bite you.

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.

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.

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

- Dynamic size
- Ease of insertion/deletion

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

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.

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

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

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

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