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]
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)
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:
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
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'
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
Python build up sorted arraypython build up sorted array input output
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.
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
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};
