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)

AWS Cert Solution Architect Associate PRO: SAA-C02

Download
QR-Code

AWS Cert Solution Architect Associate PRO: SAA-C02

Developer:
Etienne D. Noumen

Price:
$5.49

December 10, 2020December 10, 2020

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

September 10, 2019September 11, 2019

What is the programming model and best language for Hadoop and Spark? Python or Java?

Videoconferencing Apps: Zoom vs Teams vs Google Meet vs Slack

Hadoop is an open-source software framework for storing data and running applications on clusters of commodity hardware. It provides massive storage for any kind of data, enormous processing power and the ability to handle virtually limitless concurrent tasks or jobs. Apache Hadoop is used mainly for Data Analysis.

Apache Spark is an open-source distributed general-purpose cluster-computing framework. Spark provides an interface for programming entire clusters with implicit data parallelism and fault tolerance.

The question is Which programming language is good to drive Hadoop and Spark?

The programming model for developing hadoop based applications is the map reduce. In other words, MapReduce is the processing layer of Hadoop.
MapReduce programming model is designed for processing large volumes of data in parallel by dividing the work into a set of independent tasks. Hadoop MapReduce is a software framework for easily writing an application that processes the vast amount of structured and unstructured data stored in the Hadoop Distributed FileSystem (HDFS). The biggest advantage of map reduce is to make data processing on multiple computing nodes easy. Under the Map reduce model, data processing primitives are called Mapper and Reducers.

Spark is written in Scala and Hadoop is written in Java.

The key difference between Hadoop MapReduce and Spark lies in the approach to processing: Spark can do it in-memory, while Hadoop MapReduce has to read from and write to a disk. As a result, the speed of processing differs significantly – Spark may be up to 100 times faster.

In-memory processing is faster when compared to Hadoop, as there is no time spent in moving data/processes in and out of the disk. Spark is 100 times faster than MapReduce as everything is done here in memory.

Spark’s hardware is more expensive than Hadoop MapReduce because it’s hardware needs a lot of RAM.

Hadoop runs on Linux, it means that you must have knowldge of linux.

Java is important for hadoop because:

There are some advanced features that are only available via the Java API.
The ability to go deep into the Hadoop coding and figure out what’s going wrong.

In both these situations, Java becomes very important.
As a developer, you can enjoy many advanced features of Spark and Hadoop if you start with their native languages (Java and Scala).

What Python Offers for Hadoop and Spark?

Simple syntax– Python offers simple syntax which shows it is more user friendly than other two languages.
Easy to learn – Python syntax are like English languages. So, it much more easier to learn it and master it.
Large community support – Unlike Scala, Python has huge community (active), which we will help you to solve your queries.
Offers Libraries, frameworks and packages – Python has huge number of Scientific packages, libraries and framework, which are helping you to work in any environment of Hadoop and Spark.
Python Compatibility with Hadoop – A package called PyDoop offers access to the HDFS API for Hadoop and hence it allows to write Hadoop MapReduce program and application.

Hadoop is based off of Java (then so e.g. non-Hadoop yet still a Big-Data technology like the ElasticSearch engine, too – even though it processes JSON REST requests)
Spark is created off of Scala although pySpark (the lovechild of Python and Spark technologies of course) has gained a lot of momentum as of late.

If you are planning for Hadoop Data Analyst, Python is preferable given that it has many libraries to perform advanced analytics and also you can use Spark to perform advanced analytics and implement machine learning techniques using pyspark API.

The key Value pair is the record entity that MapReduce job receives for execution. In MapReduce process, before passing the data to the mapper, data should be first converted into key-value pairs as mapper only understands key-value pairs of data.
key-value pairs in Hadoop MapReduce is generated as follows:

Resources:

1- Quora

2- Wikipedia

3- Data Flair

January 8, 2019December 9, 2020

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

python build up sorted array input output

January 7, 2019January 9, 2019

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)