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....
Free Preview - 5 Backtracking Problems Rat in a maze Problem """ N = 4 m[][] = {{1, 0, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 1}} Output: DDRDRR DRDDRR Explanation: The rat can reach the destination at (3, 3) from (0, 0) by two paths - DRDDRR and DDRDRR, when printed in sorted order we get DDRDRR DRDDRR. """ def setup(): global v v = [[0 for i in range(100)] for j in range(100)] global ans ans = [] def path(arr, x, y, pth, n): if x==n-1 and y==n-1: global ans ans....