What are limitation of object Arrays?

The limitations of object arrays:

1. Not Type-Safe:

         Object[] objArray = new Object[3];
         objArray[0] = "Hello";
         objArray[1] = 10; // Adding an integer
         String str = (String) objArray[1]; // ClassCastException at runtime
               

   This issue arises because object arrays allow storing different types, but improper casting can cause runtime errors.
2. Not Suitable for Primitive Types:

         Object[] objArray = new Object[2];
         objArray[0] = 10; // Autoboxing to Integer
         objArray[1] = 20.5; // Autoboxing to Double
         int sum = (Integer) objArray[0] + (Double) objArray[1]; // Requires explicit casting
               

   Boxing and unboxing can lead to performance degradation and verbose code.
3. Fixed Size:

         Object[] objArray = new Object[3];
         objArray[0] = "Java";
         objArray[1] = "Python";
         objArray[2] = "C++";
         // Adding more elements is not possible, leading to ArrayIndexOutOfBoundsException
         objArray[3] = "JavaScript"; 
               

   The array cannot grow beyond its defined size.
4. Operations like searching, inserting, or deleting are not efficient, as arrays lack built-in methods for these operations.
5. Memory wastage can occur if the array is not fully utilized.

To overcome these limitations, use collections like ArrayList, which are dynamic, type-safe (using generics), and provide built-in methods for efficient operations.

What are differences between arrays and collections?

What are differences between arrays and ArrayList?

What is Collection API?

The Collection API in Java is a framework provided in the java.util package to handle groups of objects, known as collections. It provides a set of classes and interfaces to store, manipulate, and retrieve data efficiently. This API helps developers perform data structure-related tasks like searching, sorting, insertion, manipulation, and deletion in an easier and more organized way.

Main Features of the Collection API:

• Interfaces: The core of the Collection API is a set of interfaces like Collection, List, Set, Queue, and Map.
• Implementations: Includes concrete classes like ArrayList, LinkedList, HashSet, TreeSet, HashMap, and TreeMap.
• Algorithms: Provides utility classes like Collections to perform tasks such as sorting, searching, and shuffling.
• Generics Support: Allows type-safe collections, reducing the need for typecasting.
• Thread-Safety: Provides synchronized collection classes like Vector and thread-safe utilities in the java.util.concurrent package.
• Flexibility: Supports dynamic resizing, making it suitable for applications where the data size is unpredictable.

Key Interfaces in the Collection API:

• Collection: The root interface for all collection classes.
• List: Ordered collections that allow duplicate elements (e.g., ArrayList, LinkedList).
• Set: Collections that do not allow duplicate elements (e.g., HashSet, TreeSet).
• Queue: Collections that follow the FIFO (First In, First Out) principle (e.g., PriorityQueue).
• Map: Key-value pair collections (e.g., HashMap, TreeMap).

What are the key interfaces in the Java Collection Framework?

1. Collection Interface:

The root interface of the collection hierarchy, providing basic operations like adding, removing, and checking the size of a collection.

2. List(I):
• Insertion order is preserved.
• Duplicates are allowed.
• Implementations: ArrayList, LinkedList, Vector, Stack
3. Set(I):
• Insertion order is not preserved.
• Duplicates are not allowed.
• Implementations: HashSet, LinkedHashSet, TreeSet
4. SortedSet(I):
• Extends Set and maintains elements in a sorted order
• Implementation: TreeSet
5. Queue(I):
• Designed for holding elements before processing them.
• Follows FIFO (First In, First Out) principle.
• Implementations: PriorityQueue, LinkedList (as Queue), ArrayDeque
6. Deque(I):
• Extends Queue and allows insertion and removal from both ends
• Implementations: ArrayDeque, LinkedList (as Deque)
7. Map(I) (Not Extending Collection)
• A key-value pair-based collection that does not allow duplicate keys
• Implementations: HashMap, LinkedHashMap, TreeMap, Hashtable
8. SortedMap(I):
• Extends Map and maintains keys in a sorted order.
• Implementation: TreeMap

What is difference between Collection and Collections?

Collection list = new ArrayList<>();
  list.add("Java");

List list = new ArrayList<>();
  Collections.sort(list);

Why is the Collection interface not extended from the Cloneable and Serializable interfaces?

The Collection interface is a high-level abstraction, and its implementing classes may have different ways of handling cloning and serialization. Enforcing all collection implementations to be Cloneable and Serializable would restrict their flexibility.

Some collections, such as live views (e.g., subList in List), do not support cloning because they are directly linked to the original collection. Extending Cloneable in the Collection interface would force all implementations to support cloning, which may not always be feasible.

Serialization is not required for all collections. For example, some collections may store transient data (such as caching structures) that should not be persisted. If Collection extended Serializable, every implementation would be forced to support serialization, which is unnecessary for many use cases.

By keeping Cloneable and Serializable separate, Java allows developers to decide whether their specific collection implementation should support these features. Implementing classes like ArrayList, HashSet, and HashMap explicitly implement Serializable when needed.

Cloning a collection is not straightforward since it involves either a shallow copy (copying references) or a deep copy (copying objects inside the collection). Since the Collection interface does not define how elements should be cloned, it is left to individual implementations.

The decision to not extend Cloneable and Serializable in the Collection interface was made to ensure flexibility, maintain separation of concerns, and avoid unnecessary constraints on implementing classes. Instead, individual collection implementations can choose to support cloning and serialization based on their requirements.

What are the differences between Collection, List, Set, and Queue?

• Collection:
• Root interface of the Java Collection Framework.
• Defines common methods like add(), remove(), and size().
• Extended by List, Set, and Queue.
• Does not include Map, as it operates on key-value pairs.
• List:
• Ordered collection (sequence) of elements.
• Allows duplicate elements.
• Provides positional access via an index.
• Implementations: ArrayList, LinkedList, Vector, Stack.
• Set:
• Unordered collection that does not allow duplicate elements.
• Elements must be unique and may be sorted (depending on implementation).
• Implementations: HashSet (unordered), LinkedHashSet (insertion order), TreeSet (sorted).
• Queue:
• Follows FIFO (First-In-First-Out) ordering.
• Used for holding elements before processing.
• Variations like PriorityQueue allow elements to be processed in a specific order.
• Implementations: PriorityQueue, LinkedList (as Queue), ArrayDeque.

Explain about List Interface

The List interface is a subinterface of the Collection interface in the java.util package. It represents an ordered collection (also known as a sequence) that allows duplicate elements. Elements in a List can be accessed by their index, and insertion order is maintained.

Hierarchy:

• The List interface extends the Collection interface.
• Some common implementations of the List interface are:
  • ArrayList: A dynamic array implementation.
  • LinkedList: A doubly-linked list implementation.
  • Vector: A synchronized, dynamic array implementation.
  • Stack: A subclass of Vector implementing a LIFO (Last In, First Out) structure.

Key Features of the List Interface:

• Ordered: Elements are stored and accessed in the order they are added.
• Indexed: Allows access to elements by their zero-based index.
• Allows Duplicates: Can contain duplicate elements.

Key Methods of the List Interface:

• void add(int index, E element): Inserts the specified element at the specified position in the list.
• boolean addAll(int index, Collection c): Inserts all elements from the specified collection at the specified position.
• E get(int index): Returns the element at the specified position in the list.
• int indexOf(Object o): Returns the index of the first occurrence of the specified element, or -1 if it is not found.
• int lastIndexOf(Object o): Returns the index of the last occurrence of the specified element, or -1 if it is not found.
• E remove(int index): Removes the element at the specified position in the list.
• E set(int index, E element): Replaces the element at the specified position with the specified element.
• List subList(int fromIndex, int toIndex): Returns a view of the portion of the list between the specified fromIndex (inclusive) and toIndex (exclusive).

          import java.util.List;
          import java.util.ArrayList;
          import java.util.Collection;
          
          public class ListMethodsExample {
              public static void main(String[] args) {
                  // Create a List
                  List fruits = new ArrayList<>();
          
                  // Adding elements using add method
                  fruits.add("Apple");
                  fruits.add("Banana");
                  fruits.add("Mango");
                  fruits.add("Peach");
          
                  // Insert an element at a specific position using add(index, element)
                  fruits.add(1, "Grapes"); // Insert Grapes at index 1
        
                  // Insert all elements from another collection using addAll(index, collection)
                  Collection moreFruits = List.of("Pineapple", "Orange");
                  fruits.addAll(2, moreFruits); // Insert at index 2
          
                  // Retrieve an element at a specific index using get(index)
                  System.out.println("Element at index 2: " + fruits.get(2));
          
                  // Find the index of the first occurrence of a specific element using indexOf(object)
                  int indexOfMango = fruits.indexOf("Mango");
          
                  // Find the index of the last occurrence of a specific element using lastIndexOf(object)
                  fruits.add("Apple"); // Adding another Apple to test lastIndexOf
                  int lastIndexOfApple = fruits.lastIndexOf("Apple");
          
                  // Remove an element at a specific index using remove(index)
                  fruits.remove(4); // Removes "Peach"
          
                  // Replace an element at a specific index using set(index, element)
                  fruits.set(2, "Watermelon"); // Replace "Mango" with "Watermelon"
          
                  // Get a sublist of the list using subList(fromIndex, toIndex)
                  List sublist = fruits.subList(1, 4); // Get elements from index 1 to 3
                  System.out.println("Sublist of fruits: " + sublist);
              }
          }
                  

Explain about ArrayList Class

The ArrayList class in java.util is a resizable array implementation of the List interface. It allows dynamic growth and shrinkage of the array as elements are added or removed. ArrayList is one of the most commonly used collection classes in Java for storing and manipulating a group of objects.

Key Features of ArrayList:

• Dynamic Resizing: Automatically grows its size when the capacity is exceeded.
• Index-Based Access: Provides fast random access to elements via their index.
• Duplicate Elements: Allows duplicate elements and maintains insertion order.
• Non-Synchronized: ArrayList is not thread-safe; for concurrent access, use Collections.synchronizedList() or CopyOnWriteArrayList.
• Implements: Implements List, RandomAccess, Cloneable, and Serializable interfaces.

Key Methods:

• add(E e): Adds an element to the end of the list.
• get(int index): Retrieves the element at the specified index.
• set(int index, E element): Replaces the element at the specified index.
• remove(int index): Removes the element at the specified index.
• size(): Returns the number of elements in the list.
• clear(): Removes all elements from the list.

Example Usage:

  import java.util.*;
  
  public class ArrayListExample {
      public static void main(String[] args) {
          ArrayList list = new ArrayList<>();
  
          // Adding elements
         list.add("Java");
          list.add("Python");
          list.add("C++");
  
          // Accessing elements
          System.out.println("Element at index 1: " + list.get(1));
  
          // Updating an element
          list.set(1, "JavaScript");
  
          // Removing an element
          list.remove(2);
  
          // Iterating through the list
          System.out.println("Iterating over the list:");
          for (String s : list) {
              System.out.println(s);
          }
      }
  }
    

Advantages of ArrayList:

• Dynamic resizing eliminates the need for manual array resizing.
• Efficient for random access and retrieval of elements.
• Maintains insertion order of elements.

Disadvantages of ArrayList:

• Not thread-safe for concurrent access.
• Slower than LinkedList for insertions and deletions in the middle of the list.

What is the default size of an ArrayList?

• The default size of an ArrayList refers to its initial capacity.
• When an ArrayList is created using the default constructor new ArrayList<>(), the initial capacity is 10.
• Internally, ArrayList uses an array, which grows dynamically when elements are added.
• When the capacity is exceeded, the new capacity is calculated as oldCapacity + (oldCapacity / 2), which is 1.5 times the previous capacity.
• You can specify an initial capacity explicitly using new ArrayList<>(int initialCapacity) to optimize memory usage.

How does ensureCapacity() work in ArrayList?

• ensureCapacity(int minCapacity) is a method in ArrayList used to increase the capacity of the list to accommodate more elements.
• It helps in optimizing performance by reducing the number of times internal array resizing occurs.
• If the specified minCapacity is greater than the current capacity, the internal array is expanded.
• Internally, ensureCapacity() follows the resizing mechanism of ArrayList (increasing size by 1.5x when needed).
• It is particularly useful when a large number of elements are expected to be added, avoiding frequent reallocation.
• Example usage:

        ArrayList list = new ArrayList<>();
        list.ensureCapacity(50); // Ensures the list can hold at least 50 elements
    

What is the internal implementation of ArrayList in Java?

• Underlying Data Structure:
• ArrayList internally uses a dynamic array to store elements.
• The array grows automatically when more elements are added beyond its capacity.
• Default Capacity & Growth:
• When created using new ArrayList<>(), it has an initial capacity of 10.
• When the array reaches its capacity, a new array is created with 1.5 times the previous size, and elements are copied.
• Adding Elements:
• add(E e) appends an element at the end.
• add(int index, E e) inserts at a specific index (shifting elements).
• Resizing occurs if needed, using ensureCapacity().
• Accessing Elements:
• get(int index) retrieves an element in O(1) time complexity.
• Uses direct indexing as it is backed by an array.
• Removing Elements:
• remove(int index) shifts all elements after the removed index.
• Worst-case removal (from start) takes O(n) time complexity due to shifting.
• Iteration:
• Supports iteration using for loop, for-each, Iterator, and ListIterator.
• Thread-Safety:
• ArrayList is not synchronized, making it not thread-safe.
• For thread-safe operations, use Collections.synchronizedList() or CopyOnWriteArrayList.

What happens when an element is inserted into the middle of an ArrayList?

• Shifting Elements:
• When an element is inserted at a specific index using add(int index, E element), all elements from that index onward are shifted to the right.
• This shifting increases the time complexity to O(n) in the worst case.
• Resizing If Needed:
• If the internal array reaches its capacity, it is resized by 1.5x the current size.
• A new array is created, and all elements are copied over, adding extra overhead.
• Performance Impact:
• Insertion at the middle causes O(n) shifting cost, making it less efficient compared to a LinkedList, which has O(1) insertion time when a reference to the node is available.
• Example:

        ArrayList list = new ArrayList<>(Arrays.asList(1, 2, 4, 5));
        list.add(2, 3); // Inserting 3 at index 2
        System.out.println(list); // Output: [1, 2, 3, 4, 5]
    

• Best Practices:
• If frequent middle insertions are required, consider using a LinkedList instead of an ArrayList.
• For better performance, use batch processing instead of multiple insertions.

A bank transaction history feature requires fast access by index but also frequent updates. Which list implementation will you use?

• Best Choice: ArrayList
• ArrayList provides O(1) time complexity for accessing elements by index.
• Since transaction history needs fast retrieval, ArrayList is a good fit.
• Consideration for Updates:
• If updates involve modifying existing elements, ArrayList.set(index, element) performs in O(1) time, making it efficient.
• If frequent insertions/removals in the middle occur, shifting elements (O(n) cost) might be a downside.
• Alternative: LinkedList
• If frequent insertions and deletions (e.g., adding/removing transactions dynamically) are required, LinkedList could be considered.
• However, LinkedList has O(n) access time, which makes it slower for index-based retrieval.
• Final Decision:
• Use ArrayList if fast access by index is the top priority and updates mainly modify existing transactions.
• If frequent middle insertions or deletions are required, a hybrid approach (e.g., ArrayList + indexing techniques like HashMap) might be needed.

Explain about LinkedList Class

The LinkedList class in java.util is a doubly linked list implementation of the List and Deque interfaces. It allows dynamic memory allocation, where each element is a node containing a reference to the previous and next nodes, making it efficient for insertion and deletion operations.

Key Features of LinkedList:

• Doubly Linked Structure: Each node contains pointers to both the previous and the next nodes.
• Dynamic Size: Can grow or shrink dynamically without manual resizing.
• Efficient Insertions/Deletions: Particularly efficient for operations at the beginning or middle of the list.
• Implements: Implements List, Deque, Cloneable, and Serializable interfaces.
• Allows Duplicates: Supports duplicate elements and maintains insertion order.

Key Methods:

• add(E e): Adds an element to the end of the list.
• addFirst(E e): Adds an element at the beginning of the list.
• addLast(E e): Adds an element at the end of the list.
• remove(int index): Removes the element at the specified index.
• get(int index): Retrieves the element at the specified index.
• peek(): Retrieves the head of the list without removing it.
• poll(): Retrieves and removes the head of the list.

Example Usage:

Advantages of LinkedList:

• Efficient insertions and deletions, especially at the beginning or middle of the list.
• Can be used as both a List and a Deque, supporting stack and queue operations.
• Dynamic resizing eliminates the need for manual array resizing.

Disadvantages of LinkedList:

• Slower for random access compared to ArrayList due to sequential traversal.
• Consumes more memory because of the storage overhead for node pointers.

How to Get a Synchronized Version of ArrayList

The ArrayList class is not thread-safe by default. To get a synchronized version of an ArrayList, we can use the Collections.synchronizedList() method. This ensures that the ArrayList is synchronized, making it safe for use in multi-threaded environments.

Steps to Get a Synchronized ArrayList:

1. Create an instance of ArrayList.
2. Pass the ArrayList to the Collections.synchronizedList() method to obtain a synchronized version of it.
3. Use the synchronized list in your program.

Example:

  import java.util.*;
  
  public class SynchronizedArrayListExample {
      public static void main(String[] args) {
          // Create a regular ArrayList
          ArrayList<String> arrayList = new ArrayList<>();
          arrayList.add("Java");
          arrayList.add("Python");
          arrayList.add("C++");
  
          // Get a synchronized version of the ArrayList
          List<String> synchronizedList = Collections.synchronizedList(arrayList);
  
          // Accessing the synchronized list
          synchronized (synchronizedList) {
              for (String s : synchronizedList) {
                  System.out.println(s);
              }
          }
      }
  }
    

Key Points:

• The Collections.synchronizedList() method returns a thread-safe wrapper around the given ArrayList.
• While iterating over the synchronized list, it's recommended to explicitly synchronize on the list to avoid ConcurrentModificationException.
• This approach does not prevent logical issues like race conditions; additional synchronization might still be needed for complex operations.

Difference Between ArrayList and LinkedList

Summary: Choose ArrayList for fast random access and LinkedList for efficient insertions and deletions.

What are cursors in Collection?

In Java, a cursor is an interface that provides a way to traverse or iterate over elements in a Collection.

Java provides three types of cursors:
1. Enumerator
2. Iterator
3. ListIterator

Difference Between Enumeration and Iterator

Enumeration:
• Introduced in Java 1.0
• Applicable for Legacy classes like Vector and Stack
• Only allows forword traversal
• Cannot modify elements during iteration.

import java.util.*;

public class EnumerationExample {
    public static void main(String[] args) {
        Vector vector = new Vector<>();
        vector.add(1);
        vector.add(2);
        vector.add(3);

        Enumeration enumeration = vector.elements();
        while (enumeration.hasMoreElements()) {
            System.out.println(enumeration.nextElement());
        }
    }
}

      

Iterator:
• Introduced in: Java 1.2
• Applicable for: All Java Collection Framework classes (e.g., ArrayList, HashSet, LinkedList, etc.)
• Only allows forward traversal.
• Allows element removal during iteration using remove().
• Does not support element modification.

import java.util.*;

public class IteratorExample {
    public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            String fruit = iterator.next();
            if (fruit.equals("Banana")) {
                iterator.remove();  // Safe removal
            }
            System.out.println(fruit);
        }
        System.out.println("Final List: " + list);
    }
}

      

Difference Between Iterator and ListIterator:

Example for Iterator:

  import java.util.*;
  
  public class IteratorExample {
      public static void main(String[] args) {
          List list = new ArrayList<>(Arrays.asList("Java", "Python", "C++"));
          Iterator iterator = list.iterator();
          
          while (iterator.hasNext()) {
              System.out.println(iterator.next());
          }
      }
  }
    

Example for ListIterator:

  import java.util.*;
  
  public class ListIteratorExample {
      public static void main(String[] args) {
          List list = new ArrayList<>(Arrays.asList("Java", "Python", "C++"));
          ListIterator listIterator = list.listIterator();
          
          System.out.println("Forward Traversal:");
          while (listIterator.hasNext()) {
              System.out.println(listIterator.next());
          }
  
          System.out.println("Backward Traversal:");
          while (listIterator.hasPrevious()) {
              System.out.println(listIterator.previous());
          }
      }
  }
    

What is the difference between fail-fast and fail-safe iterators?

In Java, iterators can be categorized as Fail-Fast and Fail-Safe, depending on how they handle concurrent modifications during iteration.

• Fail-Fast Iterator:
• Throws ConcurrentModificationException if the collection is modified during iteration.
• Works directly on the original collection, detecting structural changes.
• Examples: Iterators of ArrayList, LinkedList, HashSet, HashMap, LinkedHashMap etc.
• Faster performance due to working directly on the collection.
• Should be used when thread-safety is not a concern.

import java.util.*;

public class FailFastExample {
    public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");

        Iterator iterator = list.iterator();
        
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
            list.add("Four");  // Modifying collection during iteration
        }
    }
}
        

• How to avoid it? : Use Iterator.remove() instead of list.remove()

          Iterator iterator = list.iterator();
            while (iterator.hasNext()) {
                String item = iterator.next();
                if (item.equals("Two")) {
                    iterator.remove();  // Allowed, won't throw exception
                }
            }
            
        

• Fail-Safe Iterator:
• Does not throw ConcurrentModificationException if the collection is modified during iteration.
• Works on a cloned copy of the collection, ensuring modifications do not affect iteration.
• Examples: Iterators of CopyOnWriteArrayList, CopyOnWriteArraySet, ConcurrentHashMap.
• Consumes more memory due to creating a separate copy.
• Useful in concurrent environments where modifications are frequent.

import java.util.concurrent.CopyOnWriteArrayList;
import java.util.Iterator;

public class FailSafeExample {
    public static void main(String[] args) {
        CopyOnWriteArrayList list = new CopyOnWriteArrayList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");

        Iterator iterator = list.iterator();
        
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
            list.add("Four");  // Allowed in Fail-Safe Iterators
        }
    }
}

        

Explain Set Interface

The Set interface is a subinterface of the Collection interface in the java.util package. It represents a collection that does not allow duplicate elements. A Set is primarily used when uniqueness is required, and it does not maintain any specific order of elements unless explicitly stated by its implementation.

Hierarchy:

• The Set interface extends the Collection interface.
• Some common implementations of the Set interface are:
  • HashSet: Implements a hash table to store elements and does not guarantee the order of elements.
  • LinkedHashSet: Extends HashSet and maintains the insertion order of elements.
  • TreeSet: Implements a balanced tree structure and maintains elements in their natural order or a custom order defined by a comparator.

Key Features of the Set Interface:

• No Duplicates: Ensures that all elements in the collection are unique.
• Unordered: Does not guarantee any specific order of elements (except for implementations like LinkedHashSet or TreeSet).

Key Methods of the Set Interface:

• boolean add(E e): Adds the specified element to the set if it is not already present.
• boolean contains(Object o): Checks if the set contains the specified element.
• boolean remove(Object o): Removes the specified element from the set if it is present.
• int size(): Returns the number of elements in the set.
• Iterator iterator(): Returns an iterator over the elements in the set.
• boolean isEmpty(): Checks if the set is empty.
• void clear(): Removes all elements from the set.

SortedSet Interface:

The SortedSet interface is a subinterface of the Set interface in the java.util package. It represents a set that maintains its elements in a sorted order. The sorting can be based on the natural order of elements (if the elements implement the Comparable interface) or a custom order defined by a Comparator.

Hierarchy:

• The SortedSet interface extends the Set interface.
• The TreeSet class is a common implementation of the SortedSet interface.

Key Features of the SortedSet Interface:

• Sorted Order: Ensures that elements are sorted either in their natural order or based on a custom comparator.
• No Duplicates: Ensures that all elements in the set are unique.

Key Methods of the SortedSet Interface:

• E first(): Returns the first (lowest) element in the set.
• E last(): Returns the last (highest) element in the set.
• SortedSet headSet(E toElement): Returns a view of the portion of the set whose elements are strictly less than the specified element.
• SortedSet tailSet(E fromElement): Returns a view of the portion of the set whose elements are greater than or equal to the specified element.
• SortedSet subSet(E fromElement, E toElement): Returns a view of the portion of the set whose elements range from fromElement, inclusive, to toElement, exclusive.
• Comparator<? super E> comparator(): Returns the comparator used to order the elements, or null if the set uses natural ordering.

Common Implementation of the SortedSet Interface:

• TreeSet: A balanced tree implementation of the SortedSet interface. It maintains the elements in a sorted order.

NavigableSet Interface:

• The NavigableSet interface in Java extends the SortedSet interface.
• It provides methods for navigating and retrieving elements based on closest matches.
• Introduced in Java 1.6
• Supports ascending and descending order iteration.
• Implements all methods of SortedSet (which extends Set).
• Available Implementations: TreeSet (most commonly used).
• Use : When you need navigation-based operations (lower(), ceiling(), higher(), etc.).

Explain HashSet Class

The HashSet class in java.util implements the Set interface and is backed by a hash table (actually a HashMap instance). It does not allow duplicate elements and does not maintain the insertion order of elements. The primary purpose of a HashSet is to provide a collection of unique elements and to allow fast retrieval.

Key Features of HashSet:

• No Duplicates: A HashSet does not allow duplicate elements. If you try to add a duplicate, the set remains unchanged.
• No Guaranteed Order: The elements in a HashSet are unordered, meaning there is no guarantee of the order in which the elements are stored or retrieved.
• Performance: Provides constant time performance for basic operations like add, remove, and contains (O(1) complexity) assuming the hash function distributes elements uniformly.
• Null Elements: A HashSet allows a single null element, but more than one null is not allowed.
• Implements: Implements the Set, Cloneable, Serializable, and Iterable interfaces.

Key Methods:

• add(E e): Adds the specified element to the set if it is not already present.
• remove(Object o): Removes the specified element from the set.
• contains(Object o): Returns true if the set contains the specified element.
• size(): Returns the number of elements in the set.
• clear(): Removes all the elements from the set.
• isEmpty(): Returns true if the set is empty.

Example Usage:

  import java.util.*;
  
  public class HashSetExample {
      public static void main(String[] args) {
          // Creating a HashSet
          HashSet set = new HashSet<>();
  
          // Adding elements to the HashSet
          set.add("Java");
          set.add("Python");
          set.add("C++");
          set.add("Java");  // Duplicate, will be ignored
  
          // Displaying the HashSet
          System.out.println("HashSet: " + set);
  
          // Checking if an element exists
          System.out.println("Contains 'Python': " + set.contains("Python"));
  
          // Removing an element
          set.remove("C++");
          System.out.println("After removing 'C++': " + set);
  
          // Checking size
          System.out.println("Size of HashSet: " + set.size());
      }
  }
    

What is the difference between HashSet, LinkedHashSet, and TreeSet?

• HashSet:
• HashSet is an unordered collection that does not guarantee the order of elements.
• It uses a hash table for storing elements and ensures uniqueness of elements using the hash code and equals() methods.
• It provides O(1) time complexity for basic operations like add, remove, and contains, assuming a good hash function.
• LinkedHashSet:
• LinkedHashSet is an ordered version of the HashSet. It maintains the insertion order of elements.
• Internally, it uses a hash table along with a linked list to maintain the order of elements.
• It ensures uniqueness of elements like HashSet, but also maintains the order of insertion.
• Operations like add, remove, and contains take O(1) time on average, but maintaining order adds a slight overhead compared to HashSet.
• TreeSet:
• TreeSet is a sorted set that stores elements in their natural order or based on a custom comparator.
• It uses a Red-Black tree to store elements, which ensures that the set is always sorted.
• While it guarantees uniqueness, it does not allow elements to be stored in arbitrary order, unlike HashSet or LinkedHashSet.
• Basic operations like add, remove, and contains take O(log n) time due to the underlying tree structure.
• Summary of Key Differences:
• Order:
  • HashSet: No guaranteed order.
  • LinkedHashSet: Maintains insertion order.
  • TreeSet: Stores elements in sorted order (either natural or using a comparator).
• Performance:
  • HashSet: O(1) for add, remove, contains.
  • LinkedHashSet: O(1) for add, remove, contains (with slight overhead for maintaining order).
  • TreeSet: O(log n) for add, remove, contains due to the tree structure.
• Use Case:
  • HashSet: Use when you only care about uniqueness and do not need order.
  • LinkedHashSet: Use when you care about both uniqueness and maintaining the order of insertion.
  • TreeSet: Use when you need to store elements in a sorted order and care about efficient searching and navigation.

Why does HashSet allow only one null value?

• HashSet stores elements using a hash table:
• HashSet uses a hash table (backed by a HashMap) to store its elements.
• In the hash table, the uniqueness of elements is determined by their hash code and equals() method.
• Hash code of null:
• The null value has a unique behavior in the context of hash tables.
• null has a hash code of 0, and the `equals()` method is not called for null (because it is never equal to any other object).
• This ensures that only one null can exist in the set, since all `null` elements would have the same hash code, and adding a second null would violate the uniqueness property of the set.
• Why only one null?
• Since the hash code of null is always 0, it will always map to the same bucket in the hash table.
• Even if you try to insert another null value, it will clash with the existing null value because they have the same hash code, leading to the rejection of the duplicate.
• Thus, only one null value can be stored in a HashSet to maintain the set's property of uniqueness.

How does HashSet maintain uniqueness?

• Underlying Data Structure:
• HashSet internally uses a hash table (backed by a HashMap) to store its elements.
• Each element in the HashSet is stored as a key in the hash table, and the values are dummy placeholders (often Boolean.TRUE).
• Uniqueness Mechanism:
• When an element is added to a HashSet, the set checks if the element already exists based on its hash code and equals() method.
• If the element’s hash code matches an existing element’s hash code, equals() is used to compare the elements for equality.
• If the element is equal to an existing element (i.e., both hash code and equals() comparison return true), it is not added to the set.
• This guarantees that only unique elements are stored in the set.
• Hash Code and Equals:
• HashSet relies on the correct implementation of the hashCode() and equals() methods of the objects being stored.
• If two objects have the same hash code but are not equal, they may still be stored as separate entries (but this is inefficient).
• Example:

        HashSet set = new HashSet<>();
        set.add("A");
        set.add("B");
        set.add("A"); // Duplicate, won't be added

        System.out.println(set); // Output: [A, B]
    

• Advantages:
• HashSet provides constant time complexity (O(1)) for basic operations like add, remove, and contains, assuming a good hash function.

What Happens When You Try to Insert Duplicate Values in a Set?

• When you attempt to add an element that already exists in the set, the add() method will return false, indicating that the element was not added because it was already present.
• The internal structure of the set ensures that only unique elements are stored.
• This behavior is consistent across different types of sets, such as HashSet, LinkedHashSet, and TreeSet.

LinkedHashSet Class:

The LinkedHashSet class in Java is part of the java.util package and extends the HashSet class. It implements the Set interface and is backed by a hash table (like HashSet) and a linked list that maintains the insertion order of elements. This means that in a LinkedHashSet, the elements are stored in the order in which they were added.

Key Features of LinkedHashSet:

• Insertion Order: Unlike HashSet, which does not guarantee any specific order, LinkedHashSet maintains the order of insertion. Elements are retrieved in the order they were added.
• No Duplicates: Like all sets, LinkedHashSet does not allow duplicate elements. It will ignore any attempt to add a duplicate element.
• Performance: LinkedHashSet provides constant time performance for basic operations like add(), remove(), and contains(), similar to HashSet. However, it has some overhead due to maintaining the linked list for the order.
• Allows Null: LinkedHashSet allows a single null element.
• Maintains Order of Insertion: The main difference between HashSet and LinkedHashSet is that the latter maintains the order of insertion, meaning the elements are returned in the same order they were added to the set.

Key Methods:

• add(E e): Adds the specified element to the set if it is not already present.
• remove(Object o): Removes the specified element from the set.
• contains(Object o): Returns true if the set contains the specified element.
• size(): Returns the number of elements in the set.
• clear(): Removes all elements from the set.
• isEmpty(): Returns true if the set is empty.

Example Usage:

  import java.util.*;
  
  public class LinkedHashSetExample {
      public static void main(String[] args) {
          // Creating a LinkedHashSet
          LinkedHashSet linkedHashSet = new LinkedHashSet<>();
          
          // Adding elements
          linkedHashSet.add("Java");
          linkedHashSet.add("Python");
          linkedHashSet.add("C++");
          linkedHashSet.add("Java");  // Duplicate, will be ignored
          
          // Displaying the LinkedHashSet
          System.out.println("LinkedHashSet: " + linkedHashSet);
  
          // Checking if an element exists
          System.out.println("Contains 'Python': " + linkedHashSet.contains("Python"));
  
          // Removing an element
          linkedHashSet.remove("C++");
          System.out.println("After removing 'C++': " + linkedHashSet);
      }
  }
  Output:
  LinkedHashSet: [Java, Python, C++]
  Contains 'Python': true
  After removing 'C++': [Java, Python]
    

Explain TreeSet Class

The TreeSet class in Java is part of the java.util package and implements the Set interface. It is backed by a TreeMap and stores elements in a sorted order. Unlike other set implementations like HashSet or LinkedHashSet, which do not guarantee order, a TreeSet automatically arranges its elements according to their natural ordering or by a comparator provided at the time of set creation.

Key Features of TreeSet:

• Sorted Order: Elements in a TreeSet are stored in ascending order by default. If the elements are comparable, they are sorted based on their natural ordering. If not, a custom comparator can be provided.
• No Duplicates: Like other Set implementations, TreeSet does not allow duplicate elements.
• Performance: The basic operations like add(), remove(), and contains() have a time complexity of O(log n) because the underlying data structure is a balanced tree.
• Null Elements: TreeSet does not allow null elements if the set uses natural ordering. This is because null cannot be compared with other elements in the set.
• Implements: TreeSet implements the Set, NavigableSet, and Cloneable interfaces.

Key Methods:

• add(E e): Adds the specified element to the set if it is not already present, and returns true. If the element is already present, it returns false.
• remove(Object o): Removes the specified element from the set.
• first(): Returns the first (lowest) element in the set.
• last(): Returns the last (highest) element in the set.
• ceiling(E e): Returns the least element in the set greater than or equal to the specified element.
• floor(E e): Returns the greatest element in the set less than or equal to the specified element.

Example Usage:

  import java.util.*;
  
  public class TreeSetExample {
      public static void main(String[] args) {
          // Creating a TreeSet
          TreeSet treeSet = new TreeSet<>();
          
          // Adding elements
          treeSet.add(10);
          treeSet.add(20);
          treeSet.add(15);
          treeSet.add(30);
          treeSet.add(20);  // Duplicate, will be ignored
          
          // Displaying the TreeSet
          System.out.println("TreeSet: " + treeSet);
  
          // Finding the first and last elements
          System.out.println("First Element: " + treeSet.first());
          System.out.println("Last Element: " + treeSet.last());
      }
  }
  Output:
  TreeSet: [10, 15, 20, 30]
  First Element: 10
  Last Element: 30

    

How does TreeSet maintain sorting order?

• Internal Data Structure:
• TreeSet is backed by a Red-Black tree, which is a self-balancing binary search tree.
• The elements in a TreeSet are stored in the tree nodes in such a way that the tree remains balanced, ensuring efficient access and insertion.
• Sorting Mechanism:
• TreeSet sorts its elements using their natural order (i.e., the order defined by the Comparable interface).
• If the elements implement the Comparable interface, the compareTo() method is used to determine the sorting order.
• For objects that do not implement Comparable, you can provide a custom sorting order via a Comparator.
• The Red-Black tree ensures that elements are always inserted in sorted order, and this sorting is maintained with each operation, including insertions, deletions, and lookups.
• Example of Natural Ordering:

        TreeSet set = new TreeSet<>();
        set.add(5);
        set.add(1);
        set.add(3);
        set.add(2);

        System.out.println(set); // Output: [1, 2, 3, 5]
    

• Custom Ordering (using Comparator):
• If a custom sorting order is required, a Comparator can be provided to the TreeSet.
• In this case, the Comparator will define the sorting rules for the elements.

        TreeSet set = new TreeSet<>(Comparator.reverseOrder());
        set.add(5);
        set.add(1);
        set.add(3);
        set.add(2);

        System.out.println(set); // Output: [5, 3, 2, 1]
    

• Performance:
• Because of the underlying Red-Black tree structure, operations like add, remove, and contains are O(log n) in time complexity.
• Maintaining the sorted order ensures that the set remains efficient for searching and iteration.
• Use Case:
• TreeSet is ideal when you need to store unique elements that are sorted automatically, either in their natural order or using a custom comparator.

Why is HashSet faster than TreeSet?

• Internal Data Structure:
• HashSet is backed by a hash table (or a hash map), which provides fast access to elements using a hash code.
• TreeSet is backed by a Red-Black tree, a self-balancing binary search tree, which has a more complex structure for maintaining sorting order.
• Performance of Basic Operations:
• In HashSet, operations like add, remove, and contains typically have an average time complexity of O(1), assuming a good hash function and low collision rates.
• In TreeSet, the operations like add, remove, and contains take O(log n) time due to the underlying Red-Black tree structure, which maintains sorted order at all times.
• Sorting Overhead in TreeSet:
• TreeSet maintains elements in a sorted order (either natural or custom sorting via a comparator), which requires extra effort during every insertion and deletion.
• This sorting adds additional overhead because the tree structure needs to maintain balance after each modification (insertion or deletion) to ensure efficient searching and iteration.
• Cost of Comparison:
• In a TreeSet, elements are compared during insertion and lookup to maintain the sorting order. This comparison is generally O(log n) in time complexity, depending on the number of nodes in the tree.
• In a HashSet, no comparisons are required for basic operations. Instead, elements are directly inserted or searched using their hash codes, which is faster than maintaining order.
• Use Case Differences:
• HashSet is preferred when you need fast operations for storing and accessing unique elements without caring about order.
• TreeSet is used when you need sorted elements and are willing to sacrifice some performance for automatic sorting of data.
• Summary of Key Differences:
• HashSet: Faster for basic operations (add, remove, contains) due to its O(1) time complexity (average case).
• TreeSet: Slower for basic operations due to the need to maintain sorted order and balance the tree, with time complexity of O(log n).

In an authentication system, you need to store unique user session tokens efficiently. Which Set implementation is best?

• Best Set Implementation: HashSet
• HashSet is the best choice when you need to store unique elements (such as session tokens) with fast access and insertion.
• It uses a hash table internally, which provides constant time complexity (average O(1)) for basic operations like add, remove, and contains.
• Why HashSet is Ideal for Session Tokens:
• Efficiency: Since session tokens are typically unique and need to be checked frequently for existence or removed after the session expires, HashSet is efficient because it doesn't require comparisons or sorting.
• No Ordering Required: In this case, the order of session tokens does not matter, and HashSet allows for fast access without maintaining any order, unlike TreeSet, which sorts the elements.
• Handling Duplicates: Since HashSet ensures uniqueness, you won't have to worry about storing duplicate session tokens.
• Why Not Other Set Implementations?
• TreeSet: Although it ensures uniqueness, it maintains elements in a sorted order. The sorting overhead and the fact that session tokens don't need to be sorted makes it less efficient for this use case compared to HashSet.
• LinkedHashSet: While it maintains insertion order, the extra overhead for maintaining the order makes it unnecessary for the use case of storing unique session tokens when the order is irrelevant.
• Summary:
• HashSet is the optimal choice for storing unique user session tokens efficiently in terms of time complexity and memory usage.

Map Interface:

The Map interface is part of the java.util package and represents a collection of key-value pairs, where each key is unique, and each key maps to exactly one value. It is not a subtype of Collection but provides methods to store, retrieve, and manipulate key-value mappings.

Key Features of the Map Interface:

• Key-Value Pairs: A Map stores entries, where each entry consists of a key and a value.
• Unique Keys: Every key in the map is unique, but the values associated with keys can be duplicate.
• Methods: Common methods include put() to add mappings, get() to retrieve values, and remove() to delete mappings.

      import java.util.*;
      
      public class MapExample {
          public static void main(String[] args) {
              Map map = new HashMap<>;
      
              // Adding key-value pairs
              map.put("Java", 10);
              map.put("Python", 15);
              map.put("C++", 12);
      
              // Retrieving a value using a key
              System.out.println("Java: " + map.get("Java"));
      
              // Checking if a key exists
              System.out.println("Contains 'Python': " + map.containsKey("Python"));
      
              // Iterating over keys and values
              for (Map.Entry entry : map.entrySet()) {
                  System.out.println(entry.getKey() + ": " + entry.getValue());
              }
          }
      }
      Output:
      Java: 10
      Contains 'Python': true
      Java: 10
      Python: 15
      C++: 12
        

Common Implementations of the Map Interface:

• HashMap: A widely used implementation that stores elements based on the hash of the keys, offering constant time performance for basic operations.
• TreeMap: A sorted map implementation that orders the keys according to their natural order or a custom comparator.
• LinkedHashMap: An implementation that maintains the order of insertion of the keys.
• Hashtable: An older, synchronized implementation (replaced by ConcurrentHashMap in modern applications for thread-safety).

Explain SortedMap Interface

The SortedMap interface is a subinterface of the Map interface in the java.util package. It represents a map that maintains its keys in a sorted order, either in their natural order or according to a custom comparator provided at the time of map creation. The elements in a SortedMap are ordered based on the keys, and it provides additional methods to deal with ranges of keys.

Key Features of the SortedMap Interface:

• Sorted Keys: The keys are always stored in a sorted order (either natural or based on a Comparator).
• Additional Range Methods: It provides methods to view submaps, headmaps, and tailmaps based on a specific key range.
• Methods: Methods like firstKey(), lastKey(), headMap(), and tailMap() help with navigating through the map's sorted keys.

Common Implementation of the SortedMap Interface:

• TreeMap: The most common implementation of the SortedMap interface, which stores key-value pairs in a red-black tree structure and ensures that keys are kept in sorted order.

Key Methods of the SortedMap Interface:

• K firstKey(): Returns the first (lowest) key in the map.
• K lastKey(): Returns the last (highest) key in the map.
• SortedMap headMap(K toKey): Returns a view of the portion of the map whose keys are less than the specified key.
• SortedMap tailMap(K fromKey): Returns a view of the portion of the map whose keys are greater than or equal to the specified key.
• SortedMap subMap(K fromKey, K toKey): Returns a view of the portion of the map whose keys are between fromKey (inclusive) and toKey (exclusive).

Example Usage:

import java.util.*;

public class SortedMapExample {
  public static void main(String[] args) {
      SortedMap sortedMap = new TreeMap<>();

      // Adding key-value pairs
      sortedMap.put("Java", 10);
      sortedMap.put("Python", 15);
      sortedMap.put("C++", 12);
      sortedMap.put("JavaScript", 18);

      // Displaying the sorted map
      System.out.println("SortedMap: " + sortedMap);

      // Accessing the first and last keys
      System.out.println("First Key: " + sortedMap.firstKey());
      System.out.println("Last Key: " + sortedMap.lastKey());

      // Submaps
      System.out.println("HeadMap (less than 'JavaScript'): " + sortedMap.headMap("JavaScript"));
      System.out.println("TailMap (greater than or equal to 'C++'): " + sortedMap.tailMap("C++"));
      System.out.println("SubMap (from 'Java' to 'Python'): " + sortedMap.subMap("Java", "Python"));
  }
}
Output:
SortedMap: {C++=12, Java=10, JavaScript=18, Python=15}
First Key: C++
Last Key: Python
HeadMap (less than 'JavaScript'): {C++=12, Java=10}
TailMap (greater than or equal to 'C++'): {C++=12, Java=10, JavaScript=18, Python=15}
SubMap (from 'Java' to 'Python'): {Java=10, JavaScript=18}

Eplain NavigableMap Interface

The NavigableMap interface is a subinterface of SortedMap in the java.util package. It extends the functionality of SortedMap by providing navigation methods for retrieving entries based on their proximity to a given key. It supports bidirectional traversal and allows precise control over subsets of the map.

Key Features of NavigableMap:

• Proximity Navigation: Methods like lowerKey(), floorKey(), ceilingKey(), and higherKey() help in finding keys near a specified key.
• Reverse Order: The descendingMap() method provides a view of the map in reverse order.
• Subset Views: Allows creation of subsets with precise control over inclusion/exclusion of boundary keys using subMap(), headMap(), and tailMap().
• Polling Operations: Methods like pollFirstEntry() and pollLastEntry() allow retrieval and removal of the first or last entry.

Common Implementation:

• TreeMap: The most common implementation of NavigableMap, which maintains key-value pairs in a red-black tree structure and provides navigation methods.

Key Methods of NavigableMap:

• K lowerKey(K key): Returns the greatest key strictly less than the specified key.
• K floorKey(K key): Returns the greatest key less than or equal to the specified key.
• K ceilingKey(K key): Returns the smallest key greater than or equal to the specified key.
• K higherKey(K key): Returns the smallest key strictly greater than the specified key.
• NavigableMap descendingMap(): Returns a map with the keys in reverse order.
• Map.Entry pollFirstEntry(): Retrieves and removes the first entry in the map.
• Map.Entry pollLastEntry(): Retrieves and removes the last entry in the map.

Example Usage:

import java.util.*;

public class NavigableMapExample {
    public static void main(String[] args) {
        NavigableMap navigableMap = new TreeMap<>();

        // Adding key-value pairs
        navigableMap.put("Java", 10);
        navigableMap.put("Python", 15);
        navigableMap.put("C++", 12);
        navigableMap.put("JavaScript", 18);

        // Displaying the map
        System.out.println("NavigableMap: " + navigableMap);

        // Navigation operations
        System.out.println("Lower Key (less than 'Python'): " + navigableMap.lowerKey("Python"));
        System.out.println("Floor Key (less than or equal to 'Python'): " + navigableMap.floorKey("Python"));
        System.out.println("Ceiling Key (greater than or equal to 'C++'): " + navigableMap.ceilingKey("C++"));
        System.out.println("Higher Key (greater than 'Java'): " + navigableMap.higherKey("Java"));

        // Reverse order view
        System.out.println("Descending Map: " + navigableMap.descendingMap());

        // Polling operations
        System.out.println("Poll First Entry: " + navigableMap.pollFirstEntry());
        System.out.println("Poll Last Entry: " + navigableMap.pollLastEntry());
        System.out.println("Map after polling: " + navigableMap);
    }
}
Output:
NavigableMap: {C++=12, Java=10, JavaScript=18, Python=15}
Lower Key (less than 'Python'): JavaScript
Floor Key (less than or equal to 'Python'): Python
Ceiling Key (greater than or equal to 'C++'): C++
Higher Key (greater than 'Java'): JavaScript
Descending Map: {Python=15, JavaScript=18, Java=10, C++=12}
Poll First Entry: C++=12
Poll Last Entry: Python=15
Map after polling: {Java=10, JavaScript=18}
  

Explain RandomAccess Interface

The RandomAccess interface is a marker interface in the java.util package. It is used to indicate that a List implementation supports fast (constant time) random access to its elements. This interface helps optimize operations for data structures where direct access by index is efficient.

Key Features of RandomAccess Interface:

• Marker Interface: It does not define any methods. Its purpose is to serve as a tagging mechanism.
• Improves Performance: Algorithms can check for this interface to use more efficient access methods when working with lists that support random access.
• Common Implementations: The ArrayList and Vector classes implement this interface because they allow fast, index-based access to their elements.

Usage: When iterating over a list, checking whether it implements RandomAccess can help choose between for-loop (for index-based access) and iterator-based traversal for better performance.

Example:

import java.util.*;

public class RandomAccessExample {
    public static void main(String[] args) {
        List arrayList = new ArrayList<>();
        List linkedList = new LinkedList<>();

        // Adding elements
        arrayList.add("Java");
        arrayList.add("Python");
        linkedList.add("Java");
        linkedList.add("Python");

        // Check if the list supports RandomAccess
        System.out.println("Is ArrayList RandomAccess? " + (arrayList instanceof RandomAccess));
        System.out.println("Is LinkedList RandomAccess? " + (linkedList instanceof RandomAccess));

        // Optimized iteration
        if (arrayList instanceof RandomAccess) {
            System.out.println("Iterating ArrayList using for-loop:");
            for (int i = 0; i < arrayList.size(); i++) {
                System.out.println(arrayList.get(i));
            }
        } else {
            System.out.println("Iterating ArrayList using iterator:");
            for (String s : arrayList) {
                System.out.println(s);
            }
        }
    }
}
  

Advantages:

• Helps in optimizing performance by identifying lists that support fast random access.
• Improves efficiency of algorithms by choosing appropriate access methods.

Common Implementations: ArrayList, Vector

Non-Implementations: LinkedList does not implement RandomAccess because it is designed for sequential access.

What are the differences between HashMap, LinkedHashMap, and TreeMap?

• HashMap:
• Internal Data Structure: Uses a hash table to store key-value pairs.
• Order: Does not maintain any order of the keys or values. The order is not predictable.
• Performance: Provides constant time complexity, O(1) for get and put operations, on average (assuming a good hash function).
• Null Keys and Values: Allows one null key and multiple null values.
• LinkedHashMap:
• Internal Data Structure: Uses a hash table like HashMap, but it maintains a linked list of the entries to preserve insertion order.
• Order: Maintains the insertion order of keys (or access order if specified during construction).
• Performance: Slightly slower than HashMap because of the overhead of maintaining the order. However, its get and put operations are still O(1).
• Null Keys and Values: Similar to HashMap, allows one null key and multiple null values.
• TreeMap:
• Internal Data Structure: Uses a Red-Black tree (a balanced binary search tree) to store key-value pairs.
• Order: Maintains the keys in sorted order based on their natural ordering or according to a Comparator provided at the time of creation.
• Performance: Provides O(log n) time complexity for get and put operations due to the underlying tree structure.
• Null Keys and Values: Does not allow null keys, but allows null values.
• Summary of Key Differences:
• HashMap: Fast, no order, allows one null key.
• LinkedHashMap: Maintains insertion order or access order, slightly slower than HashMap.
• TreeMap: Maintains sorted order of keys, slower than both HashMap and LinkedHashMap due to O(log n) operations.

What is the internal structure of HashMap in Java 17?

• HashMap Internal Structure:
• HashMap in Java 17 is based on an array of buckets (an array of Entry objects) and hashing to store key-value pairs.
• Each bucket stores a linked list or a balanced tree structure (in case of hash collisions) that holds multiple entries for the same hash value.
Example:
• HashMap Initialization: Default size = 16.
HashMap map = new HashMap<>();
• Inserting Key-Value Pairs:
• Key: "vishal", Value: 20 → HashCode: 118, Index: 6 → Placed at index 6.
• Key: "sachin", Value: 30 → HashCode: 115, Index: 3 → Placed at index 3.
• Key: "vaibhav", Value: 40 → HashCode: 118, Index: 6 → Collision occurs, linked list formed at index 6.

  map.put(new Key("vishal"), 20);
  Create a node object as : 
  {
    int hash = 118
    // {"vishal"} is not a string but 
    // an object of class Key
    Key key = {"vishal"}
    Integer value = 20
    Node next = null
  }
          



• Collision Handling:
• If two keys have the same index, HashMap uses a linked list (Java 8+ uses Tree after threshold).
• If keys are equal, update value. Else, link new node to the existing node.
• Retrieving Values (`get()` method):
• Key: "sachin" → HashCode: 115, Index: 3 → Found 30 at index 3.
• Key: "vaibhav" → HashCode: 118, Index: 6 → Traverse linked list → Found 40.
• Key Points:
• O(1) time complexity for `put()` and `get()` unless rehashing occurs.
• If collision → Linked List traversal until key is found or `null`.
• If key exists, value is replaced.
• `null` key has a hash code of 0.
• Example Code:

            map.put(new Key("vishal"), 20);
            map.put(new Key("sachin"), 30);
            map.put(new Key("vaibhav"), 40);
            System.out.println(map.get(new Key("sachin"))); // Output: 30
          

• Hashing Process:
• Each key is hashed using its hashCode() method, and the hash value is used to determine the index (or bucket) in the internal array.
• The position within the array is calculated using the formula:

  index = hash(key) % array.length

• Bucket Structure:
• When two or more keys hash to the same bucket index, a linked list or tree is used to store those key-value pairs.
• In Java 17, if the number of elements in a bucket exceeds a certain threshold (TREEIFY_THRESHOLD), the list is converted into a balanced red-black tree for efficient lookups and insertions (O(log n)).
• Handling Collisions:
• Chaining: In case of a hash collision, the LinkedList or TreeNode is used to store multiple entries at the same bucket index.
• In Java 17, a bucket will use a tree structure for collision resolution when the bucket exceeds a size of 8 entries (by default). Otherwise, it remains as a linked list.
• Rehashing:
• If the number of elements in the HashMap exceeds a certain load factor (e.g., 0.75), the capacity of the internal array is doubled (rehashing) to maintain efficient performance.
• Performance:
• Average Case: Lookup, insert, and delete operations are expected to be O(1) in the average case, thanks to direct indexing of the array and the efficient collision handling mechanism (linked list or balanced tree).
• Worst Case: In case of excessive collisions, where many keys hash to the same index, the worst-case performance could degrade to O(n) (with a linked list). However, in Java 17, collisions are handled more efficiently with the introduction of red-black trees, limiting the worst-case complexity to O(log n).
• Summary of Key Points:
• In Java 17, HashMap uses an array of buckets, with each bucket storing either a linked list or a red-black tree to resolve hash collisions efficiently.
• The hashing process determines the bucket where a key-value pair will be placed, and collision resolution uses either a linked list or a balanced tree depending on the number of elements in a bucket.
• Rehashing is performed when the load factor threshold is exceeded to maintain the performance of the HashMap.

How does HashMap handle collisions?

• Collision in HashMap:
• A collision occurs when two keys produce the same hash code, and they map to the same bucket in the internal array of the HashMap.
• By default, HashMap uses the hashCode() method of the key to compute its hash code, and this value is used to determine the bucket where the key-value pair will be stored.
• Collision Handling Mechanism:
• Linked List Method: When a collision occurs (i.e., two keys map to the same bucket), HashMap stores multiple key-value pairs in a linked list within that bucket.
• Each element in the linked list contains a key-value pair and a reference to the next element (if there are multiple entries in the same bucket).
• Tree-based Bucket (Since Java 8):
• Starting from Java 8, if the number of entries in a bucket exceeds a certain threshold (8 by default), HashMap replaces the linked list with a balanced binary search tree (BST) for better performance.
• The tree structure allows for faster searching (logarithmic time complexity) compared to a linked list, which has linear time complexity.
• Key Considerations:
• Collision resolution is key to maintaining the performance of the HashMap. The fewer the collisions, the faster the operations (add, remove, get) will be.
• If the hashCode() method of the key class is poorly designed (e.g., returning the same hash code for different keys), the performance can degrade significantly, leading to long chains or even trees in a single bucket.
• Summary:
• HashMap handles collisions by using a linked list in each bucket, and from Java 8 onwards, it can use a balanced binary search tree for buckets with a high number of entries to maintain efficient performance.

What is the load factor in HashMap, and how does it impact performance?

• Load Factor Definition:
• The load factor in a HashMap is a measure that determines when to increase the capacity of the map.
• It is the threshold at which the map will resize its internal array (or resize the number of buckets) to maintain efficient performance.
• The default load factor in HashMap is 0.75, meaning when the number of entries exceeds 75% of the current capacity, the map will resize.
• Impact of Load Factor on Performance:
• Resize Operations: When the load factor is exceeded, HashMap performs a resize, which involves rehashing the keys and placing them into new buckets. This is a relatively expensive operation.
• Higher Load Factor: If the load factor is set to a higher value (e.g., 0.9), the HashMap will resize less frequently, which may improve memory usage efficiency. However, it can cause more collisions, leading to longer lookup times for entries.
• Lower Load Factor: If the load factor is set to a lower value (e.g., 0.5), the map will resize more frequently, resulting in better performance for lookup operations. However, it uses more memory because it creates more buckets upfront.
• Default Load Factor:
• The default load factor of 0.75 provides a good trade-off between memory usage and performance, balancing the number of resize operations and lookup performance.
• Summary:
• The load factor in a HashMap directly affects its resizing behavior, which in turn impacts memory usage and performance (lookup and insertion times).

Why should you use ConcurrentHashMap instead of HashMap in a multi-threaded environment?

• HashMap is not thread-safe: Multiple threads modifying a HashMap can lead to race conditions, data inconsistency, or even infinite loops (due to concurrent modification during resizing).
• ConcurrentHashMap is thread-safe: It uses segment locking (before Java 8) and bucket-level locks (Java 8+) to allow safe concurrent access without blocking all operations.
• No need for external synchronization: Unlike Collections.synchronizedMap(), ConcurrentHashMap does not require full locking for read operations.

import java.util.HashMap;

public class HashMapMultithreading {
    static HashMap map = new HashMap<>();

    public static void main(String[] args) {
        Thread t1 = new Thread(() -> {
            for (int i = 1; i <= 5; i++) {
                map.put(i, "Value" + i);
                System.out.println("Thread 1 inserted: " + i);
            }
        });

        Thread t2 = new Thread(() -> {
            for (int i = 1; i <= 5; i++) {
                System.out.println("Thread 2 read: " + map.get(i));
            }
        });

        t1.start();
        t2.start();
    }
}

    

Possible Issues with HashMap:
• Race conditions when writing to the map.
• NullPointerException or incorrect values when reading while another thread is writing.
• Infinite loops due to concurrent modification during resizing.

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    static ConcurrentHashMap map = new ConcurrentHashMap<>();

    public static void main(String[] args) {
        Thread t1 = new Thread(() -> {
            for (int i = 1; i <= 5; i++) {
                map.put(i, "Value" + i);
                System.out.println("Thread 1 inserted: " + i);
            }
        });

        Thread t2 = new Thread(() -> {
            for (int i = 1; i <= 5; i++) {
                System.out.println("Thread 2 read: " + map.get(i));
            }
        });

        t1.start();
        t2.start();
    }
}

    

• Thread Safety:
• ConcurrentHashMap is designed for concurrent access by multiple threads. It allows multiple threads to read and write to the map concurrently without causing inconsistencies or data corruption.
• HashMap is not thread-safe. If multiple threads access a HashMap concurrently and at least one thread modifies the map, it can lead to unpredictable behavior and data corruption.
• Locking Mechanism:
• ConcurrentHashMap uses a technique called segmented locking (or bucket-level locking). The map is divided into several segments, and each segment can be locked independently, allowing multiple threads to access different segments concurrently.
• HashMap does not have any locking mechanism. If multiple threads modify the map, the entire map might need to be synchronized externally, which can lead to performance bottlenecks.
• Performance:
• ConcurrentHashMap offers higher performance in multi-threaded environments because it allows threads to work concurrently on different segments without blocking each other, minimizing contention.
• HashMap may suffer from performance issues in multi-threaded environments, especially when using synchronization mechanisms like synchronized blocks or methods, which can cause threads to block each other.
• Atomic Operations:
• ConcurrentHashMap supports atomic operations, like putIfAbsent, replace, and remove, which allow you to perform certain actions on the map in an atomic and thread-safe manner without needing additional synchronization.
• HashMap does not provide such atomic operations, and you would have to manually synchronize operations if you want to ensure thread-safety for specific actions.
• Use Case:
• ConcurrentHashMap is ideal for scenarios where you have frequent concurrent reads and writes from multiple threads, such as in a multi-threaded web application or a highly concurrent server environment.
• HashMap is suitable in single-threaded scenarios or when external synchronization is used to make it thread-safe, but it's not recommended in multi-threaded environments due to its lack of built-in synchronization mechanisms.
• Summary:
• ConcurrentHashMap provides built-in thread-safety, better performance in multi-threaded environments, and atomic operations, making it the preferred choice for concurrent applications. HashMap is not thread-safe and should not be used in multi-threaded environments without external synchronization.

What is the difference between HashMap and ConcurrentHashMap?

• Thread Safety:
• HashMap is not thread-safe, meaning it is not designed to handle concurrent access from multiple threads. If multiple threads modify the map simultaneously, it can lead to inconsistent state or exceptions.
• ConcurrentHashMap is thread-safe and designed for concurrent access. It allows multiple threads to read and update the map without locking the entire map, improving performance in multi-threaded environments.
• Synchronization:
• HashMap uses no synchronization. If thread safety is required, the programmer must manually synchronize the map or use a wrapper like Collections.synchronizedMap().
• ConcurrentHashMap uses fine-grained locking. It allows multiple threads to work on different segments of the map at the same time, making it more efficient in high-concurrency scenarios.
• Performance:
• HashMap performs better in a single-threaded scenario because there is no overhead of synchronization.
• ConcurrentHashMap might perform slower than HashMap in a single-threaded environment due to the additional synchronization mechanisms in place to ensure thread safety.
• Null Keys and Values:
• HashMap allows one null key and multiple null values.
• ConcurrentHashMap does not allow null keys or null values to prevent ambiguity in concurrent operations.
• Usage Context:
• HashMap is ideal when thread safety is not a concern, or if thread safety is managed manually.
• ConcurrentHashMap is preferred when dealing with high concurrency and multiple threads accessing or modifying the map simultaneously.
• Summary:
• HashMap is non-thread-safe and faster in single-threaded contexts, but not suitable for concurrent access without external synchronization.
• ConcurrentHashMap is thread-safe, designed for concurrent access, but may have a slight performance overhead due to the fine-grained locking mechanism.

How does WeakHashMap work, and when should it be used?

• WeakHashMap Overview:
• WeakHashMap is a map implementation in Java where the keys are stored as weak references. This means that the garbage collector can reclaim the memory used by the keys if there are no b references to them.
• In a WeakHashMap, the value objects are held using regular references (b references), but the keys are weakly referenced. This allows entries to be automatically removed from the map when the key is no longer referenced outside the map.
• How WeakHashMap Works:
• When an entry's key is no longer referenced anywhere else in the program (except for the map), the garbage collector can collect the key and the associated value.
• This is unlike a regular HashMap, where the entry remains in the map until it is explicitly removed, regardless of whether the key is being used elsewhere.
• When to Use WeakHashMap:
• Cache-like behavior: WeakHashMap is commonly used for caching scenarios where you want to store temporary data but don't want the map to prevent objects from being garbage collected when they are no longer in use.
• Listener patterns: In scenarios where objects act as listeners or handlers, and you want the map to automatically clean up when the listener object is no longer in use.
• Memory-sensitive applications: If your application must manage memory carefully and automatically reclaim memory used by unused keys without manual intervention.
• Example Use Case:
• Consider a scenario where you're storing references to user session data. If a user session is no longer in use (i.e., no b references remain to the session key), the session data should be automatically cleaned up. A WeakHashMap is ideal for such use cases because it allows session data to be garbage collected when the session is no longer referenced.
• Key Considerations:
• WeakHashMap should be used carefully, as objects in the map may disappear unexpectedly if their keys are garbage collected. This may lead to unexpected behaviors in the application.
• It is important to note that the map doesn't guarantee when or if a key will be garbage collected, so developers need to account for possible removal of entries without explicit removal requests.

Explain about TreeMap

• Implements Red-Black Tree (self-balancing BST).
• Stores keys in sorted order (natural/comparator). Keys are stored in ascending order by default.
• Provides log(n) time complexity for put(), get(), and remove().
• NavigableMap Methods: firstKey(), lastKey(), higherKey(), lowerKey().
• Not Thread-Safe: Needs external synchronization for multi-threading.
• No null Keys Allowed: Throws NullPointerException.
• Example 1: Basic TreeMap Usage

TreeMap treeMap = new TreeMap<>();
treeMap.put(3, "Python");
treeMap.put(1, "Java");
treeMap.put(2, "C++");
treeMap.put(5, "JavaScript");
treeMap.put(4, "Ruby");
System.out.println("TreeMap: " + treeMap);

Output:
TreeMap: {1=Java, 2=C++, 3=Python, 4=Ruby, 5=JavaScript}
First Key: 1
Last Key: 5
Higher Key than 3: 4
Lower Key than 3: 2
HeadMap (<3): {1=Java, 2=C++}
TailMap (>=3): {3=Python, 4=Ruby, 5=JavaScript}
SubMap (2 to 4): {2=C++, 3=Python, 4=Ruby}
      

• Example 2: Custom Sorting (Descending Order)

TreeMap treeMap = new TreeMap<>(Comparator.reverseOrder());
treeMap.put(10, "Java");
treeMap.put(30, "Python");
treeMap.put(20, "C++");
System.out.println("TreeMap (Descending Order): " + treeMap);

Output:
TreeMap (Descending Order): {30=Python, 20=C++, 10=Java}
      

Why does HashMap allow one null key but multiple null values?

• Null Key:
• In HashMap, only one null key is allowed because the key's hash code is used to determine the bucket where the entry is stored. However, the hash code of null is undefined, meaning that there is no specific bucket for multiple null keys.
• If HashMap allowed more than one null key, it would be impossible to differentiate between them based on the hash code alone, leading to ambiguity in the map's structure.
• Null Values:
• HashMap allows multiple null values because the values are stored independently from the keys, and the map does not rely on a value's hash code for placement in the map.
• The map only needs to ensure that the keys are unique, but it has no restriction on how many values can be null since they are not involved in the hash-based placement of entries.
• Summary:
• HashMap allows one null key because there can only be one hash code for null, while it allows multiple null values because the values are not involved in the key's hash-based placement.

Explain the resize() operation in HashMap

• resize() is an internal operation in HashMap that occurs when the number of entries exceeds a certain threshold (i.e., the load factor). This operation increases the capacity of the map to ensure that it maintains optimal performance.
• When does resize() occur?
• By default, a HashMap starts with an initial capacity of 16 and a load factor of 0.75. This means when the number of entries reaches 75% of the current capacity, the resize() operation is triggered.
• For example, if the initial capacity is 16, the resize() operation occurs when there are 12 entries in the map (16 * 0.75 = 12).
• How does resize() work?
• The resize() operation involves creating a new, larger internal array to store the entries. The new size is typically doubled (i.e., the capacity is increased by 2 times).
• After resizing, the existing entries are rehashed and placed into the new array. The rehashing involves recalculating the hash codes of the keys and distributing them into the new buckets.
• Effect of resize() on performance
• Resize operations can be expensive because they require creating a new array and rehashing all the entries, which takes time proportional to the number of entries in the map (i.e., O(n) time complexity).
• This can cause temporary performance degradation, especially when many entries are added in a short time.
• Key Points to Remember:
• The resize() operation ensures that the HashMap maintains a good balance between time complexity and space usage by adjusting the capacity.
• It is triggered when the map exceeds the threshold determined by the load factor.
• Although resizing is necessary for efficient operation, it can have a performance impact due to the rehashing process.

You need to implement a caching mechanism for a high-traffic website. Which Map implementation will you use?

• Best Map Implementation: LinkedHashMap
• LinkedHashMap is the best choice for implementing a caching mechanism where you need to store key-value pairs while maintaining the insertion order.
• It uses a hash table with a linked list to maintain the order of elements. This allows for efficient access and insertion while keeping the order intact.
• Why LinkedHashMap is Ideal for Caching:
• Access Order: LinkedHashMap provides an option to maintain access order (via constructor parameter), which is crucial for Least Recently Used (LRU) caching. When the cache reaches its size limit, you can easily evict the least recently used entry.
• Efficiency: Operations like put, get, and remove are typically performed in constant time (O(1)) under most circumstances, making it efficient for a high-traffic website.
• Why Not Other Map Implementations?
• HashMap: While HashMap is fast, it doesn't maintain any order (neither insertion nor access order). For caching where order matters (like LRU caching), LinkedHashMap is better suited.
• TreeMap: It maintains a natural ordering of the keys or custom order based on a comparator. However, this introduces overhead due to sorting, which is not necessary for a caching mechanism where quick access is more important than sorting.
• Summary:
• LinkedHashMap is the optimal choice for a caching mechanism on a high-traffic website, especially if you need to maintain insertion or access order for eviction purposes, such as in an LRU cache.

You are designing an LRU Cache for an e-commerce platform. Which Map implementation is suitable?

• Best Map Implementation: LinkedHashMap
• LinkedHashMap is the best choice for implementing an LRU (Least Recently Used) Cache.
• It maintains the insertion order or access order depending on the constructor used.
• By setting the access order to true when creating the map, LinkedHashMap automatically maintains the order in which the entries were last accessed. This is essential for an LRU Cache.
• Why LinkedHashMap is Ideal for LRU Cache:
• It allows fast access and insertion of elements (O(1) time complexity for get and put operations).
• Using LinkedHashMap with access order enabled automatically keeps track of the most recently accessed elements, which helps in efficiently evicting the least recently used items.
• When the cache exceeds its size limit, you can easily remove the oldest (least recently used) element by iterating over the linked list maintained by the map.
• Why Not Other Map Implementations?
• HashMap: While it provides fast access, it does not maintain any order, making it unsuitable for LRU cache implementations where the access order is critical.
• TreeMap: Although it maintains elements in a sorted order, it adds unnecessary complexity and overhead for the LRU use case since sorting is not needed in LRU cache systems.
• Summary:
• LinkedHashMap with access order enabled is the most suitable map implementation for designing an LRU cache, as it efficiently maintains the order of access and allows for fast eviction of least recently used elements.

In a trading system, you need to store orders with unique IDs sorted by timestamp. Which Map will you use?

• Best Map Implementation: TreeMap
• TreeMap is the ideal choice when you need to store key-value pairs that are sorted according to the natural order of the keys or a custom comparator.
• TreeMap is a Red-Black tree-based implementation of the Map interface, which maintains the order of elements by their keys.
• Why TreeMap is Ideal for Orders Sorted by Timestamp:
• The orders can be sorted by their timestamp (which can be the key in the map), and TreeMap will keep the entries sorted automatically.
• Each order will have a unique ID (the value), and the keys will be the timestamps. With this, you can efficiently retrieve the order by its timestamp or range of timestamps.
• TreeMap ensures that the orders are always ordered, which is crucial for a trading system that requires fast access to orders based on their timestamp.
• Why Not Other Map Implementations?
• HashMap: While it provides fast insertion and retrieval (O(1) average time complexity), it does not maintain any order. Since orders need to be sorted by timestamp, HashMap is not suitable.
• LinkedHashMap: Although it maintains the insertion order, it does not sort the keys by timestamp. It may be suitable for cases where you want to maintain the order of insertion but not sorting by timestamp.
• Summary:
• TreeMap is the optimal choice for storing orders with unique IDs sorted by timestamp, as it automatically maintains the order of the keys.

How would you implement your own custom HashMap?

• Overview of Custom HashMap Implementation:
• A custom HashMap can be implemented by creating a class with an array of "buckets," where each bucket is a list or linked list to handle collisions.
• Each key-value pair will be stored in a "bucket" that corresponds to the hash value of the key. The hash value determines the index of the bucket.
• Steps to Implement Custom HashMap:
• Step 1: Create a HashMap Class
• Define a class for your HashMap with an array (or list) of buckets. Each bucket stores a linked list of entries.
• Each entry will store a key-value pair.
• Step 2: Define a Hash Function
• Implement a hash function to calculate the index for a given key. You can use the key's hashCode method to generate the hash value.
• The hash value should be modulo the number of buckets to map the key to the appropriate bucket index.
• Step 3: Handle Collisions
• Use a linked list (or another data structure like a balanced tree) to handle collisions in the same bucket.
• If two keys have the same hash code and therefore map to the same bucket, store them as separate entries in the linked list.
• Step 4: Implement Basic Operations
• Define methods like put(key, value), get(key), remove(key), and containsKey(key):
• put(key, value): Compute the hash value, map it to the corresponding bucket, and store the key-value pair. If the key already exists, replace the old value.
• get(key): Compute the hash value, access the appropriate bucket, and search for the key in that bucket. Return the value if found.
• remove(key): Compute the hash value, locate the bucket, and remove the key-value pair from the linked list if the key exists.
• containsKey(key): Compute the hash value and check if the key exists in the corresponding bucket.
• Step 5: Resize the HashMap (Optional)
• If the number of elements in the HashMap exceeds a certain threshold (e.g., 75% of the total capacity), resize the HashMap by increasing the number of buckets and rehashing the existing entries to new buckets.
• Step 6: Testing and Debugging
• Test the HashMap implementation thoroughly to ensure it handles collisions, resizes, and provides correct behavior for put, get, remove, and containsKey methods.
• Example Code of Custom HashMap:

•               import java.util.Objects;
  
                // Custom HashMap implementation
                class CustomHashMap<K, V> {
                    private static final int INITIAL_CAPACITY = 16; // Default capacity
                    private static final float LOAD_FACTOR = 0.75f; // Load factor for resizing
                    private int size = 0;
                    private Node<K, V>[] table;
                
                    // Node class (Linked List for Collision Handling)
                    static class Node<K, V> {
                        final K key;
                        V value;
                        Node<K, V> next; // Pointer for chaining
                
                        Node(K key, V value) {
                            this.key = key;
                            this.value = value;
                            this.next = null;
                        }
                    }
                
                    // Constructor
                    public CustomHashMap() {
                        table = new Node[INITIAL_CAPACITY];
                    }
                
                    // Hash function
                    private int hash(K key) {
                        return Objects.hashCode(key) & (table.length - 1);
                    }
                
                    // Put method (Inserts Key-Value Pair)
                    public void put(K key, V value) {
                        int index = hash(key);
                        Node<K, V> newNode = new Node<>(key, value);
                
                        // If no collision, insert directly
                        if (table[index] == null) {
                            table[index] = newNode;
                        } else {
                            // Collision handling using Linked List
                            Node<K, V> current = table[index];
                            Node<K, V> prev = null;
                
                            while (current != null) {
                                if (Objects.equals(current.key, key)) {
                                    current.value = value; // Update value if key exists
                                    return;
                                }
                                prev = current;
                                current = current.next;
                            }
                            prev.next = newNode; // Insert at the end of linked list
                        }
                        size++;
                
                        // Resize if load factor exceeds
                        if (size > LOAD_FACTOR * table.length) {
                            resize();
                        }
                    }
                
                    // Get method (Retrieves Value by Key)
                    public V get(K key) {
                        int index = hash(key);
                        Node<K, V> current = table[index];
                
                        while (current != null) {
                            if (Objects.equals(current.key, key)) {
                                return current.value;
                            }
                            current = current.next;
                        }
                        return null; // Key not found
                    }
                
                    // Remove method
                    public void remove(K key) {
                        int index = hash(key);
                        Node<K, V> current = table[index];
                        Node<K, V> prev = null;
                
                        while (current != null) {
                            if (Objects.equals(current.key, key)) {
                                if (prev == null) {
                                    table[index] = current.next; // Remove first node
                                } else {
                                    prev.next = current.next; // Remove in-between node
                                }
                                size--;
                                return;
                            }
                            prev = current;
                            current = current.next;
                        }
                    }
                
                    // Resize method (Doubles table size when threshold exceeds)
                    private void resize() {
                        Node<K, V>[] oldTable = table;
                        table = new Node[oldTable.length * 2];
                        size = 0;
                
                        for (Node<K, V> headNode : oldTable) {
                            while (headNode != null) {
                                put(headNode.key, headNode.value);
                                headNode = headNode.next;
                            }
                        }
                    }
                
                    // Display method
                    public void display() {
                        for (int i = 0; i < table.length; i++) {
                            System.out.print("Index " + i + ": ");
                            Node<K, V> current = table[i];
                            while (current != null) {
                                System.out.print("[" + current.key + "=" + current.value + "] -> ");
                                current = current.next;
                            }
                            System.out.println("null");
                        }
                    }
                
                    // Main method (Testing)
                    public static void main(String[] args) {
                        CustomHashMap<String, Integer> map = new CustomHashMap<>();
                        map.put("Java", 10);
                        map.put("Python", 20);
                        map.put("C++", 30);
                        map.put("Java", 40); // Updates existing key
                
                        System.out.println("Value for 'Java': " + map.get("Java")); // Output: 40
                        System.out.println("Value for 'Python': " + map.get("Python")); // Output: 20
                
                        map.remove("Python");
                        System.out.println("After removing 'Python': " + map.get("Python")); // Output: null
                
                        map.display();
                    }
                }
                
              

Queue Interface:

The Queue interface is part of the java.util package and represents a collection designed for holding elements prior to processing. It is used to model data structures like queues where elements are processed in a First-In-First-Out (FIFO) order. The Queue interface extends the Collection interface and provides methods to add, remove, and examine elements in the queue.

Key Features of the Queue Interface:

• FIFO Order: Elements are processed in the order they are added (first-in, first-out).
• Operations: Common operations include offer() to add, poll() to remove, and peek() to view the front element.
• Blocking and Non-blocking Methods: Some implementations support blocking methods like take() and put() for thread-safe operations.

Common Implementations of the Queue Interface:

• LinkedList: A general-purpose implementation of the Queue interface.
• PriorityQueue: A queue where elements are ordered based on their priority (not strictly FIFO).
• ArrayBlockingQueue: A thread-safe, bounded queue implementation for concurrent programming.

• Implements FIFO (First-In-First-Out).
• Allows null elements.
• Not Thread-Safe.

import java.util.*;
public class LinkedListQueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("Java");
        queue.offer("Python");
        queue.offer("C++");

        System.out.println("Queue: " + queue);
        System.out.println("Peek: " + queue.peek());  // Front element
        System.out.println("Poll: " + queue.poll());  // Remove front element
        System.out.println("Queue after poll: " + queue);
    }
}
Output:
Queue: [Java, Python, C++]
Peek: Java
Poll: Java
Queue after poll: [Python, C++]
      

• Stores elements in natural order (or using a custom comparator).
• Does not allow null values.
• Not Thread-Safe.

import java.util.*;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(30);
        pq.offer(10);
        pq.offer(50);
        pq.offer(20);

        System.out.println("PriorityQueue: " + pq);
        System.out.println("Poll: " + pq.poll()); // Removes the smallest element
        System.out.println("Queue after poll: " + pq);
    }
}
output:
PriorityQueue: [10, 20, 50, 30]
Poll: 10
Queue after poll: [20, 30, 50]
    

• Faster than LinkedList (No node allocation overhead).
• No capacity restriction.
• Does not allow null values.

import java.util.*;

public class ArrayDequeExample {
    public static void main(String[] args) {
        Queue<String> deque = new ArrayDeque<>();
        deque.offer("Java");
        deque.offer("Python");
        deque.offer("C++");

        System.out.println("ArrayDeque: " + deque);
        System.out.println("Poll: " + deque.poll()); // Removes first element
        System.out.println("Queue after poll: " + deque);
    }
}
output:
ArrayDeque: [Java, Python, C++]
Poll: Java
Queue after poll: [Python, C++]
    

• Non-blocking, thread-safe queue.
• Uses CAS (Compare-And-Swap) for atomic operations.

import java.util.concurrent.*;

public class ConcurrentQueueExample {
    public static void main(String[] args) {
        Queue queue = new ConcurrentLinkedQueue<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        System.out.println("ConcurrentQueue: " + queue);
        System.out.println("Poll: " + queue.poll()); // Removes head element
        System.out.println("Queue after poll: " + queue);
    }
}
Output:
ConcurrentQueue: [1, 2, 3]
Poll: 1
Queue after poll: [2, 3]

    

• Thread-safe, supports blocking operations.
• Has an optional capacity limit.

import java.util.concurrent.*;

public class LinkedBlockingQueueExample {
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue queue = new LinkedBlockingQueue<>(2);
        queue.put("Java");
        queue.put("Python");
        
        System.out.println("Queue: " + queue);
        System.out.println("Take: " + queue.take()); // Removes and waits if empty
        System.out.println("Queue after take: " + queue);
    }
}
Output:
Queue: [Java, Python]
Take: Java
Queue after take: [Python]

    

What is the difference between Queue and Stack?

• Queue:
• A Queue follows the First-In-First-Out (FIFO) principle, meaning the element added first will be removed first.
• It is like a queue in real life (e.g., a line at a ticket counter), where the first person in line is the first one to be served.
• Common methods: offer(), poll(), peek().
• Used when tasks are processed in the order they are received, such as in task scheduling, message processing, and print queues.
• Stack:
• A Stack follows the Last-In-First-Out (LIFO) principle, meaning the element added last will be removed first.
• It is like a stack of plates, where the last plate placed on the stack is the first one to be removed.
• Common methods: push(), pop(), peek().
• Used in scenarios like undo operations, function calls, and depth-first search algorithms.
• Key Differences:
• Order of Processing: Queue follows FIFO, Stack follows LIFO.
• Real-World Analogy: Queue is like a line of people waiting for a service; Stack is like a stack of plates where the last plate placed is the first one to be used.
• Methods: Queue provides methods like offer(), poll(), and peek(), while Stack provides push(), pop(), and peek().
• Use Cases: Queue is used in task scheduling, print queues, and asynchronous processing, while Stack is used in undo features, recursion, and depth-first search.

How does PriorityQueue work internally?

• Internal Data Structure:
• PriorityQueue is backed by a binary heap, specifically a min-heap by default. The heap structure ensures that the element with the highest priority (or the smallest element in the case of a min-heap) is always at the root of the heap.
• The heap is implemented as an array, and the parent-child relationships are maintained by the indices in this array. For an element at index i:
  • The left child is at index 2*i + 1.
  • The right child is at index 2*i + 2.
  • The parent is at index (i - 1) / 2.
• Priority Queue Operations:
• add(E e): Adds an element to the queue. The new element is placed at the end of the heap (array), and then the heap property is restored by "bubbling up" the element to its correct position.
• remove(): Removes the root element (the element with the highest priority). The last element in the heap is moved to the root position, and the heap property is restored by "bubbling down" this element until the heap is in a valid state again.
• peek(): Returns the root element without removing it, allowing you to view the highest-priority element without altering the queue.
• poll(): Removes and returns the root element, similar to remove(), but it returns null if the queue is empty, rather than throwing an exception.
• Heap Property:
• The heap always maintains a specific property where the priority (value) of the parent node is always either greater than or less than the values of its children. In a min-heap, the root always holds the smallest value, and in a max-heap, the root holds the largest value.
• This property allows the PriorityQueue to efficiently access the highest-priority element in O(1) time and perform insertions and deletions in O(log n) time.
• Custom Ordering:
• PriorityQueue by default uses natural ordering (ascending order) if the elements are comparable, but you can provide a custom comparator to change the priority order.
• If a comparator is provided, the queue will arrange elements based on the comparator’s ordering instead of their natural order.
• Summary:
• PriorityQueue is backed by a binary heap, offering efficient priority-based element insertion and removal.
• Operations like add, remove, and poll take O(log n) time, while peeking the highest priority element takes O(1) time.
• The queue supports both natural ordering and custom comparators to define the priority of elements.

How does ArrayDeque differ from LinkedList-based Deque?

• Internal Data Structure:
• ArrayDeque is backed by a dynamic array, whereas LinkedList-based Deque is backed by a doubly linked list.
• Performance of Operations:
• ArrayDeque provides faster access and modification of elements at both ends, with amortized constant time complexity (O(1)) for operations like addFirst(), addLast(), removeFirst(), and removeLast().
• LinkedList-based Deque also offers constant time complexity for these operations, but due to the overhead of managing node pointers, it may have slightly more memory usage and overhead for some cases.
• Memory Usage:
• ArrayDeque uses less memory compared to LinkedList-based Deque because it stores elements in a contiguous array with no extra memory needed for links between nodes.
• LinkedList-based Deque requires additional memory for the previous and next node pointers along with the actual data, making it more memory-intensive.
• Resizing and Capacity:
• ArrayDeque dynamically resizes the underlying array when the capacity is exceeded. This resizing may incur a costly time complexity during resizing (O(n)), but amortized over time, the time complexity remains O(1) for most operations.
• LinkedList-based Deque does not require resizing because it uses a linked structure where each element points to the next, so memory is allocated dynamically as needed without resizing costs.
• Use Case Suitability:
• ArrayDeque is generally preferred when you have frequent push and pop operations at both ends of the deque, and constant memory usage is a priority.
• LinkedList-based Deque might be more appropriate when you require a consistent performance with complex node management (like using nodes in a broader linked structure), though it's less space-efficient than ArrayDeque.
• Null Elements:
• ArrayDeque does not allow null elements. Trying to add null will result in a NullPointerException.
• LinkedList-based Deque allows null elements, so it's possible to insert null values if needed.
• Summary:
• ArrayDeque is typically faster and more memory-efficient, especially for scenarios with frequent operations at both ends of the deque and without null element handling.
• LinkedList-based Deque provides more flexibility, allowing null elements, but at the cost of additional memory usage and slightly more overhead due to the linked structure.

How would you implement a Task Scheduler using a Queue?

• Queue Choice: PriorityQueue or LinkedList
• A PriorityQueue can be used if tasks need to be scheduled based on priority (e.g., high-priority tasks are executed first).
• If the tasks are scheduled in the order they are added, a LinkedList (as a Queue) is a simple and efficient choice.
• Task Scheduler Implementation Steps:
• Step 1: Define the task structure. A task can be represented by a class that includes task details, priority (if needed), and execution time.
• Step 2: Use a Queue to store the tasks. You can choose a PriorityQueue for priority-based scheduling or a simple LinkedList for FIFO scheduling.
• Step 3: Implement a method to add tasks to the queue. Tasks are added based on their priority or time of arrival.
• Step 4: Implement a method to process tasks from the queue. The task with the highest priority (or the first in line) will be processed first.
• Step 5: Set up a loop to continuously check the queue for tasks and execute them until all tasks are processed.
• Example Code using LinkedList as Queue:

• import java.util.LinkedList;
  import java.util.Queue;
  
  class Task {
      String name;
      int timeToExecute;
  
      public Task(String name, int timeToExecute) {
          this.name = name;
          this.timeToExecute = timeToExecute;
      }
  }
  
  public class TaskScheduler {
      Queue taskQueue = new LinkedList<>();
  
      public void addTask(Task task) {
          taskQueue.add(task);
          System.out.println("Task added: " + task.name);
      }
  
      public void processTasks() {
          while (!taskQueue.isEmpty()) {
              Task task = taskQueue.poll();
              System.out.println("Processing task: " + task.name + " (Time to Execute: " + task.timeToExecute + "ms)");
              try {
                  Thread.sleep(task.timeToExecute); // Simulate task execution time
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
          }
      }
  
      public static void main(String[] args) {
          TaskScheduler scheduler = new TaskScheduler();
          scheduler.addTask(new Task("Task1", 2000));
          scheduler.addTask(new Task("Task2", 1000));
          scheduler.addTask(new Task("Task3", 1500));
  
          scheduler.processTasks();
      }
  }
              

• Explanation:
• The task scheduler uses a LinkedList as a queue where tasks are processed in the order they are added.
• The addTask method adds tasks to the queue, and the processTasks method processes them one by one by calling poll to retrieve the next task and simulating its execution.
• If you need priority-based scheduling, you can replace the LinkedList with a PriorityQueue, where tasks with higher priority are processed first.

What are synchronized collections vs concurrent collections?

• Synchronized Collections:
• Synchronized collections are part of the java.util.Collections utility class and are thread-safe due to synchronization.
• Each method in a synchronized collection is wrapped with the synchronized keyword, ensuring that only one thread can access the collection at a time.
• Example: Collections.synchronizedList(new ArrayList())
• While synchronized collections are thread-safe, they may lead to performance issues due to the overhead of synchronization. Only one thread can access the collection at a time, which can cause contention and reduce concurrency.
• Accessing the collection in multiple threads requires careful synchronization when iterating over it. It is recommended to manually synchronize on the collection while iterating.
• Concurrent Collections:
• Concurrent collections are part of the java.util.concurrent package and are designed for high-concurrency environments.
• These collections are optimized for concurrent access by multiple threads without the need for explicit synchronization.
• Examples: CopyOnWriteArrayList, ConcurrentHashMap, BlockingQueue, etc.
• Concurrent collections provide better performance compared to synchronized collections because they allow multiple threads to work on different parts of the collection without blocking each other.
• They internally manage locking or provide lock-free access to data to improve thread safety and avoid bottlenecks.
• Unlike synchronized collections, concurrent collections handle thread safety at a finer level, allowing multiple threads to access independent parts of the collection concurrently.
• Key Differences:
• Synchronization: Synchronized collections use synchronized methods, whereas concurrent collections use advanced techniques like fine-grained locking or lock-free data structures.
• Performance: Synchronized collections can suffer from performance degradation due to blocking, whereas concurrent collections are designed for better performance in highly concurrent environments.
• Use Cases: Synchronized collections are better for simpler, single-threaded scenarios, while concurrent collections are optimized for high-concurrency, multi-threaded environments.
• Summary:
• Synchronized collections are a basic way to achieve thread-safety by wrapping collections in synchronized methods, while concurrent collections are more advanced and provide better performance in multi-threaded environments by allowing finer-grained concurrency control.

How does CopyOnWriteArrayList differ from a synchronized list?

• Internal Mechanism:
• CopyOnWriteArrayList creates a copy of the array whenever it is modified (for example, when an element is added, removed, or replaced). This ensures that iterators can operate on a consistent, unchanging snapshot of the list, even when the list is being modified.
• Synchronized list (e.g., Collections.synchronizedList(new ArrayList<>())) simply synchronizes each method call (such as add, remove, etc.) using a lock. This ensures that only one thread can access the list at a time, but it doesn't provide thread-safe iteration without additional synchronization.
• Concurrency and Thread Safety:
• CopyOnWriteArrayList is optimized for scenarios where reads are frequent and writes (modifications) are infrequent. It allows multiple threads to read the list without locking, which is highly beneficial in situations with many concurrent readers.
• Synchronized list ensures thread safety by synchronizing each method call. However, it might introduce contention, especially when multiple threads are attempting to modify the list concurrently.
• Performance:
• CopyOnWriteArrayList provides better performance for situations where reads dominate because it doesn't require locking for reading. However, it comes with a performance penalty for writes, as it creates a new copy of the array on each modification.
• Synchronized list can have worse performance than CopyOnWriteArrayList in read-heavy scenarios because it locks the list for each operation, which can introduce contention when there are multiple threads trying to read or modify the list simultaneously.
• Iteration:
• CopyOnWriteArrayList allows safe iteration even when the list is being modified concurrently, since it operates on a snapshot copy of the list.
• Synchronized list requires external synchronization during iteration to prevent concurrent modification exceptions, as the list is modified directly.
• Use Case:
• CopyOnWriteArrayList is ideal for scenarios where reads significantly outnumber writes, and thread safety for iteration is important.
• Synchronized list is better when writes are frequent and thread safety is required for both reading and writing, but you need to manually synchronize iteration to avoid concurrent modification exceptions.
• Summary:
• CopyOnWriteArrayList offers better performance for read-heavy, low-write scenarios with safe iteration, while a synchronized list provides thread safety but may suffer from performance degradation and requires additional synchronization during iteration.

How does ConcurrentHashMap handle concurrency differently than HashTable?

• Internal Locking Mechanism:
• HashTable uses a single lock for the entire map, which means if one thread is accessing the map, other threads are blocked from accessing it, resulting in reduced concurrency.
• ConcurrentHashMap uses a finer-grained locking approach by splitting the map into segments (or buckets) and locking only a specific segment when a thread accesses it. This allows multiple threads to concurrently access different segments, improving overall concurrency.
• Thread Safety and Performance:
• HashTable is fully synchronized at the method level, meaning every operation (put, get, remove) locks the entire map, which can cause significant performance degradation in multi-threaded scenarios with high contention.
• ConcurrentHashMap allows for higher performance in concurrent environments because it provides thread safety at a more granular level, allowing multiple threads to read and write concurrently without locking the whole map. This results in less contention and better scalability.
• Null Keys and Values:
• HashTable does not allow null keys or null values. If you attempt to insert a null key or value, it throws a NullPointerException.
• ConcurrentHashMap does not allow null values, but it allows null keys. This is intentional to prevent ambiguity, as a null value can indicate that the key is not present, but null keys may have a specific use case in certain scenarios.
• Performance During High Contention:
• HashTable degrades significantly under high contention because of the global lock, where only one thread can modify the map at a time.
• ConcurrentHashMap handles high contention better due to its segmented locking, allowing multiple threads to work concurrently with fewer performance hits even in heavily contended scenarios.
• Method Synchronization:
• HashTable synchronizes every method in the class, which means every operation is thread-safe but can be slow.
• ConcurrentHashMap only synchronizes the operations that need to be thread-safe, allowing other operations like get and containsKey to run without locking and thus perform better in multi-threaded environments.
• Summary:
• HashTable uses a global lock, is fully synchronized, and has performance limitations under high concurrency.
• ConcurrentHashMap provides finer-grained locking, allows for better concurrency, and is designed to work more efficiently in highly concurrent environments with less performance degradation.

Why is ConcurrentSkipListMap useful in multi-threaded applications?

• Thread Safety:
• ConcurrentSkipListMap is designed for use in multi-threaded environments and provides thread-safe operations without the need for explicit synchronization.
• It allows multiple threads to safely access and modify the map concurrently, making it ideal for high-concurrency scenarios.
• Non-blocking Reads and Writes:
• The ConcurrentSkipListMap uses a lock-free mechanism that allows threads to perform non-blocking reads, which helps to reduce contention and increase overall performance in highly concurrent systems.
• Read operations are highly optimized, ensuring minimal latency when accessing data.
• Ordered Data:
• Unlike other thread-safe maps (like Hashtable), ConcurrentSkipListMap maintains a natural ordering of its keys or can use a custom comparator.
• This ordering is maintained even in a multi-threaded environment, making it useful for applications that need to perform range-based queries or iterate over sorted keys in a concurrent manner.
• Scalability:
• ConcurrentSkipListMap provides better scalability than other thread-safe maps, as it handles concurrency more efficiently by using a skip-list data structure, which enables faster search and update times in large data sets.
• Useful in Real-time Systems:
• Because it allows concurrent read and write operations with minimal locking, ConcurrentSkipListMap is useful in real-time applications where performance is critical, such as in distributed systems or multi-threaded servers.
• Comparison with Other Maps:
• HashMap and Hashtable are not thread-safe, requiring external synchronization for thread safety.
• ConcurrentSkipListMap offers better performance for concurrent access compared to Hashtable or Collections.synchronizedMap(), which require full synchronization of operations.
• Summary:
• ConcurrentSkipListMap is an ideal choice for multi-threaded applications where thread safety, ordered data, and high scalability are needed.

In a multi-threaded data processing system, how would you handle concurrent updates to a shared collection?

• Use Thread-Safe Collections
• For thread-safe operations on shared collections, you can use Concurrent Collections such as ConcurrentHashMap or CopyOnWriteArrayList in Java.
• These collections are specifically designed to handle concurrent access and updates, ensuring that multiple threads can interact with the collection safely.
• Synchronization
• If you need to use a non-thread-safe collection like ArrayList or HashMap, you can synchronize the collection explicitly using synchronized blocks or methods.
• For example, synchronized(collection) will lock the collection during updates to ensure that only one thread can modify it at a time.
• Using Collections.synchronizedCollection
• If you are working with a legacy collection or need thread safety for a general collection, you can wrap it with Collections.synchronizedList or Collections.synchronizedMap.
• This ensures that all operations on the collection are synchronized, making it thread-safe.
• Read-Write Locks
• In scenarios where reads are more frequent than writes, you can use ReadWriteLock (e.g., ReentrantReadWriteLock) to allow multiple threads to read the collection concurrently but ensure exclusive access for writes.
• This approach improves performance when read operations dominate, as it reduces the contention between threads.
• Atomic Operations
• For specific atomic operations, you can use the Atomic* classes like AtomicInteger, AtomicLong, or AtomicReference for updating individual elements of the collection in an atomic manner without the need for manual synchronization.
• Immutable Collections
• If updates are not required after creation, using immutable collections (e.g., using Collections.unmodifiableList) can prevent any concurrent modification issues.
• Summary
• To handle concurrent updates to a shared collection, prefer using thread-safe collections or synchronize access using locks or explicit synchronization. If the collection needs frequent updates, consider using ConcurrentHashMap or CopyOnWriteArrayList for better performance.

Comparable vs Comparator in Java

In Java, Comparable and Comparator interfaces are used for sorting objects in collections such as ArrayList, TreeSet, and TreeMap. They allow us to define custom sorting logic for objects.

• It is part of the java.lang package.
• Defining the natural ordering of objects.
• Ascending order by default
• A class that implements this interface must override the compareTo() method, which compares the current object with another object of the same type.
The method returns:
• A negative integer if the current object is less than the specified object.
• A positive integer if the current object is greater than the specified object.
• Zero if the current object is equal to the specified object.

import java.util.*;

class Student implements Comparable {
    int id;
    String name;

    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    // Implementing Comparable
    @Override
    public int compareTo(Student other) {
        return this.id - other.id; // Ascending order based on 'id'
    }

    @Override
    public String toString() {
        return "Student{id=" + id + ", name='" + name + "'}";
    }
}

public class ComparableExample {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student(3, "Alice"));
        students.add(new Student(1, "Bob"));
        students.add(new Student(2, "Charlie"));

        Collections.sort(students); // Uses Comparable's compareTo()

        System.out.println(students);
    }
}

Output
[Student{id=1, name='Bob'}, Student{id=2, name='Charlie'}, Student{id=3, name='Alice'}]

      

• It is part of the java.util package.
• Defining the custom sorting order.
• Method to implement: int compare(T obj1, T obj2)

import java.util.*;

class Student {
    int id;
    String name;

    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{id=" + id + ", name='" + name + "'}";
    }
}

// Comparator for sorting by name
class NameComparator implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.name.compareTo(s2.name); // Ascending order of names
    }
}

// Comparator for sorting by id in descending order
class IdDescendingComparator implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        return s2.id - s1.id; // Descending order of IDs
    }
}

public class ComparatorExample {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student(3, "Alice"));
        students.add(new Student(1, "Bob"));
        students.add(new Student(2, "Charlie"));

        // Sort by name (using NameComparator)
        Collections.sort(students, new NameComparator());
        System.out.println("Sorted by name: " + students);

        // Sort by id in descending order (using IdDescendingComparator)
        Collections.sort(students, new IdDescendingComparator());
        System.out.println("Sorted by ID (Descending): " + students);
    }
}
Output:
Sorted by name: [Student{id=3, name='Alice'}, Student{id=1, name='Bob'}, Student{id=2, name='Charlie'}]
Sorted by ID (Descending): [Student{id=3, name='Alice'}, Student{id=2, name='Charlie'}, Student{id=1, name='Bob'}]
      

  import java.util.*;

  public class ComparatorLambdaExample {
      public static void main(String[] args) {
          List students = Arrays.asList(
              new Student(3, "Alice"),
              new Student(1, "Bob"),
              new Student(2, "Charlie")
          );

          // Sorting by name using lambda
          students.sort((s1, s2) -> s1.name.compareTo(s2.name));
          System.out.println("Sorted by name: " + students);

          // Sorting by id in descending order using lambda
          students.sort((s1, s2) -> s2.id - s1.id);
          System.out.println("Sorted by ID (Descending): " + students);
      }
  }
  Output:
  Sorted by name: [Student{id=3, name='Alice'}, Student{id=1, name='Bob'}, Student{id=2, name='Charlie'}]
  Sorted by ID (Descending): [Student{id=3, name='Alice'}, Student{id=2, name='Charlie'}, Student{id=1, name='Bob'}]
      

Use Comparable when:
• The natural ordering of objects makes sense (e.g., Integer, String, Date).
• There is only one sorting criterion (e.g., sorting students by id).
Use Comparator when:
• You need multiple sorting criteria (e.g., sorting students by name, age, etc.).
• You want to use lambda expressions for concise sorting.