Div Count (Problem on Prefix Sums)

Div Count Problem
Compute number of integers divisible by k in range [a..b].

Problem

Write a function:

def solution(A, B, K)

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

# A and B are integers within the range [0..2,000,000,000];

# K is an integer within the range [1..2,000,000,000];

# A ≤ B

Code

from math import ceil, floor 

def solution(A, B, K):
    
    start = ceil(A/K)
    end = floor(B/K)
    return end - start + 1

Complexity

Detected time complexity:

O(1)

Tests

Correctness tests

simple

A = 11, B = 345, K = 17

minimal

A = B in {0,1}, K = 11

extreme_ifempty

A = 10, B = 10, K in {5,7,20}

extreme_endpoints

verify handling of range endpoints, multiple runs

Performance tests

big_values

A = 100, B=123M+, K=2

big_values2

A = 101, B = 123M+, K = 10K

big_values3

A = 0, B = MAXINT, K in {1,MAXINT}

big_values4

A, B, K in {1,MAXINT}

Passing Cars
Count the number of passing cars on the road.
Problem on Prefix Sums

Problem

A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

0 represents a car traveling east,

1 represents a car traveling west.

The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

Write a function:

def solution(A)

that, given a non-empty array A of N integers, returns the number of pairs of passing cars.

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer that can have one of the following values: 0, 1.

Example

For example, consider array A such that:

A[0] = 0

A[1] = 1

A[2] = 0

A[3] = 1

A[4] = 1

We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

For example, given:

the function should return 5, as explained above.

Hint

Code (I)

def solution(A):
    # In the question, it is given that 0 are travelling east. We assume it to be the direction of prefix sums.
    # So if we implement using prefix counts, we would have to count zeroes.

    # '1' is going to the west, that is having the direction of suffix sums.

    prefix_counts = [0] * (len(A) + 1)

    for i in range(len(A)):
        if A[i] == 0:
            prefix_counts[i+1] = prefix_counts[i] + 1
        else:
            prefix_counts[i+1] = prefix_counts[i] + 0

    passing_cars = 0 
    for i in range(len(A)):
        if A[i] == 1:
            passing_cars += prefix_counts[i+1]

    if passing_cars > 1000000000:
        passing_cars = -1

    return passing_cars

Code (II): Now Using Suffix Sums

def solution(A):
    # In the question, it is given that 0 are traveling east. We assume it to be the direction of prefix sums.

    # '1' is going to the west, that is having the direction of suffix sums.
    # So if we implement using suffix counts, we would have to count ones.

    suffix_counts = [0] * (len(A) + 1)

    for i in range(len(A) - 1, -1, -1):
        if A[i] == 1:
            suffix_counts[i] = suffix_counts[i+1] + 1
        else:
            suffix_counts[i] = suffix_counts[i+1] + 0

    passing_cars = 0 
    for i in range(len(A)):
        if A[i] == 0:
            passing_cars += suffix_counts[i]

    if passing_cars > 1000000000:
        passing_cars = -1

    return passing_cars

Time Complexity

Detected time complexity:

O(N)

Tests

Correctness tests

single element

double

two elements

simple

simple test

small_random

random, length = 100

small_random2

random, length = 1000

Performance tests

medium_random

random, length = ~10,000

large_random

random, length = ~100,000

large_big_answer

0..01..1, length = ~100,000

large_alternate

0101..01, length = ~100,000

large_extreme

large test with all 1s/0s, length = ~100,000

Mushroom Picker (A problem on Prefix Sums)

Problem

You are given a non-empty, zero-indexed array A of n (1 <= n <= 100000) integers a0, a1,..., an−1 (0 <= ai <= 1000). This array represents number of mushrooms growing on the consecutive spots along a road. You are also given integers k and m (0 <= k, m < n).

A mushroom picker is at spot number k on the road and should perform m moves. In one move she moves to an adjacent spot. She collects all the mushrooms growing on spots

she visits. The goal is to calculate the maximum number of mushrooms that the mushroom

picker can collect in m moves.

For example, consider array A such that:

A[0]=2, A[1]=3, A[2]=7, A[3]=5, A[4]=1, A[5]=3, A[6]=9

The mushroom picker starts at spot k = 4 and should perform m = 6 moves. She might

move to spots 3, 2, 3, 4, 5, 6 and thereby collect 1 + 5 + 7 + 3 + 9 = 25 mushrooms. This is the

maximal number of mushrooms she can collect.

Code

# Counting prefix sums
  def prefix_sums(A):
      n = len(A)
      P = [0] * (n + 1)
      for k in xrange(1, n + 1):
          P[k] = P[k - 1] + A[k - 1]
      return P
  
  # Total of one slice
  def count_total(P, x, y):
      return P[y + 1] - P[x]
  # Mushroom picker — O(n + m)
  def mushrooms(A, k, m):
      n = len(A)
      result = 0
      pref = prefix_sums(A)
  
  # When we first take p steps on the left and return from their back in right direction.
      for p in xrange(min(m, k) + 1):
          left_pos = k - p
          right_pos = min(n - 1, max(k, k + m - 2*p))
          result = max(result, count_total(pref, left_pos, right_pos)) 
  
  # When we first take p steps on the right and return from their back in left direction.
      for p in xrange(min(m + 1, n - k)):
          right_pos = k + p
          left_pos = max(0, min(k, k - (m - 2*p)))
          result=max(result, count_total(pref, left_pos, right_pos)) 
      return result

Explanation (Part 1)

# When we first take p steps on the left and return from their back in right direction.
    for p in xrange(min(m, k) + 1):
        left_pos = k - p
        right_pos = min(n - 1, max(k, k + m - 2*p))
        result = max(result, count_total(pref, left_pos, right_pos)) 

Expression “for p in xrange(min(m, k) + 1)” has min(m, k) because we can only go m steps to the left or k steps to the left whichever number is minimum.

After going k steps, we cannot go past 0th position.

Or after taking m steps, we cannot take another step.

Expression “right_pos = min(n - 1, max(k, k + m – 2*p))” has ‘k+m-2*p’ because after taking p steps to the left, we are returning p steps back to position k, hence 2p.

And then number of steps left is: m – 2p

Then right position is identified by: m-2p steps after k ie, k+m-2p

Expression “right_pos = min(n - 1, max(k, k + m – 2*p))” has max(k, k + m – 2*p) because what if we take all the m steps to left and value of p becomes m.

Then there are no steps left to take to the right and right position is simply identified by k.

Similarly, for any value of p > m/2 (as in 0.6m or 0.75m), we would get same right position as k.

Explanation (Part 2)

# When we first take p steps on the right and return from their back in left direction.
    for p in xrange(min(m + 1, n - k)):
        right_pos = k + p
        left_pos = max(0, min(k, k - (m - 2*p)))
        result = max(result, count_total(pref, left_pos, right_pos))

Here in the expression “for p in xrange(min(m + 1, n – k))”, we have m+1 and not just m because xrange goes till m when passed the argument m+1. Similarly, we have n-k and not (n-1)-k because xrange goes till (n-1)-k when passed the argument n-k.

And we take minimum of m or (n-1)-k because that’s is the possible number of steps we can take on the right.

Here in the expression “left_pos = max(0, min(k, k - (m – 2*p)))”, we have k-(m-2p) because we take p steps on the right, then take those p steps back to k (on the left now).

Number of steps yet to take: m-2p

Left position would be identified by: k-(m-2p)

If p takes value m, which means we have taken m steps on the right, then we have no steps remaining to take to the left and left position is identified by k itself. (This logic is valid for any value of p > m/2)

Side Note

The way we calculating prefix sums and sums of subsections is without using the Python built-ins. But if we were to use Python built-ins, the code would look somewhat like this:

def get_mushrooms_sum(A, start, end):
  return sum(A[start : end + 1])

Coding Round in Interview for Data Scientist Role at a Bank (17 Nov 2023)

Task 1

Write a function:

    def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−1,000,000..1,000,000].

A brute-force solution to this problem that will fail the performance tests will look like this:


def solution(A):
    # a_sort = sorted(A)
    rtn = -1
    for i in range(1, 100001):
        if i in A: # This is the most time consuming instruction of this code that runs repeatedly for all of i(s)
            continue
        else:
            rtn = i
            break
    return rtn 


Task 2




Task 3

Fig 3.1



Fig 3.2



Fig 3.3

Bubble Sort (Using Recursion)

Can you give me python code for bubble sort?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Here's a simple Python implementation of the bubble sort algorithm:


def bubble_sort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:
my_list = [64, 25, 12, 22, 11]
bubble_sort(my_list)

print("Sorted array:", my_list)


This code defines a function bubble_sort that takes a list as input and sorts it in ascending order using the bubble sort algorithm. The example usage shows how to sort an example list, and the sorted array is then printed.

Using recursion?

Although bubble sort is not typically implemented using recursion due to its inefficiency compared to iterative methods, it can be done for educational purposes. Here's an example of a recursive implementation of bubble sort in Python:


def recursive_bubble_sort(arr, n=None):
    # Base case: If the array is empty or contains only one element, it is already sorted
    if n is None:
        n = len(arr)
    
    if n <= 1:
        return
    
    # One pass of bubble sort: Traverse the array and swap adjacent elements if they are in the wrong order
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]

    # Recursively call the function with a reduced size of the array
    recursive_bubble_sort(arr, n - 1)

# Example usage:
my_list = [64, 25, 12, 22, 11]
recursive_bubble_sort(my_list)

print("Sorted array:", my_list)

In this recursive implementation, the function recursive_bubble_sort takes an additional parameter n to represent the size of the array being considered in each recursive call. The base case checks if the array size is 1 or less, in which case the array is considered sorted. Otherwise, one pass of the bubble sort is performed, and the function is called recursively with a reduced size of the array.

What is the time complexity of the recursion based code?

The time complexity of the recursive version of bubble sort remains O(n^2) in the worst and average cases, just like the iterative version. This is because, even though recursion is used, the number of comparisons and swaps required to sort the array is still proportional to the square of the number of elements in the array.

Each recursive call performs one pass through the array, and there are a total of n recursive calls (each reducing the size of the array by 1). In each pass, the algorithm compares and potentially swaps adjacent elements, and this process is repeated for each pass until the array is sorted.

Therefore, the overall time complexity is still O(n^2), which makes bubble sort, whether implemented iteratively or recursively, inefficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.

Tags: Algorithms,Python,Technology,

Missing Integer: Find the smallest positive integer that does not occur in a given sequence.

MissingInteger

Find the smallest positive integer that does not occur in a given sequence.

Problem

Write a function:

def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [−1,000,000..1,000,000].

Rohit’s Solution: Based on sorting of input array

def solution(A):
  B = [i for i in A if i > 0]
  if len(B) > 1:
      B = sorted(list(set(B)))
      if B[0] != 1:
          return 1
  elif len(B) == 1:
      if B[0] == 1:
          return 2
      else:
          return 1
  else:
      return 1
  for i in range(len(B) - 1):
      if B[i+1] - B[i] != 1:
          return B[i] + 1
      elif B[i+1] - B[i] == 1 and (i+1) == len(B)-1:
          return B[i+1] + 1

The idea is to:

(1) Sort the input array

(2) Capture differences between two consecutive numbers, if the difference is not equal to one return there with the appropriate value.

My Solution: Based on a counter variable

Detected time complexity: O(N) or O(N * log(N))

The idea is to maintain a counter with length equal to len(A) + 1

This counter is initialized to False and counter[0] initialized to True.

The n’th element of counter signifies () if the element was found in input array A or not.

We iterate of A to update our counter.

Then to return an output, we iterate over A again to detect the first False flag and return it’s index.

Code

def solution(A):
  if len(A) == 1:
      if A[0] == 1:
          return 2
      else:
          return 1
  else:
      B = [False for i in range(len(A) + 1)]
      B[0] = True 
      for i in A:
          if i < len(B) and i > 0:
              B[i] = True 
          
      for i in range(len(B)):
          if B[i] == False:
              return i
      return len(B)

Tags: Algorithms,Technology,Python,

Max Counters (a problem on counting elements)

MaxCounters

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

Problem

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,

max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),

if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)

(0, 0, 1, 1, 0)

(0, 0, 1, 2, 0)

(2, 2, 2, 2, 2)

(3, 2, 2, 2, 2)

(3, 2, 2, 3, 2)

(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];

each element of array A is an integer within the range [1..N + 1].

Example

For example, given integer N = 5 and array A such that:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)

(0, 0, 1, 1, 0)

(0, 0, 1, 2, 0)

(2, 2, 2, 2, 2)

(3, 2, 2, 2, 2)

(3, 2, 2, 3, 2)

(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

If given:

A[0] = 3, A[1] = 4, A[2] = 4, A[3] = 6, A[4] = 1, A[5] = 4, A[6] = 4

the function should return [3, 2, 2, 4, 2] as explained.

Hint: Let’s analyze the Brute-Force Solution

In Brute-Force solution, we follow the instructions as given.

We increase the counters on encountering the increase operation.

And on encountering the maxCounter() operation, we loop over the counters and set them equal to max counter.

This would solve the problem but would result in a quadratic time complexity.

Hint: Worst Case Scenario For Brute Force Solution. Time Complexity of: N*M

Hint: Linear Time Complexity

The bottleneck for the code is the maxCounter() operation. So, in this solution we find a smart way of implementing the maxCounter() operation.

We would draw an analogy between our counters and racers on a race track.

We would maintain two variables:

1. startLine: that tracks the where the racers are starting.

Basically, on encountering the maxCounter() operation, we would update this field.

2. currentMax: That tracks the maximum value among the counters.

This variable will be used to update the other variable startLine on encountering a maxCounter() operation.

Hint: Linear Time Solution

Hint: What happens when we encounter a maxCounter() op? We update our startLine.

Code

def increase(X, counters, startLine, currentMax):
  if counters[X] < startLine:
      counters[X] = startLine 
  counters[X] += 1
  if counters[X] > currentMax:
      currentMax = counters[X]
  return counters, currentMax
def maxCounter(startLine, currentMax):
  startLine = currentMax
  return startLine 
def solution(N, A):
  startLine = 0
  currentMax = 0
  counters = [0 for i in range(N)]
  
  for i in A:
      if i < N+1:
          counters, currentMax = increase(i-1, counters, startLine, currentMax)
      else:
          startLine = maxCounter(startLine, currentMax)
          
  for i in range(len(counters)):
      if counters[i] < startLine:
          counters[i] = startLine 
  return counters

Detected time complexity: O(N + M)

Test Cases

Correctness tests

extreme_small: all max_counter operations

single: only one counter

small_random1: small random test, 6 max_counter operations

small_random2: small random test, 10 max_counter operations

Performance tests

medium_random1: medium random test, 50 max_counter operations

medium_random2: medium random test, 500 max_counter operations

large_random1: large random test, 2120 max_counter operations

large_random2: large random test, 10000 max_counter operations

extreme_large: all max_counter operations

Python Modules

• Simply a module is a library of code ( Python Code file with extention .py )
• It’s contains set of functions you want to include in your applications
• # For Ex – Saving following code in a file with name as mymodule.py

     def greeting(name):
	    print("Hello," + name)

• Use of an existing module in another python program...

     # For Ex –  Save following code in file with name UseOfExistingModule.py

        import mymodule               # importing an existing module
        mymodule.greeting("Jonathan") # Calling of specific function

 # Note: A module function is called as follow:

          modulename.functionname

Use of variables in modules

• A module can contain any type of variable
• Variable type can be : String , Array , List , Set , Tuple , Dictionary etc

    
     #  For Ex - Save following  code in the file  as mymodule.py 

       
     person = {
               "name":"John",
               "age": 36,
               "country:"Norway"
              }

     #  Using above module in another program as follow

       
        import mymodule
        a = mymodule.person["age"] # Accessing age property of person1 Dict.
        print(a)

        
        Output Will be  : 36

Naming And Python Modules

#  You can give any name to the module file but it must have the file extension .py
#  You can create an alias when you import a module, by using the as keyword
#  For Ex – Create an alias for mymodule called mx

    import mymodule as mx
    a = mx.person1["age"] # Use of alias name to call a module function
    print(a)

	
    Output will be : 36

#  Using Built-In Modules : you can use built in module by importing them
#  For Ex –  Import and use the platform built in module

   import platform        # platform is a built in module
   x = platform.system()  # Calling a function of built in module
   print(x)               # This will print name of running OS on system

	
   Output will be  : Windows ( In Case of Windows OS )

Use the dir() Function

• This is a built in function
• It is used to list out all the function / variables defined in a module

      # For Ex – List out all the functions and variables  in platform module

      import platform
      x = dir(platform) # Passing module name to list out its contents
      print(x)          # To display contents

      Output will be like this :
         ['DEV_NULL', '_UNIXCONFDIR', 'WIN32_CLIENT_RELEASES', ‘
         WIN32_SERVER_RELEASES', '__builtins__', '__cached__', '__copyright__',
         Note *: 
         dir() function can be use to list out contents of built in and user defined modules

Use of Import From Module Statement

• You can import a specific part of the module using the from key word

 
   #  For Ex – First  Define a module as follow and save as mymodule.py
   #  This module define a function and a dictionary 

     def greeting(name):
         print("Hello," + name)
        
     person1 = {
                "name":"John",
                "age": 36,
                "country":"Norway"
               }

   #  Now importing only dictionary as follow in another program

    
      from mymodule import person1  # importing person named dictionary only

      print (person1["age"])   #  Note: No use of module name to access dictionary

      Output Will be : 36

DateTime in Python

#There is no date data type in python
#To deal with date and time you need to use DateTime built in module of python
        
# For Ex - Current date can be displayed as follow

import datetime as dt   # importing the module

# Note below: datetime represent constructor of datetime class
x = dt.datetime.now()   

print(x)

Output will be in following format:

2023-05-25 16:02:23.115559

Note*: It contains year, month, day, hour, minute, second, and microsecond

DateTime module methods

# There are many methods to give information about date object
# For Ex – Getting the year and name of weekday using current date object

import datetime as dt
x = dt.datetime.now()    # To get current date object
print(x.year)            # To display year

print(x.strftime("%A"))  # To display day name

Output will be like: 
2023
Thursday

Creating Date Objects

# You can create a date object using datetime class constructor of the datetime module 
# And you have to pass three parameters  values: year, month and day in constructor

# The datetime() class also takes parameters for time and timezone (i.e : hour, minute, second, microsecond, tzone), but they are optional, and has a default value of 0, (None for timezone)
   
# For Ex – Creating a date object

import datetime

x = datetime.datetime(2020, 5, 17)

print(x)

Output will be: 
2020-05-17 00:00:00

The strftime() Method

# This method is used for formatting date objects into readable strings.
# It takes one parameter, format, to specify the format of the returned string

# For Ex – Displaying the name of the month 

import datetime
x = datetime.datetime(2018, 6, 1)   # Creating a specific date object

print(x.strftime("%B"))             # Getting month information from date object

Output will be: 
June

# Few Examples of format code to be pass in strftime() method :

Tags: Technology,Python,

Python Math Module

# It contains a set of built-in functions and a math module

# Used to perform various mathematical tasks on numbers

# For Ex – Finding minimum and maximum value among multiple numbers

x = min(5, 10, 25)  # Use of built in math 
y = max(5, 10, 25)  # functions

print(x)
print(y) 

Output will be :

5

25

# For Ex – Getting Absolute ( Positive) and Power Values

x = abs(-7.25)
print(x) 

Output will be : 7.25

x = pow(4, 3)
print(x) 

Output will be : 64

# Use of math module functions

# For Ex - Calculating square root value of a number

import math

x = math.sqrt(64)

print(x)

Output will be : 8

# For Ex – Getting the upward and downward nearest integer value of a real number

import math

x = math.ceil(1.4)   # Will return upward nearest number
y = math.floor(1.4)  # Will return downward nearest number

print(x) 
print(y)

Output will be: 
		2
		1

# For Ex – Getting the value of PI Constant

import math

x = math.pi

print(x) 

Output will be: 3.141592653589793

Note * : There are many more functions and constants available to use in math module

Tags: Technology,Python

Python’s Built-in Modules

Python’s Standard Library

It is there so that developers can focus on the task in hand and not sit to re-invent the wheel for common task.

Core Ideas:

- Reusability

- Standardization of code

Some commonly used modules are as given below:

# There is one for Math – as in 'math' used for constants like math.pi

# There is one for Statistics – as in statistics.mean()

# random

# “string” – for string templates like ascii_lower

# collections

# Itertools

# “dateutil” - as in dateutil.parser.parse()

---

import string
string.ascii_lowercase
'abcdefghijklmnopqrstuvwxyz'
l = [chr(i) for i in range(ord('a'), ord('z') + 1)]
print(l)

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

s = ""
for i in range(ord('a'), ord('z') + 1): s += chr(i)
print(s)
abcdefghijklmnopqrstuvwxyz    

---

String Classes Available in The Form of String Templates

print(string.digits)

0123456789

#

print(string.ascii_lowercase)

abcdefghijklmnopqrstuvwxyz

#

print(string.ascii_uppercase)

ABCDEFGHIJKLMNOPQRSTUVWXYZ

#

print(string.ascii_letters)

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

#

print(string.printable)

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

#

print(string.hexdigits)

0123456789abcdefABCDEF

#

print(string.octdigits)

01234567

Iterators in Python (Theory)

• An iterator object is used to iterate through all items/values of a Iterable Object
• To iterate we need to get Iterator object from Iterable Object
• iter() and next() method are associated with Iterator object
• String, Tuple, List, Set and Dictionaries all are iterable objects
• There is built in iter() method, that is used to get Iterator object from an iterable object
• We can iterate all items of an iterable object using for loop as well
• For loop automatically create an Iterator object for an iterable object and call next() method for iterating through all items
• To create an object/class as an iterator you have to implement the methods __iter__() and __next__() to your object

Traffic Prediction on my Blog (Oct 2023)

Poisson Distribution for Traffic Prediction in Layman Terms

Imagine you're trying to predict how many cars will pass through a specific point on a road during a certain period, like an hour. The Poisson distribution can help you make this prediction.

Here's how it works in simple terms:

Events Occurring Over Time

The Poisson distribution is used when you're dealing with events that happen randomly over a fixed period of time. In our example, these events are cars passing by.

Average Rate

You start by knowing the average rate at which these events occur. For instance, on average, 30 cars pass by in an hour.

Independence

You assume that the arrival of each car is independent of the others. In other words, one car passing by doesn't affect the likelihood of another car passing by.

Probability of a Specific Number
    
With the Poisson distribution, you can calculate the probability of a specific number of events happening in that fixed time period. So, you can calculate the chance of exactly 25 cars passing by in an hour or any other number.

Shape of Distribution
    
The Poisson distribution has a particular shape that's skewed to the right. It's more likely to have fewer events than the average rate, and less likely to have more events, but it allows for some variability.

On a side note: 
Right skewed: The mean is greater than the median. The mean overestimates the most common values in a positively skewed distribution. Left skewed: The mean is less than the median.

Use in Traffic Prediction

To predict traffic, you can use the Poisson distribution to estimate the likelihood of different traffic volumes. If the average rate is 30 cars per hour, you can calculate the probabilities of having 20 cars, 40 cars, or any other number during that hour. This information can be useful for traffic planning and management.

In summary, the Poisson distribution helps you make educated guesses about the number of random events (like cars passing by) happening in a fixed time period, assuming they occur independently and at a known average rate. It's a valuable tool for predicting and managing things like traffic flow.

Here is how I used it to predict the traffic on my blog

1: Glimpse of the data



2: Tail of the data



3: Frequency plot for views in thousands



4: Number of views in thousands and probability of seeing that many views



5: Poisson distribution for views in thousands



6: Conclusion

# There is ~1.5% chance that there will be 9 thousand views.

# There is ~10% chance that there will be 16 thousand views.

# There is ~7.8% chance that there will be 19 thousand views.
 
Download Code and Data

In the next post, we will see why our analysis could be wrong.

When not to use Poisson Distribution for prediction?

Tags: Technology,Machine Learning,Data Analytics,Python

Exception Handling in Python (Theory)

Try, Except

This statement controls how the program proceeds when an error occurs. The syntax is as follows:

try:
	do something
except:
	do something else when an error occurs

For instance, try running the program below:- 

try:
	answer = 12/0
	print(answer) 
except:
	print ("An error occurred")

Exception We Saw: ZeroDivisionError

Exception We Saw: ValueError

Exception We Saw: IndexError

Getting a default value on index out of range in Python

In the non-Python spirit of "ask for permission, not forgiveness", here's another way: b = a[4] if len(a) > 4 else '-1'

Exception We Saw: NameError

We see this error while working with “del” keyword.

Exception We Saw: KeyError

Use case: We see this exception while working with remove() and discard() methods of a set.

Another example of KeyError While Working With Dict And How to Avoid It

Exception We Saw: TypeError

Other common errors in Python

IOError:

Raised when an I/O operation (such as the built-in open() function) fails for an I/O-related reason, e.g., “file not found”.

ImportError: Raised when an import statement fails to find the module definition

IndexError: Raised when a sequence (e.g. string, list, tuple) index is out of range.

KeyError: Raised when a dictionary key is not found.

NameError: Raised when a local or global name is not found.

TypeError: Raised when an operation or function is applied to an object of inappropriate type.

Python Classes and Objects (Theory)

Python is an object oriented programming language.

Almost everything in Python is an object, with its properties and methods.

A class is a blueprint of creating an object (like a Constructor).

The keyword to remember is “class” itself.

# For Ex: Creating a class with Name MyClass

class MyClass:
  x = 5
# Print created class
print(MyClass)
Output : <class '__main__.MyClass'>

Creating an Object

# Create an object named p1, and print the value of x

class MyClass:     
  x = 5
p1 = MyClass()  # Object creation using constructor
# Accessing the property of an Object using the dot (.) notation.
print(p1.x) 

Output : 5

Define an Empty class

A class body can’t be empty , if we have nothing to define then need to use pass statement to ignore error message

# Defining an empty class

class Person :
    pass

The __init__() Function and Classes

• All classes have a function called __init__()
• It is always executed when an object is being created
• We can use it to assign values to object properties &
• To perform other necessary operations required at the time of object creation

# Create a class named Person, and use the __init__() function to assign values for name and age:

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age
p1 = Person("John", 36) 

print(p1.name)
print(p1.age) 

Output :

John 36

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
p1 = Person("John", 36)
print(p1.name)
print(p1.age) 

A word about ‘self’

Simply stated, self refers to an instance itself.

For now, just know that when we want to refer to instance variables in the class, we need to add self in front of the variable names.

In addition, most methods in a class have self as the first parameter.

Object Methods

• Class can contain methods for objects

# For Ex – Defining a method that print a message on its call by object

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age
  def greeting(self):
    print("Hello my name is " + self.name)

p1 = Person("John", 36)
p1.greeting() 

Output : Hello my name is John

Note : The self parameter is a reference to the object of the class, and is used to access properties of the object

Note : First parameter of a method always refer to the current object , no matter what its name.

Function and Method

Function is usually understood as a standalone block of code.

>>> m = lambda a, b: a * b
>>> m(5, 5)
25
>>> m
<function <lambda> at 0x7f69cd84d280>
>>> 

Method is understood as a funtion associated with a class or it’s object.

class Calc:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def add(self):
        return self.a + self.b

    def mul(self):
        return self.a * self.b
    
    def sub(self):
        return self.a - self.b

sub() has no existence outside of Calc.

Modify and Deleting Object Properties

# For Ex – Modify the age of Object p1 to 40 :

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age
  def myfunc(self):
    print("Hello my name is " + self.name)
p1 = Person("John", 36)
p1.age = 40  # Modify the age for object p1
del p1.name  # Deleting the name property for object p1 by using del keyword
print(p1.age)  # Output will be : 40 
print(p1.name) #  Output  will be  : AttributeError: 'Person' object has no attribute ‘name'

Deleting an Object

• An object can be deleted by using del key word as well

# For Ex - Delete the p1 object

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age
  def myfunc(self):
    print("Hello my name is " + self.name)
p1 = Person("John", 36)
del p1
print(p1)

Output :

NameError: 'p1' is not defined

Inheritance in Python (Theory)

• Inheritance : It allows us to define a class that inherits all the methods and properties from another class.

• Parent class /Base Class : Which methods and properties being inherited
• Child Class / Derived Class : Which inherits properites and method of other class

• Any class can be a Parent Class
• While defining a child class, we just need to pass the name of parent class as an argument

# __init__() Function and child class : If we define __init__() function in child class then it will overide the functionality of inherited __init__() function of parent class.

# __init__() this function call automatically on object creation of child class.

# Note: we can explicity call parent class __init__() function inside the definition of child class __init__() funciton as follow :

ParentClassName.__init__()

Types of Inheritance in Python: Single Inheritance

Multiple Inheritance

Multilevel Inheritance

Hierarchical Inheritance

Hybrid Inheritance

Use the super() Function in Child Class

# super() function is used to access any property and method of parent class

# We can add new properties and method in child class as its own

Recursion (An Introduction)

What's Recursion Got to do With Russian Dolls?

Before we get into recursion, have you ever seen a Russian doll?

You open it further...

And once more...

Recursion

The process of solving a problem using Recursion is like opening Russian dolls.

Once you open the biggest doll, a similar doll but a bit smaller in size appears.

The same way, when you try to solve a problem using recursion, when you try to solve a bigger problem, that usually requires you to solve a smaller instance of the same problem.

Let's take a look at some problems that can be solved using Recursion

1. Factorial

2. Determine whether a word is a palindrome

3. Computing powers of a number

4. N-th Fibonacci Number

5. Generating permutations of letters such 'a', 'b', 'c'.

Factorial

# n! = n.(n-1).(n-2)...3.2.1

Or, equivalently:

# n! = n.(n-1)!

If n=0, then declare that n!=1.

Otherwise, n must be positive. Solve the subproblem of computing (n-1)! and multiply this result by n, and declare n! equal to the result of this product.

When we're computing n!, in this way, we call the first case, where we immediately know the answer, the base case, and we call the second case, where we have to compute the same function but on a different value, the recursive case.

Distilling the idea of recursion into two simple rules

1. Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.

2. The recursive calls must eventually reach a base case, which is solved without further recursion.

Determine whether a word is a palindrome

1) If the string is made of no letters or just one letter, then it is a palindrome.

2) Otherwise, compare the first and last letters of the string.

3) If the first and last letters differ, then the string is not a palindrome.

4) Otherwise, the first and last letters are the same. Strip them from the string, and determine whether the string that remains is a palindrome. Take the answer for this smaller string and use it as the answer for the original string.

Computing powers of a number

x**n = x**(n-1) * x

N-th Fibonacci Number

fib(n) = fib(n-1) + fib(n-2)

Generating permutations of letters such 'a', 'b', 'c'

Permutations of a, b, c =

a + Permutations of (b, c),

b + Permutations of (a, c), and

c + Permutations of (a, b)

Tags: Python,Technology,Algorithms