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....
Free Preview - 5 Binary Tree Problems Level order traversal AKA BFS class Node: def __init__(self, key): self.data = key self.left = None self.right = None def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue) > 0): # Print front of queue and remove it from queue print(queue[0].data) node = queue....
Free Preview - 5 Trie Problems Construct a trie from scratch class TrieNode: def __init__(self): self.children = [None]*26 # isEndOfWord is True if node represent the end of the word self.isEndOfWord = False class Trie: def __init__(self): self.root = self.getNode() def getNode(self): # Returns new trie node (initialized to NULLs) return TrieNode() def _charToIndex(self,ch): # private helper function. # Converts key current character into index use only 'a' through 'z' and lower case return ord(ch)-ord('a') def insert(self,key): # If not present, inserts key into trie # If the key is prefix of trie node, just marks leaf node pCrawl = self....
Free Preview - 5 Array Problems Reverse the array def reverseArray(A: list): start, end= 0, len(A)-1 while start<end: A[start], A[end]= A[end], A[start] start+=1 end-=1 A=[1,54,21,51,2,353,2,1,99,121,5,5] reverseArray(A) print("After reversing:", A) Find the maximum and minimum element in an array def getMinMax(arr: list, n: int): min = 0 max = 0 # If there is only one element then return it as min and max both if n == 1: max = arr[0] min = arr[0] return min, max # If there are more than one elements, then initialize min # and max if arr[0] > arr[1]: max = arr[0] min = arr[1] else: max = arr[1] min = arr[0] for i in range(2, n): if arr[i] > max: max = arr[i] elif arr[i] < min: min = arr[i] return min, max # Driver Code if __name__ == "__main__": arr = [1000, 11, 445, 1, 330, 3000] arr_size = 6 min, max = getMinMax(arr, arr_size) print("Minimum element is", min) print("Maximum element is", max) Find the “Kth” max and min element of an array import sys # function to calculate number of elements less than equal to mid def count(nums, mid): cnt = 0 for i in range(len(nums)): if nums[i] <= mid: cnt += 1 return cnt def kthSmallest(nums, k): low = sys....