dp (min coins, ranking), graph(num shortest path)

kumaya · kumaya · commit 938824d12146 · 2019-04-16T22:11:14.000+05:30
diff --git a/TreeADT/check_full_binary_tree.py b/TreeADT/check_full_binary_tree.py
@@ -0,0 +1,36 @@
+class Node:
+    def __init__(self, key):
+        self.key = key
+        self.left = None
+        self.right = None
+
+def isFullTree(root):
+    if not root:
+        return True
+    if not root.left and not root.right:
+        return True
+    # if both subtree is not none
+    if root.left and root.right:
+        return isFullTree(root.left) and isFullTree(root.right)
+    return False
+
+if __name__ == '__main__':
+    root = Node(10)
+    root.left = Node(20)
+    root.right = Node(30)
+
+    root.left.right = Node(40)
+    root.left.left = Node(50)
+    root.right.left = Node(60)
+    root.right.right = Node(70)
+
+    root.left.left.left = Node(80)
+    root.left.left.right = Node(90)
+    root.left.right.left = Node(80)
+    root.left.right.right = Node(90)
+    root.right.left.left = Node(80)
+    root.right.left.right = Node(90)
+    root.right.right.left = Node(80)
+    root.right.right.right = Node(90)
+
+    print "Binary tree is full: ", isFullTree(root)
diff --git a/dynamic_prog/minCoins.py b/dynamic_prog/minCoins.py
@@ -0,0 +1,65 @@
+# Given an integer representing a given amount of change, write a
+# function to compute the total number of coins required to make
+# that amount of change. You can assume that there is always a
+# 1 coin
+
+from datetime import datetime
+
+
+def minCoinsRec(change, coins):
+    if change == 0:
+        return 0
+    tot_min_coins = 10000000
+    for coin in coins:
+        if change-coin >= 0:
+            this_min_coins = minCoinsRec(change-coin, coins)
+            if this_min_coins < tot_min_coins:
+                tot_min_coins = this_min_coins
+    return tot_min_coins + 1
+
+
+def minCoinsTopDownDP(change, coins, dp):
+    if change == 0:
+        return 0
+    if dp[change] != -1:
+        return dp[change]
+    tot_min_coins = 99999999
+    for coin in coins:
+        if change-coin >= 0:
+            this_min_coins = minCoinsTopDownDP(change - coin, coins, dp)
+            if this_min_coins < tot_min_coins:
+                tot_min_coins = this_min_coins
+    dp[change] = tot_min_coins + 1
+    return dp[change]
+
+
+def minCoinsBottomUpDP(change, coins, dp):
+    dp[0] = 0
+    for i in range(1, change+1):
+        for coin in coins:
+            if i-coin >= 0:
+                curr_min_coins = dp[i-coin] + 1
+                if curr_min_coins < dp[i]:
+                    dp[i] = curr_min_coins
+    return dp[change]
+
+
+if __name__ == '__main__':
+    coins = [1, 2, 5]
+    change = 31
+    s = datetime.now()
+    print "minimum coins with recursion: ", minCoinsRec(change, coins)
+    e = datetime.now()
+    print "total time taken using recursion: ", e-s
+
+    dp = [-1] * (change+1)
+    s = datetime.now()
+    print "minimum coins with top down dp: ", minCoinsTopDownDP(change, coins, dp)
+    e = datetime.now()
+    print "total time taken using top down dp: ", e - s
+
+    dp = [99999999] * (change+1)
+    s = datetime.now()
+    print "minimum coins with bottom up dp: ", minCoinsBottomUpDP(change, coins, dp)
+    e = datetime.now()
+    print "total time taken using bottom up dp: ", e - s
diff --git a/dynamic_prog/ranking.py b/dynamic_prog/ranking.py
@@ -0,0 +1,37 @@
+# MegaCorp wants to give bonuses to its employees based on how many lines of
+# codes they have written. They would like to give the smallest positive amount
+# to each worker consistent with the constraint that if a developer has written
+# more lines of code than their neighbor, they should receive more money.
+#
+# Given an array representing a line of seats of employees at MegaCorp,
+# determine how much each one should get paid.
+#
+# For example, given [10, 40, 200, 1000, 60, 30],
+# you should return [1, 2, 3, 4, 2, 1].
+
+
+def ranking(n, arr):
+    out = [1] * n
+    # pass 1 from left to right
+    for i in range(1, n):
+        if arr[i] > arr[i-1]:
+            out[i] = out[i-1] + 1
+    # pass 2 from right to left for correct ordering
+    for i in range(n-2, -1, -1):
+        if arr[i] > arr[i+1] and out[i] <= out[i+1]:
+            out[i] = out[i+1] + 1
+        # elif arr[i] == arr[i+1] and out[i] == out[i+1]:
+        #     out[i] = out[i + 1] + 1
+    return out
+
+
+if __name__ == '__main__':
+    n = 6
+    inp = [10, 40, 200, 1000, 60, 30]
+    out_arr = ranking(n, inp)
+    print out_arr
+    assert out_arr == [1, 2, 3, 4, 2, 1]
+
+    n = 10
+    inp = [9, 2, 3, 6, 5, 4, 3, 2, 2, 2]
+    print ranking(n, inp)
diff --git a/graph/numShortestPath.py b/graph/numShortestPath.py
@@ -0,0 +1,62 @@
+from collections import defaultdict
+
+
+class Graph(object):
+    def __init__(self, v):
+        self.vertices = v
+        self.graph = defaultdict(list)
+
+    def add_edge(self, u, v):
+        self.graph[u].append(v)
+
+    def bfs(self, src, dist, paths):
+        visited = [False] * self.vertices
+        # distance of any node from itself is 0
+        dist[src] = 0
+        # there is always 1 way to move from node to itself
+        paths[src] = 1
+
+        queue = list()
+        queue.append(src)
+        visited[src] = True
+
+        while queue:
+            curr = queue.pop(0)
+            for vertex in self.graph[curr]:
+                if not visited[vertex]:
+                    queue.append(vertex)
+                    visited[vertex] = True
+
+                # print curr, vertex, dist[curr], dist[vertex], queue
+                # new shortest path
+                if dist[vertex] > dist[curr] + 1:
+                    dist[vertex] = dist[curr] + 1
+                    paths[vertex] = paths[curr]
+                # another shortest path
+                elif dist[vertex] == dist[curr] + 1:
+                    paths[vertex] += 1
+        print dist
+        print paths
+
+    def num_shortest_path(self, src, dst):
+        dist = [1000000] * self.vertices
+        paths = [0] * self.vertices
+        g.bfs(src, dist, paths)
+        return paths[dst]
+
+
+if __name__ == '__main__':
+    g = Graph(7)
+    g.add_edge(0, 1)
+    g.add_edge(0, 2)
+    g.add_edge(1, 2)
+    g.add_edge(1, 3)
+    g.add_edge(2, 3)
+    g.add_edge(3, 4)
+    g.add_edge(3, 5)
+    g.add_edge(4, 6)
+    g.add_edge(5, 6)
+
+    src = 2
+    dst = 6
+    print("Number of shortest path from %d to %d = %d" % (src, dst, g.num_shortest_path(src, dst)))
diff --git a/minCoinsRequired.py b/minCoinsRequired.py
