O(n) Reverse Arrays to Make Equal with Python

Reverse to Make EqualCompare two arrays without sorting themPython

Given two arrays A and B of length N, determine if there is a way to make A equal to B by reversing any subarrays from array B any number of times.

Signature bool areTheyEqual(int[] arr_a, int[] arr_b)

Input All integers in array are in the range [0, 1,000,000,000].

Output Return true if B can be made equal to A, return false otherwise.

Example A = [1, 2, 3, 4] B = [1, 4, 3, 2] output = true

After reversing the subarray of B from indices 1 to 3, array B will equal array A.

SOlution:

O(n) Contiguous Subarray in Python

O(n) Contiguous Subarray in Python

You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfills the following conditions:

  • The value at index i must be the maximum element in the contiguous subarrays, and
  • These contiguous subarrays must either start from or end on index i.

Signature int[] countSubarrays(int[] arr)Input

  • Array arr is a non-empty list of unique integers that range between 1 to 1,000,000,000
  • Size N is between 1 and 1,000,000

Output An array where each index i contains an integer denoting the maximum number of contiguous subarrays of arr[i]Example: arr = [3, 4, 1, 6, 2] output = [1, 3, 1, 5, 1]Explanation:

  • For index 0 – [3] is the only contiguous subarray that starts (or ends) with 3, and the maximum value in this subarray is 3.
  • For index 1 – [4], [3, 4], [4, 1]
  • For index 2 – [1]
  • For index 3 – [6], [6, 2], [1, 6], [4, 1, 6], [3, 4, 1, 6]
  • For index 4 – [2]

So, the answer for the above input is [1, 3, 1, 5, 1]

Solution in Python O(n)

O(n) Rotational Cipher in Python

O(n) Rotational Cipher in Python

Rotational Cipher: One simple way to encrypt a string is to “rotate” every alphanumeric character by a certain amount. Rotating a character means replacing it with another character that is a certain number of steps away in normal alphabetic or numerical order. For example, if the string “Zebra-493?” is rotated 3 places, the resulting string is “Cheud-726?”. Every alphabetic character is replaced with the character 3 letters higher (wrapping around from Z to A), and every numeric character replaced with the character 3 digits higher (wrapping around from 9 to 0). Note that the non-alphanumeric characters remain unchanged. Given a string and a rotation factor, return an encrypted string.

Signature

string rotationalCipher(string input, int rotationFactor)

Input

1 <= |input| <= 1,000,000 0 <= rotationFactor <= 1,000,000

Output

Return the result of rotating input a number of times equal to rotationFactor.

Example 1

input = Zebra-493?

rotationFactor = 3

output = Cheud-726?

Example 2

input = abcdefghijklmNOPQRSTUVWXYZ0123456789

rotationFactor = 39

output = nopqrstuvwxyzABCDEFGHIJKLM9012345678

O(n) Solution in Python:

Test 1:

PS C:\dev\scripts> .\test_rotational_cipher_python.py
Length Dic Numbers : 10
Length Dic lowercase : 26
Length Dic uppercase : 26
Input: Zebra-493?
Output: Cheud-726?

Test2:

PS C:\dev\scripts> .\test_rotational_cipher_python.py
Length Dic Numbers : 10
Length Dic lowercase : 26
Length Dic uppercase : 26
Input: abcdefghijklmNOPQRSTUVWXYZ0123456789
Output: nopqrstuvwxyzABCDEFGHIJKLM9012345678

Pair Sum with Python O(n)

Given a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k. If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn’t, even if they include the same values.

Signature

int numberOfWays(int[] arr, int k)

Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000,000,000]. k is in the range [1, 1,000,000,000].

Output

Return the number of different pairs of elements which sum to k.

Example 1

n = 5 k = 6 arr = [1, 2, 3, 4, 3] output = 2The valid pairs are 2+4 and 3+3.

Example 2

n = 5 k = 6 arr = [1, 5, 3, 3, 3] output = 4There’s one valid pair 1+5, and three different valid pairs 3+3 (the 3rd and 4th elements, 3rd and 5th elements, and 4th and 5th elements).

Solution using Python:

Pair Sum with Python

Complexity:

  • Time: O(n)
  • Space: Array of n and Hash of n (Who cares about space?? really ??)

Execution:

Case 1:

[1, 2, 3, 4, 3]
{1: 1, 2: 1, 3: 2, 4: 1}
Total Pairs is: 2.0

Case 2:

[1, 5, 3, 3, 3]
{1: 1, 5: 1, 3: 3}
Total Pairs is: 4.0

AWS Lambda to auto start stop Ec2 instance on schedule using python and boto3

Use this lambda function to auto start stop all Ec2 instances based on schedule from tags.

aws ec2 auto start stop lambda


#Auto Shutodown - Start EC2 instances based on tags
import boto3
import os
import json
import croniter
import datetime
# Enter the region your instances are in. Include only the region without specifying Availability Zone; e.g., 'us-east-1'
region = 'us-west-2'

EC2_STATUS_CODE_RUNNING = 16
EC2_STATUS_CODE_STOPPED = 80

def lambda_handler(event, context):
ec2 = boto3.client('ec2', region_name=region)

#auto_start_stop_tag = 'tc:uptime_schedule_gmt'
auto_start_tag = 'tc:start_time_schedule_gmt_24h_format'
auto_shutdown_tag = 'tc:shutdown_time_schedule_gmt_24h_format'

instances_to_shutdown = []
instances_to_start = []
# Query ec2 machines for auto_start_stop_tag,
#instances_with_schedules = get_instance_schedules(auto_start_stop_tag)
instances_with_start_schedules = get_instance_schedules(auto_start_tag)
instances_with_shutdown_schedules = get_instance_schedules(auto_shutdown_tag)
print("instances_with_start_schedules: %s" % instances_with_start_schedules)
print("instances_with_shutdown_schedules: %s" % instances_with_shutdown_schedules)

for instance_id, values in instances_with_start_schedules.items():
now = datetime.datetime.now()
print("now: %s" % now)
iterator = croniter.croniter(values['Schedule'], now)
next_run_time = iterator.get_next(datetime.datetime)
print("next_run_time: %s" % next_run_time)
duration_until_next_run_time = next_run_time - now
print("duration_until_next_start_time: %s" % duration_until_next_run_time)
duration_of_one_hour = datetime.timedelta(hours=1)

if duration_until_next_run_time <= duration_of_one_hour and values['State']['Code'] == EC2_STATUS_CODE_STOPPED: print("true") print("instance_to_stop.append(%s)" % instance_id) instances_to_start.append(instance_id) for instance_id, values in instances_with_shutdown_schedules.items(): now = datetime.datetime.now() print("now: %s" % now) iterator = croniter.croniter(values['Schedule'], now) next_run_time = iterator.get_next(datetime.datetime) print("next_run_time: %s" % next_run_time) duration_until_next_run_time = next_run_time - now print("duration_until_next_shutdown_time: %s" % duration_until_next_run_time) duration_of_one_hour = datetime.timedelta(hours=1) if duration_until_next_run_time <= duration_of_one_hour and values['State']['Code'] == EC2_STATUS_CODE_RUNNING: print("instance_to_shutdown.append(%s)" % instance_id) instances_to_shutdown.append(instance_id) if len(instances_to_shutdown) > 0:
ec2.stop_instances(InstanceIds=instances_to_shutdown)
print('stopped your instances: ' + str(instances_to_shutdown))
send_shutdown_notification(instances_to_shutdown, "STOPPED")

if len(instances_to_start) > 0:
ec2.start_instances(InstanceIds=instances_to_start)
print('started your instances: ' + str(instances_to_start))
send_start_notification(instances_to_start, "STARTED")

def send_shutdown_notification(instances, event):
instances_json_object = {"instances":instances, "event":event}
instances_json_string = json.dumps(instances_json_object)
instances_json_bytes = instances_json_string.encode('utf-8')

lambda_arn = os.environ['LAMBDA_NOTIFICATION_SHUTDOWN_ARN']
lambda_client = boto3.client("lambda")
lambda_client.invoke(
FunctionName=lambda_arn,
InvocationType='Event',
LogType='None',
Payload=instances_json_bytes
)

def send_start_notification(instances, event):
instances_json_object = {"instances":instances, "event":event}
instances_json_string = json.dumps(instances_json_object)
instances_json_bytes = instances_json_string.encode('utf-8')

lambda_arn = os.environ['LAMBDA_NOTIFICATION_START_ARN']
lambda_client = boto3.client("lambda")
lambda_client.invoke(
FunctionName=lambda_arn,
InvocationType='Event',
LogType='None',
Payload=instances_json_bytes
)

def get_instance_schedules(tag_name):
# When passed a tag key, tag value this will return a list of InstanceIds that were found.

ec2client = boto3.client('ec2')

response = ec2client.describe_instances(
Filters=[
{
'Name': 'tag-key',
'Values': [tag_name]
}
]
)
instancelist = {}
for reservation in (response["Reservations"]):
for instance in reservation["Instances"]:
tag_value = ''
for tag in instance['Tags']:
if tag['Key'] == tag_name:
tag_value = tag['Value']
break
instancelist[instance["InstanceId"]] = {'Schedule':tag_value,'State':instance['State']}

return instancelist

Get all All AWS Ec2 snapshop reports with python and boto3

Use this python script to get all EC2 snapshot report in your AWS account.

AWS EC2 snapshop report


import boto3
def lambda_handler(event, context):
session = boto3.Session(profile_name='saml')
ec2client = session.client('ec2')
instances_with_volumes = get_instance_ids(ec2client, "tc:OpsAutomatorTaskList")

for instance_id, volume_ids in instances_with_volumes.items():
response = ec2client.describe_snapshots(
Filters = [
{'Name':'volume-id', 'Values': volume_ids}
#{'Name':'start-time', 'Values': ['2019-01-01']}
]
#MaxResults = 10
)
#print(response['ResponseMetadata'])
#print("instance_id:%s, number_of_snapshots:%s" % (instance_id, len(response['Snapshots'])))
if len(response['Snapshots']) > 0:
#print(response['Tags'])
#Print Header
print('InstanceId' + ' , ' + 'Description' + ' , ' + 'Encrypted' + ' , ' + 'OwnerId' + ' , ' + 'Progress' + ' , ' + 'SnapshotId' + ' , ' + 'StartTime' + ' , ' + 'State' + ' , ' + 'VolumeId' + ' , ' + 'VolumeSize')
for snapshot in response['Snapshots']:
print(instance_id + ' , ' + snapshot['Description'] + ' , ' + str(snapshot['Encrypted']) + ' , ' + str(snapshot['OwnerId']) + ' , ' + snapshot['Progress'] + ' , ' + snapshot['SnapshotId'] + ' , ' + str(snapshot['StartTime']) + ' , ' + snapshot['State'] + ' , ' + snapshot['VolumeId'] + ' , ' + str(snapshot['VolumeSize']) )

def get_instance_ids(ec2client, tag_name):
# When passed a tag key, tag value this will return a list of InstanceIds that were found.

response = ec2client.describe_instances(
Filters=[
{
'Name': 'tag-key',
'Values': [tag_name]
}
]
)
instancelist = {}
for reservation in (response["Reservations"]):
for instance in reservation["Instances"]:

ebs_volume_ids = []
for ebs in instance['BlockDeviceMappings']:
ebs_volume_ids.append(ebs['Ebs']['VolumeId'])

instancelist[instance["InstanceId"]] = ebs_volume_ids

return instancelist

lambda_handler('','')

How to call a shell script from python code?

This is how to How to call a shell script from python code


import subprocess
subprocess.call(['sh shell_script.sh arguments'])


or





import sys, os
os.system("sh shell_script.sh arguments")

Output Example

Quicksort Algorithm Implementation with Python

QuickSort is an O(nlogn) efficient sorting algorithm, serving as systematic method for placing elements of an array in order. Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting. It is very similar to selection sort, except that it does not always choose worst-case partition.
Source: https://en.wikipedia.org/wiki/Quicksort
Below are 2 versions of the Quicksort Algorithm Implementation with Python. The first version is easy, but use more memory. The second version use the memory very efficiently.




I- QuickSort Algorithm Implementation with Python (Memory intensive version)

QuickSort Algorithm Implementation with Python method1

Output:

II- Quicksort Algorithm Implementation with Python (with Memory Optimisation)

III- QuickSort Algorithm Implementation with Python for Both Methods with duration captured

Output

III- Most Efficient Quicksort implementation in Python on array of  integer represented as string. Example: Array=[“1″,”237373737″,”3″,”1971771717171717″,”0”]

def QuickSort(array):
    return sorted(array, key=lambda x: (len(x),x))
input:
6
31415926535897932384626433832795
1
3
10
3
5
Output:
1
3
3
5
10
31415926535897932384626433832795

Just to clarify that lambda part, in case someone else doesn't understand how exactly string comparison works: '2' > '1' is True, but '2' > '10' is also True, as well as '2' > '1000'. That's why the strings are sorted by length first, because len('2') < len('10'). IV- Build up a sorted array, one element at a time. Print the array after each iteration of the insertion sort, i.e., whenever the next element has been inserted at its correct position
build up sorted array
Python build up sorted array
python build up sorted array input output
python build up sorted array input output

Binary Search Algorithm Implementation with Python

Binary Search  is an algorithm that finds the position of a target in a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation, particularly if the values in the array are not all of the whole numbers in the range.

Source: https://en.wikipedia.org/wiki/Binary_search_algorithm

Below the binary search algorithm implementation  with python:





#Test_Binary_Search.py
Array=[-2,1,0,4,7,8,10,13,16,17, 21,30,45,100,150,160,191,200]
Target=201
n=len(Array)
def binarySearch(A,T):
L=0
R=n-1
while (L <= R):
m=int((L + R)/2)
if ( A[m] < T ):
L = m +1
elif (A[m] > T):
R = m-1
else:
print("Target is at %s:" % m)
return m
print("Target not found")
return "unsuccessful"

binarySearch(Array, Target)

Binary Search Algorithm implementation with python

Script with hash tables on windows and Linux

How to declare and write a script with hash tables on windows and linux

  • Hash tables with powershell on windows

    Declaration:
    $states=@{“Alberta” = “Calgary”; “British Columbia” = “Vancouver”; “Ontario” = “Toronto” ; “Quebec” = “Montreal”}

    Name
    _____
    Value
    _______
    Alberta Calgary
    British Columbia Vancouver
    Ontario Toronto
    Quebec Montreal

    Add new key-value in hashtable:
    $states.Add(“Manitoba”,”Winnipeg”)

    Remove key-value in hashtable:
    $states.Remove(“Manitoba”,”Winnipeg”)
    Change value in hashtable:
    $states.Set_Item(“Ontario”,”Ottawa”)
    Retrieve value in hashtable:
    $states.Get_Item(“Alberta”)
    Find key in hashtable:
    $states.ContainsKey(“Alberta”)
    Find Value in hashtable:
    $states.ContainsValue(“Calgary”)
    Count items in hashtable:
    $states.Count
    Sort items by Name in hashtable:
    $states.GetEnumerator() | Sort-Object Name -descending
    Sort items by Value in hashtable:
    $states.GetEnumerator() | Sort-Object Value -descending

  • Hash tables with perl on linux or windows

     
    Declaration:
    my %hash = (); #Initialize a hash
    my $hash_ref = {}; # Initialize a hash reference. ref will return HASH
    Clear (or empty) a hash
    for (keys %hash)
    {
    delete $hash{$_};
    }
    Clear (or empty) a hash reference
    for (keys %$href)
    {
    delete $href->{$_};
    }
    Add a key/value pair to a hash
    $hash{ ‘key’ } = ‘value’; # hash
    $hash{ $key } = $value; # hash, using variables
    Using Hash Reference
    $href->{ ‘key’ } = ‘value’; # hash ref
    $href->{ $key } = $value; # hash ref, using variables
    Add several key/value pairs to a hash
    %hash = ( ‘key1’, ‘value1’, ‘key2’, ‘value2’, ‘key3’, ‘value3’ );
    %hash = (
    key1 => ‘value1’,
    key2 => ‘value2’,
    key3 => ‘value3’,
    );

    Copy a hash
    my %hash_copy = %hash; # copy a hash
    my $href_copy = $href; # copy a hash ref
    Delete a single key/value pair
    delete $hash{$key};
    delete $hash_ref->{$key};

  • Hash tables with python on linux or windows

    Hash tables are called dictionary in python.
    Declaration:
    dict = {‘Name’: ‘Zara’, ‘Age’: 7, ‘Class’: ‘First’}
    Accessing Values
    print “dict[‘Name’]: “, dict[‘Name’]
    print “dict[‘Age’]: “, dict[‘Age’]
    Output:
    dict[‘Name’]: Zara
    dict[‘Age’]: 7
    Updating Dictionary
    dict = {‘Name’: ‘Zara’, ‘Age’: 7, ‘Class’: ‘First’}

    dict[‘Age’] = 8; # update existing entry
    dict[‘School’] = “DPS School”; # Add new entry
    Delete Dictionary Elements
    #!/usr/bin/python

    dict = {‘Name’: ‘Zara’, ‘Age’: 7, ‘Class’: ‘First’}

    del dict[‘Name’]; # remove entry with key ‘Name’
    dict.clear(); # remove all entries in dict
    del dict ; # delete entire dictionary

Source:

  1. https://technet.microsoft.com/en-us/library/ee692803.aspx
  2. http://www.cs.mcgill.ca/~abatko/computers/programming/perl/howto/hash/
  3. http://www.tutorialspoint.com/python/python_dictionary.htm