Collection Based Interview Question

Created on: Oct 12, 2024

What is the demerit in simple queue that we used blocking queue ?

Simple queue like LinkedList is not thread safe.
Simple queue don't have any way to block producer or consumer based on queue state that it is full or empty.
Simple queue has no notion for capacity limits. A producer can add indefinitely which can cause out of memory exception.

Blocking queue give you

Thread safety operation
Blocking behavior
Bounded capacity which prevents overflow.

package org.learning.misc;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class Test {
    public static void main(String[] args) {
        BlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<>(5);

        blockingQueue.add(1);
        blockingQueue.add(2);
    }
}

Internal Working: Internally ArrayBlockingQueue have a array of fixed size. And it uses lock for put which ensure that only thread can access it at a time. It also check if size is full, it waits until there some items pop out.

class ArrayBlockingQueue {

     // Internal queue array (circular buffer)
     array[]     // Fixed-size array to store elements
     capacity    // The maximum number of elements the queue can hold
     count       // The current number of elements in the queue
     putIndex    // The index where the next element will be added
     takeIndex   // The index where the next element will be removed

     // Locks and Condition Variables
     lock        // ReentrantLock to ensure thread-safety
     notFull     // Condition to signal producers when space is available
     notEmpty    // Condition to signal consumers when elements are available

     // Constructor: Initialize the queue
     function constructor(capacity) {
         this.capacity = capacity
         array = new array[capacity]
         count = 0
         putIndex = 0
         takeIndex = 0
         lock = new ReentrantLock()
         notFull = lock.newCondition()
         notEmpty = lock.newCondition()
     }

     // Producer adds an element to the queue (blocking if full)
     function put(item) {
         lock.lock()     // Acquire the lock to ensure mutual exclusion
         try {
             // Wait while the queue is full
             while (count == capacity) {
                 notFull.await()   // Block until there is space (queue is not full)
             }

             // Add the item to the queue at the putIndex
             array[putIndex] = item
             putIndex = (putIndex + 1) % capacity  // Circular buffer logic
             count++                               // Increment the count of elements

             // Signal consumers that an element is available
             notEmpty.signal()
         } finally {
             lock.unlock()   // Release the lock after operation
         }
     }

     // Consumer removes an element from the queue (blocking if empty)
     function take() {
         lock.lock()     // Acquire the lock to ensure mutual exclusion
         try {
             // Wait while the queue is empty
             while (count == 0) {
                 notEmpty.await()   // Block until there are elements to consume
             }

             // Remove the item from the queue at the takeIndex
             item = array[takeIndex]
             takeIndex = (takeIndex + 1) % capacity  // Circular buffer logic
             count--                               // Decrement the count of elements

             // Signal producers that space is available
             notFull.signal()
         } finally {
             lock.unlock()   // Release the lock after operation
         }
         return item
     }
 }

What is lock in multi threading Java program ? Lock are used to manage access to shared resource in a multithreading environment. It ensure that only one thread can access at a time.

package org.learning.misc;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class BankAccount {
    private double balance;
    private final Lock lock =  new ReentrantLock();

    public BankAccount(double balance) {
        this.balance = balance;
    }

    public void deposit(double amount){
        lock.lock();
        try{
            balance += amount;
        }finally {
            lock.unlock();
        }
    }

    public void withdraw(double amount){
        lock.lock();
        try{
            if(balance>=amount){
                balance -= amount;
            }
            else{
                System.out.println("insufficient balance");
            }
        }finally {
            lock.unlock();
        }
    }

    public double getBalance(){
        return this.balance;
    }
}

ReentrantLock is used to avoid race condition while performing transaction.

import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class BankAccount {
    private double balance;
    private final ReadWriteLock lock =  new ReentrantReadWriteLock();

    public BankAccount(double balance) {
        this.balance = balance;
    }

    public void deposit(double amount){
        lock.writeLock().lock();
        try{
            balance += amount;
        }finally {
            lock.writeLock().unlock();
        }
    }

    public void withdraw(double amount){
        lock.writeLock().lock();
        try{
            if(balance>=amount){
                balance -= amount;
            }
            else{
                System.out.println("insufficient balance");
            }
        }finally {
            lock.writeLock().unlock();
        }
    }

    public double getBalance(){
        lock.readLock().lock();
        try{
            return this.balance;
        }finally {
            lock.readLock().unlock();
        }
    }
}

Above code uses ReadWriteLock which ensure two things

Multiple read operation concurrently
Only one user can modify balance.

Note: Only one of read or write lock can acquire lock on resource at a time. Multiple read lock can acquire lock simultaneously while only one write lock can acquire lock on resource. If multiple read lock acquires lock continuously without releasing resource, it will lead to starvation of write lock. In this case, ReadWriteLock can be configured to give prioritization to write lock. Below is code

ReadWriteLock lock = new ReentrantReadWriteLock(true);  // Fair version

StampedLock is used when there is a frequent read operation and modification is rare, using a optimistic read operation can significantly improve performance.

import java.util.concurrent.locks.StampedLock;

public class BookingSystem {
    private boolean[] seats;  // Array representing available (false) or booked (true) seats
    private final StampedLock lock = new StampedLock(); // StampedLock

    public BookingSystem(int totalSeats) {
        seats = new boolean[totalSeats]; // All seats start as available (false)
    }

    // View available seats (Optimistic Read)
    public void viewAvailableSeats() {
        long stamp = lock.tryOptimisticRead(); // Optimistic read lock
        try {
            int availableSeats = 0;
            for (boolean seat : seats) {
                if (!seat) availableSeats++;
            }

            // Validate that no write happened while reading
            if (!lock.validate(stamp)) {
                // Fallback to a pessimistic read if validation fails
                stamp = lock.readLock();
                try {
                    availableSeats = 0;
                    for (boolean seat : seats) {
                        if (!seat) availableSeats++;
                    }
                } finally {
                    lock.unlockRead(stamp); // Release the read lock
                }
            }
            System.out.println("Available seats: " + availableSeats);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    // Book a seat (Write Lock)
    public boolean bookSeat(int seatNumber) {
        long stamp = lock.writeLock(); // Acquire the write lock
        try {
            if (seatNumber < 0 || seatNumber >= seats.length) {
                System.out.println("Invalid seat number");
                return false;
            }
            if (!seats[seatNumber]) {
                seats[seatNumber] = true; // Mark seat as booked
                System.out.println("Seat " + seatNumber + " successfully booked.");
                return true;
            } else {
                System.out.println("Seat " + seatNumber + " is already booked.");
                return false;
            }
        } finally {
            lock.unlockWrite(stamp); // Release the write lock
        }
    }

    // Cancel a booking (Write Lock)
    public boolean cancelBooking(int seatNumber) {
        long stamp = lock.writeLock(); // Acquire the write lock
        try {
            if (seatNumber < 0 || seatNumber >= seats.length) {
                System.out.println("Invalid seat number");
                return false;
            }
            if (seats[seatNumber]) {
                seats[seatNumber] = false; // Mark seat as available
                System.out.println("Booking for seat " + seatNumber + " has been canceled.");
                return true;
            } else {
                System.out.println("Seat " + seatNumber + " is not booked yet.");
                return false;
            }
        } finally {
            lock.unlockWrite(stamp); // Release the write lock
        }
    }
}

Important points:

ReentrantLock is useful for scenarios where you need full control over locking, especially when multiple threads can modify shared resources.
ReadWriteLock is great when the system has more frequent read operations and fewer writes, like viewing account balance.
StampedLock is ideal when reads dominate and you want an optimistic lock that provides better performance for read-heavy use cases.

write even using one thread and odd using another thread. Use Lock concept for this.

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class EvenOdd {
    private final int LIMIT;
    private int counter;
    private final Lock lock;
    private final Condition evenCondition;
    private final Condition oddCondition;

    public EvenOdd(int LIMIT) {
        this.LIMIT = LIMIT;
        this.counter = 1;
        lock = new ReentrantLock();
        evenCondition = lock.newCondition();
        oddCondition = lock.newCondition();
    }

    public void printEven() {
        while (counter < LIMIT) {
            lock.lock();
            try {
                while (counter % 2 != 0) {
                    evenCondition.await();
                }
                System.out.println(Thread.currentThread().getName() + " count is: " + counter++);
                oddCondition.signal();
            } catch (InterruptedException interruptedException) {
                interruptedException.printStackTrace();
            } finally {
                lock.unlock();
            }

        }
    }

    public void printOdd() {
        while (counter < LIMIT) {
            lock.lock();
            try {
                while (counter % 2 == 0) {
                    oddCondition.await();
                }
                System.out.println(Thread.currentThread().getName() + " count is: " + counter++);
                evenCondition.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    }

    public static void main(String[] args) {
        EvenOdd evenOdd = new EvenOdd(10);

        Thread evenThread = new Thread(evenOdd::printEven, "even thread");
        Thread oddThread = new Thread(evenOdd::printOdd, "odd thread");

        evenThread.start();
        oddThread.start();
    }
}

What are different implementation of blocking queue when to use each one.

Queue	Bounded/Unbounded	Use Case
ArrayBlockingQueue	Bounded	Fixed-size task queues, rate-limiting, thread pools.
LinkedBlockingQueue	Optionally Bounded	Dynamic workloads with unpredictable queue size.
PriorityBlockingQueue	Unbounded	Prioritized task processing.
DelayQueue	Unbounded	Delayed task scheduling (e.g., retries).
SynchronousQueue	No Capacity (0)	Direct handoff between threads (no buffering).
LinkedTransferQueue	Unbounded	Efficient handoff with optional queuing if no consumer is waiting.
LinkedBlockingDeque	Optionally Bounded	Double-ended task queue for LIFO/FIFO operations.

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;

public class Test {
    public static void main(String[] args) throws InterruptedException{
        BlockingQueue<Integer> arrayBlockingQueue = new ArrayBlockingQueue<>(5);

        BlockingQueue<Integer> linkedBlockingQueue = new LinkedBlockingQueue<>();

        BlockingQueue<Integer> priorityBlockingQueue = new PriorityBlockingQueue<>();
    }
}

What is priority queue and when to use it. Explain with a example.

import java.util.Objects;
import java.util.PriorityQueue;

class Patient implements Comparable<Patient>{
    private String name;
    private int severity;

    public Patient(String name, int severity) {
        this.name = name;
        this.severity = severity;
    }

    public String getName() {
        return name;
    }

    public int getSeverity() {
        return severity;
    }

    @Override
    public int compareTo(Patient o) {
        return Integer.compare(severity, o.severity)*-1;
    }

    @Override
    public boolean equals(Object object){
        if(this==object)
            return true;
        if(object==null || getClass()!=object.getClass())
            return false;
        Patient patient = (Patient) object;
        return severity == patient.severity;
    }

    @Override
    public int hashCode(){
        return Objects.hash(severity);
    }
}

public class HospitalEmergencyRoom {
    public static void main(String[] args) {
        PriorityQueue<Patient> emergencyRoomQueue = new PriorityQueue<>();

        emergencyRoomQueue.add(new Patient("John doe", 5));
        emergencyRoomQueue.add(new Patient("John Smith", 4));
        emergencyRoomQueue.add(new Patient("Tom Johnson", 3));
        emergencyRoomQueue.add(new Patient("Emily Davis", 2));

        while (!emergencyRoomQueue.isEmpty()){
            Patient patient = emergencyRoomQueue.poll();
            System.out.println("patient name "+ patient.getName()+" severity: "+ patient.getSeverity());
        }
    }
}

Real-World Usage of PriorityQueue:

Emergency Rooms: Patients are treated based on the severity of their conditions.
Job Scheduling: In operating systems or distributed systems, tasks are prioritized based on their importance or urgency.
Event Processing: High-priority events are processed before others.
Network Packet Handling: Prioritize packets that need faster transmission in a network.

Priority queue is java uses binary heap. It uses min-heap to keep smallest element at root. vice versa for max heap.

What is LinkedBlockingDeque. Explain with a example.

The LinkedBlockingDeque is a thread-safe, blocking double-ended queue (deque) which allows you to insert and retrieve elements from both ends.

import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.TimeUnit;

public class Test {

    public static void main(String[] args) {

        // Create a LinkedBlockingDeque with a capacity of 5
        BlockingDeque<Integer> linkedBlockingDeque = new LinkedBlockingDeque<>(5);

        // Producer thread
        Thread producer = new Thread(() -> {
            try {
                for (int i = 1; i <= 10; i++) {
                    linkedBlockingDeque.put(i);  // Blocks if the deque is full
                    System.out.println("Produced: " + i);
                    TimeUnit.MILLISECONDS.sleep(100); // Simulate time taken to produce
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });

        // Consumer thread
        Thread consumer = new Thread(() -> {
            try {
                for (int i = 1; i <= 10; i++) {
                    Integer item = linkedBlockingDeque.take();  // Blocks if the deque is empty
                    System.out.println("Consumed: " + item);
                    TimeUnit.MILLISECONDS.sleep(150); // Simulate time taken to consume
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });

        // Start both threads
        producer.start();
        consumer.start();

        // Wait for both threads to finish
        try {
            producer.join();
            consumer.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("All items have been produced and consumed.");
    }
}

Differentiate between failfast and failsafe.

failfast	failsafe
Doesn't allow modifications of a collection while iterating	Allows modifications of a collection while iterating
Throws `ConcurrentModificationException`	Don't throw any exceptions
Uses the original collection to traverse over the elements	Uses a copy of the original collection to traverse over the elements
Don’t require extra memory	Require extra memory

Give me pesudocode of internal working of Linkedhashmap

Linked hashmap node contains two more extra field to maintain insertation order other than simple hashmap. after node and before Node to store pointer of next and before node. Also there is a header node which is the header that links all the nodes.
```
LinkedHashMapEntry<K, V> before, after;
        final K key;
        V value;
        HashMapEntry<K, V> next;
        int hash;

LinkedHashMapEntry<K, V> header;
```
explanation in medium

Difference between HashMap and LinkedHashMap

Aspect	HashMap	LinkedHashMap
Order of Elements	No guaranteed order (unordered).	Maintains insertion order or access order.
Iteration Order	Unpredictable, varies depending on hash codes.	Predictable, based on insertion or access order.
Data Structure	Hash table only.	Hash table and doubly linked list.
Performance (Insert/Retrieve)	O(1) for put and get operations (in general).	O(1) for put and get, but slightly slower due to maintaining the linked list.
Memory Overhead	Lower memory usage.	Higher memory usage due to the linked list.
Use Case	Best when the order of elements does not matter.	Best when insertion or access order is important.
Access Order Support	No access order tracking.	Can be configured to maintain access order.
Example Use	General-purpose key-value storage.	Caches (e.g., LRU cache) or use cases where order matters.
Removal of Eldest Entry	No direct support for removing the eldest entry.	Can automatically remove the eldest entry when configured (useful in caches).
Null Keys/Values	Allows one null key and multiple null values.	Same as HashMap – allows one null key and multiple null values.

How treemap works internally

Internally Treemap uses RedBlack tree which is self balancing BST(Binary Balance tree). Time complexity is log(n) for search, get, put, remove. Treemap is not synchronised. To work with multiple thread, we can use collections method to get synchronized map.

import java.util.*;

public class Test {

    public static void main(String[] args) {
        TreeMap<String , Integer> treeMap = new TreeMap<>();
        Map<String, Integer> synchronizedMap = Collections.synchronizedMap(treeMap);
    }
}

What is Iterable interface and how it is different from Listiterator ?

Object Implementing Iterable allows it to be iterated.

public interface Iterable<T> {

    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

Difference between hashmap and treemap
1. Treemap preserve natural ordering. There is no ordering in hashmap
2. Hashing priciple is used in hashmap and Red black tree is used in treemap.
3. hashmap can contain one null key while treemap can't contain any null value.

Explain internal working of hashtable and how it is different from hashmap.

    bucketArray[] = new Bucket[initialCapacity]

    // put operation
        hashCode = key.hashCode()
    index = hashCode % bucketArray.length

    if bucketArray[index] == null:
        bucketArray[index] = new LinkedList()
    bucketArray[index].add(new Entry(key, value))

    // If key already exists in the bucket, update the value:
    for each Entry in bucketArray[index]:
        if Entry.key == key:
            Entry.value = value
            return

    // get operation
    hashCode = key.hashCode()
    index = hashCode % bucketArray.length

    for each Entry in bucketArray[index]:
        if Entry.key == key:
            return Entry.value

Aspect	HashMap	Hashtable
Synchronization	Not synchronized, meaning it is not thread-safe.	Synchronized, making it thread-safe. Multiple threads cannot access it simultaneously.
Performance	Faster in single-threaded environments due to no synchronization overhead.	Slower due to synchronization overhead in multi-threaded environments.
Null Keys/Values	Allows one `null` key and multiple `null` values.	Does not allow `null` keys or `null` values.
Legacy or Modern	Part of Java 1.2, part of the Collection Framework.	Legacy class from Java 1.0, not part of the Collection Framework, but retrofitted to implement the `Map` interface.
Iterator	Fail-fast iterator, meaning it throws `ConcurrentModificationException` if the map is modified while iterating.	Enumerations or iterators are fail-safe, but are synchronized, meaning they work correctly even if modified by other threads.
Thread Safety	Not thread-safe (can use `Collections.synchronizedMap()` to make it thread-safe).	Thread-safe due to synchronization.
Use Case	Best for non-threaded applications where performance is important.	Best for legacy applications where thread-safety is a concern.
Alternative for Thread Safety	Use `ConcurrentHashMap` for better thread-safety without performance impact.	Thread-safe but with high contention.

What is the difference between ConcurrentHashMap and SynchronizedMap? When would you choose one over the other?

Synchronized map locks entire for any operation be it read or write. So there is a significant degrade in performance. Concurrent hash map lock a portion of map to do operation like read and write.

Explain why LinkedHashMap is a good option to implement LRU(Least recently used) Cache. Since LinkedHashMap can maintain the insertion order, we can easily track the least used cache and evict it.

public class Test {

    public static void main(String[] args) {

        Map<String, Integer> map = new LinkedHashMap<>();

        map.put("BAAAAAAA", 2);
        map.put("C", 3);
        map.put("DAAA", 4);
        map.put("A", 1);

        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();

        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

Suppose we have a task with attribute name, priority and deadline. We are given a list of task and that need to taken based on priority first and then deadline. Implement a sample code to perform this task.

import java.util.*;

class Task {
    private String name;
    private int priority;
    private Date deadline;

    public Task(String name, int priority, Date deadline) {
        this.name = name;
        this.priority = priority;
        this.deadline = deadline;
    }

    public String getName() {
        return name;
    }

    public int getPriority() {
        return priority;
    }

    public Date getDeadline() {
        return deadline;
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if(object==null || getClass() != object.getClass())
            return false;
        Task that = (Task) object;
        return name.equals(that.name) && Integer.compare(priority, that.priority) == 0 && deadline.compareTo(that.deadline) == 0;
    }

    @Override
    public int hashCode(){
        return Objects.hash(name, priority, deadline);
    }

    @Override
    public String toString() {
        return "Task{" +
                "name='" + name + '\'' +
                ", priority=" + priority +
                ", deadline=" + deadline +
                '}';
    }
}

public class Test {

    public static void main(String[] args) {

        Queue<Task> priorityTask = new PriorityQueue<>(new Comparator<Task>() {
            @Override
            public int compare(Task o1, Task o2) {
                if(o1.getPriority() != o2.getPriority()){
                    return Integer.compare(o1.getPriority(), o2.getPriority());
                }else{
                    return o1.getDeadline().compareTo(o2.getDeadline());
                }
            }
        });
        priorityTask.add(new Task("task 1", 4, new Date(2024, 10, 25)));
        priorityTask.add(new Task("task 2", 1, new Date(2024, 10, 20)));
        priorityTask.add(new Task("task 3", 3, new Date(2024, 10, 14)));
        priorityTask.add(new Task("task 4", 2, new Date(2024, 10, 17)));
        priorityTask.add(new Task("task 5", 1, new Date(2024, 10, 16)));

        while (!priorityTask.isEmpty()){
            Task task = priorityTask.poll();
            System.out.println(task);
        }
    }
}

Explain a use case where IdentityHashMap would be more suitable than HashMap ?

IdentityHashMap is used when keys equals method do not use logical equality instead based on identity of object.

import java.util.IdentityHashMap;
import java.util.Map;

class Service {
    String name;

    public Service(String name) {
        this.name = name;
    }

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Service service = (Service) o;
        return name.equals(service.name);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

public class ObjectPool {
    public static void main(String[] args) {
        Map<Service, String> pool = new IdentityHashMap<>();

        Service s1 = new Service("DatabaseService");
        Service s2 = new Service("DatabaseService");
        Service s3 = s1;

        pool.put(s1, "First Instance");
        pool.put(s2, "Second Instance");
        pool.put(s3, "Third Instance (Same as First)");

        System.out.println(pool);
    }
}

Use case is Object Pool or Dependency Injection with Object Identity.

Can you explain how ArrayBlockingQueue and LinkedBlockingQueue differ in terms of performance?

ArrayBlockingQueue is generally preferred for fixed-size queues with known maximum capacity due to its lower memory overhead and better performance in terms of throughput.
LinkedBlockingQueue is more flexible, allowing for dynamic sizing and better concurrency at the cost of slightly higher memory usage and potential overhead due to pointer management.
Since ArrayBlockingQueue used index for traversal, so its is more efficient in performance.

Feature	ArrayBlockingQueue	LinkedBlockingQueue
Underlying Structure	Array	Linked List
Capacity	Fixed size (defined at creation)	Can be fixed or unbounded
Memory Usage	More efficient for smaller queues	Higher memory overhead due to node pointers
Throughput	Generally better for fixed-size queues	Slightly lower due to overhead of linked nodes
Access Time	O(1) for insertions/deletions (direct indexing)	O(1) for insertions/deletions (pointer dereferencing)
Blocking Behavior	Blocks when full	Can be unbounded, may not block when adding
Concurrency	Single lock for the entire queue	Separate locks for put and take operations
Use Cases	Best for known, fixed-size queues	Better for dynamically sized or larger datasets

Briefly explain about internal of vector and its drawback ?

Vector is a legacy class which give resizable array implementation. It uses array internally to store elements. When the internal array runs out of space it allocates a new array for larger size. Vector is thread safe because all its methods are synchronized.

Drawback
1. Since every method is synchronized, only one thread can access the object at a time.
2. Vector is slower due to default synchronization.
3. Vector takes too much memory since it double the array size when the capacity is increased.
Explain the internal structure and usage of the Deque interface ?

Internally Deque uses double ended queue which means we can add and remove from both sides. Below is major implementation of Deque (pronounced "deck").
1. ArrayDeque
2. LinkedList
One of major benefit of Deque is that It can act as both queue(FIFO) and stack(LIFO).
Why do we use Deque with LinkedList over stack.

Since stack uses vector and synchronization block the entire object leading to degrade in performance. Since it is not synchronized making in more performant in non-concurrent environment.

Given a mathematical expression, check if parenthesis is balanced or not.

(1 + 2) * (3 / (4 - 5)) -> true
(1 + 2) * (3 / (4 - 5) -> false

import java.util.Deque;
import java.util.LinkedList;

class ParenthesisCheck{
    public boolean isBalanced(String expression){
        Deque<Character> stack = new LinkedList<>();

        for(char ch: expression.toCharArray()){
            if(ch=='('){
                stack.push(ch);
            }else if(ch==')'){
                if(stack.isEmpty() || stack.pop() != '('){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {

        String expression1 = "(1 + 2) * (3 / (4 - 5))";
        String expression2 = "(1 + 2) * (3 / (4 - 5)";

        ParenthesisCheck parenthesisCheck = new ParenthesisCheck();

        System.out.println(parenthesisCheck.isBalanced(expression1));
        System.out.println(parenthesisCheck.isBalanced(expression2));
    }
}

Design a customer support system which which get a lots of tickets. Some of the ticket has high priority that need to give higher priority and some has lower priority. Design a lld with appropriate collection which will give more priority to high priority ticket.

package org.learning.misc;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;

class Ticket {
    private String priority;
    private String details;

    public Ticket(String priority, String details) {
        this.priority = priority;
        this.details = details;
    }

    public String getPriority() {
        return priority;
    }

    public String getDetails() {
        return details;
    }

    @Override
    public int hashCode() {
        return Objects.hash(priority, details);
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if (object == null || object.getClass() != getClass()) return false;
        Ticket ticket = (Ticket) object;
        return Objects.equals(priority, ticket.priority) && Objects.equals(this.details, ticket.details);
    }

    @Override
    public String toString() {
        return "Ticket{" +
                "priority='" + priority + '\'' +
                ", details='" + details + '\'' +
                '}';
    }
}

public class CustomerSupport {
    private Deque<Ticket> tickets;
    public CustomerSupport() {
        tickets = new LinkedList<>();
    }

    public void addHighPriorityTicket(Ticket ticket) {
        tickets.addFirst(ticket);
    }

    public void addLowPriorityTicket(Ticket ticket) {
        tickets.addFirst(ticket);
    }

    public Ticket pullTicket() {
        if (tickets.isEmpty()) {
            return null;
        }
        return tickets.pollFirst();
    }

    public static void main(String[] args) {
        CustomerSupport customerSupport = new CustomerSupport();

        customerSupport.addHighPriorityTicket(new Ticket("MEDIUM", "ticket 1"));
        customerSupport.addHighPriorityTicket(new Ticket("HIGH", "ticket 2"));
        customerSupport.addHighPriorityTicket(new Ticket("MEDIUM", "ticket 3"));
        customerSupport.addHighPriorityTicket(new Ticket("MEDIUM", "ticket 4"));
        customerSupport.addHighPriorityTicket(new Ticket("HIGH", "ticket 5"));

        Ticket ticket;
        do {
            ticket = customerSupport.pullTicket();
            System.out.println(ticket);
        } while (ticket != null);
    }
}

Ticket{priority='HIGH', details='ticket 5'}
Ticket{priority='MEDIUM', details='ticket 4'}
Ticket{priority='MEDIUM', details='ticket 3'}
Ticket{priority='HIGH', details='ticket 2'}
Ticket{priority='MEDIUM', details='ticket 1'}
null

Can you explain the differences between ArrayDeque and LinkedList for Deque usage ?

Aspect	`ArrayDeque`	`LinkedList`
Underlying Structure	Resizable array	Doubly linked list
Insertion/Removal	O(1) (amortized)	O(1)
Random Access	O(1)	O(n)
Memory Efficiency	More efficient	Higher overhead
Null Elements	Not allowed	Allowed
Iteration Speed	Faster (contiguous memory)	Slower (non-contiguous memory)
Use Case	General-purpose, caching, stacks	Frequent insertions/removals, lists
Resizing	Yes (expensive occasionally)	No need to resize

Explain internal working of LinkedBlockingQueue with a pseudocode.

class Node:
    element  // Stores the data
    next     // Points to the next node in the queue

class LinkedBlockingQueue:
    head -> Node    // Head of the queue (dummy node)
    tail -> Node    // Tail of the queue
    capacity        // Maximum number of elements
    count           // Current number of elements in the queue
    lock            // Reentrant lock to ensure thread-safety
    notEmpty        // Condition variable for "not empty" signal
    notFull         // Condition variable for "not full" signal

constructor(capacity):
    this.capacity = capacity   // Initialize the maximum capacity
    head = tail = new Node(null)  // Create a dummy node for the linked list
    count = 0                    // Initially, the queue is empty

put(element):
    acquire lock
    while count == capacity:    // If the queue is full
        wait on notFull         // Block until there is space
    // Insert the element
    node = new Node(element)
    tail.next = node            // Append the new node at the tail
    tail = node                 // Update the tail to the new node
    count += 1                  // Increment the count
    signal notEmpty             // Signal that the queue is not empty
    release lock

take():
    acquire lock
    while count == 0:           // If the queue is empty
        wait on notEmpty        // Block until an element is available
    // Remove the element
    node = head.next            // The real first element is after the dummy head
    element = node.element      // Get the element to return
    head = node                 // Move head to the next node
    count -= 1                  // Decrement the count
    signal notFull              // Signal that the queue is not full
    release lock
    return element

size():
    acquire lock
    return count
    release lock

isEmpty():
    acquire lock
    return count == 0
    release lock

isFull():
    acquire lock
    return count == capacity
    release lock

Create LinkedBlockingQueue with a fixed size

 LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>(100);

How stream works internally, explain with a example. Let's take a example below.
```
import java.util.List;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Test2 {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6);
        List<Integer> primeNumber = list.stream().filter(item -> item % 2 == 0).collect(Collectors.toList());
        System.out.println(primeNumber);
    }
}
```
Internal working involves three steps.
1. Source: When the above code runs, firstly we create a stream of list. Stream object provides a way to access the data and perform multiple operation like filtering, mapping, collecting.
2. Intermediate operations: Then we add multiple operation on these stream source. Like map(), filter(), flatMap(), sorted(), distinct(), and limit()
3. Terminal operations: Terminal operation process the elements and produce the final result. It apply all the intermediate operation on source object.
Key concept of stream:
1. Laziness: Since intermediate operation are only added to list of operation.
2. Pipelines: Streams are processed in a pipeline fashion, where each operation takes the output of the previous one as input.
3. Functional style: Streams are designed to be used in a functional style, with operations that take functions as arguments and return new streams.
4. Immutability: Stream are immutable meaning they don't modify underlying data structure.

Give me a low label code to implement similar feature in pipeline ?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
import java.util.function.Predicate;

class StreamPipeline {
    List<Integer> source;
    List<Operation> operations = new ArrayList<>();

    StreamPipeline(List<Integer> source) {
        this.source = source;
    }

    void addIntermediateOperation(Operation op) {
        operations.add(op);
    }

    List<Integer> collect() {
        List<Integer> result = new ArrayList<>();


        for (Integer element : source) {
            boolean shouldInclude = true;
            Integer transformedElement = element;


            for (Operation op : operations) {

                if (op.isFilter()) {
                    if (!op.applyFilter(transformedElement)) {
                        shouldInclude = false;
                        break;
                    }
                }

                else if (op.isMap()) {
                    transformedElement = op.applyMap(transformedElement);
                }
            }


            if (shouldInclude) {
                result.add(transformedElement);
            }
        }

        return result;
    }
}


abstract class Operation {

    boolean isFilter() {
        return this instanceof FilterOperation;
    }


    boolean isMap() {
        return this instanceof MapOperation;
    }


    boolean applyFilter(Integer element) {
        return true;
    }


    Integer applyMap(Integer element) {
        return element;
    }
}


class FilterOperation extends Operation {
    Predicate<Integer> predicate;

    FilterOperation(Predicate<Integer> predicate) {
        this.predicate = predicate;
    }


    boolean applyFilter(Integer element) {
        return predicate.test(element);
    }
}


class MapOperation extends Operation {
    Function<Integer, Integer> mapper;

    MapOperation(Function<Integer, Integer> mapper) {
        this.mapper = mapper;
    }


    Integer applyMap(Integer element) {
        return mapper.apply(element);
    }
}


public class Test {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6);

        StreamPipeline pipeline = new StreamPipeline(numbers);

        pipeline.addIntermediateOperation(new FilterOperation(n -> n % 2 == 0));

        pipeline.addIntermediateOperation(new MapOperation(n -> n * 2));

        List<Integer> result = pipeline.collect();

        System.out.println(result);
    }
}

How to handle exception in stream operation ? explain with example Handling Checked Exception

import java.util.*;
import java.util.function.Consumer;

@FunctionalInterface
interface CheckedExceptionHandlerConsumer<Target, ExObj extends Exception> {
    public void accept(Target target) throws ExObj;
}

class Test {
    static <Target> Consumer<Target> handleCheckedExceptionConsumer(CheckedExceptionHandlerConsumer<Target, Exception> handlerConsumer) {
        return obj -> {
            try {
                handlerConsumer.accept(obj);
            } catch (Exception ex) {
                throw new RuntimeException(ex);
            }
        };
    }
    public static void main(String[] args) {
        List<String> list2 = Arrays.asList("10", "20", "abc");

        list2.forEach(handleCheckedExceptionConsumer(num -> {
            int number = Integer.parseInt(num);
            System.out.print(num+" ");
        }));

        System.out.println("successful run ");
    }
}

Handling checked exception

import java.util.*;
import java.util.function.Consumer;

class Test {
    static <Target, ExObj extends Exception> Consumer<Target> handleGenericException(Consumer<Target> targetConsumer,
                                                                                    Class<ExObj> exObjClass) {
        return obj -> {
            try {
                targetConsumer.accept(obj);
            } catch (Exception ex) {
                try {
                    ExObj exObj = exObjClass.cast(ex);
                    System.out.println("exception : " + exObj.getMessage());
                } catch (ClassCastException ecx) {
                    throw ex;
                }
            }
        };
    }

    public static void main(String[] args) {
        List<String> list = Arrays.asList("44", "373", "xyz");
        List<Integer> list1 = Arrays.asList(1, 0);

        list1.forEach(handleGenericException(s -> System.out.println(10 / s), ArithmeticException.class));
        list.forEach(handleGenericException(s -> System.out.println(Integer.parseInt(s)), NumberFormatException.class));
    }
}

What is Steam ? A stream in Java is a sequence of objects that supports various methods that can be pipelined to produce the desired result.

What design pattern is mostly used in java stream api

a. Decorator pattern

    import java.util.List;
    import java.util.function.Function;
    import java.util.stream.Collectors;

    public class Person {
        private String name;
        private int age;

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

        public String getName() {
            return name;
        }

        public int getAge() {
            return age;
        }

        public String toString() {
            return name + " is " + age + " years old.";
        }
    }

    public class DecoratorExample {
        public static void main(String[] args) {
            List<Person> people = List.of("Alice", "Bob", "Charlie")
                    .stream()
                    .map(Person::new)
                    .map(person -> decorate(person, p -> p.getName().toUpperCase()))
                    .map(person -> decorate(person, p -> p.getAge() + 10))
                    .collect(Collectors.toList());

            people.forEach(System.out::println);
        }

        private static Person decorate(Person person, Function<Person, Person> decorator) {
            return decorator.apply(person);
        }
    }

Each decorator method applies a transformation to person object

b. Composition pattern

List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David");

List<String> result = names.stream()
    .filter(name -> name.startsWith("A"))
    .map(String::toUpperCase)
    .sorted()
    .collect(Collectors.toList());

Each operation (filter, map, sorted, and collect) is a component in the composite structure of the stream pipeline.

c. Chain of responsibility

EmployeeFilter filter = new JoinedAfter2015Filter();
return employees.stream()
    .filter(filter::filter) // Chain responsibility through filter method
    .collect(Collectors.toList());

Check all design pattern in below stream program.


    Map<String, Employee> youngestEmployeeInEachDept = employeeList.stream()
        .collect(Collectors.groupingBy(Employee::getDepartment, Collectors.minBy(Comparator.comparingInt(Employee::getAge) )))
        .entrySet().stream()
        .filter(entity-> entity.getValue().isPresent() == true)
        .collect(Collectors.toMap(Map.Entry::getKey, entry-> entry.getValue().get()));

a. Command pattern: Stream operations like groupingBy, minBy, filter, and map act as commands that transform the data in a sequential manner. b. Iterator pattern: The stream acts as an iterator, providing access to elements one by one.