Daily Archives: October 31, 2021

python coding question

Substring Subset Permutation Combination


# O(n^3)
import itertools

def substring(s):
    substrings = []
    for i in range(len(s)):
        for j in range(i + 1, len(s)+1):
            substrings.append(s[i:j])
    return substrings

# O(2^N)
def subset(s):
    store = []
    running = []
    def helper(s, index, running, store):
        if index == len(s):
            store.append("".join(running))
            return
        running.append(s[index])
        helper(s, index + 1, running, store)
        running.pop()
        helper(s, index + 1, running, store)
    helper(s, 0, running, store)
    return store

# O(N!)
def permutation(s):
    #print(s)
    if len(s) == 1:
        return [s]
    base = s[0]
    array = permutation(s[1:])
    newarray = []
    for word in array:
        for i in range(len(word)+1):
            addedword = word[:i] + base + word[i:]
            newarray.append(addedword)
    #print(newarray)
    return newarray

# O(N!)
def combination(s, r):
    visited = set()
    running, store = [], []
    def helper(s, index, r, visited, running, store):
        if len(running) == r:
            store.append("".join(running))
            return
        if len(s) == index:
            return
        for i in range(index, len(s)):
            if i not in visited:
                running.append(s[i])
                visited.add(i)
                helper(s, index + 1, r, visited, running, store)
                running.pop()
                visited.discard(i)
    helper(s, 0, r, visited, running, store)
    return store

s = "abc"
#s = "stackover"
print(substring(s))
print(subset(s))
print(combination(s, 3))
print(combination(s, 2))
print(combination(s, 1))
print(permutation(s))

print("PYHTON itertools library ")
import itertools
import math

print("PERMUTATION For array :3P3")
print(math.factorial(3))
print(list(itertools.permutations([1,2,3])))

print("PERMUTATION [1,2,3], 2 :3P2")
print(math.factorial(3)//math.factorial(3-2))
print(list(itertools.permutations([1,2,3],2)))

print("PERMUTATION [1,2,3], 1 : 3P1")
print(math.factorial(3)//math.factorial(3-1))
print(list(itertools.permutations([1,2,3],1)))

print("COMBINATION [1,2,3], 3 : 3C3")
print(math.factorial(3)//(math.factorial(3-3)*math.factorial(3)))
print(list(itertools.combinations([1,2,3], 3)))

print("COMBINATION [1,2,3], 2 : 3C2")
print(math.factorial(3)//(math.factorial(3-2)*math.factorial(2)))
print(list(itertools.combinations([1,2,3],2)))

print("COMBINATION [1,2,3], 1 : 3C1")
print(math.factorial(3)//(math.factorial(3-1)*math.factorial(1)))
print(list(itertools.combinations([1,2,3],1)))


def nPr(n, r):
    return int(math.factorial(n)//math.factorial(n-r))

def nCr(n, r):
    return int(math.factorial(n)/(math.factorial(n-r)*math.factorial(r)))
Graph, python coding question

Topological Sort

Topological sorting for a graph is not possible if the graph is not a DAG.

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.vertices = vertices

    def addEdge(self, u, v):
        self.graph[u].append(v)

def getDegree(graph, vertices):
    degrees = [0]*vertices
    for v in graph:
        for vv in graph[v]:
            degrees[vv] += 1
    return degrees

BFS TopologicalSort

def topologicalSort(graph) :
    indegrees = getDegree(graph.graph, graph.vertices)
    visited = set()
    path = []
    for v in range(graph.vertices):
        #print(v)
        if indegrees[v] == 0:
            bfs_ts(graph.graph, v, visited, path)
    return path

import collections
def bfs_ts(graph, v, visited, path):
    queue = collections.deque()
    queue.append(v)
    visited.add(v)
    while queue:
        v = queue.popleft()
        path.append(v)
        for nei in graph[v]:
            if nei not in visited:
                visited.add(nei)
                queue.append(nei)
# If vertices left, indegree ==0 will add the path

DFS TopologicalSort

def topologicalSort(graph):
    degree = getDegree(graph.graph, graph.vertices)
    visited = set()
    path = []
    for v in range(graph.vertices):
        if degree[v] == 0:
            dfs_ts(graph.graph, v, visited, path)
    return path[::-1]

def dfs_ts(graph, v, visited, path):
    visited.add(v)
    for nb in graph[v]:
        if nb not in visited:
            dfs_ts(graph, nb, visited, path)
    path.append(v)

Test topologicalSort

myGraph = Graph(5)
myGraph.addEdge(0, 1)
myGraph.addEdge(0, 3)
myGraph.addEdge(1, 2)
myGraph.addEdge(2, 3)
myGraph.addEdge(2, 4)
myGraph.addEdge(3, 4)

print(topologicalSort(myGraph)) # [0, 1, 2, 3, 4]

myGraph = Graph(6)
myGraph.addEdge(5, 2)
myGraph.addEdge(5, 0)
myGraph.addEdge(4, 0)
myGraph.addEdge(4, 1)
myGraph.addEdge(2, 3)
myGraph.addEdge(3, 1)

print(topologicalSort(myGraph))  # [5, 4, 2, 3, 1, 0]"