Category Archives: python coding question

sort

Cyclic Sort

1 Comment

Cyclic Sort

Time Complexcity:  O(n)
Space Complexity: O(1)
for i in 0 to n-1:
    while nums[i] is not the value expected at the spot:
        let d = destination index to which nums[i] should be sent
        nums[i], nums[d] = nums[d], nums[i]
def cyclic_sort(nums):
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while nums[i] != i + 1: 
            nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
            destinationIndex = nums[i] - 1
    return nums

print(cyclic_sort([3, 1, 5, 4, 2]))
print(cyclic_sort([2, 6, 4, 3, 1, 5]))
print(cyclic_sort([1, 5, 6, 4, 3, 2]))
Given an array nums containing n distinct numbers in the range [0, n],
return the only number in the range that is missing from the array.
def missingNumber(nums):
   for i in range(len(nums)): 
       destinationIndex = nums[i]
       while 0 <= destinationIndex < len(nums) and nums[i] != i: # while value is not the expected value            
            nums[destinationIndex], nums[i] = nums[i], nums[destinationIndex]
            destinationIndex = nums[i] 

   for i in range(len(nums)):
      if nums[i] != i:
         return i
   return len(nums)

 

Given an unsorted integer array nums, find the smallest missing positive integer.
def firstMissingPositive(nums):
    # nums = [1,2,3,4...]
    # nums[nums[i] - 1] = nums[i]
    for i in range(len(nums)):
    destinationIndex = nums[i] - 1
    while 0 <= destinationIndex < len(nums) and nums[i] != i + 1:
        nums[destinationIndex], nums[i] = nums[i], nums[destinationIndex]
        destinationIndex = nums[i] - 1

for i in range(len(nums)):
    target = i + 1
    if nums[i] != target:
        return target
return len(nums) + 1
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
Time Complexcity:  O(n)
Space Complexity: O(1)

def findDuplicate(nums):
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while 0 <= destinationIndex < len(nums) and nums[i] != i + 1:
        if nums[destinationIndex] == destinationIndex + 1:
            break
        nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
        destinationIndex = nums[i] - 1

for i in range(len(nums)):
    if nums[i] != i + 1:
        return nums[i]
We are given an unsorted array containing numbers taken from the range 1 to ‘n’.
The array can have duplicates, find all duplicates.
def find_all_duplicates(nums):
  for i in range(len(nums)):
    destinationIndex = nums[i] - 1
    while nums[i] != i + 1:
      if nums[destinationIndex] == destinationIndex +1:
        break
      nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]  # swap
      destinationIndex = nums[i] - 1
  duplicateNumbers = []
  for i in range(len(nums)):
    if nums[i] != i + 1:
      duplicateNumbers.append(nums[i])
return duplicateNumbers

 

We are given an unsorted array containing numbers taken from the range 1 to ‘n’.
The array can have duplicates, which means some numbers will be missing.
Find all those missing numbers.
def find_missing_numbers(nums):
    missingNumbers = []
    for i in range(len(nums)):
        destinationIndex = nums[i] -1
        while nums[i] != i + 1:
            if nums[destinationIndex] == destinationIndex + 1:
                break
            nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
            destinationIndex = nums[i] - 1
    for i in range(len(nums)):
        if nums[i] != i + 1:
            missingNumbers.append(i + 1)
    return missingNumbers
We are given an unsorted array containing ‘n’ numbers taken from the range 1 to ‘n’. 
The array originally contained all the numbers from 1 to ‘n’, but due to a data error, 
one of the numbers got duplicated which also resulted in one number going missing. 
Find both these numbers.

def find_corrupt_numbers(nums):
    missingpair = []
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while nums[i] != i + 1:
            if nums[destinationIndex] == destinationIndex + 1:
                break
            nums[destinationIndex], nums[i] = nums[i] , nums[destinationIndex]
            destinationIndex = nums[i] - 1

    for i in range(len(nums)):
        if nums[i] != i + 1:
            missingpair.append(i+1)
            missingpair.append(nums[i])
    return missingpair

 

Given an unsorted array containing numbers and a number ‘k’,
find the first ‘k’ missing positive numbers in the array.

def find_first_k_missing_positive(nums, k):
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while nums[i] != i + 1:
            if not 0 <= destinationIndex < len(nums) or nums[destinationIndex] == destinationIndex + 1:
                break
            nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
            destinationIndex = nums[i] - 1
    missingNums = []

    for i in range(len(nums)):
        if nums[i] != i + 1:
            missingNums.append(i+1)
        if len(missingNums) >= k:
            break

    i = 1
    while len(missingNums) < k:
        missingNums.append(nums[-1] + i)
        i += 1
    return missingNums


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]"