https://github.com/buy/cc150 https://github.com/kdn251/interviews/tree/master/CrackingTheCodingInterview
In [1]:
# Tree with defaultdict
# from collections import defaultdict
# def tree():
# return defaultdict(tree)
# users = tree()
# users['cindy']['username'] = 'cindy.lxr'
# def add(t, path):
# for node in path:
# t = t[node]
# add(users, ['left', 'right'])
In [2]:
from collections import defaultdict
In [3]:
class Node:
def __init__(self,data):
self.data = data
self.children = defaultdict(Node)
In [ ]:
In [12]:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def add_left(self, data):
self.left = Node(data)
def add_right(self, data):
self.right = Node(data)
In [16]:
node1 = Node(3)
node1.add_left(2)
node1.add_right(5)
node1.left.add_left(1)
In [109]:
def inOrderTraverse(n):
if BT[n]:
if BT[n]['left']:
inOrderTraverse(BT[n]['left'])
print(n)
if BT[n]['right']:
inOrderTraverse(BT[n]['right'])
In [110]:
BT = defaultdict(lambda: {'left': None, 'right': None})
In [111]:
BT[10]['left'] = 5
BT[5]['left'] = 3
BT[5]['right'] = 7
BT[10]['right'] = 20
BT[20]['right'] = 30
In [112]:
inOrderTraverse(10)
In [113]:
def preOrderTraverse(n):
if BT[n]:
print(n)
if BT[n]['left']:
preOrderTraverse(BT[n]['left'])
if BT[n]['right']:
preOrderTraverse(BT[n]['right'])
In [114]:
preOrderTraverse(10)
In [ ]:
In [17]:
def inOrderTraverse(node):
if node:
inOrderTraverse(node.left)
print(node.data)
inOrderTraverse(node.right)
In [18]:
inOrderTraverse(node1)
In [19]:
def preOrderTraverse(node):
if node:
print(node.data)
preOrderTraverse(node.left)
preOrderTraverse(node.right)
In [20]:
preOrderTraverse(node1)
In [21]:
def postOrderTraverse(node):
if node:
postOrderTraverse(node.left)
postOrderTraverse(node.right)
print(node.data)
In [22]:
postOrderTraverse(node1)
In [23]:
class Node:
def __int__(self, data):
self.data = data
self.children = defaultdict(Node)
class Graph:
def __int__(self):
self.nodes = []
def addNode(self, node):
self.nodes.append(node)
In [40]:
adjacencyMatrix = defaultdict(lambda: defaultdict(bool))
In [41]:
for (k, v) in [
(1, 3),
(2, 3),
(1, 6),
(6, 2)
]:
adjacencyMatrix[k][v] = True
adjacencyMatrix[v][k] = True
In [42]:
adjacencyMatrix[2]
Out[42]:
In [ ]:
In [43]:
adjacencyMatrix[0][1]
Out[43]:
In [55]:
from collections import deque
In [64]:
def hasRoute(adjacencyMatrix, a, b):
visited = defaultdict(bool)
visited[a] = True
q = deque()
q.append(a)
while len(q) > 0:
r = q.popleft()
if r == b:
return True
for n in adjacencyMatrix[r].keys():
if not visited[n]:
visited[n] = True
q.append(n)
return False
In [77]:
adjacencyMatrix = defaultdict(lambda: defaultdict(bool))
for (k, v) in [
(0, 1),
(0, 5),
(0, 4),
(1, 3),
(1, 4),
(2, 1),
(3, 2),
(3, 4)
]:
adjacencyMatrix[k][v] = True
5 <-- 0 --> 1 <-- 2
↘ ↓ ↘ ↑
4 <-- 3
In [82]:
for (a, b) in [
(2, 5),
(0, 5),
(5, 0),
(4, 5),
(0, 3),
(3, 0)
]:
print("({}, {}) => {}".format(a, b, hasRoute(adjacencyMatrix, a, b)))
In [119]:
mylist = [n for n in range(4, 17)]
In [120]:
mylist
Out[120]:
In [121]:
def minBST(mylist):
def createMinBST(mylist, start, end):
if end < start:
return None
mid = (start + end) // 2
In [123]:
3//2
Out[123]:
In [49]:
class Node(object):
def __init__(self, data=None):
self.data = data
self.left = None
self.right = None
def add_left(self, data):
self.left = Node(data)
def add_right(self, data):
self.right = Node(data)
In [46]:
def getHeight(node):
if node is None:
return 0
return 1 + max(getHeight(node.left), getHeight(node.right))
def isBalanced(node):
if node is None:
return True
if abs(getHeight(node.left) - getHeight(node.right)) > 1:
return False
return isBalanced(node.left) and isBalanced(node.right)
In [54]:
root = Node('root')
root.left = Node("left")
root.right = Node("right")
root.left.left = Node("left 2")
root.left.right = Node("left-right")
In [55]:
getHeight(root)
Out[55]:
In [56]:
isBalanced(root)
Out[56]:
In [1]:
inputList = [[1,4], [1,5], [2,5], [3,6], [6,7]]
In [5]:
class Tree:
def __init__(self, root=None):
self.nodes = [root]
class Node:
def __init__(self, data=None):
self.data = data
self.left = None
self.right = None
def add_left(self, data):
self.left = Node(data)
def add_right(self, data):
self.right = Node(data)
In [6]:
myTree = Tree()
In [25]:
def Node(data=None):
return {
"data": data,
"children": defaultdict(Node)
}
In [26]:
myNode = Node(3)
In [29]:
myNode['children'][1] = 5
In [ ]:
In [ ]:
In [17]:
myTree = Tree()
In [18]:
Out[18]:
In [ ]:
In [8]:
inputDict
Out[8]:
In [ ]: