Algorithms
def zeros(arr, n):
count = 0
for i in range(n):
if arr[i] != 0:
arr[count] = arr[i]
count += 1
while count < n:
arr[count] = 0
count += 1
def print_arr(arr, n):
for i in range(n):
print(arr[i], end=" ")
arr = [1, 0, 0, 2, 5, 0]
zeros(arr, len(arr))
print_arr(arr, len(arr))
# Simple function that will take a string of latin characters and return a unique hash
def hashString(str):
# Map characters to prime numbers to multiply
charMap = {
"a": 2,
"b": 3,
"c": 5,
"d": 7,
"e": 11,
"f": 13,
"g": 17,
"h": 19,
"i": 23,
"j": 29,
"k": 31,
"l": 37,
"m": 41,
"n": 43,
"o": 47,
"p": 53,
"q": 59,
"r": 61,
"s": 67,
"t": 71,
"u": 73,
"v": 79,
"w": 83,
"x": 89,
"y": 97,
"z": 101,
"A": 103,
"B": 107,
"C": 109,
"D": 113,
"E": 127,
"F": 131,
"G": 137,
"H": 139,
"I": 149,
"J": 151,
"K": 163,
"L": 167,
"M": 173,
"N": 179,
"O": 181,
"P": 191,
"Q": 193,
"R": 197,
"S": 199,
"T": 211,
"U": 223,
"V": 227,
"W": 229,
"X": 233,
"Y": 239,
"Z": 241,
}
return reduce(lambda memo, char: memo * charMap[char], list(str), 1)
def anagramDetection(parent, child):
length = len(child)
anagram = hashString(child)
total = 0
for i in range(0, len(parent) - length):
if hashString(parent[i : i + length]) == anagram:
total = total + 1
return total
def SortAnagram(arr):
temp = []
stage = []
dic = []
for i in arr:
for j in i:
stage.append(j)
stage.sort()
temp.append("".join(stage))
stage = []
for index, value in enumerate(temp):
dic.append([index, value])
temp = []
dic = sorted(dic, key=lambda x: x[1])
for i in range(len(dic)):
stage.append(dic[i][0])
for i in stage:
temp.append(arr[i])
print(temp)
arr = ["cat", "dog", "tac", "god", "act"]
SortAnagram(arr)
import unittest
"""solution to the array pair sum problem"""
def array_pair_sum_iterative(arr, k):
"""
returns the array of pairs using an iterative method.
complexity: O(n^2)
"""
result = []
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == k:
result.append([arr[i], arr[j]])
return result
def array_pair_sum_sort(arr, k):
"""
first sort the array and then use binary search to find pairs.
complexity: O(nlogn)
"""
result = []
arr.sort()
for i in range(len(arr)):
if k - arr[i] in arr[i + 1 :]:
result.append([arr[i], k - arr[i]])
return result
def array_pair_sum_hash_table(arr, k):
"""
Use a hash table to store array elements of pairs.
complexity: O(n)
"""
result = []
hash_table = {}
for e in arr:
if e in hash_table:
result.append([k - e, e])
else:
hash_table[k - e] = True
result.reverse()
return result
# Unit tests
class array_pair_sum_tests(unittest.TestCase):
def setUp(self):
self.arr1 = [3, 4, 5, 6, 7]
self.arr2 = [3, 4, 5, 4, 4]
self.result1 = [[3, 7], [4, 6]]
self.result2 = [[3, 5], [4, 4], [4, 4], [4, 4]]
def test_one(self):
self.assertEqual(array_pair_sum_iterative(self.arr1, 10), self.result1)
self.assertEqual(array_pair_sum_sort(self.arr1, 10), self.result1)
self.assertEqual(array_pair_sum_hash_table(self.arr1, 10), self.result1)
def test_two(self):
self.assertEqual(array_pair_sum_iterative(self.arr2, 8), self.result2)
self.assertEqual(array_pair_sum_sort(self.arr2, 8), self.result2)
self.assertEqual(array_pair_sum_hash_table(self.arr2, 8), self.result2)
if __name__ == "__main__":
unittest.main()
# Use a dictionary to map sets of brackets to their opposites
brackets = {"(": ")", "{": "}", "[": "]"}
# On each input string, process it using the balance checker
def balancedBrackets(string):
stack = []
# Process every character on input
for char in string:
# Assign an initial value in case the stack is empty
last = 0
# Assign the value of the last element if stack is not empty
if stack:
last = stack[len(stack) - 1]
if stack and last in brackets and brackets[last] == char:
stack.pop()
else:
stack.append(char)
return not stack
def balance(arr):
open_bracket = ["[", "{", "("]
close_bracket = ["]", "}", ")"]
stack = []
for i in arr:
if i in open_bracket:
stack.append(i)
elif i in close_bracket:
pos = close_bracket.index(i)
if len(stack) >= 0 and (open_bracket[pos] == stack[len(stack) - 1]):
stack.pop()
else:
return "unbalanced"
if len(stack) == 0:
return "balanced"
else:
return "unbalanced"
arr = ["{", "[", "]", "}"]
print(balance(arr))
arr = [1, 2, 3, 4, 5, 6]
x = 5
print("iterative approach to find element using")
def binary_search_iterative(arr, l, r, x):
while l <= r:
mid = l + (r - l) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
l = mid + 1
else:
l = r - 1
return -1
result_iterative = binary_search_iterative(arr, 0, len(arr) - 1, x)
if result_iterative != -1:
print("element found: " + str(result_iterative))
else:
print("not found")
print("#########################################")
print("recursive approach to find element using")
def binary_search_recursive(arr, l, r, x):
if l <= r:
mid = l + (r - l) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
return binary_search_recursive(arr, mid + 1, r, x)
else:
return binary_search_recursive(arr, l, mid - 1, x)
else:
return -1
result_recursive = binary_search_recursive(arr, 0, len(arr) - 1, x)
if result_iterative != -1:
print("element found: " + str(result_recursive))
else:
print("not found")
# sample input : 4
# -1,0,3,57,89,9
# output : -1,0,3,9,57,89
def bubble_sort(arr, n):
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
result = bubble_sort(arr, len(arr))
print(result)
def orangesRotting(elemnts):
if not elemnts or len(elemnts) == 0:
return 0
n = len(elemnts)
m = len(elemnts[0])
rotten = []
for i in range(n):
for j in range(m):
if elemnts[i][j] == 2:
rotten.append((i, j))
mins = 0
def dfs(rotten):
count = []
for i, j in rotten:
if i > 0 and rotten[i - 1][j] == 1:
count.append((i - 1, j))
elemnts[i - 1][j] = 2
if j > 0 and rotten[i][j - 1] == 1:
count.append((i, j - 1))
elemnts[i][j - 1] = 2
if i < n - 1 and rotten[i][j] == 1:
count.append((i, j))
elemnts[i][j] = 2
if j < m - 1 and rotten[i][j] == 1:
count.append((i, j))
elemnts[i][j] = 2
return count
while rotten:
rotten = dfs(rotten)
if not rotten:
break
mins += 1
for i in range(n):
for j in range(m):
if elemnts[i][j] == 1:
return -1
return mins
"""solution to the convert array problem"""
def f(arr):
"""sorts the array by numbers in place using constant extra space"""
position = 0
for i in xrange(len(arr) / 3):
gap = (len(arr) - position) / 3
arr.insert(position + 1, arr.pop(position + gap * 1))
arr.insert(position + 2, arr.pop(position + gap * 2))
position += 3
return arr
#!/bin/python3
import sys
#
# Complete the 'countingValleys' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
# 1. INTEGER steps
# 2. STRING path
#
def countingValleys(steps, path):
# Write your code here
path = list(path)
sealevel = valley = 0
for paths in path:
if paths == "U":
sealevel += 1
else:
sealevel -= 1
if paths == "U" and sealevel == 0:
valley += 1
return valley
path = "UDDDUDUU"
steps = 8
print(countingValleys(steps, path))
# Input:
# S = "geeksforgeeks", N = 2
# Output: 4
# Explanation: 'g', 'e', 'k' and 's' have
# 2 occurrences.
def CountChar(String, Occurance):
STROCR = {}
RESULT = []
for i in range(len(String)):
if String[i] in STROCR.keys():
STROCR[String[i]] += 1
else:
STROCR[String[i]] = 1
for j in STROCR.keys():
if STROCR[j] == Occurance:
RESULT.append(j)
elif STROCR[j] > Occurance:
RESULT.append(j)
else:
pass
print(RESULT)
String = "geeksforgeeks"
Occurance = 2
CountChar(String, Occurance)
def cyclic_rotation(arr, n):
temp = arr[n - 1]
for i in range(n - 1, 0, -1):
arr[i] = arr[i - 1]
arr[0] = temp
def print_array(arr, n):
for i in range(n):
print(arr[i])
arr = [1, 2, 3, 4, 5]
cyclic_rotation(arr, 5)
print_array(arr, 5)
# Input: nums = [131, 11, 48]
# Output: 1 3 4 8
# Explanation: 1, 3, 4, and 8 are only distinct
# digits that can be extracted from the numbers
# of the array.
def Dis_array(arr):
dup = []
for i in arr:
length = len(str(i))
i = str(i)
for j in range(length):
if i[j] in dup:
pass
else:
dup.append(i[j])
print(dup)
arr = [131, 11, 48]
Dis_array(arr)
class Stack:
def __init__(self, limit=10):
self.stack = []
self.limit = limit
def push(self, n):
if len(self.stack) > self.limit:
self.doublelimit()
else:
self.stack.append(n)
def pop(self):
if len(self.stack) > 0:
self.stack.pop()
def is_empty(self):
if len(self.stack) == 0:
return True
else:
return False
def PrintStack(self):
for i in self.stack:
print(i)
def Length(self):
n = len(self.stack)
print(n)
# logic for douling the stack
def doublelimit(self):
newStack = self.stack
self.limit = 2 * self.limit
self.stack = newStack
sta = Stack(5)
sta.push(1)
sta.push(2)
sta.push(1)
sta.push(2)
sta.push(2)
sta.push(2)
sta.PrintStack()
sta.Length()
def duplicate_removal(arr):
dictonary = {}
for i in arr:
if i in dictonary:
dictonary[i] = dictonary[i] + 1
else:
dictonary[i] = 1
return dictonary.keys()
arr = [1, 2, 2, 3, 4, 5, 5, 6, 7]
print(int(len(list(duplicate_removal(arr)))))
def even_occuring_element(arr):
"""Returns the even occuring element within a list of integers"""
dict = {}
for num in arr:
if num in dict:
dict[num] += 1
else:
dict[num] = 1
for num in dict:
if not dict[num] & 1: # bitwise check for parity.
return num
def find(arr, search, n):
for i in range(n):
if arr[i] == search:
return True
break
arr = [1, 2, 3, 4, 5, 6]
search = 4
print(find(arr, search, 6))
import tarfile
fname = "spark-3.0.2-bin-hadoop2.7.tgz"
if fname.endswith("tgz"):
tar = tarfile.open(
"C:\\Users\\ag16000\Downloads\\spark-3.0.2-bin-hadoop2.7.tgz", "r:gz"
)
tar.extractall()
tar.close()
elif fname.endswith("tar"):
tar = tarfile.open(
"C:\\Users\\ag16000\Downloads\\spark-3.0.2-bin-hadoop2.7.tgz", "r:"
)
tar.extractall()
tar.close()
"""solutions to the factorial problem"""
def factorial_iterative(num):
"""returns the factorial of num using an iterative method."""
factor = 1
for i in xrange(1, num + 1):
factor *= i
return factor
def factorial_reduce(num):
"""returns the factorial of num using a reduce (shortest method)."""
return reduce(lambda x, y: x * y, range(1, num + 1))
def factorial_recursive(num):
"""returns the factorial of num using a recursive method."""
if num == 1:
return 1
return num * factorial_recursive(num - 1)
"""solutions to the fibonacci problem"""
def fibonacci_iterative(limit):
"""fibonacci sequence using an iterative approach."""
a, b = 0, 1
for i in xrange(limit):
a, b = b, a + b
return a
def fibonacci_recursive(limit):
"""fibonacci sequence using a recusive approach."""
if limit <= 1:
return limit
return fibonacci_recursive(limit - 1) + fibonacci_recursive(limit - 2)
def fibonacci_reduce(limit):
"""fibonacci sequence using reduce (shortest option)."""
return reduce(lambda x, y: x + [x[y] + x[y - 1]], range(1, limit), [0, 1])[-1]
def fibonacci_comprehension(limit):
"""fibonacci sequence using a list comprehension."""
sequence = [0, 1]
[sequence.append(sequence[i] + sequence[i - 1]) for i in range(1, limit)]
return sequence[-1]
def fib_series(count):
a = 0
b = 1
c = 1
for i in range(count):
a = b
b = c
c = a + b
print(a)
fib_series(10)
"""finds the missing element in the shuffled list"""
def difference_set(orig, shuffled):
"""finds the missing element using a set."""
return set(orig).difference(set(shuffled)).pop()
def difference_iterative(orig, shuffled):
"""finds the missing element by iterating over the list"""
for x in orig:
if not x in shuffled:
return x
# 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.
# Example 1:
# Input: nums = [1,3,4,2,2]
# Output: 2
def findDuplicate(arr):
for i in range(len(arr)):
if arr[i] == arr[i + 1]:
return arr[i]
else:
pass
arr = [1, 3, 4, 2, 2]
print(findDuplicate(arr))
"""solution for the first-non-repeated-character problem"""
def first_non_repeated_character(str):
"""finds the first character in a string that's not repreated"""
for i, char in enumerate(str):
if i - 1 >= 0 and char == str[i - 1]:
continue
if i + 1 < len(str) and char == str[i + 1]:
continue
return char
def left_search(arr, low, high, x):
temp = -1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] > x:
high = mid - 1
elif arr[mid] < x:
low = mid + 1
else:
temp = mid
high = mid - 1
return temp
def right_search(arr, low, high, x):
temp = -1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] > x:
high = mid - 1
elif arr[mid] < x:
low = mid + 1
else:
temp = mid
low = mid + 1
return temp
arr = [1, 4, 4, 4, 5, 6, 7]
l_result = left_search(arr, 0, len(arr), 4)
r_result = right_search(arr, 0, len(arr), 4)
print("first occurance:" + str(l_result))
print("last occurance: " + str(r_result))
"""accepts a multi dimensional array and returns a flattened version"""
def flatten_array(orig):
"""returns a new, flattened, list"""
flattened_list = []
for item in orig:
if isinstance(item, list):
flattened_list += flatten_array(item)
else:
flattened_list.append(item)
return flattened_list
def flatten_in_place(orig):
"""flattens a given list in place"""
is_flattened = False
while not is_flattened: # iterating until no more lists are found
is_flattened = True
for i, item in enumerate(orig):
if isinstance(item, list):
is_flattened = False
orig = orig[:i] + item + orig[i + 1 :]
return orig
def jumpingOnClouds(c):
i = counter = 0
length = len(c)
while i < length - 1:
if c[i + 2] == 0:
i += 2
else:
i += 1
counter += 1
return counter
arr = [0, 0, 0, 0, 1, 0]
print(jumpingOnClouds(arr))
def kidsWithCandies(candies, extraCandies):
temp_array = []
max_element = max(candies)
for i in candies:
temp = i + extraCandies
if max_element <= temp:
temp_array.append(True)
else:
temp_array.append(False)
return temp_array
candies = [2, 3, 5, 1, 3]
extraCandies = 3
print(kidsWithCandies(candies, extraCandies))
def kth_array(arr, n):
arr.sort(reverse=True)
for i in range(n):
print(arr[i])
arr = [1, 23, 12, 9, 30, 2, 50]
kth_array(arr, 3)
# Input:
# N = 6
# arr[] = 7 10 4 3 20 15
# K = 3
# Output : 7
# Explanation :
# 3rd smallest element in the given
# array is 7.
# def kthSmallest(arr, l, r, k):
# '''
# arr : given array
# l : starting index of the array i.e 0
# r : ending index of the array i.e size-1
# k : find kth smallest element and return using this function
# '''
# arr.sort()
# return(arr[k-1])
# r=int(input())
# arr=input()
# array=list(map(int,arr.strip().split()))
# k=int(input())
# print(kthSmallest(array,0,r-1,k))
def kthSmallest(arr, l, r, k):
if k > 0 and k <= r - l + 1:
pos = randomPartition(arr, l, r)
if pos - l == k - 1:
return arr[pos]
if pos - l > k - 1:
return kthSmallest(arr, l, pos - 1, k)
return kthSmallest(arr, pos + 1, r, k - pos + l - 1)
return 999999999999
def swap(arr, a, b):
temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
def partition(arr, l, r):
x = arr[r]
i = l
for j in range(l, r):
if arr[j] <= x:
swap(arr, i, j)
i += 1
swap(arr, i, r)
return i
def randomPartition(arr, l, r):
n = r - l + 1
pivot = int(random.random() % n)
swap(arr, l + pivot, r)
return partition(arr, l, r)
"""solution to the largest-continuous-sum problem"""
def largest_continuous_sum(arr):
"""returns the highest sum of a continuous sequence in a given list"""
largest = 0
queue = []
for num in arr:
if len(queue) > 0 and queue[-1] + 1 != num:
sum = reduce(lambda x, y: x + y, queue)
if largest < sum:
largest = sum
queue = []
queue.append(num)
return largest
def addTwoNumbers(l1, l2):
l1.reverse()
l2.reverse()
con_1 = ""
con_2 = ""
for i in l1:
con_1 += str(i)
for i in l2:
con_2 += str(i)
result = int(con_1) + int(con_2)
temp = str(result)
lis = []
for i in temp:
lis.append(i)
lis.reverse()
return lis
l1 = [2, 4, 3]
l2 = [5, 6, 4]
result = addTwoNumbers(l1, l2)
print(result)
# linked list creation
# singly linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def PrintList(self):
if self.head is not None:
itr = self.head
while itr:
print(itr.data, end="-->")
itr = itr.next
if __name__ == "__main__":
# creating empty linked list
l = LinkedList()
# assigning the first node to head of linked list
l.head = Node(1)
# assigining the second node
l2 = Node(2)
# assigining the third node
l3 = Node(3)
# linking the first node to the second
l.head.next = l2
# linking the second node to the third
l2.next = l3
# printing the list
l.PrintList()
from __future__ import division
from math import ceil
from itertools import combinations
from operator import mul
# Sum of multiples of 3 or 5 under 1000, simplified:
# print (3 * 333 * 334 / 2) + (5 * 199 * 200 / 2) - (15 * 66 * 67 / 2)
def getSumOfMultiple(num, limit):
return int((ceil(limit / num) - 1) * ceil(limit / num) * num / 2)
def getSumOfMultiples(multiples, limit):
result = 0
sign = 1
for i in range(1, len(multiples) + 1):
for x in combinations(multiples, i):
result += sign * getSumOfMultiple(reduce(mul, x, 1), limit)
sign *= -1
return result
class once:
def __init__(self, func, times=1):
self.times = int(times)
self.func = func
def __call__(self, *args, **kwargs):
if self.times > 0:
self.times -= 1
return self.func(*args, **kwargs)
from math import sqrt
def is_prime(n):
if n <= 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
for i in xrange(3, int(sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
from random import randint
def quickSort(lst):
# List of 0 or 1 items is already sorted
if len(lst) <= 1:
return lst
else:
# Pivot can be chosen randomly
pivotIndex = randint(0, len(lst) - 1)
pivot = lst[pivotIndex]
# Elements lower than and greater than pivot
lesser, greater = [], []
for index in range(len(lst)):
# Don't do anything if you're at the pivot
if index == pivotIndex:
pass
else:
# Sort elements into < pivot and >= pivot
el = lst[index]
if el < pivot:
lesser.append(el)
else:
greater.append(el)
# Sort lesser and greater, concatenate results
return quickSort(lesser) + [pivot] + quickSort(greater)
def sort_num(arr, n):
cnt0 = 0
cnt1 = 0
cnt2 = 0
for i in range(n):
if arr[i] == 0:
cnt0 += 1
elif arr[i] == 1:
cnt1 += 1
elif arr[i] == 2:
cnt2 += 1
i = 0
while cnt0 > 0:
arr[i] = 0
i += 1
cnt0 -= 1
while cnt1 > 0:
arr[i] = 1
i += 1
cnt1 -= 1
while cnt2 > 0:
arr[i] = 2
i += 1
cnt2 -= 1
def print_arr(arr, n):
for i in range(n):
print(arr[i], end=" ")
arr = [0, 1, 2, 0, 1, 2]
n = len(arr)
sort_num(arr, n)
print_arr(arr, n)
def sorted_rotation(arr, low, high, n):
while low < high:
if arr[low] <= arr[high]:
return low
mid = low + (high - low) // 2
next = (mid + 1) % n
prev = (mid + n - 1) % n
if arr[mid] < arr[next] and arr[mid] < arr[prev]:
return mid
elif arr[mid] <= arr[high]:
high = mid - 1
elif arr[mid] >= arr[low]:
low = mid + 1
return -1
arr = [6, 7, 8, 9, 1, 2, 3, 4, 5]
result = sorted_rotation(arr, 0, len(arr) - 1, len(arr))
print("array is rotated by : " + result)
def sprialMatrix(arr, m, n):
k = 0
l = 0
while k < m and l < n:
for i in range(l, n):
print(arr[k][i], end=" ")
k += 1
for i in range(k, m):
print(arr[i][n - 1], end=" ")
n -= 1
if k < m:
for i in range(n - 1, l - 1, -1):
print(arr[m - 1][i], end=" ")
m -= 1
if l < n:
for i in range(m - 1, k - 1, -1):
print(arr[i][l], end=" ")
l += 1
# function calling
sprialMatrix([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 3, 3)
import sys
class Stack:
# initialize the constructor of empty array
def __init__(self, arr, limit):
self.arr = arr
self.arr = []
self.limit = limit
# defining an method to get all the elements in the que
def print_elements(self):
for i in range(len(self.arr)):
print(self.arr[i])
# defining an method to append elements in a stack
def push(self, i):
# limiting the stack size
if len(self.arr) <= self.limit - 1:
self.arr.append(i)
else:
# limit of stack exceeds stack overflow
print("elements are : ")
for i in range(len(self.arr)):
print(self.arr[i])
print("stack overflow occurred")
sys.exit()
# defining an method to pop an element from the array
def pop(self):
self.arr.pop()
# defining an method to check if the stack is empty
def is_empty(self):
n = len(self.arr)
if n == 0:
print("array is empty")
else:
print("array is not empty")
# defining an method to get the top element
def top(self):
n = len(self.arr)
return self.arr[n]
# initialize the object
sta = Stack([], 4)
# pushing an element to the array
sta.push(1)
sta.push(2)
sta.push(1)
sta.push(2)
sta.push(2)
sta.push(2)
# printing all the elements in the stack
sta.print_elements()
# popping the element from the array
sta.pop()
# printing all the elements in the stack
sta.print_elements()
# popping an element from the array
sta.pop()
# checking if the array is empty or not
sta.is_empty()
class Stack:
# initialize the constructor of empty array
def __init__(self, arr, limit):
self.arr = arr
self.arr = []
self.limit = limit
self.max_array = []
# defining an method to get all the elements in the que
def print_elements(self):
for i in range(len(self.arr)):
print(self.arr[i])
# defining an method to append elements in a stack
def push(self, i):
# limiting the stack size
if len(self.arr) <= self.limit - 1:
self.arr.append(i)
def maxPush(self):
# if len(self.arr) <= self.limit - 1:
if len(self.arr) == 1:
self.max_array.append(self.arr[len(self.arr) - 1])
elif self.arr[len(self.arr) - 1] < self.max_array[len(self.max_array) - 1]:
self.max_array.append(self.max_array[len(self.max_array) - 1])
else:
self.max_array.append(self.arr[len(self.arr) - 1])
print("max value is : " + str(self.max_array[len(self.max_array) - 1]))
# defining an method to pop an element from the array
def pop(self):
self.arr.pop()
max_array.pop()
# defining an method to get the top element
def top(self):
n = len(self.arr)
return self.arr[n]
# initialize the object
sta = Stack([], 6)
# pushing an element to the array
sta.push(10)
sta.maxPush()
print("-------------------")
sta.push(2)
sta.maxPush()
print("-------------------")
sta.push(3)
sta.maxPush()
print("-------------------")
sta.push(4)
sta.maxPush()
print("-------------------")
sta.push(5)
sta.maxPush()
print("-------------------")
sta.push(6)
sta.maxPush()
print("-------------------")
# printing all the elements in the stack
# sta.print_elements()
# popping the element from the array
# sta.pop()
class Solution:
def strongPasswordChecker(self, s: str) -> int:
len_passwd = len(s)
lowercase, uppercase, digit = False, False, False
repeating = [] # list of interval of consecutive char.
for idx, char in enumerate(s):
if not lowercase and 97 <= ord(char) <= 122:
lowercase = True
if not uppercase and 65 <= ord(char) <= 90:
uppercase = True
if not digit and char in {"1", "2", "3", "4", "5", "6", "7", "8", "9", "0"}:
digit = True
if (
repeating
and repeating[-1][1] + 1 == idx
and s[repeating[-1][1]] == s[idx]
):
repeating[-1][1] = idx # extend the lastest interval
if (
0 < idx < len_passwd - 1
and s[idx - 1] == s[idx] == s[idx + 1]
and (not repeating or idx > repeating[-1][1])
):
repeating.append([idx - 1, idx + 1]) # new an interval
def helper(lenpass, case, repeat):
if 6 <= lenpass <= 20 and case == 3 and repeat == ():
return 0
ans = inf
if lenpass < 6:
# Insertion
if repeat:
add_repeat = [repeat[0] - 2] if repeat[0] > 4 else []
ans = min(
ans,
helper(
lenpass + 1,
min(case + 1, 3),
tuple(list(repeat[1:]) + add_repeat),
),
)
else:
ans = helper(lenpass + 1, min(case + 1, 3), ())
elif lenpass > 20:
# Deletion
if repeat:
for i in range(len(repeat)):
repeat_del = list(repeat)
if repeat_del[i] > 3:
repeat_del[i] -= 1
else:
del repeat_del[i]
ans = min(ans, helper(lenpass - 1, case, tuple(repeat_del)))
else:
ans = helper(lenpass - 1, case, ())
else:
# Replace
if repeat:
add_repeat = [repeat[0] - 3] if repeat[0] > 5 else []
ans = min(
ans,
helper(
lenpass,
min(case + 1, 3),
tuple(list(repeat[1:]) + add_repeat),
),
)
else:
ans = helper(lenpass, min(case + 1, 3), ())
return 1 + ans
return helper(
len_passwd,
sum([lowercase, uppercase, digit]),
tuple([term[1] - term[0] + 1 for term in repeating]),
)
Sol = Solution()
print(Sol.strongPasswordChecker("a"))
# Recursive Python3 program to find if a given pattern is
# present in a text
def exactMatch(text, pat, text_index, pat_index):
if text_index == len(text) and pat_index != len(pat):
return 0
# Else If last character of pattern reaches
if pat_index == len(pat):
return 1
if text[text_index] == pat[pat_index]:
return exactMatch(text, pat, text_index + 1, pat_index + 1)
return 0
# This function returns true if 'text' contain 'pat'
def contains(text, pat, text_index, pat_index):
# If last character of text reaches
if text_index == len(text):
return 0
# If current characters of pat and text match
if text[text_index] == pat[pat_index]:
if exactMatch(text, pat, text_index, pat_index):
return 1
else:
return contains(text, pat, text_index + 1, pat_index)
# If current characters of pat and tex don't match
return contains(text, pat, text_index + 1, pat_index)
# Driver program to test the above function
print(contains("geeksforgeeks", "geeks", 0, 0))
print(contains("geeksforgeeks", "geeksquiz", 0, 0))
print(contains("geeksquizgeeks", "quiz", 0, 0))
# def twoSum(arr,n,target):
# for i in range(n):
# for j in range(1,n):
# result=arr[i]+arr[j]
# if result==target:
# print("["+str(i)+","+str(j)+"]")
# arr=[2,7,11,15]
# twoSum(arr,len(arr),9)
class Solution:
# def __init__(self,arr,n,target):
# self.arr=arr
# self.n=n
# self.target=target
def twoSum(self, arr, n, target):
for i in range(self.n):
for j in range(1, self.n):
result = self.arr[i] + self.arr[j]
if result == self.target:
print("[" + str(i) + "," + str(j) + "]")
temp = Solution([2, 7, 11, 15], len([2, 7, 11, 15]), 9)
temp.twoSum()
import psutil
import json
def getListOfProcessSortedByMemory():
listOfProcObjects = []
for proc in psutil.process_iter():
pinfo = proc.as_dict(attrs=["pid", "name"])
pinfo["CPU_USAGE"] = proc.memory_info().vms / (1024 * 1024)
# Append dict to list
listOfProcObjects.append(pinfo)
listOfProcObjects = sorted(
listOfProcObjects, key=lambda procObj: procObj["CPU_USAGE"], reverse=True
)
result = json.dumps(listOfProcObjects)
lis = result.split("}")
lst = [e[3:] for e in lis]
start_text = """
<html>
<body>"""
end_text = """
</body>
</html>
"""
f = open("dump.html", "w+")
f.write(start_text)
for elem in lst:
print(elem + str(" MB"))
f.write("<p>" + str(elem) + " MB" + "</p>")
f.write(end_text)
f.close()
def main():
print("##### Create a list of all running processes #######")
getListOfProcessSortedByMemory()
if __name__ == "__main__":
main()
# class human():
# def __init__(self,name,age):
# self.name=name
# self.age=age
# class rohan(human):
# def __init__(self, name, age,year):
# super().__init__(name,age)
# self.year=year
# def welcome(self):
# print("hello "+str(self.name) + " "+str(self.age)+" " + str(self.year))
# ron=rohan("rohan",22,2019)
# ron.welcome()
# class incr():
# def itr(self):
# self.a=1
# def next(self):
# if self.a <=5:
# print(self.a)
# self.a+=1
# else:
# raise StopIteration
# zip=incr()
# zip.itr()
# zip.next()
# zip.next()
# zip.next()
# zip.next()
# zip.next()
theBoard = [' '] * 10
print(theBoard)
((bo[7] == le and bo[8] == le and bo[9] == le) or # across the top
(bo[4] == le and bo[5] == le and bo[6] == le) or # across the middle
(bo[1] == le and bo[2] == le and bo[3] == le) or # across the bottom
(bo[7] == le and bo[4] == le and bo[1] == le) or # down the left side
(bo[8] == le and bo[5] == le and bo[2] == le) or # down the middle
(bo[9] == le and bo[6] == le and bo[3] == le) or # down the right side
(bo[7] == le and bo[5] == le and bo[3] == le) or # diagonal
(bo[9] == le and bo[5] == le and bo[1] == le))
print(' | |')
print(' ' + board[7] + ' | ' + board[8] + ' | ' + board[9])
print(' | |')
print('-----------')
print(' | |')
print(' ' + board[4] + ' | ' + board[5] + ' | ' + board[6])
print(' | |')
print('-----------')
print(' | |')
print(' ' + board[1] + ' | ' + board[2] + ' | ' + board[3])
print(' | |')
import random
def drawBoard(board):
# This function prints out the board that it was passed.
# "board" is a list of 10 strings representing the board (ignore index 0)
print(" | |")
print(" " + board[7] + " | " + board[8] + " | " + board[9])
print(" | |")
print("-----------")
print(" | |")
print(" " + board[4] + " | " + board[5] + " | " + board[6])
print(" | |")
print("-----------")
print(" | |")
print(" " + board[1] + " | " + board[2] + " | " + board[3])
print(" | |")
def inputPlayerLetter():
# Lets the player type which letter they want to be.
# Returns a list with the player’s letter as the first item, and the computer's letter as the second.
letter = ""
while not (letter == "X" or letter == "O"):
print("Do you want to be X or O?")
letter = input().upper()
# the first element in the list is the player’s letter, the second is the computer's letter.
if letter == "X":
return ["X", "O"]
else:
return ["O", "X"]
def whoGoesFirst():
# Randomly choose the player who goes first.
if random.randint(0, 1) == 0:
return "computer"
else:
return "player"
def playAgain():
# This function returns True if the player wants to play again, otherwise it returns False.
print("Do you want to play again? (yes or no)")
return input().lower().startswith("y")
def makeMove(board, letter, move):
board[move] = letter
def isWinner(bo, le):
# Given a board and a player’s letter, this function returns True if that player has won.
# We use bo instead of board and le instead of letter so we don’t have to type as much.
return (
(bo[7] == le and bo[8] == le and bo[9] == le)
or (bo[4] == le and bo[5] == le and bo[6] == le) # across the top
or (bo[1] == le and bo[2] == le and bo[3] == le) # across the middle
or (bo[7] == le and bo[4] == le and bo[1] == le) # across the bottom
or (bo[8] == le and bo[5] == le and bo[2] == le) # down the left side
or (bo[9] == le and bo[6] == le and bo[3] == le) # down the middle
or (bo[7] == le and bo[5] == le and bo[3] == le) # down the right side
or (bo[9] == le and bo[5] == le and bo[1] == le) # diagonal
) # diagonal
def getBoardCopy(board):
# Make a duplicate of the board list and return it the duplicate.
dupeBoard = []
for i in board:
dupeBoard.append(i)
return dupeBoard
def isSpaceFree(board, move):
# Return true if the passed move is free on the passed board.
return board[move] == " "
def getPlayerMove(board):
# Let the player type in their move.
move = " "
while move not in "1 2 3 4 5 6 7 8 9".split() or not isSpaceFree(board, int(move)):
print("What is your next move? (1-9)")
move = input()
return int(move)
def chooseRandomMoveFromList(board, movesList):
# Returns a valid move from the passed list on the passed board.
# Returns None if there is no valid move.
possibleMoves = []
for i in movesList:
if isSpaceFree(board, i):
possibleMoves.append(i)
if len(possibleMoves) != 0:
return random.choice(possibleMoves)
else:
return None
def getComputerMove(board, computerLetter):
# Given a board and the computer's letter, determine where to move and return that move.
if computerLetter == "X":
playerLetter = "O"
else:
playerLetter = "X"
# Here is our algorithm for our Tic Tac Toe AI:
# First, check if we can win in the next move
for i in range(1, 10):
copy = getBoardCopy(board)
if isSpaceFree(copy, i):
makeMove(copy, computerLetter, i)
if isWinner(copy, computerLetter):
return i
# Check if the player could win on their next move, and block them.
for i in range(1, 10):
copy = getBoardCopy(board)
if isSpaceFree(copy, i):
makeMove(copy, playerLetter, i)
if isWinner(copy, playerLetter):
return i
# Try to take one of the corners, if they are free.
move = chooseRandomMoveFromList(board, [1, 3, 7, 9])
if move != None:
return move
# Try to take the center, if it is free.
if isSpaceFree(board, 5):
return 5
# Move on one of the sides.
return chooseRandomMoveFromList(board, [2, 4, 6, 8])
def isBoardFull(board):
# Return True if every space on the board has been taken. Otherwise return False.
for i in range(1, 10):
if isSpaceFree(board, i):
return False
return True
print("Welcome to Tic Tac Toe!")
while True:
# Reset the board
theBoard = [" "] * 10
playerLetter, computerLetter = inputPlayerLetter()
turn = whoGoesFirst()
print("The " + turn + " will go first.")
gameIsPlaying = True
while gameIsPlaying:
if turn == "player":
# Player’s turn.
drawBoard(theBoard)
move = getPlayerMove(theBoard)
makeMove(theBoard, playerLetter, move)
if isWinner(theBoard, playerLetter):
drawBoard(theBoard)
print("Hooray! You have won the game!")
gameIsPlaying = False
else:
if isBoardFull(theBoard):
drawBoard(theBoard)
print("The game is a tie!")
break
else:
turn = "computer"
else:
# Computer’s turn.
move = getComputerMove(theBoard, computerLetter)
makeMove(theBoard, computerLetter, move)
if isWinner(theBoard, computerLetter):
drawBoard(theBoard)
print("The computer has beaten you! You lose.")
gameIsPlaying = False
else:
if isBoardFull(theBoard):
drawBoard(theBoard)
print("The game is a tie!")
break
else:
turn = "player"
if not playAgain():
break
# Recursive Python function to solve the tower of hanoi
def TowerOfHanoi(n, source, destination, auxiliary):
if n == 1:
print("Move disk 1 from source", source, "to destination", destination)
return
TowerOfHanoi(n - 1, source, auxiliary, destination)
print("Move disk", n, "from source", source, "to destination", destination)
TowerOfHanoi(n - 1, auxiliary, destination, source)
# Driver code
n = 4
TowerOfHanoi(n, "A", "B", "C")
def LeftMax(array, i):
left = array[i]
for j in range(i):
# left=max(left,array[j])
if left < array[j]:
left = array[j]
else:
left = left
return left
def RightMax(array, i):
right = array[i]
for j in range(i + 1, len(array)):
# right=max(right,array[j])
if right < array[j]:
right = array[j]
else:
right = right
return right
def TrappingWater(array):
totalwater = 0
for i in range(1, len(array) - 1):
leftMax = LeftMax(array, i)
rightMax = RightMax(array, i)
totalwater = totalwater + (min(leftMax, rightMax) - array[i])
return totalwater
array = [2, 0, 2]
print(TrappingWater(array))
class node:
def __init__(self, val):
self.right = None
self.left = None
self.val = val
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.right = node(5)
root.left.left = node(4)
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
def preorder_traversal(root):
if root:
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
print("########################")
print("inorder traversal: L N R ")
inorder_traversal(root)
print("########################")
print("preorder traversal: N L R ")
preorder_traversal(root)
print("########################")
print("postorder traversal: N R L")
postorder_traversal(root)
class Tree:
def __init__(self, data):
self.data = data
self.children = []
self.parent = None
def add_child(self, child):
child.parent = self
self.children.append(child)
def print_elements(self):
print(self.data)
for i in self.children:
print(" !-" + i.data)
for j in i.children:
print(" !----" + j.data)
root = Tree("electronics")
laptop = Tree("laptop")
laptop.add_child(Tree("mac"))
laptop.add_child(Tree("windows"))
cell = Tree("cell")
cell.add_child(Tree("LG"))
cell.add_child(Tree("apple"))
root.add_child(laptop)
root.add_child(cell)
root.print_elements()
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def traverse_levelorder(root):
if not root:
return
q = [root, True] # Use True as sentinel for end of row
while len(q) > 0:
node = q.pop(0)
print node.value,
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if q[0] is True: # End of row
q.pop(0)
if len(q) > 0:
q.append(True)
print
# https://www.geeksforgeeks.org/find-triplets-array-whose-sum-equal-zero/
# o(n^3)
# def Triplet(arr):
# n = len(arr)
# found = False
# for i in range(0, n - 2):
# for j in range(i + 1, n - 1):
# for k in range(j + 1, n):
# if arr[i] + arr[j] + arr[k] == 0:
# print(arr[i], arr[j], arr[k])
# found=True
#
# if not found:
# print("element not found")
#
#
# arr=[0, -1, 2, -3, 1]
#
# Triplet(arr)
# optimal soultion
# o(n^2)
def Triplet(arr):
n = len(arr)
found = True
for i in range(n - 1):
l = i + 1
r = n - 1
x = arr[i]
while l < r:
if arr[l] + arr[r] + x == 0:
print(arr[l], arr[r], x)
l += 1
r -= 1
found = True
elif arr[l] + arr[r] + x < 0:
l += 1
else:
r -= 1
if not found:
print("triplet not found")
arr = [0, -1, 2, -3, 1]
Triplet(arr)
# Time complexity O(M*N)
# Space Complexity O(M+N)
# Method 1
class Solution:
# Function to return the count of number of elements in union of two arrays.
def doUnion(self, a, n, b, m):
c = a + b
c.sort()
d = []
for i in c:
if i not in d:
d.append(i)
else:
pass
return len(d)
if __name__ == "__main__":
t = int(input())
for _ in range(t):
n, m = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]
ob = Solution()
print(ob.doUnion(a, n, b, m))
# Time complexity O(M)+O(N)+O(Mlog(M)+Nlog(N))
# Space Complexity O(n+m)
# Method 2
class Solution:
# Function to return the count of number of elements in union of two arrays.
def doUnion(self, a, n, b, m):
c = a + b
c.sort() # O(Mlog(M))+O(Nlog(N))
sample_dict = {}
for i in c: # O(M)+O(N)
if i in sample_dict.keys():
sample_dict[i] += 1
else:
sample_dict[i] = 1
return len([int(x) for x in sample_dict.values()])
if __name__ == "__main__":
t = int(input())
for _ in range(t):
n, m = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]
ob = Solution()
print(ob.doUnion(a, n, b, m))
def wave(arr, n):
arr.sort()
for i in range(0, n - 1, 2):
arr[i], arr[i + 1] = arr[i + 1], arr[i]
arr = [10, 90, 49, 2, 1, 5, 23]
wave(arr, len(arr))
for i in range(len(arr)):
print(arr[i], end=" ")
file = open("sample.txt", "r")
d = dict()
for lines in file:
lines = lines.strip()
lines = lines.lower()
words = lines.split(" ")
for word in words:
if word in d:
d[word] = d[word] + 1
else:
d[word] = 1
find = str(input("enter the word to count: "))
find = find.lower()
if find in list(d.keys()):
print(f"{find} : " + str(d.get(find)))
else:
print("word not present!! ")
def xor(arr, n):
xor_val = 0
for i in range(n):
xor_val = xor_val ^ arr[i]
return xor_val
arr = [3, 9, 12, 13, 15]
n = len(arr)
print(xor(arr, n))
import pafy
url = "https://www.youtube.com/watch?v=OE7wUUpJw6I&list=PL2_aWCzGMAwLPEZrZIcNEq9ukGWPfLT4A"
video = pafy.new(url)
print(video.title)
stream = pafy.new(url).streams
best = video.getbest()
for i in stream:
print(i)
print(best.resolution, best.extension)
print(best.url)
best.download(quiet=False)Last updated