Skip to main content

Posts

Cells with Odd Values in a Matrix

Problem -  https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/ Given  n  and  m  which are the dimensions of a matrix initialized by zeros and given an array  indices  where  indices[i] = [ri, ci] . For each pair of  [ri, ci]  you have to increment all cells in row  ri  and column  ci  by 1. Return  the number of cells with odd values  in the matrix after applying the increment to all  indices . Example 1: Input: n = 2, m = 3, indices = [[0,1],[1,1]] Output: 6 Explanation: Initial matrix = [[0,0,0],[0,0,0]]. After applying first increment it becomes [[1,2,1],[0,1,0]]. The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers. Approach -  Iterate over indices and fetch row and column indices.  First loop keep row index constant and increment column index and updated each cell values until it reaches column max size. Repeat same step and keep column index constant and increment row index and update all cell values until it reaches row max s
Recent posts

Find all the existing paths in graph from source to destination node - BFS and DFS

#!/usr/bin/env python import collections graph = {'A': ['B', 'C'],              'B': ['C', 'D'],              'C': ['D'],              'D': ['C'],              'E': ['F'],              'F': ['C']} #Using DFS algorithm #Ref -   https://www.python.org/doc/essays/graphs/ def find_all_paths_dfs(graph, start, end, path = []):   path = path + [start]   #Reachd end return path   if start == end:         return [path]   #No path found found   if not graph.has_key(start):         return []   paths = []   for node in graph[start]:     if node not in path:       new_paths = find_all_paths_dfs(graph, node, end, path)       for new_path in new_paths:         paths.append(new_path)   return paths #Using BFS #Reference - http://code.activestate.com/recipes/576675/ def find_all_paths_bfs(graph, start,

Python Program to Print Directory Structure Recursively

os.walk - Recursively Generate the file names in a directory tree by walking the tree either top-down or bottom-up. For each directory in the tree rooted at directory top (including top itself), it yields a 3-tuple (dirpath, dirnames, filenames). Reference - https://docs.python.org/2/library/os.html Python Program - #!/usr/bin/python3 #Python Program to Print Directory and Files Recursively import os def print_dir(path):   for dirName,subdirList,fileList in os.walk(path):     nw_path = dirName.split('/')     print("|",(len(nw_path))*"---","[",os.path.basename(dirName),"]")     for fl in fileList:       print("|",len(nw_path)*"---","->",str(fl)) if __name__ == "__main__":   path = input("Enter the directory path :-")   print_dir(path) Output - surendra@Surendra:~/workspace/Python_Programs$ python3 recurse_print.py Enter the directory path :-/home/surendra

Program to validate IPv4 Private Address and print the class

#!/usr/bin/python3  #Program to Validate the IP Address and Print the class of the IPV4 Address #  - 10.0.0.0 - 10.255.255.255 -Class A - NetId 8 Bits , Host Id 24 Bits  #   - 172.16.0.0 - 172.31.255.255 - Class B - NetID 12 Bits, Host ID 20 Bits  #   - 192.168.0.0 - 192.168.255.255 - Class C - NetID 16 Bits , Host ID 16 Bits  #   - 127.0.0.0 to 127.255.255.255 - LocalHost / LoopBack  ''' Steps -         Read Input         Validate IP         split and map the input to integer         From list items 0 to 3 , check for IP Range Conditions ''' import re def validate_ip(ip_addr):  if re.search('\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}',ip_addr):           lst = list(map(int,ip_addr.split('.')))                      #CLASS A Range - 10.0.0.0 - 10.255.255.255       if((lst[0] == 10) and (lst[1] >= 10 and lst[1] <= 255) and (lst[2] >= 0 and lst[2] <= 255)  and (lst[3] >= 0 and lst[3] <= 255)):             print(

Best Time to Buy and Sell Stock

Program to Implement - Best Time to Buy and Sell Stock  Say you have an array for which the ith element is the price of a given stock on day i.  If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.  Example 1:  Input: [7, 1, 5, 3, 6, 4]  Output: 5  max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)  Example 2:  In this case, no transaction is done, i.e. max profit = 0.  Input: [7, 6, 4, 3, 1]  Output: 0  '''  class Solution(object):      def maxProfit(self, prices):          """          :type prices: List[int]          :rtype: int          """                 # Brute Force - O(n^2)          profit = 0          for i in range(0,len(prices)):              for j in range(i+1,len(prices)):                  if(prices[j] > prices[i] and profit < prices[j] - prices[i]):