Java Implementation

Hello, welcome to this page ;) This article is about the Java Language, Data Structures and also some other useful facts about sorting.

What are the core interfaces of the Java Collection Framework?

1. List: represents an ordered collection of elements that allows duplicate elements. The key implementations of List are ArrayList and LinkedList. ArrayList internally uses array. LinkedList uses a doubly linked list.
2. Set: A collection of unique elements which does not allow duplicate elements. The key implementation of set are Hashset and TreeSet. HashSet internally uses Hash Table, TreeSet uses a Red black Tree (self balancing binary search tree) which elements are sorted in a order defined by either their natural order of a custom Comparator.
3. Queue: A collection to hold elements in First In First out. The key implementations of Queue are LinkedList and PriorityQueue (based on the natural ordering of elements or a custom comparator).
4. Map: Represents an object that maps keys to values, where each key is unique. Implementation of Map are HashMap and TreeMap.

What are Hash Set, Hash Map? Describe their use cases and how they are implemented.

• HashSet is implementation of Set Interface which does not allow duplicate value.
• HashMap is an implementation of Map Interface, which map a key to value. Duplicate keys are not allowed in a map. Basically Map Interface has two implementation classes HashMap and TreeMap the main difference is TreeMap maintains order of the objects but HashMap will not. HashMap allows null values and null keys.

• HashMap internally uses hashing to store or add objects, HashSet internally uses HashMap object to store or add the objects.
• HashMap is faster: They both have to calculate the hashcode, but think about the nature of the key of a HashMap — it is typically a simple String or even a number. Calculating the hashcode of that is much faster than the default hashcode calculation of an entire object. If the key of the HashMap was the same object as that stored in a HashSet, there would be no real difference in performance. The difference comes in the what sort of object is the HashMap’s key.

As seen above, the key of the object is passed into the Hash function for HashMap. In the case of HashSet, the entire object is being passed into the Hashfunction. Remember that HashSet is also implemented by HashMap. We can view the objects being inserted into a HashMap to be an object containing only Keys.

What are the differences between HashSet and TreeSet?

• (What does it implement) Both implements set interface.
• (Underlying data structure): Hash set uses hash map internally while treeset uses tree-map -> Red-Black Tree.
• (Complexity performance) HashSet is faster than TreeSet which means if you need performance use HashSet but HashSet doesn’t provide any kind of ordering so if you need ordering then you need to switch to TreeSet which provides sorting of keys. TreeSet is internally backed by a Red-Black tree. Adding an element of a tree is slower than adding it to a hash table but it is still much faster than adding it into the right place in the linked list or array. If the tree contains n elements, then an average log2N comparisons are required to find the correct position for a new element.
• (How many objects are stored) HashSet allows null object but TreeSet doesn’t allow null Object and throw NullPointerException, Why, because TreeSet uses compareTo() method to compare keys and compareTo() will throw java.lang.NullPointerException
• (Compare) HashSet uses equals() method to compare two objects in Set and for detecting duplicates while TreeSet uses compareTo() method for the same purpose.

Equals

• Equals and hashCode in Java are two fundamental methods which are declared in Object class. equals() method is used to compare Objects for equality while hashCode is used to generate an integer code corresponding to that object. equals and hashCode are used extensively in HashMap. equals method is also used to avoid duplicates on HashSet and other Set implementation and every other place where you need to compare Objects.
• Default implementation of equals() class provided by java.lang.Object compares memory location and only return true if two reference variable is pointing to the same memory location i.e. essentially they are the same object.
• The hashCode() method is used to generate the hash values of objects. Using these hash values, these objects are stored in Java collections such as HashMap, HashSet and HashTable. Two objects with the same value have the same hashcode.

class Coordinate {
    int x;
    int y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
    // Defining custom equals and hashcode

    ** MEMORISE THE IMPLEMENTATION FOR EQUALS AND HASHCODE BELOW **
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        Coordinate other = (Coordinate) obj;
        return x == other.x && y == other.y;
    }
    ** RETURN TYPE IS INT NOT INTEGER **
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

• compareTo in Java is in the same category as equals() and hashcode() and used to implement natural order of object. Natural sorting means the sort order which naturally applies on object e.g. lexical order for String, numeric order for Integer or Sorting employee by there ID, etc.
• compareTo is slightly different to compare() method of Comparator interface which is used to implement custom sorting order.
• CompareTo method must return negative number if current object is less than other object, positive number if current object is greater than other object and zero if both objects are equal to each other.
• CompareTo must be in consistent with equals method e.g. if two objects are equal via equals() , there compareTo() must return zero otherwise if those objects are stored in SortedSet or SortedMap they will not behave properly. Since SortedSet or SortedMap use compareTo() to check the object if two unequal object are returned equal by compareTo those will not be added into Set or Map if they are not using external Comparator.

What are the differences between HashMap and ArrayList

• (What does it implement) The first difference between ArrayList and HashMap is that ArrayList implements List interface while HashMap implements Map interface in Java.
• (What is the underlying data structure) One of the most critical difference between HashMap and ArrayList class is that former is the implementation of the hash table while later is a dynamic array which can resize itself.
• (How many objects are stored) ArrayList only stores one object while HashMap stores two objects key and value.
• (Ordering of objects) ArrayList maintains the order of object, in which they are inserted while HashMap doesn’t provide any ordering guarantee.
• (Complexity performance) ArrayList get(index) method always gives an O(1) performance but HashMap get(key) can be O(1) in the best case and O(n) in the worst case.

What are the differences between ArrayList and LinkedList

LinkedList

• Both are implementation of the List Interface.
• (Underlying data structure) ArrayList is backed by Array while LinkedList internally uses a doubly linked list to store the elements.
• (Complexity performance)
• Adding an element in ArrayList is O(1) operation if it doesn’t trigger re-size of Array, in which case it becomes O(log(n)), On the other hand, appending an element in LinkedList is O(1) operation, as it doesn’t require any navigation.
• In order to remove an element from a particular index e.g. by calling remove(index), ArrayList performs a copy operation which makes it close to O(n) while LinkedList needs to traverse to that point which also makes it O(n/2), as it can traverse from either direction based upon proximity.
• ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).
• https://www.baeldung.com/java-arraylist-linkedlist

What are the differences between Array and ArrayList?

• Array is a fixed length data structure whereas ArrayList is a Dynamic sized arrays in Java that implement List interface. We cannot change length of array once created in Java but ArrayList can be changed.
• Array can contain both primitive data types as well as objects of a class depending on the definition of the array. However, ArrayList only supports object entries, not the primitive data types.
  Note: When we do arraylist.add(1); : it converts the primitive int data type into an Integer object.
• Since ArrayList can’t be created for primitive data types, members of ArrayList are always references to objects at different memory locations (See this for details). Therefore in ArrayList, the actual objects are never stored at contiguous locations. References of the actual objects are stored at contiguous locations.
• In array, it depends whether the arrays is of primitive type or object type. In case of primitive types, actual values are contiguous locations, but in case of objects, allocation is similar to ArrayList.
• https://www.geeksforgeeks.org/array-vs-arraylist-in-java/

Difference between Set and List

• Both are collections interfaces
• Set allows us to add objects, but does not have duplicates. List allows duplicates.
• Set is not indexed, List is indexed. When we want to delete stuff in set, we pass in the object. When we want to delete stuff in List, we pass in the index.
• Set is unordered, list is ordered.

What are the differences between abstract class and interfaces?

• Main difference is methods of a Java interface are implicitly abstract and cannot have implementations. A Java abstract class can have instance methods that implements a default behavior.
• Variables declared in a Java interface is by default final. An abstract class may contain non-final variables.
• Members of a Java interface are public by default. A Java abstract class can have the usual flavors of class members like private, protected, default etc..
• An interface can extend another Java interface only, an abstract class can extend another Java class and implement multiple Java interfaces.

The Default: No keyword required. Accessible only within the same package

Why do we need interfaces?

• Classes can only inherit or extend from 1 abstract class. Interfaces allows for multiple implementation.
• Variables in interfaces are static and final but it can hold other types in abstract class.

When do we use Interface or Abstract Classes?

https://www.tutorialspoint.com/when-to-use-an-abstract-class-and-when-to-use-an-interface-in-java

• If the functionality we are creating will be useful across a wide range of disparate objects, use an interface. Abstract classes should be used primarily for objects that are closely related, whereas interfaces are best suited for providing a common functionality to unrelated classes.
• Interfaces are a good choice when we think that the API will not change for a while.
• Interfaces are also good when we want to have something similar to multiple inheritances since we can implement multiple interfaces.
• If we are designing small, concise bits of functionality, use interfaces. If we are designing large functional units, use an abstract class.

Why choose to use Abstract class instead of a normal Java base class?

• Enforce constaints: An abstract class can enforce constraints on its subclasses, such as requiring them to implement certain methods or prohibiting them from overriding others. This can help ensure that the subclasses behave in a certain way and avoid unexpected behavior.
• It cannot be instantiated on its own: An abstract class cannot be instantiated on its own, which ensures that only its subclasses can be created. This can help prevent accidental use of the abstract class and encourage developers to create specific subclasses that follow the contract defined by the abstract class.

What is Final property?

• Usually set for a variable to have a constant value. It cannot be changed.
• If the variable is a referenced object, then the referenced outer DS cannot be changed. However, items within this DS can be changed. For eg, ArrayList<Integer>, the ArrayList DS cannot be changed. However, numbers inside it can change.

What are the synchronization issues in Java?

• Concurrent access of shared objects in Java introduces to kind of errors: thread interference and memory consistency errors.
• Locking can be used to resolve.

What is the purpose of the Comparable and Comparator interfaces in Java? Provide an example of their usage.

The comparable and comparator interfaces in Java are used for sorting objects. The Comparable interface defines a natural ordering for a class, allowing objects of that class to be sorted based on their natural order. The Comparator interface provides an external comparison mechanism and allows objects to be sorted based on custom criteria.

public class Person implements Comparable<Person>{
  private String name;
  private int age;

  // constructor and other methods

  public int compareTo(Person other){
    return this.name.compareTo(other.getName());
  }

}

PriorityQueue<Node> pq = new PriorityQueue<Node>(new NodeComparator());
// Initialise comparator
static class NodeComparator implements Comparator<Node>{
       public int compare(Node n1, Node n2){
           //Method 1 -> min heap
           if(n1.getNum()<n2.getNum()) return -1;
           else if (n1.getNum()>n2.getNum()) return 1;
           return 0;
           //Method 2 -> Min Heap           
           return n1.getNum-n2.getNum();
       } 
}

Arrays.sort(employees, Comparator.comparing(Employee::getName));
Arrays.sort(Comparator.comparing(Employee::getName).reversed());
Arrays.sort(employees, Comparator.comparingInt(Employee::getAge));
Arrays.sort(employees, Comparator.comparing(Employee::getAge).thenComparing(Employee::getName));

comparable -> compareTo -> Put in the object class

comparator -> compare -> Pass as a function

Why use a comparator when we already have comparable?

• Sometimes we cannot modify the source code of the class whose objects we want to sort, thus making using Comparable impossible.
• Using Comparators allows us to avoid adding additional code to our domain class.

How does garbage collection works in Java? How often do you think the GC cleans up the memory?

Garbage collection is the process of looking at heap memory, identifying which objects are in use and which are not, and deleting the unused objects.

An in-use object, or a referenced object, means that some part of your program still maintains a pointer to that object. An unused object, or unreferenced object, is no longer referenced by any part of your program. So the memory used by an unreferenced object can be reclaimed.

Whenever the garbage collector runs, it has an effect on the application’s performance. This is because all other threads in the application have to be stopped to allow the garbage collector thread to effectively do its work.

The heap is divided into a number of sections called generations, each of which will hold objects according to their “age” on the heap. The term “age” in generational garbage collection refers to the number of collection cycles the object has survived. These spaces are Young Generation, Old or Tenured Generation, and Permanent Generation.

Whenever the garbage collector is running, the first step in the process is called marking. This is where the garbage collector identifies which pieces of memory are in use and which are not. This can be a very time-consuming process if all objects in a system must be scanned.

The young generation hosts most of the newly created objects. Therefore, new objects start their journey here and are only “promoted” to the old generation space after they have attained a certain “age”.

The old generation hosts objects that have lived in memory longer than a certain “age”. It is generally larger than the young generation. As it is bigger in size, the garbage collection is more expensive and occurs less frequently than in the young generation.

The permanent generation or more commonly called, PermGen, contains metadata required by the JVM to describe the classes and methods used in the application. It also contains the string pool for storing interned strings. It is populated by the JVM at runtime based on classes in use by the application. In addition, platform library classes and methods may be stored here.

After every minor garbage collection cycle, the age of each object is checked. Those that have reached a certain arbitrary age, for example, 8, are promoted from the young generation to the old or tenured generation. For all subsequent minor GC cycles, objects will continue to be promoted to the old generation space.

You, as Java programmer, can not force garbage collection in Java; it will only trigger if JVM thinks it needs a garbage collection based on Java heap size.

(The above is taken from another website)

— — ACTUALLY, this might be outdated — -

Explain the Heap Memory in Java

Heap space in Java is used for dynamic memory allocation for Java objects at run time. New objects are always created in heap space and the references to this objects are stored in stack memory.

These objects have global access and can be accessed from anywhere in the application.

This memory model is further broken into smaller parts called generations, these are:

Young Generation: This is where all new objects are allocated and aged. A minor Garbage collection occurs when this fills up.

Old or Tenured generation: This is where long surviving objects are stored. When objects are stored in the Young Generation, a threshold for the object’s age is set and when that threshold is reached, the object is moved to the old generation.

Permanent Generation: This consists of JVM metadata for the runtime classes and application methods.

If heap space is full, Java throws java.lang.OutOfMemoryError

This memory, in contrast to stack, isn’t automatically deallocated. It needs Garbage Collector to free up unused objects so as to keep the efficiency of the memory usage. Garbage Collection runs on the heap memory to free the memory used by objects that don’t have any reference.

Explain Stack Memory in Java

Stack memory in Java is used for static memory allocation and the execution of a thread. It contains primitive values that are specific to a method and references to objects that are in a heap, referred from the method.

When a new method is called, a new block on top of the stack is created. When a method finishes execution, it’s corresponding stack frame is flushed.

Variables inside stack exist only as long as the method that created them is running. This structure allows the runtime to return from the method knowing the address where it was called, and also clear all local variables after exiting the method. Every thread has its own stack.

If this memory is full, Java throws java.lang.StackOverFlowError

Access to this memory is fast when compared to heap memory.

Example of heap and stack

• As soon as we run the program, it loads all the Runtime classes into the Heap space. When the main() method is found at line 1, Java Runtime creates stack memory to be used by main() method thread.
• We are creating primitive local variable at line 2, so it’s created and stored in the stack memory of main() method.
• Since we are creating an Object in the 3rd line, it’s created in heap memory and stack memory contains the reference for it. A similar process occurs when we create Memory object in the 4th line.
• Now when we call the foo() method in the 5th line, a block in the top of the stack is created to be used by the foo() method. Since Java is pass-by-value, a new reference to Object is created in the foo() stack block in the 6th line.
• A string is created in the 7th line, it goes in the String Pool in the heap space and a reference is created in the foo() stack space for it.
• foo() method is terminated in the 8th line, at this time memory block allocated for foo() in stack becomes free.
• In line 9, main() method terminates and the stack memory created for main() method is destroyed. Also, the program ends at this line, hence Java Runtime frees all the memory and ends the execution of the program.

Difference between Heap and Stack

• Whenever an object is created, it’s always stored in the Heap space and stack memory contains the reference to it. Stack memory only contains local primitive variables and reference variables to objects in heap space.
• Objects stored in the heap are globally accessible whereas stack memory can’t be accessed by other threads and is used only by one thread of execution.
• Memory management in stack is done in LIFO manner whereas it’s more complex in Heap memory because it’s used globally. Heap memory is divided into Young-Generation, Old-Generation etc, more details at Java Garbage Collection.
• Stack memory is short-lived whereas heap memory lives from the start till the end of application execution.
• When stack memory is full, Java runtime throws java.lang.StackOverFlowError whereas if heap memory is full, it throws java.lang.OutOfMemoryError: Java Heap Space error.
• Stack memory size is very less when compared to Heap memory. Because of simplicity in memory allocation (LIFO), stack memory is very fast when compared to heap memory.
• Over time, as memory is allocated and deallocated on the heap, it can become fragmented, which means free memory are scattered through the heap, making it difficult to find continuous block of memory for large memeory allocation. Hence, garbage collection or memory defragmentation is required.

Why is stack memory fast compared to heap memory?

1. Memory Allocation: Stack memory is allocated in advanced (when program is compiled/executed) when the program is created. By having the memory already allocated in advance, the process of allocating and deallocating memory for variables on the stack becomes quicker and easier compared to heap memory, which requires more dynamic memory management.
2. Locality of Reference / Cache: When variables are stored in the stack, they are typically accessed in a limited scope, such as a specific function or block of code. Hence, they are accessed in a predictable order and frequently. This allows data to be cached and re-used by subsequent accesses.
3. Simple Operations: Accessing stack memory involves simple operations. The computer adjusts a pointer to allocate and deallocate memory, which is faster compared to the additional operations required for heap memory. In heap memory, memory is allocated dynamically during program runtime. Eg, using malloc() or new(). The memory manager will then need to search for a suitable block of memory to fulfil the request.

What is JDK?

The Java Development Kit (JDK) is a software development environment that offers a collection of tools and libraries necessary for developing Java applications. You need the JDK to convert your source code into a format that the Java Runtime Environment (JRE) can execute.

The JDK includes the Java Runtime Environment (JRE), an interpreter (java), a compiler (javac), an archiver (jar), a documentation generator (javadoc), and some other development tools. The Java Runtime Environment itself consists of the Java Virtual Machine (JVM), supporting files, and core classes.

Typically, if you are only interested in running Java programs on your machine or browser, you only need to install JRE. However, if you would like to develop an application and do Java programming, you will need JDK.

JVM

Java Virtual Machine is an implementation of a virtual machine which executes a Java program.

In C/C++, the compiler compiles code into machine code. In Java, Java compiler compiles code to Java Bytecode.

HelloWorld.class can be executed in linux, window or mac JVM.

The 3 major components of JVM architecture

• Class loader
• Runtime data area
• Execution engine

Class loader: The first main component with 3 phases: Loading, Linking and initialisation.

Loading:

• Loads .class file into memory
• Boot strap class loader -> Move .class from RT.jar to runtime memory.
• Application class loader -> Loads class file (App.class) from App.java into runtime memory.
• Extension loader -> Move /jre/lib/ext/ to runtime memory.

Linking:

• Verify: Once the class files are loaded into memory, there is a verify phase where the bytecode class files are verified if they conform to standards.
• Prepare: Memory is allocated for the static variables and default values are assigned. Eg, static int count = 0;
• Resolve: All symbolic references are replaced with actual references.

Initialisation:

• Static variables are assigned with actual values and it also executes the static initialisers.

Runtime data area

Execution engine

The engine that converts bytecode to machine code and executes the instructions.

It contains interpreter (read class file/bytecode and executes it one by one), JIT compiler (helps overcoming problem of interpreter. When repeated method calls occur, JIT compiler compiles the bytecode to native code which will be used directly for repeated method calls), profiler (find hotspots, method which are used repeatedly), garbage collector (Destroy unused objects), Java Native Method Interface (Responsible for interacting with native libraries and makes it available for the JVM execution engine).

Explain compilation in Java

In Java, the compilation process involves several steps that transform human-readable Java source code into platform-independent bytecode that can be executed by the Java Virtual Machine (JVM). Here’s a high-level overview of the Java compilation process:

1. Writing Java Source Code: Developers write Java programs using a text editor or an Integrated Development Environment (IDE). Java source code files have the .java extension and contain classes, methods, variables, and other program elements.
2. Compilation: The Java source code is compiled using the Java compiler (javac). The compiler reads the .java files and generates corresponding bytecode files with the .class extension. The bytecode is a low-level representation of the Java program, consisting of instructions that can be executed by the JVM.
3. Bytecode Verification: The bytecode files undergo verification by the JVM to ensure their integrity and security. This step checks for bytecode validity, proper class file format, and adherence to bytecode safety rules.
4. Class Loading: The JVM’s class loader loads the compiled bytecode files into memory when they are needed for execution. The class loader is responsible for locating the bytecode files and dynamically loading them into the JVM.
5. Bytecode Execution: The JVM executes the bytecode instructions one by one. It interprets the bytecode or may use Just-In-Time (JIT) compilation techniques to convert frequently executed bytecode into native machine code for better performance.
6. Runtime Optimizations: The JVM performs various runtime optimizations to improve the execution speed and memory efficiency of the Java program. These optimizations include inlining methods, eliminating dead code, and optimizing memory allocation.
7. Runtime Environment: The JVM provides a runtime environment that manages memory, garbage collection, and other runtime services required by the Java program. It provides an execution platform that abstracts the underlying operating system and hardware, enabling Java programs to run consistently across different platforms.

It’s important to note that the compilation process in Java is different from traditional compilation in languages like C++. Java source code is compiled into bytecode, which is then executed by the JVM. This intermediate step of bytecode allows Java programs to be portable and platform-independent.

By separating the compilation and execution phases, Java achieves the “write once, run anywhere” principle, enabling Java programs to be executed on any system that has a compatible JVM installed. This makes Java a versatile and widely adopted programming language for various applications, from desktop software to web applications and mobile apps.

What is a compiler? What is an interpreter?

A compiler is a special program that translates the entire program into a different language (machine code) all at once, and the resulting translation can be used many times.

An interpreter translates the program line by line as it is being executed, without creating a separate translated version.

More on Hash Table Operations

• Solutions to collision: Chaining, Linear Probing, Quadratic Probing, double Hashing

Linear Probing

• Insert -> If hashed value slot is taken up, we iterate and move to the next until we see null then, we insert the item.
• Delete -> If we do not find the item in the index that the hash function points to, we continue searching. Even if we see a slot with DEL, we still continue. Stop only when there is a null slot. Hence, when we delete an item, we have to mark with DEL and not delete so that future search/insert won’t be affected since most ops will stop once they encounter a null slot.
• Insert can override Delete.

• Potential problems of linear probe: Clusters => Collection of consecutive occupied slots.

Quadratic Probing

• We can avoid big clusters by doing quadratic probing.

• But this will then lead to secondary clustering problem. Because: if two keys have the same probe position, their probe sequences are the same. Clustering around different points (rather than the primary probe point)

Double Hashing

• To resolve, we do second hashing.

Heapsort VS Quicksort

• Heapsort is slower than Quicksort, but the worst case running time is O(nlogn). Quicksort is usually faster although there is a chance of a worse case performance O(n²) except in the introsort variant.

• Quick sort is faster because it does not do any unnecessary swaps if the data is already ordered. With heapsort, even if all your data is already ordered, you are going to swap 100% of the elements to order the array.
• With merge sort, it is even worse. You will have to write 100% of elements in another array and write back the original one even if they are already ordered.

Why do we often use Quicksort over Merge sort even when worst case complexity of Quicksort is worse than Merge sort?

Merge sort (Simple split, Clever Combine)

• O(NlogN)

Quick Sort (Clever split, Simple combine)

• De-facto sorting method. It can be 2x3 times faster than Merge sort. Quicksort usually is better than merge sort for two reasons:
• Quicksort has better locality of reference than merge sort, which means that the accesses performed in quicksort are usually faster than the corresponding accesses in merge sort. This is because it requires little additional space and exhibits good cache locality, and this makes it faster than merge sort in many cases.
• Quicksort uses worst-case O(log n) memory (if implemented correctly), while merge sort requires O(n) memory due to the overhead of merging.
• Suppose you want to sort a linked list of elements. The linked list elements are scattered throughout memory, so advantage (1) disappears (there’s no locality of reference). Second, linked lists can be merged with only O(1) space overhead instead of O(n) space overhead, so advantage (2) disappears. Consequently, you usually will find that mergesort is a superior algorithm for sorting linked lists, since it makes fewer total comparisons and isn’t susceptible to a poor pivot choice.
• Deterministic quicksort is O(n²) -> Each call to partition only sorts 1 element.
• If your pivot point chosen is median or randomise, you might get complexity O(nlogn)
• If split is 10:90, the complexity if O(nlogn)

Quick sort algorithm

This implementation of quick sort uses a helper method partition to partition the array around a pivot element. The quickSort method recursively sorts the left and right subarrays obtained by partitioning the array. The swap method is used to swap two elements in the array.

Note that this implementation is in-place, meaning it sorts the array without creating new arrays for the left, middle, and right subarrays. It works by partitioning the array in place around the pivot element.

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        // Partition the array and get the pivot index
        int pivotIndex = partition(arr, left, right);
        
        // Recursively sort the left and right subarrays
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int randomIndex = left + (int)(Math.random() * (right - left + 1));    
    // 1: swap random index and right 
    swap(arr, right, randomIndex); 
    // 2: now the arr[right] is pivot 
    int pivot = arr[right];
    
    // Initialize the partition index
    int i = left; 
    // index of smaller element and indicates the right position of pivot found so far
    
    // Partition the array around the pivot
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    
    // Move the pivot to its final position
    swap(arr, i, right);
    
    // Return the pivot index
    return i;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// BETTER TO select a random index as pivot
int randomIndex = left + (int)(Math.random() * (right - left + 1));

// 1: swap random index and right 
swap(unique, right, randomIndex); 
// 2 : now the unique[right] is pivot 
int pivotValue = unique[right];

Merge sort algorithm

Merge sort is defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

Merge sort has time complexity of O(nlogn), which means it can sort large arrays relatively quickly. (Guaranteed worse case) It is also a stable sort, which means the order of elements with equal values is preserved during the sort.

Space complexity: O(n)

Drawbacks:

1. Space complexity of O(n). Even if the array may be sorted, we still perform the whole process…

public void mergeSort(int[] nums, int low, int high){
  if(low < high){
    int mid = low + (high-low) / 2;
    mergeSort(nums, low, mid);
    mergeSort(nums, mid+1, high);
    merging(nums, low, mid, high);
  }
}

public void merging(int[] nums, int low, int mid, int high){
  int[] copy = new int[nums.length];
  for(int i=0; i<nums.length; i++){
    copy[i] = nums[i];
  }

  int i=low;
  int j=mid+1;
  int index=low;
  while(i<=mid && j<=high){
    if(copy[i] < copy[j]){
      nums[index] = copy[i];
      index++;
      i++;
    } else {
      nums[index] = copy[j];
      index++;
      j++;
    }
  }

  while(i<=mid){
    nums[index] = copy[i];
    index++;
    i++;
  }

  while(j<=high){
    nums[index] = copy[j];
    index++;
    j++;
  }
  
}

Bubble sort

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

Here’s a step-by-step explanation of how bubble sort works:

1. Start with an unsorted list of elements.
2. Compare the first element with the second element. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements (the second and third) and compare them. Again, if the second element is greater, swap them.
4. Repeat this process for each subsequent pair of elements, moving from left to right through the list.
5. After completing a pass through the entire list, the largest element will “bubble” up to the end of the list (i.e., it will be in its correct sorted position).
6. Repeat steps 2–5 for the remaining unsorted portion of the list (excluding the last sorted element from the previous pass).
7. Continue these passes until the entire list is sorted.

Bubble sort has a time complexity of O(n²) in the worst case, where n is the number of elements in the list. It is not considered an efficient sorting algorithm for large datasets, but it is easy to understand and implement.

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted list one element at a time. It works by dividing the list into two parts: a sorted portion and an unsorted portion. Initially, the sorted portion contains only the first element of the list, and the unsorted portion contains the remaining elements. The algorithm then iterates through the unsorted portion, taking each element and inserting it into its proper position within the sorted portion.

Here’s a step-by-step explanation of how insertion sort works:

1. Start with an unsorted list of elements.
2. Consider the first element as the sorted portion.
3. Take the next element from the unsorted portion and compare it with each element in the sorted portion, moving from right to left.
4. If the element from the unsorted portion is smaller than the current element in the sorted portion, shift the current element one position to the right.
5. Repeat step 4 until you find the correct position to insert the element from the unsorted portion.
6. Insert the element into its proper position within the sorted portion.
7. Repeat steps 3–6 for each remaining element in the unsorted portion.
8. Once all elements have been processed, the list is sorted.

Insertion sort has a time complexity of O(n²) in the worst case, where n is the number of elements in the list. It is considered efficient for small datasets or partially sorted lists.

When to use bigdecimal, float or double

BigDecimal, float, and double are all numeric data types in Java, but they have different use cases and precision levels. Here’s a brief overview of each type:

1. BigDecimal: BigDecimal is used when high precision is required in decimal calculations. It is an immutable arbitrary-precision decimal type that allows for precise decimal arithmetic, even for very large or very small numbers. BigDecimal is typically used in financial calculations, where rounding errors cannot be tolerated.
2. Float: Float is a single-precision 32-bit IEEE 754 floating-point type. It is used when performance is a concern and when the precision of the result is not critical. Float can represent a wide range of values but has limited precision and can result in rounding errors when performing calculations.
3. Double: Double is a double-precision 64-bit IEEE 754 floating-point type. It has higher precision than Float and can represent larger values with more accuracy. Double is generally used when higher precision is required, but performance is still important.

In general, use BigDecimal when precision is critical and use float or double when performance is a concern and precision is not as critical. However, it’s important to note that all numeric types have their trade-offs, so the choice ultimately depends on the specific use case and requirements of the application.

Synchronized

In Java, the synchronized keyword is used to enforce mutual exclusion or synchronization between multiple threads accessing a shared resource. When a method or a block of code is marked as synchronized, only one thread can execute that code at a time. Other threads that attempt to execute the same code must wait until the executing thread has released the lock on the shared resource.

ConcurrentHashMap

ConcurrentHashMap is a thread-safe implementation of the Map interface in Java. It provides a highly scalable and efficient way to store and retrieve key-value pairs concurrently from multiple threads.

ConcurrentHashMap achieves concurrency by partitioning the Map into segments, each with its own lock. This allows multiple threads to access different segments of the Map simultaneously, without blocking each other. ConcurrentHashMap also uses internal mechanisms to ensure that the Map is consistent even when multiple threads modify it concurrently.

Some of the key features of ConcurrentHashMap are:

• Thread-safe: ConcurrentHashMap is designed to be used in multi-threaded environments and supports concurrent read and write access by multiple threads.
• High scalability: ConcurrentHashMap is highly scalable and can handle a large number of threads accessing the Map simultaneously. It achieves this by partitioning the Map into segments and allowing concurrent access to different segments.
• Consistent: ConcurrentHashMap uses internal mechanisms to ensure that the Map is consistent even when multiple threads modify it concurrently. For example, it uses atomic operations to update values and a lock-free algorithm for reads.

When a thread updates a value in ConcurrentHashMap, 
it uses an atomic operation to ensure that the update is atomic and 
that other threads cannot see intermediate or inconsistent values. 


For example, when updating the value associated with a key, a thread 
might use the atomic compareAndSet operation, which compares the 
current value with the expected value and only sets the new value 
if the current value matches the expected value.

• Iteration support: ConcurrentHashMap provides support for safe and efficient iteration over its elements. It supports both key and value iteration, as well as iterating over the Map entries.
• Performance: ConcurrentHashMap provides excellent performance for concurrent read and write access. However, it may not perform as well as non-concurrent Maps for single-threaded access.

Overall, ConcurrentHashMap is a powerful and efficient data structure for concurrent programming in Java. It provides a safe and scalable way to store and retrieve key-value pairs in multi-threaded environments.

Executor Service

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

// create thread pool
final ExecutorService executor = Executors.newFixedThreadPool(5); // num of threads
// submit tasks to thread
IntStream.range(1, 1000)
. forEach(id -> executor.submit(() -> {
  // do whatever you want...
  // create object or whatever
}));

// wait for all threads to finish
executor.shudown();
executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);

Array blocking queue

ArrayBlockingQueue is a class in Java that implements the BlockingQueue interface. It is a bounded blocking queue that is backed by an array. This means that it has a fixed capacity and elements are added and removed in a FIFO (first-in-first-out) manner.

When you create an ArrayBlockingQueue object, you specify the maximum capacity of the queue. Once the queue is full, any attempt to add an element to the queue will block until there is space available. Similarly, if you try to remove an element from an empty queue, the operation will block until an element becomes available.

The ArrayBlockingQueue class provides methods for adding and removing elements from the queue, as well as methods for checking the state of the queue. For example, you can use the put method to add an element to the queue, which will block if the queue is full, or the take method to remove an element from the queue, which will block if the queue is empty.

ArrayBlockingQueue is a thread-safe class, which means that it can be safely used in a multi-threaded environment. It provides atomic operations for adding and removing elements from the queue, so multiple threads can safely access the queue at the same time without interfering with each other.

private final Queue<Call> calls = new ArrayBlockingQueue<>(numberOfAgents);

Runnable

Runnable is an interface in Java that is used to define a task that can be executed by a thread. It defines a single method run(), which has no arguments and no return value.

The run() method contains the code that should be executed when the thread is started. When a class implements the Runnable interface and its run() method is invoked, the code defined in that method will be executed in a separate thread.

public class MyRunnable implements Runnable {
    public void run() {
        // Code to be executed in a separate thread
        System.out.println("Hello from a separate thread!");
    }
}

To use MyRunnable in a separate thread, you can create a Thread object and pass an instance of MyRunnable to its constructor, like this:

public class Main {
    public static void main(String[] args) {
        // Create a Thread object with MyRunnable as its target
        Thread thread = new Thread(new MyRunnable());

        // Start the thread
        thread.start();

        // The code here will continue to run in the main thread
        System.out.println("Hello from the main thread!");
    }
}

If we want the Thread to sleep

public class MyRunnable implements Runnable {
    public void run() {
        System.out.println("Starting MyRunnable...");

        try {
            Thread.sleep(5000); // Sleep for 5 seconds
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("MyRunnable has finished.");
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Starting Main...");

        Thread thread = new Thread(new MyRunnable());
        thread.start();
        thread.join();
        System.out.println("Main has finished.");
    }
}

In this example, MyRunnable contains a call to Thread.sleep() that lasts for 5 seconds. When the Thread object is started in Main, it will execute the run() method of MyRunnable. When it reaches the Thread.sleep() call, it will be blocked for 5 seconds, during which time the main thread will continue to execute and print "Main has finished." Once the sleep time has elapsed, the thread executing MyRunnable will resume and print "MyRunnable has finished."

In Java, there are two types of threads: user threads and daemon threads. User threads are created by the user/application and continue to run until their work is complete or until the application explicitly terminates them. On the other hand, daemon threads are background threads that run in the background and do not prevent the application from terminating. If all user threads have finished executing, the JVM will exit, regardless of whether daemon threads are still running.

In the given code, the thread created using new Thread(new MyRunnable()) is a user thread. It is not set as a daemon thread explicitly. Therefore, if the main() thread completes its execution before the thread finishes running, the JVM will not exit until the thread completes.

Difference between StringBuilder and StringBuffer?

1. Thread safety: StringBuffer is thread-safe, which means it is designed to be used in a multi-threaded environment where multiple threads may try to access and modify the same string concurrently. On the other hand, StringBuilder is not thread-safe and is designed for use in a single-threaded environment.
2. Performance: StringBuilder is generally faster than StringBuffer, because it does not incur the overhead of synchronization that StringBuffer has to deal with in a multi-threaded environment.
3. Mutability: Both StringBuilder and StringBuffer are mutable, which means that you can modify the contents of the string that they represent. However, StringBuilder is generally preferred for most use cases, because it is faster and more efficient, unless thread-safety is a requirement.

What is volatile keyword?

In Java, the “volatile” keyword is used to indicate that a variable’s value may be modified by multiple threads, and that any thread accessing the variable should always read the latest value from main memory, rather than relying on a cached value.

Without the “volatile” keyword, a thread may read a stale value of the variable from its local cache, which can lead to incorrect behavior in a multithreaded program.

When a variable is declared as “volatile”, Java ensures that all writes to the variable are immediately visible to all threads, and that all reads of the variable are performed from main memory.

What is static block?

It is a set of instructions that is run only once when a class is loaded into memory.

It is also called a static initialisation block.

It spans all instances of a class.

public class SvC{
  static {
    // static block
  }
}

A constructor is run each time a new instance of a class is created.

What is ACID?

• Atomicity: This refers to the property of a transaction where all its operations are treated as a single unit of work that either succeeds completely or fails completely. In other words, a transaction is atomic, meaning that it should be treated as an indivisible and irreducible unit of work.
• Consistency: This refers to the property of a transaction where it ensures that the database is in a consistent state before and after the transaction is executed. This means that any changes made to the database should not violate any integrity constraints or business rules.
• Isolation: This refers to the property of a transaction where it ensures that concurrent transactions do not interfere with each other. In other words, each transaction should be executed independently of other transactions, as if it is the only transaction being executed.
• Durability: This refers to the property of a transaction where it ensures that once a transaction is committed, its changes to the database are permanent and survive any subsequent failures or system crashes. This means that the data is stored in a persistent and reliable way, and can be retrieved even if the system is restarted or fails.

When to use ExecutorService, or CompletableFuture?

ExecutorService executor = Executors.newFixedThreadPool(4);

List<Callable<Integer>> tasks = new ArrayList<>();
for (int i = 0; i < 10; i++) {
    tasks.add(() -> {
        // Task logic goes here
        return 1;
    });
}

List<Future<Integer>> futures = executor.invokeAll(tasks);

// Wait for all tasks to complete and retrieve their results
int sum = 0;
for (Future<Integer> future : futures) {
    sum += future.get();
}

executor.shutdown();

In this example, we create an ExecutorService with four threads using the newFixedThreadPool method. We then create a list of Callable objects that represent the tasks we want to perform concurrently. We submit the tasks to the thread pool using the invokeAll method, which returns a list of Future objects that we can use to retrieve the results of the tasks. We then wait for all tasks to complete and retrieve their results by iterating over the list of Future objects.

List<CompletableFuture<Integer>> futures = new ArrayList<>();
for (int i = 0; i < 10; i++) {
    CompletableFuture<Integer> future = CompletableFuture.supplyAsync(() -> {
        // Task logic goes here
        return 1;
    });
    futures.add(future);
}

CompletableFuture<Void> allFutures = CompletableFuture.allOf(futures.toArray(new CompletableFuture[0]));
CompletableFuture<List<Integer>> results = allFutures.thenApply(v -> {
    return futures.stream()
            .map(future -> future.join())
            .collect(Collectors.toList());
});

List<Integer> resultList = results.get();



///////////////////////////////////////
CompletableFuture<String> task1 = CompletableFuture.supplyAsync(() -> "Task 1");
CompletableFuture<String> task2 = CompletableFuture.supplyAsync(() -> "Task 2");
CompletableFuture<String> task3 = CompletableFuture.supplyAsync(() -> "Task 3");

CompletableFuture<String> result = task1
    .thenCompose((String t1Result) -> task2)
    .thenCompose((String t2Result) -> task3);

In this example, we create a list of CompletableFuture objects that represent the tasks we want to perform asynchronously. We use the supplyAsync method to perform each task in a separate thread and return a CompletableFuture that we can use to retrieve the task's result. We then use the allOf method to create a new CompletableFuture that completes when all of the tasks have completed. We use the thenApply method to specify an operation to be performed on the result of the allOf future when it becomes available. Finally, we retrieve the results of all tasks by calling the get method on the results future.

1. Use cases: ExecutorService is primarily used for managing a pool of threads that can be used to perform multiple tasks concurrently. It is designed for cases where you have a set of tasks that can be executed independently and don't depend on each other. CompletableFuture, on the other hand, is designed for cases where you have a set of tasks that may depend on each other and need to be executed in a specific order. It provides a way to chain together a series of asynchronous operations and combine their results.
2. Task dependencies: ExecutorService doesn't provide any built-in support for task dependencies. If you have a set of tasks that depend on each other, you will need to implement the dependency management yourself. CompletableFuture, on the other hand, provides a powerful way to express dependencies between tasks using methods like thenApply, thenCompose, and thenCombine.
3. Result retrieval: ExecutorService returns a Future object when you submit a task to the pool, which you can use to retrieve the result of the task or cancel the task if necessary. CompletableFuture, on the other hand, returns a CompletableFuture object that you can use to retrieve the result of the task or combine the results of multiple tasks.
4. Error handling: CompletableFuture provides more powerful error handling capabilities than ExecutorService. It allows you to specify a series of operations to be performed on a task's result when it becomes available, including error handling operations that can be performed if the task fails.
5. Asynchronous composition: CompletableFuture provides a way to perform asynchronous composition of tasks, which can be useful for tasks that involve I/O or other blocking operations. By chaining together a series of CompletableFuture objects, you can perform a series of tasks without blocking the current thread.

In summary, ExecutorService is best suited for managing a pool of threads and performing a set of independent tasks concurrently, while CompletableFuture is best suited for managing a set of tasks that may depend on each other and need to be executed in a specific order.

What is difference between user Thread and daemon Thread?

When we create a Thread in java program, it’s known as user thread. A daemon thread runs in background and doesn’t prevent JVM from terminating. When there are no user threads running, JVM shutdown the program and quits. A child thread created from daemon thread is also a daemon thread.

How to create a Thread in Java?

There are two ways to create Thread in Java — first by implementing Runnable interface and then creating a Thread object from it and second is to extend the Thread Class.

Java Thread Example | DigitalOcean

package com.journaldev.threads;

public class HeavyWorkRunnable implements Runnable {

    @Override
    public void run() {
        System.out.println("Doing heavy processing - START "+Thread.currentThread().getName());
        try {
            Thread.sleep(1000);
            //Get database connection, delete unused data from DB
            doDBProcessing();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Doing heavy processing - END "+Thread.currentThread().getName());
    }

    private void doDBProcessing() throws InterruptedException {
        Thread.sleep(5000);
    }

}

/////OR/////////

package com.journaldev.threads;

public class MyThread extends Thread {

    public MyThread(String name) {
        super(name);
    }

    @Override
    public void run() {
        System.out.println("MyThread - START "+Thread.currentThread().getName());
        try {
            Thread.sleep(1000);
            //Get database connection, delete unused data from DB
            doDBProcessing();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("MyThread - END "+Thread.currentThread().getName());
    }

    private void doDBProcessing() throws InterruptedException {
        Thread.sleep(5000);
    }
    
}

If your class provides more functionality rather than just running as Thread, you should implement Runnable interface to provide a way to run it as Thread. If your class only goal is to run as Thread, you can extend Thread class. Implementing Runnable is preferred because java supports implementing multiple interfaces. If you extend Thread class, you can’t extend any other classes.

What are the different states in the lifecycle of a Thread?

When we create a Thread in java program, its state is New. Then we start the thread that change it’s state to Runnable. Thread Scheduler is responsible to allocate CPU to threads in Runnable thread pool and change their state to Running. Other Thread states are Waiting, Blocked and Dead.

Can we call run() method of a Thread class

Yes, we can call run() method of a Thread class but then it will behave like a normal method. To actually execute it in a Thread, we need to start it using Thread.start() method.

Some extra knowledge about threads

Every thread has a priority, usually higher priority thread gets precedence in execution but it depends on Thread Scheduler implementation that is OS dependent. We can specify the priority of thread but it doesn’t guarantee that higher priority thread will get executed before lower priority thread. Thread priority is an _int_ whose value varies from 1 to 10 where 1 is the lowest priority thread and 10 is the highest priority thread.

Thread Scheduler is the Operating System service that allocates the CPU time to the available runnable threads. Once we create and start a thread, it’s execution depends on the implementation of Thread Scheduler. Time Slicing is the process to divide the available CPU time to the available runnable threads. Allocation of CPU time to threads can be based on thread priority or the thread waiting for longer time will get more priority in getting CPU time. Thread scheduling can’t be controlled by java, so it’s always better to control it from application itself.

Context Switching is the process of storing and restoring of CPU state so that Thread execution can be resumed from the same point at a later point of time. Context Switching is the essential feature for multitasking operating system and support for multi-threaded environment.

We can use Thread join() method to make sure all the threads created by the program is dead before finishing the main function.

When threads share resources, communication between Threads is important to coordinate their efforts. Object class wait(), notify() and notifyAll() methods allows threads to communicate about the lock status of a resource.

In Java every Object has a monitor and wait, notify methods are used to wait for the Object monitor or to notify other threads that Object monitor is free now. There is no monitor on threads in java and synchronization can be used with any Object, that’s why it’s part of Object class so that every class in java has these essential methods for inter thread communication.

Top 15 Java Multithreading, Concurrency Interview Questions Answers asked in Investment banks

How to do log tracing?

Open Trace

Jaeger: open source, end-to-end distributed tracing

Jaeger, inspired by Dapper and OpenZipkin, is a distributed tracing system released as open source by Uber Technologies. It is used for monitoring and troubleshooting microservices-based distributed systems, including:

Evolving Distributed Tracing at Uber Engineering

End-to-end distributed tracing is a technique used to monitor and analyse the flow of requests across multiple services in a distributed system. It helps developers and operators understand the interactions and performance characteristics of various components involved in handling a single user request or transaction.

A trace represents the path of a request as it flows through the system, encompassing all the services it touches. Each service generates trace data by recording information about its processing, such as timestamps, request and response data, and any significant events or operations.

These traces are then collected and correlated to reconstruct the complete flow of the request.

Jaeger is an open-source distributed tracing system that has gained popularity in the software development community.

Here’s a simplified overview of how Jaeger works:

1. Instrumentation: Developers add code to their services to generate trace data. This can be done using Jaeger client libraries, which integrate with various programming languages and frameworks.
2. Trace Generation: As requests flow through the system, each service generates trace data, including information such as span IDs, timestamps, and metadata.
3. Trace Collection: Jaeger agents or sidecar proxies collect the trace data emitted by the services and forward it to a central component called the Jaeger Collector.
4. Trace Storage: The Jaeger Collector receives the trace data, performs validation, and stores the traces in a distributed storage backend, such as Elasticsearch or Cassandra.
5. Indexing: The stored traces are indexed to enable efficient querying and retrieval. This allows users to search for traces based on specific criteria like service name, operation, or duration.
6. Visualization: Jaeger provides a web-based user interface called the Jaeger UI. It allows users to search and visualize traces, inspect individual spans, understand dependencies, and analyze performance metrics.

What is RPC?

RPC stands for Remote Procedure Call.

It is a communication protocol that allows a computer program to execute a procedure or function in a different address space or on a remote server. RPC enables the client-side program to invoke methods or procedures on the server-side program as if they were local, abstracting the complexities of network communication.

In an RPC system, the client program sends a request to the server program, specifying the procedure to be executed and any necessary arguments. The server program receives the request, performs the requested operation, and sends back a response to the client program with the result or any relevant data.

RPC typically follows a client-server architecture and relies on a specific network protocol to handle the communication between the client and server. Commonly used protocols for RPC include:

1. RPC over HTTP: This protocol uses HTTP as the transport layer, allowing RPC requests and responses to be transmitted over the web.
2. gRPC: gRPC is a modern RPC framework developed by Google. It uses the Protocol Buffers (protobuf) as the interface definition language and supports multiple programming languages. gRPC is known for its efficiency, scalability, and support for bi-directional streaming.
3. XML-RPC: This protocol uses XML to encode the requests and responses. It has been widely used in web services and allows for interoperability between different systems.
4. JSON-RPC: Similar to XML-RPC, JSON-RPC uses JSON for encoding requests and responses. It is lightweight and easy to use, often employed in web-based applications.

RPC provides a convenient way to build distributed systems by abstracting the remote procedure invocation mechanism. It enables different software components or services to communicate and collaborate seamlessly, even if they are running on different machines or in different environments. RPC has been widely used in various domains, including client-server applications, microservices architectures, and inter-process communication (IPC) scenarios.

RestTemplate

The RestTemplate and RPC (Remote Procedure Call) are two different concepts related to communication between distributed systems.

RestTemplate is a class provided by the Spring Framework in Java that simplifies the process of making HTTP requests to interact with RESTful web services. It provides a high-level API to send HTTP requests, handle responses, and deserialize JSON or XML data. RestTemplate is commonly used in Java applications to consume RESTful APIs.

On the other hand, RPC is a communication protocol that allows a client program to invoke procedures or methods on a remote server or service. RPC abstracts the complexities of network communication, making it appear as if the remote procedure invocation is local. RPC systems typically provide mechanisms for marshalling and unmarshalling data, handling network communication, and remote method invocation.

While both RestTemplate and RPC involve communication between distributed systems, they have different approaches and purposes:

1. RestTemplate: It is designed specifically for interacting with RESTful web services using HTTP. It follows the principles of the Representational State Transfer (REST) architectural style, where resources are identified by URIs, and different HTTP methods are used to perform operations on these resources. RestTemplate simplifies the process of making HTTP requests, handling headers, authentication, and serialization/deserialization of data formats like JSON or XML.
2. RPC: It is a more general communication protocol that allows a client program to invoke methods or procedures on a remote server. RPC abstracts the network communication details and makes remote invocation transparent to the client. RPC frameworks typically provide a language-agnostic interface definition language, serialization mechanisms, and transport protocols to enable communication between the client and server. Examples of RPC frameworks include gRPC, Apache Thrift, or Java RMI (Remote Method Invocation).

Iterators

An iterator is an object (like a pointer) that points to an element inside the container. We can use iterators to move through the contents of the container. They can be visualized as something similar to a pointer pointing to some location and we can access the content at that particular location using them.

Many types of iterators

1. random access
2. bidirectional
3. forward

private class ArrayListIterator implements Iterator<E> {
    private int currentIndex;

    public ArrayListIterator() {
        currentIndex = 0;
    }

    public boolean hasNext() {
        return currentIndex < size();
    }

    public E next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        E element = get(currentIndex);
        currentIndex++;
        return element;
    }

    public void remove() {
        if (currentIndex <= 0) {
            throw new IllegalStateException("next() must be called before remove()");
        }

        ArrayList.this.remove(currentIndex - 1);
        currentIndex--;
    }
}

For removal:

1. It checks if next() has been called at least once before calling remove(). If currentIndex <= 0, it means next() hasn't been called, so it throws an IllegalStateException to indicate that next() must be called first.
2. It invokes the remove(index) method of the ArrayList with currentIndex - 1 as the index. This removes the last retrieved element from the underlying ArrayList.
3. It decrements the currentIndex to adjust the position of the iterator after the removal.

Reactive programming

The alternative to reactive programming is imperative. Imperative code is a serial set of tasks, each running one at a time, each after the previous task.

In Reactive code, we have a set of tasks defined to process data, but those tasks can run in parallel. Each task can process subsets of the data, handling it off to the next task in line while it continues to work on another subset of data.

Imagine a water balloon as imperative programming. Reactive programming is like a garden hose, which allows for more scalability and performance.

Java Streams VS Reactive Streams

• Java Streams are synchronous and work with a finite set of data. They are a means of iterating over a collection with functions.
• Reactive streams support asynchronous processing of datasets of any size, including infinite datasets. They process data in real time, as it is available.

The Reactive streams specifications can be summed up by 4 interface definitions.

1. Publisher: Produce data and sends to a Subscriber per subscription. Declares a single method subscribe(), that a subscriber can subscribe to.
2. Subscriber: Can call request() to request for a certain amount of data to be sent.
3. Subscription: An object that the publisher will pass to the subscriber.
4. Processor: A combination of publisher and subscriber.

There are 2 core types

1. Mono: specialised reactive type that is optimised for when dataset is known to have no more than 1 data item
2. Flux: a pipeline of 0,1 or many data items

Mono.just("Name")
   .map(n -> n.toUpperCase())
   .map(cn -> "Hello, " + cn+ "!")
   .subscribe(System.out::println);

In the example above, there are 3 Monos. The final call to subcribe() subscribes to the mono, receives the data and prints it.

Creating Reactive types

1. create from object: Use just keyword
2. create from collection

Flux<String> fruitFlux = Flux.just("Apple", "Orange", "Grape");

// To subscribe to it, you need to
fruitFlux.subscribe(f -> System.out.println("Here's some fruits "+f);


// The lambda given to subscribe is a Java.util.Consumer to create a Reactive Streams 
// subscriber.

// To verify, you can use a StepVerifier.
// It subscribes to the reactive type and applies assertions against the
// data as it flows through the stream
StepVerifier
  .create(fruitFlux)
  .expectNext("Apple")
  .expectNext("Orange")...
  .verifyComplete();

// This is often used in testing




// Creating from collections
String[] fruits = new String[]{"Apple", "Orange", "Grape"};
Flux.fromArray(fruits);

// If you need to create a Flux from List, Set or other implementation
// of Iterable, you can pass it into the static fromIterable() method

Flux.fromIterable(set);

Flux.fromStream(stream);

You can combine 2 Flux objects using merge with

characterFlux.mergeWith(foodFlux);

To slow down, you can use .delayElements() or delaySubscription()

The order of elements in the merged flux will depend on the timing that they are emitted from the source.

Using Flux.zip(fluxOne, fluxTwo) will result in a tuple of items.

Spring Webflux -> a reactive web framework

Requests are handled in an event loop. Everything is handled as an event, including requests and callbacks from intenive operations like database and network operations. When a costly operation is needed, the event loop registers a callback for that operation to be performed in parallel, while it moves to handle other events.

When the operation completes, it is treated as an event by the event loop, same as requests.

@GetMapping("/recent")
public Flux<Taco> recentTacos(){
  return Flux.fromIterable(tacoRepo.findAll()).take(12):
}

Of course, ideally the database returns a reactive object.

import reactor.core.publisher.Flux;

@RestController
public class MyController {
    @GetMapping("/data-stream")
    public Flux<String> getDataStream() {
        return Flux.just("Data 1", "Data 2", "Data 3")
                .delayElements(Duration.ofSeconds(1)); // Simulating a delay of 1 second between each element
    }
}


import reactor.core.publisher.Flux;
import org.springframework.web.reactive.function.client.WebClient;

public class FluxConsumer {
    public static void main(String[] args) {
        WebClient client = WebClient.create();

        Flux<String> dataStream = client.get()
                .uri("http://localhost:8080/data-stream")
                .retrieve()
                .bodyToFlux(String.class);

        dataStream.subscribe(
            data -> System.out.println("Received: " + data),
            error -> System.err.println("Error: " + error),
            () -> System.out.println("Stream completed")
        );
    }
}

Why use Stream API?

1. concise and readable code
2. declarative programming -> Focus on what you want, rather than how to achieve it
3. parallel processing -> .parallel() allows multi-threading
4. lazy evaluation -> Optimise performance by avoiding unnecessary computations through Lazy evaluation.

What is Immutable class?

An immutable class is a class whose instances cannot be modified after they are created. Once an object of an immutable class is created, its state remains constant throughout its lifetime.

Immutable objects are thread-safe and can be safely shared among multiple threads without the need for synchronization.

• State cannot be modified
• Instance methods do not modify state
• No setter or mutator methods
• Equality and Hashcode based on content rather than references
• Thread Safe

Examples of Immutable classes in Java include String, Integer, LocalDate and BigInteger.

public final class ImmutablePerson {
    private final String name;
    private final int age;

    public ImmutablePerson(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

What is Intern?

It is a method provided by the String class that is used to optimized string storage and facilitate efficient string comparison.

When a string literal (e.g., "Hello") is encountered in Java code, a new String object is created to represent that string. However, if the same string literal is encountered again, the java runtime will automatically check if an identical string already exists in the intern pool. If found, the existing string in the pool is returned instead of creating a new String object. This can help conserve memory and improve performance in certain scenarios. If not, a new string is created and added to the pool.

String str1 = "Hello";
String str2 = new String("Hello");
String str3 = str2.intern();

System.out.println(str1 == str2);  // false
System.out.println(str1 == str3);  // true

intern() returns a reference to the string literal in the string pool. 
As a result, str3 refers to the same object as str1, and the comparison 
str1 == str3 evaluates to true.

The intern() method allows you to manually add a string to the intern pool or retrieve an existing interned string. If the string is already interned, the intern() method returns a reference to the interned string. If the string is not interned, the intern() method adds it to the intern pool and returns a reference to the interned string.

It’s important to note that excessive and unnecessary use of intern() can lead to increased memory usage and should be used judiciously when there is a genuine need for string interning and efficient string comparison.

We should avoid it if

• Large or unique string data
• Short lived strings
• Multi-threaded environments. intern() is thread safe and the intern pool is shared across all threads in the JVM. However, excessive use of intern() can introduce contention and synchronisation overhead due to multiple threads accessing and modifying the intern pool simultaneously.
• String manipulation happen frequently….since interned strings are immutable, modifying or concatenating them would require creating new instances.
• Limited memory resource. Interning strings can lead to increased memory consumption.

What is Completable Future, how is it different from Runnable?

Runnable interface represents a task or piece of code that can be executed asynchronously. It does not return a result or allow chaining of dependent tasks. Runnable does not have built-in support for handling exceptions.

Completable fulture is a more powerful construct that represents a future result of an asynchronous computation. It supports composing, chaining and combining multiple asynchronous operations. thenApply(), thenCompose(), thenCombine(). Provides various methods to handle exceptions, such as exceptionally(), handle() and whenComplete().

What is Java Boxing and Unboxing?

What happens if you return an Integer but we expect int?

@Override
public int hashCode(){
  return Objects.hashcode(this.x, this.y);
} // correct

@Override
public Integer hashCode(){
  return Objects.hashcode(this.x, this.y);
} // will this work?

// No it won't work because the function signature does not match the hashcode
// function that it is supposed to override.

Java boxing and unboxing are mechanisms that allow automatic conversion between primitive types and their corresponding wrapper classes (e.g., int and Integer). These conversions are performed by the Java compiler to provide convenience when working with primitive types as objects.

Boxing

Boxing is the process of converting a primitive type to its corresponding wrapper class. For example, converting an int to an Integer.

It happens automatically when a primitive value is assigned to a variable of the corresponding wrapper class. It can also occur implicitly when a primitive value is passed as an argument to a method that expects an object of the wrapper class.

int primitiveInt = 42;
Integer boxedInt = primitiveInt;  // Boxing int to Integer

Unboxing

Unboxing is the process of converting a wrapper class object to its corresponding primitive type. For example, converting an Integer to an int

It happens automatically when a wrapper class object is assigned to a variable of the corresponding primitive type. Unboxing can also occur when a wrapper class object is passed as an argument to a method that expects a primitive type.

Integer boxedInt = 42;
int primitiveInt = boxedInt;  // Unboxing Integer to int

Note that autoboxing and unboxing come with a performance cost, as they involve the creation and conversion of objects. In situations where performance is critical or when working with large datasets, it may be more efficient to manually perform explicit boxing or unboxing to control the conversions explicitly

What is checked and unchecked exception?

In Java, exceptions are divided into two categories: checked exceptions and unchecked exceptions.

Checked exceptions are exceptions that the compiler requires the programmer to handle explicitly by either catching them using a try-catch block or declaring them in the method signature using the throws clause.

These exceptions typically represent expected and recoverable error conditions, such as I/O errors, network errors, or file not found.

The compiler checks that the programmer has taken appropriate measures to handle checked exceptions, either by catching them or propagating them to the calling method.

public void readFile() {
    try {
        // Code that may throw a checked exception
        FileReader fileReader = new FileReader("file.txt");
        // ...
    } catch (IOException e) {
        // Exception handling code
        e.printStackTrace();
    }
}

Unchecked exceptions, also known as runtime exceptions, are exceptions that do not require explicit handling. The compiler does not enforce handling or declaring them in the method signature.

These exceptions typically represent unexpected and unrecoverable error conditions, such as null pointer dereference, arithmetic overflow, or invalid input arguments.

Unchecked exceptions are subclasses of RuntimeException or its subclasses.

public void divide(int dividend, int divisor) {
    // Runtime exception: ArithmeticException
    int result = dividend / divisor;
}

End for now :)