graph problems ctci

0 CTCI Graph problems.md

Graph problems ctci

build_order.py

# Find build order for related projects
class queue:

  def __init__(self):
    self.arr = []
  
  def enq(self, val):
    self.arr.append(val)
  
  def deq(self):
    return self.arr.pop(0)
  
  def printq(self):
    for i in self.arr:
      print(i, end=" ")
    print()
  
  def is_empty(self):
    return len(self.arr) == 0

class graph:

  def __init__(self, vertices):
    self.adj_list = {}
    self.incoming = {}
    for v in vertices:
      self.adj_list[v] = []
      self.incoming[v] = 0
    

  def add_edge(self, a, b):
    self.incoming[b] += 1
    self.adj_list[a].append(b)

def build_order(vertices, arr):
  g = graph(vertices)
  for s, e in arr:
    g.add_edge(s, e)
  print(g.adj_list)
  print(g.incoming)

  built = set() # init built
  q = queue()
  for k, v in g.incoming.items():
    if k in built:
      continue
    if v == 0:
      built.add(k)
      print(k, end=" ")
      for k in g.adj_list[k]:
        q.enq(k)
  
  while not q.is_empty():
    v = q.deq()
    if v in built:
      continue
    for j in g.adj_list[v]:
      q.enq(j)
    built.add(v)
    print(v, end=" ")
  print()

vertices = ['a', 'b', 'c', 'd', 'e', 'f']
arr = [('a','d'), ('f','b'), ('b', 'd'), ('f', 'a'), ('d', 'c')]
build_order(vertices, arr)

check_subtree.py

class queue:

  def __init__(self):
    self.arr = []
  
  def enq(self, val):
    self.arr.append(val)
  
  def deq(self):
    self.arr.pop(0)

from binarytree import build, bst, Node
from copy import deepcopy

arr = [5,6,7,12,23,27,31,44,56,65,99,100]
tree = bst(4, is_perfect=False)

t1 = tree
t2 = deepcopy(tree.left.right)
t2.left = Node(4)
print(t1, t2)

def match_tree(t1, t2):
  if not t1 and not t2:
    return True
  if t1 and t2:
    if t1.value == t2.value:
      return match_tree(t1.left, t2.left) and match_tree(t1.right, t2.right)
  return False


def check_subtree(t1, t2):
  if not t1:
    return False
  
  if t1.value == t2.value and match_tree(t1, t2):
    return True
  
  return check_subtree(t1.left, t2) or check_subtree(t1.right, t2)

print(check_subtree(t1, t2))

##########################################################################

from binarytree import bst, build, Node

t1 = build([3, 5, 67, 89, 10, 45, 67, 78, 56, 34])
t2 = build([10])
t2.right = Node(34)

print(t1, t2)

def pre_order(tree, result):
  if tree:
    pre_order(tree.left, result)
    pre_order(tree.right, result)
    result.append(str(tree.value))
  else:
    result.append('None')

pre_t1 = []
pre_order(t1, pre_t1)
print(pre_t1)
print()
pre_t2 = []
pre_order(t2, pre_t2)
print(pre_t2)

pre_t1 = " ".join(pre_t1)
pre_t2 = " ".join(pre_t2)

print(pre_t2 in pre_t1)

common_ancestor.py

class node:

  def __init__(self, val):
    self.val = val
    self.children = []
    self.parent = None

  def __repr__(self):
    return str(self.val)

def common_ancestor(n1, n2):
  it1 = n1 # find height of n1
  height1 = 0
  while it1.parent:
    it1 = it1.parent
    height1 += 1
  
  it2 = n2 # find height of n2
  height2 = 0
  while it2.parent:
    it2 = it2.parent
    height2 += 1

  if height1 < height2: # set greater height in n1
    height1, n1, height2, n2 = height2, n2, height1, n1
  
  diff = height1 - height2
  it1 = n1 # skip diff number of parents in tree
  while diff:
    it1 = it1.parent
    diff -= 1
  
  it2 = n2
  while it1.parent != it2.parent: # run up till common ancestor
    it1 = it1.parent
    it2 = it2.parent
  
  return it1.parent


node1 = node(1)
node2 = node(2)
node3 = node(3)
node4 = node(4)
node5 = node(5)
node6 = node(6)
node7 = node(7)
node8 = node(8)
node9 = node(9)
node10 = node(10)

node1.children = [node2, node10]
node2.parent = node10.parent = node1

node2.children = [node5, node3, node4]
node5.parent = node3.parent = node4.parent = node2

node5.children = [node6, node7, node8, node9]
node6.parent = node7.parent = node8.parent = node9.parent = node5

print(common_ancestor(node7, node10))

graph_traversals.py

from collections import deque

class Graph:

  def __init__(self, v):
    self.vertices = v
    self.adjlist = {}
    self.adjmatrix = []
    for i in range(self.vertices):
      self.adjlist[i] = []
      self.adjmatrix.append([0]*self.vertices)
      
  
  def add_edge(self, i, w):
    if i in self.adjlist:
      self.adjlist[i].append(w)
      self.adjmatrix[i][w] = 1
    else:
      print("Invalid vertex!", i)

  def dfs(self, start=0):
    visited = [False]*self.vertices
    stack = deque()
    stack.append(start)
    while len(stack) > 0:
      node = stack.pop()
      if visited[node]:
        continue
      visited[node] = True
      for i in self.adjlist[node]:
        stack.append(i)
      print(node, end="->")
    print()
  
  def bfs(self, start=0):
    visited = [False]*self.vertices
    queue = deque()
    queue.append(start)
    while len(queue) > 0:
      node = queue.popleft()
      if visited[node]:
        continue
      visited[node] = True
      for i in self.adjlist[node]:
        queue.append(i)
      print(node, end="->")
    print()


g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 0)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 2)
g.add_edge(3, 4)
g.add_edge(4, 3)

print(g.adjlist)
print(g.adjmatrix)
g.dfs(start=1)
g.bfs(start=1)

inorder_successor.py

class node:

  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    self.parent = None


def create_minimal(arr):
  n = len(arr)
  half = int(n/2)
  if half == 0:
    return node(arr[0])
  root = node(arr[half])
  # print(arr[:half], root.val, arr[half+1:])
  root.left = create_minimal(arr[:half])
  root.left.parent = root
  if half + 1 >= n:
    return root
  root.right = create_minimal(arr[half+1:])
  root.right.parent = root
  return root

def find_succ(n):
  if not n:
    return None
  
  if n.right:
    it = n.right
    while it.left:
      it = it.left
    return it.val 
  else:
    it = n
    p = it.parent
    while p and p.left != it:
      it = p
      p = p.parent
    return p.val
  

def inorder(bst):
  # pass
  if bst:
    inorder(bst.left)
    print(bst.val)
    inorder(bst.right)

def postorder(bst):
  # pass
  if bst:
    postorder(bst.left)
    postorder(bst.right)
    print(bst.val)

def preorder(bst):
  # pass
  if bst:
    print(bst.val)
    preorder(bst.left)
    preorder(bst.right)
    

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
# arr = [5, 6, 7, 12, 23, 31, 44, 56, 65, 99, 100]
bst = create_minimal(arr)
inorder(bst)
print()
n = bst.left.right
print(n.val, find_succ(n))

minmal_bst_from_sorted.py

class node:

  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None


def create_minimal(arr):
  n = len(arr)
  half = int(n/2)
  if half == 0:
    return node(arr[0])
  root = node(arr[half])
  # print(arr[:half], root.val, arr[half+1:])
  root.left = create_minimal(arr[:half])
  if half + 1 >= n:
    return root
  root.right = create_minimal(arr[half+1:])
  return root


def inorder(bst):
  # pass
  if bst:
    inorder(bst.left)
    print(bst.val)
    inorder(bst.right)

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
inorder(create_minimal(arr))

tree_class_random.py

from random import uniform

class tree:

  def __init__(self, val):
    self.val = val
    self.left = self.right = None
    self.size = 1
  
  def insert(self, val):
    if val < self.val:
      if self.left:
        self.left.insert(val)
      else:
        self.left = tree(val)
    else:
      if self.right:
        self.right.insert(val)
      else:
        self.right = tree(val)
    self.size += 1
  
  def printtree(self):
    print(self.val, self.size)
    if self.left:
      self.left.printtree()
    if self.right:
      self.right.printtree()

  # TODO
  def delete(self, val):
    print("Not implemented")
  
  def random_node(self):
   num = int(uniform(0, self.size))
   print(f"Getting {num}th node")
   return self._random_node(num)

  def _random_node(self, i):
    leftsize = self.left.size if self.left else 0
    if i == leftsize:
      return self.val
    if i < leftsize:
      return self.left._random_node(i)
    else:
      return self.right._random_node( i - (leftsize + 1) )


t = tree(3)
t.insert(5)
t.insert(67)
t.insert(89)
t.insert(10)
t.insert(78)
t.insert(56)
t.insert(34)
t.insert(45)
t.insert(57)

t.printtree()
print()
print(t.random_node())

tree_depth_to_ll.py

class node:

  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None


def create_minimal(arr):
  n = len(arr)
  half = int(n/2)
  if half == 0:
    return node(arr[0])
  root = node(arr[half])
  # print(arr[:half], root.val, arr[half+1:])
  root.left = create_minimal(arr[:half])
  if half + 1 >= n:
    return root
  root.right = create_minimal(arr[half+1:])
  return root


def inorder(bst):
  # pass
  if bst:
    inorder(bst.left)
    print(bst.val)
    inorder(bst.right)

class llnode:

  def __init__(self, val):
    self.val = val
    self.next = None

class llist:

  def __init__(self):
    self.head = None
    
  def add(self, val):
    if not self.head:
      self.head = llnode(val)
      return
    it = self.head
    while it.next:
      it = it.next
    it.next = llnode(val)
  
  def printll(self):
    it = self.head
    while it:
      print(it.val, end="->")
      it = it.next
    print()

def depth_to_ll(tree, llists, depth=0):
  if tree:
    if depth >= len(llists):
      llists.append(llist())
    depth_to_ll(tree.left, llists, depth + 1)
    llists[depth].add(tree.val)
    depth_to_ll(tree.right, llists, depth + 1)


arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 89, 109]
bst = create_minimal(arr)
llists = []
depth_to_ll(bst, llists)
for ll in llists:
  ll.printll()