💻Tech

Free Preview - 5 Dynamic Programming Problems Coin ChangeProblem """ Given an unlimited supply of coins of given denominations, find the total number of distinct ways to get the desired change. For example, Input: S = { 1, 3, 5, 7 }, target = 8 The total number of ways is 6 { 1, 7 } { 3, 5 } { 1, 1, 3, 3 } { 1, 1, 1, 5 } { 1, 1, 1, 1, 1, 3 } { 1, 1, 1, 1, 1, 1, 1, 1 } Input: S = { 1, 2, 3 }, target = 4 The total number of ways is 4 { 1, 3 } { 2, 2 } { 1, 1, 2 } { 1, 1, 1, 1 } """ def count(S, n, target): if target == 0: return 1 # return 0 (solution does not exist) if total becomes negative, no elements are left if target < 0 or n < 0: return 0 # Case 1....

Free Preview - 5 Elementary Problems Check Leap Year year = 2000 # divided by 100 means century year (ending with 00) century year divided by 400 is leap year if (year % 400 == 0) and (year % 100 == 0): print("{0} is a leap year".format(year)) # not divided by 100 means not a century year year divided by 4 is a leap year elif (year % 4 ==0) and (year % 100 !...

Free Preview - 5 Graph Problems Implement Graph class Graph: def __init__(self, edges, n): self.adjList = [[] for _ in range(n)] for (src, dest) in edges: self.adjList[src].append(dest) def printGraph(graph): for src in range(len(graph.adjList)): for dest in graph.adjList[src]: print(f'({src} —> {dest}) ', end='') print() edges = [(0, 1), (1, 2), (2, 0), (2, 1), (3, 2), (4, 5), (5, 4)] n = 6 graph = Graph(edges, n) printGraph(graph) Implement Weighted Graph class Graph: def __init__(self, edges, n): self....

Free Preview - 5 Greedy Problems Activity Selection Problem """ There is one meeting room in a firm. There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is finish time of meeting i. What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a particular time?...

Free Preview - 5 Heap Problems Implement a Maxheap/MinHeap using arrays and recursion. (Heapify) def heapify(arr, n, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # If left child is larger than root if l < n and arr[l] > arr[largest]: largest = l # If right child is larger than largest so far if r < n and arr[r] > arr[largest]: largest = r # If largest is not root if largest !...

Free Preview - 5 Linked List Problems Write a Program to reverse the Linked List. (Both Iterative and recursive) class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def reverse(self): prev = None current = self.head while current is not None: next = current.next current.next = prev prev = current current = next self.head = prev # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node....

Free Preview - 5 Matrix Problems Spiral traversal on a Matrix def spiralOrder(matrix): ans = [] if (len(matrix) == 0): return ans m = len(matrix) n = len(matrix[0]) seen = [[0 for _ in range(n)] for _ in range(m)] dr = [0, 1, 0, -1] dc = [1, 0, -1, 0] x = 0 y = 0 di = 0 # Iterate from 0 to R * C - 1 for _ in range(m * n): ans....

Free Preview - 5 Search and Sort Problems Bubble Sort def bubble_sort(array): n=len(array) for i in range(n): for j in range(n-i-1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] array=[5,2,3,1,4, -99, 0] bubble_sort(array) print(array) Selection Sort def selection_sort(array): global iterations iterations = 0 for i in range(len(array)): minimum_index = i for j in range(i + 1, len(array)): iterations += 1 if array[minimum_index] > array[j]: minimum_index = j # Swap the found minimum element with the first element if minimum_index !...

Free Preview - 5 Stack and Queue Problems Implement Stack from Scratch class Stack: def __init__(self, size): self.arr = [None] * size self.capacity = size self.top = -1 def push(self, val): if self.isFull(): print('Stack Overflow!! Calling exit()…') exit(-1) print(f'Inserting {val} into the stack…') self.top = self.top + 1 self.arr[self.top] = val def pop(self): if self.isEmpty(): print('Stack Underflow!! Calling exit()…') exit(-1) print(f'Removing {self.peek()} from the stack') # decrease stack size by 1 and (optionally) return the popped element top = self....

Free Preview - 5 String Problems Check whether a String is Palindrome or not def isPalindrome(s): return s == s[::-1] s = "malayalam" ans = isPalindrome(s) if ans: print("Yes") else: print("No") Find Duplicate characters in a string def printDups(Str): count = {} for i in range(len(Str)): if(Str[i] in count): count[Str[i]] += 1 else: count[Str[i]] = 1 #increase the count of characters by 1 for it,it2 in count.items(): #iterating through the unordered map if (it2 > 1): #if the count of characters is greater then 1 then duplicate found print(str(it) + ", count = "+str(it2)) Str = "test string" printDups(Str) Write a Code to check whether one string is a rotation of another def check_rotation(s, goal): if (len(s) !...

Free Preview - 5 Binary Search Tree Problems Find a value in a BST class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to insert a key into a BST def insert(root, key): # if the root is None, create a new node and return it if root is None: return Node(key) # if the given key is less than the root node, recur for the left subtree if key < root....