DEV Community: Gopi Gorantala

Leetcode 238: Product Of Array Except Self

Gopi Gorantala — Thu, 12 Sep 2024 16:19:48 +0000

This problem looks simple to solve in linear time and space. This problem builds on some of the fundamental concepts of arrays.

Array traversals.
Prefix and Suffix sum.

Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe, and many more top tech companies.

Problem statement

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Test case#1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Test case#2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Understanding the problem

This problem looks simpler to solve in linear time and space, but it is tricky when writing the pseudocode or actual code implementation.

Illustration

Let us see what the results that are expected from a simple array containing 4 elements:

input = {1, 2, 3, 4}

So, the value at each index is the product of all the other elements in the array except the value itself. The following figure illustrates this.

Based on the above figure, we can come up with a formula. For any given index i, we can find the value using the product of the elements from o to (i - 1) plus product of elements from (i + 1) to (N - 1). This is illustrated in the following figure:

Thought process

Before writing pseudo code, come up with questions and ask the interviewer.

Should I be worried about duplicates?
What if the array is empty or has a single element? What are the expected results?
Should I consider/ignore 0 value in any of the indexes in the array? because all other values get 0 except the index containing 0.
What are the corner/edge cases for this problem?

Once you and the interviewer have discussed the above questions, devise various approaches to solving the problem.

Naive approach/brute-force.
Product of all elements.
Left and Right products.
Prefix and suffix sums.

Approach 1: Naive/Brute-force

Intuition

To employ the brute force approach, we must execute two for-loops. When the outer loop index matches the inner loop index value, we should skip the product; otherwise, we proceed with the product.

Algorithm

Initialize Variables:
- N = nums.length (length of the input array).
- result = new int[N] (array to store the results).
Outer Loop (Iterate through each element in nums):
- For i = 0 to N-1:Initialize currentProduct = 1.
Inner Loop (Calculate product for current element), for j = 0 to N-1:
- If i == j, skip the current iteration using continue.
- Multiply currentProduct by nums[j].
- Assign currentProduct to result[i].
Return result.

Code

// brute force
static int[] bruteForce(int[] nums) {
    int N = nums.length;
    int[] result = new int[N];

    for (int i = 0; i < N; i++) {
        int currentProduct = 1;
        for (int j = 0; j < N; j++) {
            if (i == j) {
                continue;
            }
            currentProduct *= nums[j];
        }
        result[i] = currentProduct;
    }
    return result;
}

Complexity analysis

Time complexity: O(n^2), for iterating the array twice in outer and inner loops.
Space complexity: O(n), for the auxiliary space (result[] array) we used.

Approach 2: Product of array ❌

One way most developers think is to run a product sum of all elements, divide the product sum by each array value, and return the result.

Pseudocode

// O(n) time and O(1) space
p = 1
for i -> 0 to A[i]
  p * = A[i]
for i -> 0 to (N - 1)
  A[i] = p/A[i] // if A[i] == 0 🤔 BAM error‼️

Code

// code implementation
static int[] productSum(int[] nums) {
    int product_sum = 1;
    for(int num: nums) {
        product_sum *= num;
    }

    for(int i = 0; i < nums.length; i++) {
        nums[i] = product_sum/nums[i];
    }
    return nums;
}

What if one of the array elements contain 0? 🤔

The value at all the indexes except the index containing 0 will definitely be infinity. Also, the code throws java.lang.ArithmeticException.

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.productSum(ProductOfArrayItself.java:24)
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.main(ProductOfArrayItself.java:14)

Approach 3: Find Prefix and Suffix product

Learn more about prefix and suffix sum in the Arrays Mastery Course on my website https://ggorantala.dev

Intuition & formulae's

Prefix and Suffix are calculated before writing an algorithm for the result. Prefix and Suffix sum formulae are given below:

Algorithm Steps

Create an array result of the same length as nums to store the final results.
Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
Calculate Prefix Products:
- Set the first element of prefix_sum to the first element of nums.
- Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i-1] and nums[i].
Calculate Suffix Products:
- Set the last element of suffix_sum to the last element of nums.
- Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element. For each index i, set suffix_sum[i] to the product of suffix_sum[i+1] and nums[i].
Calculate the result: Iterate through the input array nums.
- For the first element (i == 0), set result[i] to suffix_sum[i + 1].
- For the last element (i == nums.length - 1), set result[i] to prefix_sum[i - 1].
- For all other elements, set result[i] to the product of prefix_sum[i - 1] and suffix_sum[i + 1].
Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function usingPrefixSuffix(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = nums[0]
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i]

    // Calculate suffix products
    suffix_sum[N-1] = nums[N-1]
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i]

    // Calculate result array
    For i from 0 to N-1:
        If i == 0:
            result[i] = suffix_sum[i+1]
        Else If i == N-1:
            result[i] = prefix_sum[i-1]
        Else:
            result[i] = prefix_sum[i-1] * suffix_sum[i+1]

    Return result

Code

// using prefix and suffix arrays
private static int[] usingPrefixSuffix(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation
    suffix_sum[nums.length - 1] = nums[nums.length - 1];
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = suffix_sum[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index 
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * suffix_sum[i + 1];
        }
    }
    return result;
}

Complexity analysis

Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
- Calculating the prefix_sum products take O(n) time.
- Calculating the suffix_sum products take O(n) time.
- Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

Space complexity: The space complexity of the given code is O(n). This is because:
- The prefix_sum array requires O(n) space.
- The suffix_sum array requires O(n) space.
- Theresult array requires O(n) space. All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Optimization 🤩

For the suffix array calculation, we override the input nums array instead of creating one.

private static int[] usingPrefixSuffixOptimization(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation, in-place - `nums` array override
    for (int i = nums.length - 2; i >= 0; i--) {
        nums[i] = nums[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = nums[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * nums[i + 1];
        }
    }
    return result;
}

Hence, we reduced the space of O(n). Time and space are not reduced, but we did a small optimization here.

Approach 4: Using Prefix and Suffix product knowledge 🧐

Intuition

This is a rather easy approach when we use the knowledge of prefix and suffix arrays.

For every given index i, we will calculate the product of all the numbers to the left and then multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index i. Let's look at a formal algorithm that describes this idea more clearly.

Algorithm steps

Create an array result of the same length as nums to store the final results.
Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
Calculate Prefix Products:
- Set the first element of prefix_sum to 1.
- Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i - 1] and nums[i - 1].
Calculate Suffix Products:
- Set the last element of suffix_sum to 1.
- Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element.
- For each index i, set suffix_sum[i] to the product of suffix_sum[i + 1] and nums[i + 1].
Iterate through the input array nums.
- For each index i, set result[i] to the product of prefix_sum[i] and suffix_sum[i].
Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function prefixSuffix1(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = 1
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i-1]

    // Calculate suffix products
    suffix_sum[N-1] = 1
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i+1]

    // Calculate result array
    For i from 0 to N-1:
        result[i] = prefix_sum[i] * suffix_sum[i]

    Return result

Code

private static int[] prefixSuffixProducts(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    prefix_sum[0] = 1;
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i - 1];
    }

    suffix_sum[nums.length - 1] = 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i + 1];
    }

    for (int i = 0; i < nums.length; i++) {
        result[i] = prefix_sum[i] * suffix_sum[i];
    }

    return result;
}

Complexity analysis

Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
- Calculating the prefix_sum products take O(n) time.
- Calculating the suffix_sum products take O(n) time.
- Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

Space complexity: The space complexity of the given code is O(n). This is because:
- The prefix_sum array requires O(n) space.
- The suffix_sum array requires O(n) space.
- The result array requires O(n) space.

All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Approach 5: Carry Forward technique

Intuition

The carry forward technique optimizes us to solve the problem with a more efficient space complexity. Instead of using two separate arrays for prefix and suffix products, we can use the result array itself to store intermediate results and use a single pass for each direction.

Here’s how you can implement the solution using the carry-forward technique:

Algorithm Steps for Carry Forward Technique

Initialize Result Array:
- Create an array result of the same length as nums to store the final results.
Calculate Prefix Products:
- Initialize a variable prefixProduct to 1.
- Iterate through the input array nums from left to right. For each index i, set result[i] to the value of prefixProduct. Update prefixProduct by multiplying it with nums[i].
Calculate Suffix Products and Final Result:
- Initialize a variable suffixProduct to 1.
- Iterate through the input array nums from right to left. For each index i, update result[i] by multiplying it with suffixProduct. Update suffixProduct by multiplying it with nums[i].
Return the result array containing the product of all elements except the current element for each index.

Pseudocode

prefix products
    prefixProduct = 1
    For i from 0 to N-1:
        result[i] = prefixProduct
        prefixProduct = prefixProduct * nums[i]

    // Calculate suffix products and finalize result
    suffixProduct = 1
    For i from N-1 to 0:
        result[i] = result[i] * suffixProduct
        suffixProduct = suffixProduct * nums[i]

    Return result

Code

// carry forward technique
private static int[] carryForward(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // Calculate prefix products
    int prefixProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = prefixProduct;
        prefixProduct *= nums[i];
    }

    // Calculate suffix products and finalize the result
    int suffixProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }
    return result;
}

Explanation

Prefix Products Calculation:
- We initialize prefixProduct to 1 and update each element of result with the current value of prefixProduct.
- Update prefixProduct by multiplying it with nums[i].
Suffix Products Calculation:
- We initialize suffixProduct to 1 and update each element of result(which already contains the prefix product) by multiplying it with suffixProduct.
- Update suffixProduct by multiplying it with nums[i].

Complexity analysis

Time Complexity: O(n) time
Space Complexity: O(n) (for the result array)

This approach uses only a single extra array (result) and two variables (prefixProduct and suffixProduct), achieving efficient space utilization while maintaining O(n) time complexity.

A Guide To Master Bit Manipulation For Coding Interviews

Gopi Gorantala — Sun, 15 Oct 2023 13:58:27 +0000

You can find the complete Bit manipulation tutorial on my website for FREE.

🚀 https://www.ggorantala.dev/all-courses/.

This article will teach you the basics of the number system and bitwise operators.

Please check out my free course for detailed explanations, sketches, illustrations, and coding interview problems in 5 different languages, including C++, Java, Python, JavaScript, and TypeScript.

Number system

A number system is a writing system where digits and symbols are used consistently to represent values.

The exact sequence of symbols may represent different numbers in different number systems.

Mathematics has various types of number systems, like binary, decimal, octal, and hexadecimal.

Number System	Base	Used Digits
Binary	2	0, 1
Octal	8	0, 1, 2, 3, 4, 5, 6, 7
Decimal	10	0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Hexadecimal	16	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

Of all these number systems, decimal and binary are the most important for bit manipulation.

What is the binary number system?

Another number system that became famous after the decimal is the binary number system, which has only two digits, 0 and 1.

If a number system has n digits, we say that the base of the number system is n. So, the binary number system can also be called the base-2 number system.

Representation

Power of two	Binary	Decimal Value
2^0	0001	1
2^1	0010	2
2^2	0100	4
2^3	1000	8
2^4	0001 0000	16
2^5	0010 0000	32
2^6	0100 0000	64
2^7	1000 0000	128
2^8	0001 0000 0000	256
2^9	0010 0000 0000	512
2^10	0100 0000 0000	1,024

For example, 125 can be represented as 01111101 in the computer binary system. Anything in computer language gets converted into a binary number system.

What do binary numbers represent?

In mathematics and digital electronics:

A binary number is expressed in the base-2 or binary number system.
It uses only two symbols: typically “0” (zero) and “1” (one). The base-2 number system is a positional notation with a radix of 2. Each digit is referred to as a bit.

Binary counting

Binary counting follows the same procedure, except only the symbols 0 and 1 are available. Thus, after a digit reaches 1 in binary, an increment resets it to 0 but also causes an increment of the next digit to the left.

0000,

0001, (rightmost digit starts over, and next digit is incremented)

0010, 0011, (rightmost two digits start over, and next digit is incremented)

0100, 0101, 0110, 0111, (rightmost three digits start over, and the next digit is incremented)

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111,…

Binary to decimal conversion

In the binary system, each digit represents an increasing power of 2, with the rightmost digit representing 2⁰, the next representing 2¹, then 2², and so on. The value of a binary number is the sum of the powers of 2 represented by each “1” digit. For example, the binary number 100101 is converted to decimal form as follows:

1001012 = [ ( 1 ) x 2⁵ ] + [ ( 0 ) x 2⁴ ] + [ ( 0 ) x 2³ ] + [ ( 1 ) x 2² ] + [ ( 0 ) x 2¹ ] + [ ( 1 ) x 2⁰ ]

1001012 = [ ( 1 ) x 32 ] + [ ( 0 ) x 16 ] + [ ( 0 ) x 8 ] + [ ( 1 ) x 4 ] + [ ( 0 ) x 2 ] + [ ( 1 ) x 0 ]

1001012 = 3710

Bitwise Operators

In computer programming, a Bitwise operation operates on one or more bit patterns or binary numerals at the bit level.

They are fast and simple actions.
The processor directly supports them.
They are used to manipulate values for comparisons and calculations.
Bitwise operations are incredibly simple and faster than arithmetic operations.

Bitwise algorithms are used to perform operations at the bit level or to manipulate bits in different ways.

Bitwise operations are much faster and are sometimes used to improve the efficiency of a program.

Any indication of a bit’s position is counted from the right (least significant) side to the left.

Bitwise AND

Bitwise AND is the most commonly used logical Bitwise operator. It is represented by a sign (&).

AND operator is the same as the AND gate we studied in the chapter on digital electronics, as shown below:

The Bitwise AND operator is denoted by &. When an AND gate is given with two inputs, the corresponding output will be:

If two input bits are 1, the output is 1.
In all other cases, it's 0. For example
1 & 0 => yields to 0.
0 & 1 => yields to 0.
0 & 0 => yields to 0.

Let us visualize the steps in detail:

class AndOperation {
    public static void main( String args[] ) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise AND of (" + x + " , " + y + ") is: " + (x & y)); // yields to 8
    }
}

// Outputs: Bitwise AND of (12 , 10) is: 8

Bitwise OR

Bitwise OR is the most commonly used logical Bitwise operator. It is represented by a sign (|).

OR operator is the same as the OR gate we studied in the chapter on digital electronics, as shown below:

The Bitwise OR operator is denoted by |. When an OR gate is given with two inputs, the corresponding outputs will be:

If two input bits are 0, the output is 0.
In all other cases, it is 1. For example
1 | 0 => yields to 1.
0 | 1 => yields to 1.
1 | 1 => yields to 1.
So, Bitwise OR returns 1 if one of the inputs given is 1.

a	b	a \| b
0	0	0
0	1	1
1	0	1
1	1	1

a = 12
b = 10
---------------------------------
a in Binary : 0000 0000 0000 1100
b in Binary : 0000 0000 0000 1010
---------------------------------
a | b       :                   0
---------------------------------

class OROperation {
    private static int helper(int x, int y) {
        return x | y;
    }

    public static void main(String[] args) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise OR of " + x + ", " + y + " is: " + helper(x, y)); // yields to 14
    }
}

// Output : Bitwise OR of 12, 10 is: 14

Bitwise NOT

This introduces the tilde '~' character. This is applied to a single operand and inverts each input operand's bit. This is the same as the NOT gate we studied in the digital electronics chapter shown below:

a	~a
1	0
0	1

We already discussed the NOT operator and how it inverts each input bit.

Now let’s see in-depth how to represent the output of each input and its decimal equivalent.

As the name suggests, it takes the input number, considers its binary representation, and inverts every bit, which means the 0 bit becomes 1, and the 1 bit becomes 0.

Example:
Let’s consider x = 1;

The binary representation of x as follows:

x  = 00000000 00000000 00000000 00000001

Now, Bitwise NOT of x will be:

~x = 11111111 11111111 11111111 11111110

So,

x contains 31 zeros(0's) and one 1
~x contains 31 ones(1's) and one 0(zero)
So, how do we calculate the value of this? It is tough since we have 31 ones and 1 zero.
To guess the value, we must know how signed numbers are stored in a programming language.
Since we know Java integers have the range from -2^31 to 2^31-1, or -2,147,483,648 to 2,147,483,647.
In Java, positive numbers are stored by doing decimal to binary conversion.

For example, if we have the decimal number 3, then the binary is 11 with 30 0's on the left side. Nevertheless, negative numbers are stored in 2’s complement.

What is 2’s complement?

The rule of 2’s complement is:

If the leading bit on the left side is 0, then it is a positive number.
If the leading bit on the left side is 1, then it is a negative number.
When doing NOT operation on positive numbers, they become negative and vice-versa. Now, 2’s complement representation is

If we were given a negative number “-x”, its 2’s complement representation is "2^32 - x".

Formula

~x=(2^32 - x)

a =  1 => in Binary : 0000 0000 0000 0001

        ~a in Binary : 1111 1111 1111 1110
 ----------------------------------------

So,  a = 1 becomes -2(~a)

I can't give many details about 2's compliment here as this article size will last longer. The course explains everything.

class NOTOperation {
    public static void main( String args[] ) {
        int a = 1;
        System.out.println("Bitwise NOT of a is : " + ~a);
    }
}

//Output : Bitwise NOT of a is : -2

Bitwsie XOR

This operator is the same as the XOR gate that we studied in the digital electronics chapter, as shown below:

The Bitwise XOR operator is denoted by ^. When an XOR gate is given with 2 inputs, the corresponding outputs will be:

If two input bits are different, the output is 1.
In all other cases, it is 0.

1^1 => yields to 0
0^0 => yields to 0
1^0 => yields to 1
0^1 => yields to 1.

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

a = 12
b = 10
---------------------------------
a in binary : 0000 0000 0000 1100
b in binary : 0000 0000 0000 1010
---------------------------------
a ^ b       : 0000 0000 0000 0110
---------------------------------

class XOROperation {
    public static void main( String args[] ) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise XOR of (x , y) is : " + (x ^ y)); // yields to 6
    }
}

Bitwise Left, Right

A bit shift is a Bitwise operation where the order of a series of bits is moved, either to the left or right, to efficiently perform a mathematical operation.

A bit shift moves each digit in a number’s binary representation left or right. The bit-shifting operators do precisely what their name implies: they shift bits. Here is a brief introduction to the different shift operators.

Types

There are three main types of shifts:

Left shift: << is the left shift operator and meets both logical and arithmetic shifts’ needs.
Arithmetic/signed right shift: >> is the arithmetic (or signed) right shift operator.
Logical/unsigned right shift: >>> is the logical (or unsigned) right shift operator. > Note: <<< is not an operator because it would be redundant. These operators can be applied to integer values int, long, short, byte or char.

In some languages, applying the shift operators to any datatype smaller than int automatically resizes the operand to be an int.

Left shift

The left shift operator is written as <<.

Integers are stored in memory as a series of bits. For example, the number 6 stored as a 32-bit int would be:

6 = 00000000 00000000 00000000 00000110

Shifting this bit pattern to the left one position (6 << 1) would result in the number 12:

6 << 1 = 00000000 00000000 00000000 00001100

As you can see, the digits have shifted to the left by one position, and the last digit on the right is filled with a zero. You might also note that shifting left is equivalent to multiplication by powers of 2.

So,

6 << 1 → 6 * 2^1 → 6 * 2

6 << 3 → 6 * 2^3 → 6 * 8

A good optimization compiler will replace multiplications with shifts when possible.

32-bit representation

00000000 00000000 00000000 00000010 << 1  →  00000000 00000000 00000000 00000100

4-bit representation

0010 << 2  →  1000

As seen above, a single left shift multiplies a binary number by 2.

0010 << 1  →  0100

0010 is 2
0100 is 4

Formula

a << b = (a * 2^b)

class LeftShift {
    private static int helper(int number, int i) {
        return number << i;// multiplies `number` with 2^i times.
    }

    public static void main(String[] args) {
        int number = 100;

        System.out.println(number + " shifted 1 position left, yields to " + helper(number, 1));
        System.out.println(number + " shifted 2 positions left, yields to " + helper(number, 2));
        System.out.println(number + " shifted 3 positions left, yields to " + helper(number, 3));
        System.out.println(number + " shifted 4 positions left, yields to " + helper(number, 4));
    }
}

Logical right shifts

The logical right-shift operator is written as >>>.

Integers are stored in memory as a series of bits. For example, the number 12 stored as a 32-bit int would be:

12 = 00000000 00000000 00000000 00001100

When we shift it one position (12 >>> 1), the answer is 6.

12 >>> 1 = 12/2^1 = 12/2 = 6

The binary representation of the number 6 is as follows.

(12 >>> 1) = 00000000 00000000 00000000 00000110

Formula

a >>> b = a/2^b

Arithmetic right shift (>>)

Right shift

The right shift operator is written as >>.

Integers are stored in memory as a series of bits. For example, the number 6 stored as a 32-bit int would be:

6 = 00000000 00000000 00000000 00000110

Shifting this bit pattern to the right one position (6 >> 1) would result in the number 3:

6 >> 1 = 00000000 00000000 00000000 00000011

As you can see, the digits have shifted to the right by one position, and the last digit on the left is filled with a zero. You might also note that shifting right is equivalent to dividing by powers of 2.

So,

6 >> 1 => 6/2^1 = 6/2 = 3

6 >> 3 => 6/2^3 = 6/8 = 0

A good optimization compiler will replace division with shifts when possible.

1011 >> 1  →  1101
1011 >> 3  →  1111

0011 >> 1  →  0001
0011 >> 2  →  0000

The first two numbers had a 1 as the most significant bit, so more 1's were inserted during the shift. The last two numbers had a 0 as the most significant bit, so the shift inserted more 0's.

If a number is encoded using two’s complement, then an arithmetic right shift preserves the number’s sign, while a logical right shift makes the number positive.

// Arithmetic shift
1011 >> 1  →  1101    
    1011 is -5    
    1101 is -3

Formula

x >> y = x/2^y

class RightShift {
   private static int helper(int number, int i) {
        return number >> i;// divides `number` with 2^i times.
    }

    public static void main(String[] args) {
        int number = 100;

        System.out.println(number + " shifted 1 position right, yields to " + helper(number, 1));
        System.out.println(number + " shifted 2 positions right, yields to " + helper(number, 2));
        System.out.println(number + " shifted 3 positions right, yields to " + helper(number, 3));
        System.out.println(number + " shifted 4 positions right, yields to " + helper(number, 4));
    }
}

This concludes the basics of the bitwise operators. Please feel free to check my course on https://www.educative.io/courses/bit-manipulation. You can get up to 40% discount using https://www.educative.io/gopi. Or you can always visit the same course on my website for free.

Dynamic Arrays vs Traditional Arrays, With Illustrations and Examples

Gopi Gorantala — Wed, 26 Jul 2023 17:27:51 +0000

In this article, you will learn how to resize a static array. Most of the advanced and complex data structures are built on arrays.

Introduction

Arrays are fixed size. You need to specify the number of elements your array will hold ahead of time.

Converting an array from fixed size to resizing itself is the most common use-case for creating all complex data structures like ArrayList, growable arrays and many more. The other names of dynamic arrays are mutable arrays, resizable arrays etc.

A dynamic array resizes or expands when you add more elements than the capacity of the array.

Strengths

1. Fast lookups

Retrieving the element at a given index takes O(1) time, regardless of the array's length.

2. Array size

You can add as many elements as you need. There is no limitation. Dynamic arrays expand to hold them.

3. Cache friendly

Just like arrays, dynamic arrays place items right next to each other in memory, making efficient use of caches.

Weaknesses

1. Size doubling appends

Let us consider an array with a capacity of 5 elements.

But the elements we want to store in this array are more, which means we have to double the size, create a new array, copy the old array elements and add new elements, which takes O(n) time.

2. Costly inserts

Inserting an element at the end of the array takes O(1) time. But, inserting an element at the start/middle of the array takes O(n) time. Why?

If we want to insert something into an array, first, we have to make space by "scooting over" everything starting at the index we're inserting into, as shown in the image. In the worst case, we're inserting into the 0th index in the array (prepending), so we have to "scoot over" everything in the array.

That's O(n) time.

Inserting an element at the 2nd index and moving the rest of the element right shift each once. The resultant array becomes – { A, B, C, D, E }.

I recommend you read Array insertions and shifting algorithms(link below) with a clear explanation with code snippets and sketches to understand why these inserts are expensive at the start and middle.

3. Costly deletes

Deleting an element at the end of the array takes O(1) time, which is the best case. In computer science, we only care about the worse case scenarios when working on algorithms. But, when we remove an element from the middle or start of the array, we have to fill the gap by scooting over all the elements after it. This will be O(n) if we consider a case of deleting an element from the 0th index.

Deleting an element at the 3rd index and filling the gap by left-shifting the rest of the elements; the resultant array becomes – { A, B, C, D, E }.

Big-O worst-case time complexities

Operation	Worst-Case Time Complexity
Lookup/access a value at a given index	O(1)
Update a value at a given index	O(1)
Insert at the beginning/middle	O(N)
Insert at the end for dynamic array	O(N)
Insert at the end for Static array	O(1)
Append at the end	O(1)
Delete at the beginning/middle	O(N)
Delete at the end	O(1)
copying the array	O(N)

How To Convert Array to Dynamic/resizable array?

The previous lesson (How to implement array-like data structure) taught you how to create/implement an array-like data structure.

Converting an array from fixed size to resizing itself is the most common use-case for creating all complex data structures like ArrayList, growable arrays and many more. The other names of dynamic arrays are mutable arrays, resizable arrays etc.

Why resize an array in the first place?

Arrays have fixed sizes. If we were to make this fixed-size array into a dynamic array, it's doable but comes with a cost.

So why resize an array in the first place? Why can't we use the existing array?

One thing to keep in mind about arrays is that they're fixed size, which means you need to figure out how many elements they can hold before you start using them.

In other words, how to make this a dynamic array that resizes itself when the array is full.

This approach is expensive as it occupies extra memory. You will learn more about Memory Management later. This is just for your understanding, and traditionally this is how it's done for all the dynamic arrays, like List, HashMap, etc., in Java API.

A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time.

Thought process

Steps to develop an approach for an array that resizes itself when more items are added.

The dynamic array needs to resize itself.
We need to find a way to resize the array when the array is full.
Copy all the previous items from the old static array to the new dynamic array.
De-reference the old array and assign it to the new array. In practice, for each insert, we are incrementing the size variable. So let us check to see when an array is full.

if(size == data.length) {
  // array is full
}

With this knowledge, we can create a new array double the previous size.

int[] newData = new int[size * 2];

Copy all the previous items in the old array into the new dynamic array.

// copy all existing items
for (int i = 0; i < size; i += 1) {
    newData[i] = data[i];
}

With all these changes in place, insert method looks something like this:

public void insert(int element) {

    // if the array is full, resize it
    if (data.length == size) {
      // create a new array (twice the size)
      int[] newData = new int[size * 2];

      // copy all existing items
      for (int i = 0; i < size; i += 1) {
        newData[i] = data[i];
      }
      data = newData;
    }
    data[size] = element;
    size++;
  }

Code

Following is the Array, we constructed in How to implement array-like data structure article. The final code is as follows:

package dev.ggorantala.ds.arrays;

public class Array {
  private int[] data;
  private int size;

  public Array(int capacity) {
    data = new int[capacity];
    size = 0;
  }

  public void insert(int element) {

    // if the array is full, resize it
    if (data.length == size) {
      // create a new array (twice the size)
      int[] newData = new int[size * 2];

      // copy all existing items
      for (int i = 0; i < size; i += 1) {
        newData[i] = data[i];
      }
      data = newData;
    }
    data[size] = element;
    size++;
  }

  public boolean isOutOfBounds(int index) {
    return index < 0 || index >= size;
  }

  public void remove(int index) {
    if (isOutOfBounds(index)) {
      throw new IndexOutOfBoundsException();
    }

    for (int i = index; i < size; i += 1) {
      data[i] = data[i + 1];
    }
    size--;
  }

  public int get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    return data[index];
  }

  public int size() {
    return size;
  }

  public void print() {
    for (int i = 0; i < data.length; i += 1) {
      System.out.print(data[i] + ", ");
    }
  }
}

Dynamic array execution class

Let us create an array with capacity as 4 and insert 9 numbers in it, the size of the array becomes 16.

Code

Following is the execution class

package dev.ggorantala.ds.arrays;

public class DynamicArrayExecution {
    private static final int[] INPUT = new int[] {1, 2, 3, 4, 5, 6, 7, 11, 9};

    public static void main(String[] args) {
        Array array = new Array(4);
        for (int value : INPUT) {
            array.insert(value);
        }

        array.remove(2); // removed element `3` from array

        System.out.println(array.get(0)); // 1
        System.out.println(array.size()); // 8

        // The extra o's are because of the array capacity which is 16
        array.print(); // 1, 2, 4, 5, 6, 7, 11, 9, 0, 0, 0, 0, 0, 0, 0, 0
    }
}

Illustrations & Explanation

We gave our array-like data structure with 9 elements {1, 2, 3, 4, 5, 6, 7, 11, 9}, But we initialized the size to 4 using Array array = new Array(4);.

A simple illustration is as follows:

So our array is ready to be loaded with input data. Our array instance size is 4, but we are inputting an array containing 9 elements.

private static final int[] INPUT = new int[] {1, 2, 3, 4, 5, 6, 7, 11, 9};

After adding the first 4 elements from the input array, our array has reached its maximum capacity. Now the insert method doubles the array size and adds the next round of 4 elements. The following illustration explains.

After adding the first 8 elements from the input array, our array has reached its maximum capacity again. Now the insert method doubles the array size and adds the next round of 1 elements from the input array. The following illustration explains.

The insert method doubles its size when the array is not sufficient, and there are extra elements to add. So the size increases from 4 to 8, then from 8 to 16.

Note: Do not get confused about the size variable and how it's doubling itself. Check the insert method that does this trick when the array is full. This is the reason you are seeing extra zeros for print() method in above code.

This concludes the dynamic array topic. In the next lessons, you will learn about the 2-Dimensional arrays with illustrations and sketches detailing indexes.

What Are SOLID Design Principles

Gopi Gorantala — Tue, 25 Jul 2023 04:38:11 +0000

SOLID is an acronym for the first five Object-Oriented design (OOD) principles by Robert C. Martin.

Introduction

SOLID principles are intended to make the software more understandable, flexible, scalable and maintainable.

These are not design patterns, but design principles for effective object-oriented design while designing a class structure.

This is generally asked in Java Senior Coding Interviews. Sadly developers don't care about them until they appear for an interview.

Design principles

The 5 design principles are:

Single Responsibility Principle (Keeping components laser focused).
Open-Closed Principle (Evolving code without modifying existing components).
Liskov Substitution Principle (Generating correct relationships between types).
Interface Segregation Principle (Modularizing abstractions).
Dependency Inversion Principle (Decoupling Components) Learning and knowing these principles will help you design a solid object-oriented software product. Most developers apply them to software components and microservices to build robust and maintainable software.

Each principle is intended to address a different aspect of software design and development, but together they form a comprehensive set of guidelines for building high-quality, flexible software.

Importance of software design principles

They promote good design practices and help developers create flexible, maintainable, and easy-to-understand software.

Java is an object-oriented language, which means that it is designed to model real-world objects and their relationships.

The SOLID principles are guidelines that can help developers create more effective and efficient object-oriented code.

By following the SOLID principles in Java programming, developers can:

Create more modular code: Each SOLID principle promotes modularity by separating concerns and responsibilities. This makes it easier to change and maintain the code over time.
Improve code quality: SOLID principles encourage best practices such as encapsulation, abstraction, and polymorphism. These practices help to create more reusable code.
Promote code reusability: SOLID principles encourage the creation of interfaces and abstract classes, which can be used to define common functionality that can be reused across different parts of the codebase.
Increase code maintainability: SOLID principles make it easier to identify and isolate problems in the code, making it easier to maintain and update.

Overall, following the SOLID principles can help Java developers create software that is more effective, efficient, and maintainable, leading to better software development practices and better software products.

Advantages

Increased maintainability: SOLID principles promote writing code that is easier to maintain and modify over time.
Improved scalability: SOLID principles help write code handling increased complexity as the application grows.
Better code reuse: SOLID principles lead to writing more modular, reusable, and easily testable code.
Enhanced collaboration: SOLID principles make it easier for developers to understand and work with each other's code.

Disadvantages

Steep learning curve: Adopting SOLID principles requires a deep understanding of object-oriented programming, which may be challenging for some developers.
Overhead: Applying SOLID principles may require more time and effort during development.
Rigidity: Strictly adhering to SOLID principles can lead to overly complex code that is difficult to understand and modify.
Inflexibility: SOLID principles are guidelines, not strict rules, but some developers may treat them as such, leading to inflexible code.Introduction

How To Construct An Array-Like Data Structure?

Gopi Gorantala — Tue, 25 Jul 2023 04:13:32 +0000

You will learn to implement a custom array-like data structure and basic array operations.

Introduction

Before you start solving array problems, understanding and implementing an array-like data structure is a good practice.

This lesson teaches you how to implement common array operations, such as inserting an element, removing an element, getting an element, finding the length of the array, and printing elements of the array.

What are we building?

We are going to build an array from scratch that contains some of the most common array operations, as discussed above.

We will also learn how to convert the fixed-size array into a dynamic array by tweaking a method. This is the concept of dynamic arrays: LinkedList, ArrayList, and a few more complex data structures.

Every requirement in software is divided into pieces, we work on each piece, and finally, we bring them all together. So let's break down the requirements.

Problem statement

Build an array from scratch and store elements in it. The array should allow inserting, deleting, getting, and printing elements.

Input:
CREATE -> 10 // create an array with capacity 10
INSERT -> {1, 2, 3, 4, 5} // insert these elements
DELETE -> 2 // remove 2nd index element
GET -> 0 // print 0th element
SIZE -> `.size()` // should print how many items currently an array has
PRINT -> // print all elements shown in output

Output: 
{1, 2, 4, 5, 0, 0, 0, 0, 0, 0}

Requirements breakdown

When asked a question or given a problem, write down the requirements on paper.

Our requirements are:

Create an array.
The array should have the following methods.
- insert()
- remove()
- get()
- size()
- print()
Make the array resizable automatically (covered in next article release).
Error handling (optional, but it adds value when you work with the interviewer in building an array). We have our requirements. Let's break down the problem.

Always break the problem into smaller chunks. It will be easy to build smaller parts and combine them to complete the requirement.

Array Construction

Creating an array

Create an array with two fields/properties int[] data and size. A constructor to initialize the array size.

public class Array {
  private int[] data;
  private int size;

  public Array(int capacity) {
    data = new int[capacity];
    size = 0;
  }
}

We initialized size = 0, for our zero index-based arrays. When we insert elements into an array, we are inserting them from the index 0.

We created a base Array class, we need to write some of the basic array operations we need to perform on the custom array data structure we created.

Insert an element

We need to write a method that inserts items into our array.

public void insert(int element) {  
  data[size] = element;  
  size += 1;  
}

Or you can use specify the short-hand syntax:

public void insert(int element) {  
  data[size++] = element; 
}

We initialized the array size with 0 in the constructor. So the first element gets stored in 0th index.

When we call data[size] = element, we are storing an item in the array right at the 0th index.

In the next line, we have size += 1, which increments the size variable from 0 to 1. So the next item gets stored in the next slot.

What if we want to insert elements in the middle index or starting index? do we need to replace that element in that slot? or should we shift the elements and insert an element in the slot?

In the upcoming lessons, you will learn how to write shifting algorithms in an array to insert elements.😅

Remove an element at a specific index

Our array-like data structure should handle removing items.

What if the index provided to the remove() method is either negative or more than the size of the array? We run into ArrayIndexOutOfBoundsException.

If the index provided is either negative or more than the size of the array, we purposefully throw IndexOutOfBoundsException(). Or we can add a message to our logger by providing the error message that prints on the console or application logs.

if (index < 0 || index >= size) {  
  throw new IndexOutOfBoundsException();
}

After our error handling is in place, we can remove an element from the index and shift all the array elements to the left.

Anything else we need to take care of? We need to decrement the size variable value by 1 using size--.

With all these changes in place, remove() method looks like this:

public void remove(int index) {  
  if (index < 0 || index >= size) {  
    throw new IndexOutOfBoundsException();  
  }

  for (int i = index; i < size; i += 1) {
    data[i] = data[i + 1];
  }
  size--;  
}

So why are we shifting elements?

Suppose we want to delete/remove elements in the middle or starting index? as discussed above. In that case, we need to delete the element from the given index and shift all the right elements to the left by one position to fill the deleted slot.

In the upcoming lessons, you will learn how to write shifting algorithms in an array. 😅

Get an item at a specific index

This is no different from the above explanation. We need to check if the given is either negative or more than the size of the array. In either case, we run into ArrayIndexOutOfBoundsException.

The method looks like this:

public int get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }

  return data[index];
}

Size of array

This is quite straightforward. In all the array operations, we decrement the size when we need to remove/delete an element and increment the size when we add a new element to the array. So returning the size directly gives us the result.

public int size() {  
  return size;  
}

Print array items

A simple for-loop to iterate through all the array elements and display them.

public void print() {
  for (int i = 0; i < data.length; i += 1) {
    System.out.println(data[i]);
  }
}

The same code with enhanced for-loop is:

public void print() {
  for (int el : data) {
    System.out.println(el);
  }
}

Final-look at our custom array-like DS

All these smaller chunks are combined, and the final array we built is:

package dev.ggorantala.ds.arrays;

public class Array {
  private int[] data;
  private int size;

  public Array(int capacity) {
    data = new int[capacity];
    size = 0;
  }

  public void insert(int element) {
    data[size] = element;
    size++;
  }

  public boolean isOutOfBounds(int index) {
    return index < 0 || index >= size;
  }

  public void remove(int index) {
    if (isOutOfBounds(index)) {
      throw new IndexOutOfBoundsException();
    }

    for (int i = index; i < size; i += 1) {
      data[i] = data[i + 1];
    }
    size--;
  }

  public int get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    return data[index];
  }

  public int size() {
    return size;
  }

  public void print() {
    for (int i = 0; i < data.length; i += 1) {
      System.out.print(data[i] + ", ");
    }
  }
}

Array execution class

Let us create an array with capacity as 10 and insert 5 numbers in it, the size of the array becomes 5.

Illustration's

A simple illustration is as follows:

Another illustration that clarifies the difference between capacity and size of the array.

What do you think is stored in the index 5 to index 9? The answer is zeros.

So 0's are stored from the index 5 to 9. So when you access A[6] you get 0, for A[2] you get 3, and so on.

In the above, we have constructed an Array class and basic operations insert, remove, get, and size etc. Let us test each of the methods to ensure nothing is breaking in our code.

Code

Following is the execution class

package dev.ggorantala.ds.arrays;

public class ArrayExecution {
  private static final int[] INPUT = new int[] {1, 2, 3, 4, 5};

  public static void main(String[] args) {
    Array array = new Array(10);
    for (int value : INPUT) {
      array.insert(value);
    }

    array.remove(2); // removed element `3` from array

    System.out.println(array.get(0)); // 1
    System.out.println(array.size()); // 4

    // The extra o's are because of the array capacity which is 10
    array.print(); // 1, 2, 4, 5, 0, 0, 0, 0, 0, 0
  }
}

Explanation

Array array = new Array(10); creates an array with a capacity 10.

The input array we declared holds 5 elements.

private static final int[] INPUT = new int[] {1, 2, 3, 4, 5};

Using a simple for-loop, we are storing the INPUT data into our newly created array instance variable.

for (int value : INPUT) {
  array.insert(value);
}

We removed an element at the index 2 using array.remove(2);.

Finally, we called get, size and print methods to display data on the console.

Hurrah! You just implemented your first data structure in computer science and successfully tested it.

SOLID: Single Responsibility Principle With Examples

Gopi Gorantala — Sun, 23 Jul 2023 07:40:20 +0000

In this article, you will learn about the following:

What is SRP?
Importance of SRP in software development
Strengths
Weaknesses
Twitter Registration

What is SRP?

The Single Responsibility Principle (SRP) is one of the five SOLID design principles that guide software development.

Definition: A class or module should have only one reason to change.

The principle states that a class should have only one reason to change and one responsibility. This principle is intended to promote modularity and help developers create easier code to understand, modify, and maintain.

In essence, the SRP states that each class should have a single, well-defined responsibility and that responsibility should be encapsulated within that class.

This means that a class should not have multiple responsibilities, as this can make it harder to understand and modify. By following the SRP, developers can create more maintainable and flexible code that is easier to work with over time.

The SRP is a fundamental principle in object-oriented programming, and it can significantly impact the quality and effectiveness of software development. We will explore the SRP in more detail, including how it works, why it is important, and how to apply it effectively in Java programming.

Importance of SRP in software development

There are several reasons why SRP is important in software development:

Enhances code readability: Reading and understanding the code becomes easier when each class or module has a single responsibility. This helps developers quickly understand the purpose of the class or module and its relationship with other parts of the system.
Increases code maintainability: By breaking down complex functionality into smaller, more focused modules, SRP enables developers to make changes to the code more easily without affecting other parts of the system. This means that maintenance and troubleshooting of the code become less time-consuming and costly.
Facilitates code reuse: Code that adheres to SRP is often more modular and reusable. This means developers can easily reuse the code in other parts of the system or projects.
Improves system scalability: Maintaining a single responsibility for each class or module becomes increasingly important as the codebase grows. SRP ensures that the codebase remains scalable and can easily accommodate changes or new features without impacting the rest of the system.

Overall, adhering to the Single Responsibility Principle improves the quality and maintainability of the codebase, making it easier to manage, test, and deploy.

Advantages

The advantages of following the Single Responsibility Principle (SRP) include the following:

Better code organization and maintainability.
Improved readability and understanding of code.
Easier debugging and testing of code.
A higher degree of code reusability.
Facilitation of parallel development and implementation of new features.
Ability to make changes to code with less risk of introducing bugs.

Disadvantages

Some of the disadvantages of the Single Responsibility Principle (SRP) include the following:

Increased complexity, as a system may require more classes to implement the same functionality.
Potential for over-engineering, leading to too much abstraction and unnecessary code.
Difficulties in determining the appropriate granularity of responsibilities.
Challenges in balancing the trade-off between separating responsibilities and maintaining performance.

When programmers try to add features or new behaviour to a software product, they frequently integrate everything within the current class. When something needs to be changed later, due to the complexity of the code, the code refactor process is extremely time-consuming and tedious.

The Single Responsibility Principle helps us create simple classes that perform just one task. This helps make modifications or adding extensions to the existing code much more effortless.

Twitter Registration Using Single Responsibility Principle

We design Twitter registration software with the help of the single responsibility principle that contains a notification service, database repository, account service, and execution class.

Let's implement the first design principle on Twitter registration flow.

🔐 Signup process on Twitter

Consider a use case where a user wants to register with Twitter. The steps Twitter takes to register are user are:

Twitter asks users to register with signup forms.
Twitter stores the user object in their database, which contains User details - email, name, password, and other metadata etc.
Twitter sends a welcome message to the user.

Let us declare a class that does the above steps.

public class TwitterRegistration {
    public void register() {
        // step 1
        System.out.println("Fill signup form");

        // step 2
        System.out.println("Store account details in database");

        // step 3
        System.out.println("Send a welcome message");
    }
}

We are creating an account on Twitter, and the three steps should be handled separately. But the above class declared them all in a single TwitterRegistration class. Isn't this a violation of SRP?

Also, step 2 of storing an object in the database requires additional work to open a connection with the database, authenticate the handshake, and store the user object. This is insertion logic and should be handled separately.

The third step is sending out a welcome message to the user, which should be handled by NotificationService, separately.

Using the SRP principle, we divide the above TwitterRegistration class into three different classes, each having a single and only one responsibility.

Refactoring for SRP

Refactoring TwitterRegistration the class gives:

// Notification Service
class NotificationService {
    public void sendNotification() {
        // step 3
        System.out.println("Send out welcome message");
    }
}

// Database handshakes
class AccountRepository {
    public void createUser() {
        // step 2
        System.out.println("🔐 Auth Success!");
        System.out.println("Store user data into database");
    }
}

// Account Registration
class TwitterAccountRegister {
    public void registerUser() {
        // step 1
        System.out.println("fill account internal details");
    }
}

Finally, after refactoring the above classes. We first allow the TwitterAccountService to create a couple of objects for AccountRepository and NotificationService to register users with Twitter.

// Execution Class or Main class
public class TwitterAccountRegister {
    public static void main(String[] args) {
        TwitterAccountService service = new TwitterAccountService();
        service.registerUser();
    }
}

// Account Registration Service
class TwitterAccountService {
    AccountRepository repository = new AccountRepository();
    NotificationService notificationService = new NotificationService();

    public void registerUser() {
        // step 1
        System.out.println("fill account internal details");

        repository.createUser();
        notificationService.sendNotification();
    }
}

// Notification Service
class NotificationService {
    public void sendNotification() {
        // step 3
        System.out.println("Send out welcome message");
    }
}

// Database handshakes
class AccountRepository {
    public void createUser() {
        // step 2
        System.out.println("🔐Signup Success!! Registered");
        System.out.println("Store user data into database");
    }
}

/*
Outputs:
fill account internal details
🔐Signup Success!! Registered
Store user data into database
Send out welcome message
*/

In above TwitterAccountService is doing all three tasks. The primary responsibility is to fill in account details in account details and delegate the other responsibilities to other classes.

Finally, we know many teams work on the same software product.
By following the SRP principle, if we see file changes in Github for a file named TweetAnalytics, we can be sure that the changes incorporated are related to analytics. This helps version control with ease.

Conclusion

In conclusion, the Single Responsibility Principle (SRP) is a software design principle that states that every class should have only one reason to change.

Following SRP makes code easier to understand, maintain, and extend. It reduces the risk of introducing bugs and makes it easier to test individual components in isolation.

SRP encourages the separation of concerns, making the code more modular and scalable. This principle is one of the five SOLID principles of object-oriented design and is an important aspect of creating clean, maintainable, and scalable code.

You will get the complete written notes @ https://www.ggorantala.dev/

Array Strengths, Weaknesses, Insertion & Deletion Algorithms With Big-O

Gopi Gorantala — Sat, 22 Jul 2023 03:25:06 +0000

Arrays are fundamental data structures in computer science and programming, offering a range of strengths, weaknesses, and Big-O complexities that impact their efficiency and usability.

Understanding the characteristics of arrays is crucial for choosing the right data structure for specific tasks and optimizing program performance.

In this article, we delve into arrays' strengths, weaknesses, and Big-O complexities. We explore the benefits arrays provide, such as random and sequential access, simplicity of implementation, and cache-friendliness. Simultaneously, we address their limitations, including a fixed size, insertion, and deletion operations challenges, and inflexibility.

Additionally, we discuss the time complexities associated with common array operations, such as access, search, insertion, deletion, and resizing. By gaining insights into these aspects, programmers can make informed decisions when utilizing arrays and effectively balance trade-offs between efficiency and functionality in their applications.

Strengths

There are many advantages to using arrays, some of which are outlined below:

Fast lookups (random access)
Fast appends
Simple implementation
Cache friendliness

1. Fast lookups (Random access)

Retrieving the element at a given index takes O(1) time, regardless of the array's length.

For example:

int[] A = {-1, 7, 9, 100, 1072};

The array has five elements, and the length of the array is calculated using, A.length, which is 5. As arrays are zero indexed, the last element is accessed using A[A.length - 1] which is A[4] as shown in the following sketch.

If we access array elements using the index, like A[0] or A[4], it takes a single unit of time or, in big-o terms, constant operation.

A[0]; // -1
A[3]; // 100
A[4]; // 1072
A[5]; // Index out of bounds exception, as there is no A[5] value.

All of the above operations consume a single unit of time which is O(1) time.

2. Fast appends

Adding a new element at the end of the array takes O(1) time if the array has space.

Let us create an array with a capacity 5 and insert values 100 and 101 at indexes 0 and 1.

The following code explains it.

int[] A = new int[5];

A[0] = 100;
A[1] = 101;

Now if we were to insert a new value into the array, we could do A[2] = 200. Which inserts value 200 at the index 2. This operation consumes a single unit of time which is constant.

This is the reason the appends at the end are fast.

Enough talk. Here is a simple algorithm that creates an array with a size 5, and inserts 100, 101 values into the array. Finally, we insert an element at the array length.

import java.util.Arrays;

public class ArrayAppends {
  public static void main(String[] args) {
    int[] A = new int[5];
    int currentLength = 0;

    // Let us add 2 elements to the array
    for (int i = 0; i < 2; i++) {
      A[i] = i + 100;
      currentLength++; // when i=1, length is set to 2
    }

    System.out.println(Arrays.toString(A)); // [100, 101, 0, 0, 0]
    System.out.println("current array items length " + currentLength); // 2
    System.out.println("Array capacity " + A.length); // 5
    System.out.println(
        "Element insert at end "
            + Arrays.toString(insertAtEnd(A, currentLength))); // [100, 101, 200, 0, 0]
  }

  // Inserting element at the end
  public static int[] insertAtEnd(int[] A, int currentLength) {
    A[currentLength] = 200;
    return A;
  }
}

/* 
Outputs:
[100, 101, 0, 0, 0]
current array items length 2
Array capacity 5
Element insert at end [100, 101, 200, 0, 0]
*/

3. Simple Implementation

Arrays have a straightforward implementation in most programming languages, making them easy to understand and use.

4. Cache Friendliness

Elements in an array are stored contiguously in memory, which improves cache performance and can lead to faster access times.

Weaknesses

There are some dis-advantages of using arrays, some of which are outlined below:

Fixed size.
Memory unused or wasted.
Size doubling.
Costly inserts
Costly deletes

1. Fixed-size

Arrays have a fixed size defined at the time of creation. Adding or removing elements beyond the initial size requires creating a new array and copying the existing elements, which can be inefficient.

You need to specify how many elements you will store in your array ahead of time. (Unless you're using a fancy dynamic array).

int[] A = new int[5]; // contains 5 elements

2. Memory unused or wasted

If an array's size is larger than the number of elements it contains, memory is wasted.

Imagine an array with a capacity of 5. We have two elements to store in this array, and then we are wasting three unfilled cells and a waste of memory, which means 3*(4 bytes) = 12 bytes of memory is wasted (integer takes 4 bytes).

3. Size doubling

Let us consider an array with a capacity of 5 elements. But the elements we want to store in this array are more, which means we have to double the size, create a new array, copy the old array elements and add new elements. The time complexity is O(n).

You will learn how to double the array size in the next lessons.

4. Costly inserts

Inserting/appending an element at the end of the array takes O(1) time. We have seen this in the strengths(fast appends).

But, inserting an element at the start/middle of the array takes O(n) time. Why? 🤔

Inserting an element at the 2nd index and moving the rest of the element right shift each once. The resultant array becomes – { A, B, C, D, E }.

In the next lessons, you will learn more about insertion and shifting algorithms, with clear explanations, code snippets, and sketches to understand why these inserts are expensive at the start and middle.

5. Costly deletes

Deleting an element at the 3rd index and filling the gap by left-shifting the rest of the elements; the resultant array becomes – { A, B, C, D, E }.

Big-O Complexities

Operation	Complexity	Explanation
Lookup/Access a value at a given index	O(1)	Accessing an element by its index is a constant-time operation.
Search an element in an array	O(N)	Searching for a specific element in an unsorted array requires iterating through each element in the worst case.
Update a value at a given index	O(1)	Updating any element at any given index is always constant time.
Insert at the beginning/middle	O(N)	Inserting an element at the beginning or middle of the array requires shifting the existing elements, resulting in a linear time complexity.
Append at the end	O(1)	If the array has space available, inserting an element at the end takes constant time.
Delete at the beginning/middle	O(N)	Deleting an element from the beginning or middle of the array requires shifting the remaining elements, resulting in a linear time complexity.
Delete at the end	O(1)	Deleting the last element of an array can be done in constant time.
Resize array	O(N)	Resizing an array requires creating a new array and copying the existing elements, which takes linear time.

The the Big-O complexities mentioned above are for basic operations and assume an unsorted array. Some specialized data structures, such as Heaps or HashTable's, can provide more efficient alternatives for specific use cases.

In the next lessons, you will learn more about array capacity vs. length, insertions, and deletion algorithms. They are the simplest yet most powerful and helps you when working on array problems.

Array Data Structure: With Sketches and Examples

Gopi Gorantala — Wed, 19 Jul 2023 13:32:20 +0000

Introduction

Arrays are built in most programming languages. They are the most fundamental data structures of all in computer science. Arrays are the building blocks for many other, more complex data structures.

Why do we need an array to store elements? Why can't we make use of int primitive type?

Why not make use of primitives?

In Java int takes 4 bytes. So the declaration below occupies 4 bytes of memory.

int a = 100;

What if we want to store six int values (or 24 bytes)? We need to use six different variables individually, each occupying 4 bytes so that the total will be 6 * 4 = 24 bytes.

// each of the following occupies 4 bytes, which is 6 * 4 bytes
int a1 = 100;
int a2 = 200;
int a3 = 300;
int a4 = 400;
int a5 = 500;
int a6 = 600;

Creating six different variables is a bit dirty and not a good idea. What if we wanted to store a million entries, are we supposed to create a million different variables? 😢 Isn't this bad coding?

Instead, we store the million items in an array sequentially in an int[] array. This can be achieved easily by following the declaration and initialization with values.

int[] array = {100, 200, 300, 400, 500, 600};

Isn't the array beautiful? 🤩

What is an array?

In Java and many other languages, arrays are static(fixed size). Array organizes items sequentially, one after another, in memory.

The items could be Integer, String, Object, – anything. The items are stored in contiguous (adjacent to each other) memory locations.

Each position in the array has an index, starting at the 0th index. In Java, integers take 4 bytes, so the memory addresses of each adjacent element are added by 4 bytes.

Sketch

A simple sketch of this is as follows.

If we say our array memory, location/address starts from 100, then the following integer address will start from 104(100+4) bytes, and so on.

In the above illustration/figure, we have an array with 6 elements in it, with a memory address pointed from 100 to 120. So theoretically, anything that we store after this array takes the address from 124.

Note: In Java, we have to specify the size of the array ahead of time before initializing the array.

We knew everything on the computer is stored in bits 0 or 1. Let us see how these array numbers from the above sketch are stored in memory and addressed in binary.

Declaration and initialization

Consider an array A[] that has 5 elements. To access the last element of the array, we use A[4].

With this knowledge, if N is the array length, then (N-1) is how we access the last element. There are two ways we can declare and initialize the array in Java.

What happens if we declare an array as follows?

int[] A = new int[3]; 
// stores 3 items, capacity = 3 and size is 0(no items added, so far)

System.out.println(Arrays.toString(A)); // [0, 0, 0]

Initially, we did not add any items to the array, so the array values are defaulted to 0 as seen above.

Let us see another way where we declare and initialize the array.

// approach 1
int[] A = new int[5];

A[0] = 1;
A[1] = 2;
A[2] = 3;
A[3] = 4;
A[4] = 5;

// approach 2
int[] A = {1, 2, 3, 4, 5};

Arrays with char datatype and String class is as follows.

// String arrays
String[] fruits = new String[3]; // contains 3 strings

// char arrays
char[] chars = new char[256]; // contains 256 items

This small illustration helps you understand how we access array elements using their indexes.

How to access elements?

Following is a simple sketch of an array A with a capacity N.

Since arrays in Java starts from 0th index. If you want to access the first element, you need to give A[0], and A[1] for accessing the second element, and so on A[N-1] to access the last element.

What happens if we do A[-100], A[N], and A[N+1]? 🤔

You guessed it. We run into ArrayIndexOutOfBoundsException.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100 out of bounds for length 5
    at array.ArrayIntroduction.main(ArrayIntroduction.java:20)

At most, we can access the last element of the array using A[N-1].

How to print array elements

A simple snippet to print the array elements from 0 to (N-1) index.

public class PrintElements {
    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 5};

        int N = A.length;

        for (int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }
    }
}

The time and space complexity to print these array elements are:

Time complexity - O(N) - We iterated over all the array elements of size N, so the time complexity is linear.

Space complexity - O(1) - No algorithmic memory is used here. We just used the input A[] memory, hence Constant time.

Capacity vs Length

How long is an array?

If someone asks you how long an array is, there could be two possible answers when discussing how long an array is.

How many items can an array hold, and
How many items currently an array has?

The first point is about capacity, and the second is about length.

Let us create an array A[10] whose capacity is 10, but no items are added. Technically we can say the length is 0.

int[] A = new int[10];

Let's insert integers 1, 2, 3, and 4 into the above array.

A[0] = 1;
A[1] = 2;
A[2] = 3;
A[3] = 4;

At this point, the length/size of the array is 4 and the capacity of the array that has room to store elements is 10.

The following code snippets explain the difference between array length vs. capacity.

Capacity

The capacity of an array in Java can be checked by looking at the value of its length attribute. This is done using the code A.length where A the Array's name is.

public class ArrayCapacityLength {
    public static void main(String[] args) {
        int[] A = new int[10];

        System.out.println("Array Capacity " + A.length); // 10
    }
}

Running the above snippet gives

// Array Capacity is 10

Length

This is the number of items currently in the A[] array.

import java.util.Arrays;

public class ArrayCapacityLength {
    public static void main(String[] args) {
        int[] A = new int[10];

        int currentItemsLength = 0;
        for (int i = 0; i < 4; i++) {
            currentItemsLength += 1;
            A[i] = i + 10;
        }

        System.out.println(Arrays.toString(A)); // [10, 11, 12, 13, 0, 0, 0, 0, 0, 0]
        System.out.println("Array length is " + currentItemsLength); // 4
        System.out.println("Array Capacity is " + A.length); // 10
    }
}

Running the above snippet gives

// Array length is 4
// Array Capacity is 10

Bit Manipulation for Technical Interviews

Gopi Gorantala — Tue, 21 Feb 2023 04:47:15 +0000

I launched a FREE "A Fun Guide To Bit Manipulation For Coding Interviews" course for Problem-solvers, competitive programming aspirants, and FAANG/startup aspirants.

Takeaway Skills

Master problem-solving that involves bit manipulation.
Master how the bit-level operations are computed. Understand that bit-level operations are based on all the arithmetic operations built into all languages.
These bit tricks help in competitive programming in running algorithms mostly in O(1) time.
Master the bit manipulation, which allows you to organize all inputs in binary representation at the memory levels.
Solve problems that are commonly asked in coding interviews related to bit manipulation.
Solutions are available in 5 different languages.

"From Zero To Binary Hero: A Fun Guide to Bit Manipulation For Coding Interviews"

What do you get?

✅ 44 lessons categorized based on topics.
✅ 28 challenges.
✅ 27+ Illustrations.
✅ 271 solutions provided.
✅ Solutions are written in Java, Python, JavaScript, C++, and TypeScript.
✅ GitHub repository access.
📢 Rust and Go solutions are in progress.
📢 Few Medium, Hard problems asked at FAANG, top tech, and startup companies are on the way. You will see them live in 2-3 weeks.

Course Overview

This course teaches bit manipulation, a powerful technique to enhance algorithmic and problem-solving skills. It is a critical topic for those preparing for coding interviews for top tech companies, startups and industry leaders. Competitive programmers can take full advantage of this course by running most of the bit-related problems in O(1) complexity.

The course will begin by educating you about the number system and its representation, decimal and binary, followed by the six bitwise operators: AND, OR, NOT, XOR, and bit-shifting (left, right).

You will receive ample practical experience working through practice problems to improve your comprehension.

Upon completing this course, you will be able to solve problems with greater efficiency and speed.

Lessons

A few lessons listed here are from the course:

Note: In the upcoming edits, you will see the following items:

Solutions in Rust and Go.
A few medium and hard problems were asked in recent FAANG and fast-paced startup coding interviews.

Please take some time to share feedback. It helps and encourages me to write more courses and make them FREE forever.

How To Solve Missing Number Problem In Java, An Amazon Interview Question

Gopi Gorantala — Tue, 29 Mar 2022 06:46:35 +0000

Introduction

We make use of XOR principles in finding a missing element.

Let’s see how to achieve this using the XOR operator.

Problem statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Input: nums = { 9, 6, 4, 2, 3, 5, 7, 0, 1 }

Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

Do it in Linear Complexity.
n == nums.length

Hint: Use arithmetic progression and go with the Brute force approach. Then optimize it.

Solution

Approach 01: Hashtable

This one is better than the one above as we are iterating over all the elements once with O(n)extra memory space.

Algorithm

This algorithm is almost identical to the Brute force approach, except we first insert each element of nums into a Set, allowing us to later query for containment in O(1) time.

Code

import java.util.HashSet;

class MissingNumber {
    private static int helper(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();

        for (int num : nums) {
            set.add(num);
        }

        int n = nums.length + 1;

        for (int i = 0; i < n; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Complexity analysis

Time complexity: O(n), the time complexity of for loops is O(n) and the time complexity of the hash table operation add is O(1).

Space complexity: O(n), the space required by the hash table is equal to the number of elements in nums.

Approach 01: Maths

This uses concepts regarding n natural numbers.

Algorithm

We know the sum of n natural numbers is [n(n+1)/2]
Now, the difference between the actual sum of the given array elements and the sum of n natural numbers gives us the missing number.

Code

class MissingNumber {
    private static int helper(int[] nums) {
        int n = nums.length;
        int expectedSum = ((n * (n + 1)) / 2);

        int actualSum = 0;

        for (int num : nums) {
            actualSum += num;
        }

        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Complexity Analysis

Time complexity: O(n), the time complexity of the for loop is O(n).

Space complexity: O(1), as we are not using any extra space.

Coding exercise

First, take a closer look at these code snippets above and think of a solution.

Your solution must use the ^ operator.

This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck!

class Solution{
    public static int missingNumber(int[] nums){
       // Write - Your - Code- Here

        return -1; // change this, return missing element; if none, return -1
    }
}

The solution is explained below.

We solved the problem using lookup (Memoization/Hashtable) and using the mathematical formula for the sum of n natural numbers, Let's solve this more efficiently using bit-level operations with ^ or xor.

Solution review: Bit manipulation

We are dealing with bit manipulation and want to solve all of these problems with Bitwise operators.

Concepts

If we take XOR of 0 and a bit, it will return that bit.

a ^ 0 = a

If we take XOR of two same bits, it will return 0.

a ^ a = 0

For n numbers, the math below can be applied.

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b;

For example:

1 ^ 5 ^ 1 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5;

So, we can XOR all bits together to find the unique number.

Algorithm

Initialize a variable, res = 0.
Iterate over array elements from 0 to length + 1 and do ^ of each with the above-initialized variable.

Iterate over all the elements and store the value in the variable.

Code

Here is the logic for this solution.

class MissingNumber {
    private static int helper(int[] nums) {
        int n = nums.length + 1;
        int res = 0;

        for (int i = 0; i < n; i++) {
            res ^= i;
        }

        for (int value : nums) {
            res ^= value;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Complexity analysis

Time complexity: O(n), we are using two independent for loops. So Time = O(n) + O(n) => O(n).

Where, n is the number of elements in the array, since we need to iterate over all the elements to find a missing number. So, the best and the worst-case time is O(n).

Space complexity: O(1), the space complexity is O(1). No extra space is allocated.

Optimization

Let us optimize the last solution.

We are using two independent for loops to find the missing number.

Now, let’s make it a single for loop. If we have an array of one million integers, then we do two million operations.

We can reduce the number of operations into n, where n is the array’s size.

Let’s look at the below code.

class MissingNumber {
    private static int helper(int[] nums) {
        int missing = nums.length;

        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Here the code has less lines compared to the one above.

Complexity analysis

Time complexity: O(n): Where, n is the number of elements in the array, as we need to iterate over all the elements to find a missing number. So, the best, worst-case time is O(N).

Space complexity: O(1), the space complexity is O(1), no extra space is allocated.

Learn more

I’ve got a course on bit manipulation that is loved by more than 200k+ programmers. Find it here: Master Bit Manipulation for Coding Interviews.

In this course, we learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize our algorithmic and problem-solving skills. The course has simple explanations with sketches, detailed step-by-step drawings, and various ways to solve problems using bitwise operators.

How To Master React Library And Continuous Deployment

Gopi Gorantala — Mon, 14 Mar 2022 17:08:21 +0000

React is one of the most popular libraries in the frontend world.

Being a backend developer for over 10 years, I agree I started with React 4 years ago and found it awesome 😅. And there is no reason for me to switch.

Developers, you can buy some paid courses online by Stephen Grider(react), and Andrei Neagoie(zeroToMastery.io).

BUT... why can't you learn by doing?

For starters, on react homepage ReactJS, there are four example code snippets guiding you to the basics. This alone documentation is enough for you to bootstrap your react app from just printing something on a browser/console to building a full-stack application.

Start writing something, it won't come up... read documentation reactjs, it's the best site that gives insights on each and every line of code you write.

I would say you don't mimic already existing applications. Here are some of my ideas which if it helps, try it and if it not, please don't hesitate to ask questions.

Advice

For starters, learn the basics that's enough, don't go deep...

First bootstrap a react application with CRA npx create-react-app my-application or any boilerplate code.
I would recommend using functional components with hooks,MaterialUI, React Hook Form for form data, React Query for queries etc.

Material UI

React Hook Form

React Query

Now think of an idea or application you want to build. I recommend you build an app that represents your resume (more like a portfolio website). You can showcase this to recruiters once it's deployment-ready 🤩.
Don't build re-usable components right away.
Start simple, go check StackOverflow and get some ideas in building Appbar, Sidebar, Navbar, or check for ideas to do them.
Now, write some code and bring up the app.
Hardcode data, for now, there is no rush in getting data from API, and don't mess the code right away with APIs, databases, etc.
When you think your app is ready with hardcoded data. I would recommend Firebase as your database, everything JSON and you'll love it 😍.

Connect the Firebase with your app. Get some data and refactor the hardcoded data with API payloads.
Now where ever you feel you duplicated code, make them a reusable component. Like Card, ChipInput, Modal, Button, TextField, Notification, Select, Image,c FileUpload, ToolTip, AutocompleteTextField, and much more etc.
Now once this is up and working... install redux and inflate the state. Connect the store and get it ready.
By this time your hands are dirty and you know what's happening within the app.
Now you are an intermediate React developer--------------

Do you want to become an expert?

Have an API wrapper that takes the request and serves you API data. This will be a pattern all your XHR requests follow.
Each Component should serve a single purpose, if you think the feature you're adding should be separated, don't hesitate... Just separate, and later you can clean and make sure the code is readable.
Check for code quality, your code should not flood the state.
Now, check how many times each of your individual components are rendered. You should use useCallback or useMemo to reduce the number of re-renders, this will lower the burden on DOM.

Deploy the app using Netlify

This is quite easy, follow the steps along to make your react app live.

We will use Github + Netlify to do the continuous deployment. So, whenever there is a new change in the repository, Netlify watches the changes and deploys the latest artifacts onto the server.

You need to build the app first, by running the command npm run build. This will minify the app into the build folder under the root project directory.
log in to your GitHub account, or signup if you don't have one.
Create a repository(either public/private repo) and push all of your react app code to this new repository.
Go to Netlify and signup.
After signup, you are redirected to the sites screen, click New Site from Git and connect choose your Github account.
Don't choose All Repositories, choose Only select repositories to choose the latest repo you created and click install.
Don't change the defaults on Netlify, click on Deploy Site. This will start deploying your site and it will take some time to run the builds.
When the deployment is successful, you see Site is Live on Netlify Deploy Log.
You can set up your own domain or Netlify gives you a URL so you can share.

Note: Consider using NextJS to take your app to next level.

Don't buy all the paid courses. There are plenty of online free resources available and they would definitely help you. Spend a week determined and if you still feel there are bits and pieces missing. You can always buy a paid course.

I love React ❤️ frontend gives me some sort of aesthetic vibes!!!

What Are Java Method References And Kinds Of Method References Available?

Gopi Gorantala — Sat, 12 Mar 2022 04:41:19 +0000

Method References

Method reference operator :: is used to refer to the methods of functional interface. It is a compact and easy form of the lambda expression.

Lambda expressions are used to create anonymous methods.

Most of the time, we do some operations inside the lambda expression. Sometimes, however, a lambda expression does nothing but call an existing method. In those cases, it’s often clearer to refer to the existing method by name.

So, whenever you are using a lambda expression to refer to a method, you can also do the same using a method reference. Replace the lambda expression with method reference and it works!

Method references allow you to do this. They are compact each-to-read lambda expressions for methods that already have a name.

Method reference is a wonderful feature introduced in Java 8. Apart from taking advantage of functional programming, one of the biggest advantages of using a Method Reference is it minimizes the number of lines of code even more than lambda expressions.

Method references are a special type of lambda expression. They’re often used to create simple lambda expressions by referring to existing methods.

Example 01: Uppercase Strings

import java.util.Arrays;
import java.util.List;

class Main {
  public static void main(String[] args) {
    List<String> fruits = 
      Arrays.asList("Apple", "Banana", "guava", "grapes");

    fruits.stream()
      .map(String::toUpperCase)
      .forEach(System.out::println);
    }
}

We could have used lambda expression inside the terminal operation .forEach(...) like below.

fruits.stream()
  .map(String::toUpperCase)
  .forEach(fruit -> System.out.println(fruit));

But, method reference syntaxes are clean and simple. The above lambda expression syntax is refactored with method reference as follows.

    .forEach(System.out::println);

Explanation

Let us see in detail what we are trying to achieve in the above snippet.

We have a list of fruits.
Chained with .stream(), so the collection of String objects gets converted into Stream of String objects.
Now, we need to chain .stream() with intermediate operations, such as .map(...) which makes use of Method Reference, String::toUpperCase to uppercase all the stream elements.
At last we chained it with a terminal operation .forEach(...) which also uses a Method Reference to print the data.

To understand what does intermediate and terminal operations mean in streams API, follow these hashnode articles for a better understanding.

Lambda Expressions to Method References

Here are some examples of how we can replace the lambda expressions using method references.

Following, we will discuss different kinds of method references, their uses, an example code snippet, and an explanation.

Kinds of Method References

There are four kinds of method references.

Reference to static methods.
Reference to instance methods of particular objects.
Reference to an instance method of an arbitrary object of a particular type.
Reference to a constructor.

Generic syntax

So, the generic syntax for all these kinds of method references is as follows.

class/object::method

1. Reference to a static method

A static method reference refers to the static method for a class. We can use a method reference to directly call the static methods. The syntax for referencing a static method is as follows.

Syntax

This is a classic syntax, and it's the class name followed by the static method you are trying to refer to.

className::staticMethodName

Code

An example code snippet that explains how static methods are called using method references.

Book POJO with a constructor, getters, and setters.

class Book {
  String title;
  String author;
  Integer year;
  Integer copiesSoldInMillions;
  Double rating;
  Double costInEuros;

  public Book(String title, String author, Integer year, Integer copiesSoldInMillions, Double rating, Double costInEuros) {
    this.title = title;
    this.author = author;
    this.year = year;
    this.copiesSoldInMillions = copiesSoldInMillions;
    this.rating = rating;
    this.costInEuros = costInEuros;
  }

  public String getTitle() {
    return title;
  }

  public Double getRating() {
    return rating;
  }

  @Override
  public String toString() {
    return "Book{" +
      "title='" + title + '\'' +
      ", author='" + author + '\'' +
      ", year=" + year +
      ", copiesSoldInMillions=" + copiesSoldInMillions +
      ", rating=" + rating +
      ", costInEuros=" + costInEuros +
      '}';
  }
}

BookDatabase for dummy data injection.

import java.util.Arrays;
import java.util.List;

public class BookDatabase {
  public static List<Book> getAllBooks() {
    return Arrays.asList(
      new Book("Don Quixote", "Miguel de Cervantes", 1605, 500, 3.9, 9.99),
      new Book("A Tale of Two Cities", "Charles Dickens", 1859, 200, 3.9, 10.0),
      new Book("The Lord of the Rings", "J.R.R. Tolkien", 2001, 150, 4.0, 12.50),
      new Book("The Little Prince", "Antoine de Saint-Exupery", 2016, 142, 4.4, 5.0),
      new Book("The Dream of the Red Chamber", "Cao Xueqin", 1791, 100, 4.2, 10.0)
    );
  }
}

Following is our BookApplication class that does the imperative programming or mutations on book variable inside for-loop using static method reference.

import java.util.List;

public class BookApplication {

  public static int compareByTitle(Book first, Book second) {
    return first.getTitle().compareTo(second.getTitle());
  }

  public static int compareByRating(Book first, Book second) {
    return first.getRating().compareTo(second.getRating());
  }

  public static void main(String[] args) {
    List<Book> books = BookDatabase.getAllBooks();

    System.out.println("SORT BASED ON RATINGS: ");
    books.sort(BookApplication::compareByRating);
    books.stream()
      .map(book -> book.getTitle() + " -> " + book.getRating())
      .forEach(System.out::println);

    System.out.println("---------");

    System.out.println("SORT BASED ON TITLES: ");
    books.sort(BookApplication::compareByTitle);
    books.stream()
      .map(book -> book.getTitle() + " -> " + book.getRating())
      .forEach(System.out::println);
  }
}

Output:

Above code, snippet outputs the following on console.

SORT BASED ON RATINGS: 
Don Quixote -> 3.9
A Tale of Two Cities -> 3.9
The Lord of the Rings -> 4.0
The Dream of the Red Chamber -> 4.2
The Little Prince -> 4.4
---------
SORT BASED ON TITLES: 
A Tale of Two Cities -> 3.9
Don Quixote -> 3.9
The Dream of the Red Chamber -> 4.2
The Little Prince -> 4.4
The Lord of the Rings -> 4.0

2. Reference to an instance method of a particular object

The following is an example of a reference to an instance method of a particular object:

Syntax:

This is another syntax that uses instances of a particular object followed by the static method you are trying to refer to.

object::staticMethodName

Code

An example code snippet that explains how static methods are called using method references.

For simplicity, I am not duplicating Book and BookDatabase classes here, refer to them in the above example.

So, let's directly jump into the BookApplication class.

import java.util.List;

public class BookApplication {

  public static void main(String[] args) {
    List<Book> books = BookDatabase.getAllBooks();

    BookApplication bookApplication = new BookApplication();

    System.out.println("SORT BASED ON RATINGS");
    books.sort(bookApplication::compareByRating);
    books.stream()
      .map(book -> book.getTitle() + " -> " + book.getRating())
      .forEach(System.out::println);

    System.out.println();

    System.out.println("SORT BASED ON TITLES: ");
    books.sort(bookApplication::compareByTitle);
    books.stream()
      .map(book -> book.getTitle() + " -> " + book.getRating())
      .forEach(System.out::println);
  }

  public int compareByTitle(Book first, Book second) {
    return first.getTitle().compareTo(second.getTitle());
  }

  public int compareByRating(Book first, Book second) {
    return first.getRating().compareTo(second.getRating());
  }
}

Output:

Above code, snippet outputs the following on console.

SORT BASED ON RATINGS
Don Quixote -> 3.9
A Tale of Two Cities -> 3.9
The Lord of the Rings -> 4.0
The Dream of the Red Chamber -> 4.2
The Little Prince -> 4.4

SORT BASED ON TITLES: 
A Tale of Two Cities -> 3.9
Don Quixote -> 3.9
The Dream of the Red Chamber -> 4.2
The Little Prince -> 4.4
The Lord of the Rings -> 4.0

The method reference bookApplication::compareByRating invokes the method compareByRating that is part of the object bookApplication. The JRE infers the method type arguments, which in this case are (Book book).

The above simple explanation is the same for this method reference bookApplication::compareByTitle.

3. Reference to an instance method of an arbitrary object of a particular type.

The following is an example of a reference to an instance method of an arbitrary object of a particular type.

Code

Approach 01

import java.util.Arrays;
import java.util.List;

class Main {
  public static void main(String[] args) {
    List<String> fruits = 
        Arrays.asList("Banana", "Grapes", "guava", "apples");
    fruits.sort(String::compareToIgnoreCase);
    fruits.forEach(System.out::println);
  }
}

Output:

apples
Banana
Grapes
guava

The equivalent lambda expression for the method reference String::compareToIgnoreCase would have the formal parameter list (String a, String b), where a and b are arbitrary names used to better describe this example. The method reference would invoke the method a.compareToIgnoreCase(b).

Similarly, the method reference String::concat would invoke the method a.concat(b).

Approach 02

import java.util.Arrays;
import java.util.List;

class Main {
  public static void main(String[] args) {
    List<Integer> numbers = 
      Arrays.asList(11, 4, 2, 8, 9, 10, 32, 22, 20, 17);

    numbers.stream()
      // .sorted((a, b) -> a.compareTo(b)) lambda way
        .sorted(Integer::compareTo) 
        .forEach(s -> System.out.print(s + " "));
  }
}

Output:

2 4 8 9 10 11 17 20 22 32

4. Reference to a Constructor

Constructor references are specialized forms of method references that refer to the constructors of a class. They can be created using the className and the keyword new.

Syntax

className::new

Code

public class BookApplication {
  public static void main(String[] args) {
    BookService bookService = Book::new;
    Book book = bookService.getBook(
      "The Little Prince",
      "Antoine de Saint-Exupery",
      2016, 142,
      4.4,
      5.0);

    System.out.println(book);
  }
}

Output:

Book{title='The Little Prince', author='Antoine de Saint-Exupery', year=2016, copiesSoldInMillions=142, rating=4.4, costInEuros=5.0}

This wraps everything you need to know about Method References in Java. Happy Coding 🤩.