Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts

Data Structures and Algorithms for Every Java Developer

Whether you're preparing for a coding interview, building scalable backend systems, or aiming to write high-performance applications, a solid understanding of data structures and algorithms (DSA) is non-negotiable. In this blog, we’ll walk through the must-know DSA topics specifically for Java developers, with real-world relevance and Java-specific tips.


 Why Java Developers Must Learn DSA

  • Interviews: DSA is the backbone of technical interviews at FAANG and top-tier companies.

  • Performance: The right data structure can drastically reduce latency and resource usage.

  • Scalability: Efficient algorithms make your systems handle 10x more users without 10x cost.

  • Problem Solving: Builds logical thinking and improves your debugging abilities.


Core Data Structures in Java

1. Linear Data Structures

Data Structure Use Case Java API
Array Fast access by index int[], ArrayList<T>
Linked List Dynamic memory allocation LinkedList<T>
Stack LIFO operations (undo, backtracking) Stack<T>
Queue/Deque FIFO, Double-ended operations Queue<T>, Deque<T>

2. Hash-Based Structures

Data Structure Use Case Java API
HashMap Key-value storage HashMap<K, V>
HashSet Fast membership test HashSet<T>

3. Tree-Based Structures

Data Structure Use Case Java API
Binary Tree/BST Hierarchical storage Custom
Red-Black Tree Balanced search tree TreeMap<K, V>, TreeSet<T>
Trie Prefix searching (e.g., autocomplete) Custom

4. Heap (Priority Queue)

Used for scheduling, top-k problems, and greedy algorithms
 Java: PriorityQueue<T> with custom Comparator

5. Graph

Represent networks (social, pathfinding, dependency graphs)
Java: Adjacency List/Matrix with custom classes or JGraphT

6. Advanced

Structure Use Case
Segment Tree Range queries
Fenwick Tree Prefix sums
Disjoint Set (Union-Find) Connected components, Kruskal’s MST

Algorithms to Focus On

Searching & Sorting

  • Binary Search, Merge Sort, Quick Sort

  • Heap Sort, Counting Sort

  • Java APIs: Arrays.sort(), Collections.sort(), custom Comparator

Recursion & Backtracking

  • N-Queens, Maze Path, Subsets, Permutations

Dynamic Programming

  • Knapsack, Fibonacci, LCS, Matrix DP

  • Practice via tabulation and memoization

Greedy Algorithms

  • Activity selection, Huffman Coding, Interval Scheduling

Graph Algorithms

  • BFS, DFS, Topological Sort

  • Dijkstra, Kruskal, Prim, Union-Find

Bit Manipulation

  • XOR Tricks, Set/Unset Bits, Power of 2

Sliding Window & Two Pointers

  • Max sum subarrays, Longest substring without repeating chars

Math & Number Theory

  • GCD/LCM, Sieve of Eratosthenes, Modular Exponentiation


 Java-Specific Tips for DSA

  • Master Collections Framework (List, Map, Set, Queue)

  • Use Comparator & Comparable for custom sorting logic

  • Understand autoboxing, generics, and performance tradeoffs

  • Dive into Concurrency APIs: ExecutorService, ConcurrentHashMap


 Learning Plan for Java DSA

  1. Start with Collections API – understand how ArrayList, HashMap, TreeMap, etc. work under the hood.

  2. Implement Data Structures Manually – Build your own LinkedList, Stack, etc.

  3. Tackle Real Problems – Use LeetCode, GeeksForGeeks, or HackerRank.

  4. Practice Patterns – Sliding window, recursion with memoization, etc.

  5. Master Algorithms – Solve classic problems and understand trade-offs.


Top Resources

  • 📘 Cracking the Coding Interview – Gayle Laakmann McDowell

  • 📘 Effective Java – Joshua Bloch

  • 💻 LeetCode's Top 100 Liked Problems

  • 📚 GeeksForGeeks Java Data Structures Section

Whether you’re targeting top companies, building scalable software, or just enhancing your core dev skills—mastering DSA is your gateway. For Java developers, pairing algorithmic thinking with powerful tools like the Collections Framework will elevate your code from functional to exceptional.



Least Recently Used (LRU) cache in Java

What is LRU Cache?

Least Recently Used (LRU) is a caching strategy that evicts the least recently accessed item when the cache exceeds its capacity. It ensures that the most frequently or recently used data stays in memory while discarding older, less useful entries.


Real-World Use Case

  • Android image loading: Cache recently viewed images to avoid reloading from the network.

  • Database query results: Store recently used queries for faster results.

  • Web browsers: Maintain a small history of visited pages.

  • Memory-constrained systems: Manage resource usage by limiting active items in memory.


Best Way to Implement LRU in Java

The simplest and most effective way to implement an LRU Cache in Java is by using LinkedHashMap with access-order enabled.


LRU Cache Using LinkedHashMap (Best Practice)

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");

        // Access key 2 (makes 2 most recently used)
        cache.get(2);

        // Add key 4 - should evict key 1 (least recently used)
        cache.put(4, "Four");

        System.out.println(cache);
        // Output: {3=Three, 2=Two, 4=Four}
    }
}

 Output

{3=Three, 2=Two, 4=Four}

Explanation:

  • Initially added 1, 2, 3.

  • Accessed key 2 → usage order becomes [1, 3, 2]

  • Adding key 4 → evicts 1 as it is the Least Recently Used.


Custom LRU Without LinkedHashMap (for interviews)

Here’s how you can manually implement an LRU Cache using a Doubly Linked List and HashMap in Java — this is the classic approach commonly asked in interviews because it guarantees O(1) time complexity for both get() and put() operations.


Key Concepts

  • HashMap gives O(1) lookup for keys.

  • Doubly Linked List maintains access order (most recent at the front, least at the end).

  • Each node contains key & value and links to its previous and next node.

import java.util.HashMap;

public class LRUCache<K, V> {
    private final int capacity;
    private final HashMap<K, Node> map;
    private final Node head, tail;

    private class Node {
        K key;
        V value;
        Node prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();

        // Dummy head and tail nodes to avoid null checks
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        moveToHead(node); // Mark as most recently used
        return node.value;
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);

            if (map.size() > capacity) {
                Node lru = tail.prev;
                removeNode(lru);
                map.remove(lru.key);
            }
        }
    }

    // Helper methods for doubly linked list operations
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    public void printCache() {
        Node current = head.next;
        while (current != tail) {
            System.out.print(current.key + "=" + current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");

        cache.printCache(); // 3=Three 2=Two 1=One

        cache.get(2); // Access 2 to move it to front
        cache.printCache(); // 2=Two 3=Three 1=One

        cache.put(4, "Four"); // Evicts 1 (least recently used)
        cache.printCache(); // 4=Four 2=Two 3=Three
    }
}

Output

3=Three 2=Two 1=One
2=Two 3=Three 1=One
4=Four 2=Two 3=Three

Benefits of This Approach

Feature Description
Time Complexity O(1) for both get() and put()
Space Complexity O(capacity)
No built-in Java tricks Great for coding interviews
Full control Easy to customize or extend

Key Takeaways

  • Use LinkedHashMap with accessOrder = true for easy and efficient LRU.

  • Override removeEldestEntry() to control eviction.

  • Prefer it for in-memory caches in performance-sensitive apps.

  • For interviews, know the manual implementation using Doubly Linked List + HashMap.


📢 Feedback: Did you find this article helpful? Let me know your thoughts or suggestions for improvements! 😊 please leave a comment below. I’d love to hear from you! 👇

Happy coding! 💻✨

Longest Common Subsequence (LCS) in Java

Longest Common Subsequence (LCS) problem, including its problem statement, solution, and Java implementation using the best possible approach — Dynamic Programming (Tabulation - Bottom-Up) for optimal performance.


Problem Statement: Longest Common Subsequence (LCS)

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The LCS is "ace" with length 3.

Optimal Solution: Dynamic Programming (Bottom-Up Tabulation)

💡 Idea:

We use a 2D DP array dp[i][j] where each cell represents the length of the LCS of the first i characters of text1 and the first j characters of text2.

Transition Formula:

  • If text1[i-1] == text2[j-1]
    → dp[i][j] = 1 + dp[i-1][j-1]

  • Else
    → dp[i][j] = max(dp[i-1][j], dp[i][j-1])


Java Code (Bottom-Up Approach)

public class LongestCommonSubsequence {

    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        // Create a 2D dp array
        int[][] dp = new int[m + 1][n + 1];

        // Fill the dp array from bottom up
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If characters match, move diagonally and add 1
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    // Else take max from left or top
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // The answer is in dp[m][n]
        return dp[m][n];
    }

    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        int result = longestCommonSubsequence(text1, text2);
        System.out.println("Length of LCS: " + result);  // Output: 3
    }
}

Time and Space Complexity

Complexity Value
Time O(m * n)
Space O(m * n)

You can optimize space to O(min(m, n)) by using a 1D rolling array instead of a 2D array if needed.


Bonus: To Reconstruct the LCS String

If you want to reconstruct the LCS itself, not just its length, we can backtrack from dp[m][n] to dp[0][0] while tracing the matching characters.

📢 Feedback: Did you find this article helpful? Let me know your thoughts or suggestions for improvements! 😊 please leave a comment below. I’d love to hear from you! 👇

Happy coding! 💻✨

SOLID principle in Java

The SOLID principles are essential object-oriented programming (OOP) design principles that help create maintainable, flexible, scalable, and robust software systems.

Here's a clear explanation of each SOLID principle in Java, along with real-time examples and their significance in software projects:


1. Single Responsibility Principle (SRP)

Definition:
A class should have only one reason to change, meaning it should have only one responsibility.

Example:
Suppose you're designing an e-commerce system:

Bad Example:

class OrderProcessor {
    void processOrder(Order order) {
        // Process payment
        // Notify customer via email
        // Update inventory
    }
}

Good Example (SRP applied):

class PaymentProcessor {
    void processPayment(Order order) { }
}

class NotificationService {
    void notifyCustomer(Order order) { }
}

class InventoryService {
    void updateInventory(Order order) { }
}

class OrderProcessor {
    PaymentProcessor paymentProcessor;
    NotificationService notificationService;
    InventoryService inventoryService;

    void processOrder(Order order) {
        paymentProcessor.processPayment(order);
        notificationService.notifyCustomer(order);
        inventoryService.updateInventory(order);
    }
}

Importance:

  • Improves readability, easier to debug.

  • Changes to one responsibility don’t affect others.

  • Easier testing and less coupling between classes.


2. Open/Closed Principle (OCP)

Definition:
Software components (classes, modules, functions) should be open for extension but closed for modification.

Example:
Suppose you are handling different payment methods.

Bad Example:

class PaymentProcessor {
    void processPayment(String paymentType) {
        if(paymentType.equals("CreditCard")) {
            // process credit card payment
        } else if(paymentType.equals("PayPal")) {
            // process PayPal payment
        }
        // If a new payment type comes, this method must be modified.
    }
}

Good Example (OCP applied):

interface PaymentMethod {
    void processPayment();
}

class CreditCardPayment implements PaymentMethod {
    public void processPayment() { }
}

class PayPalPayment implements PaymentMethod {
    public void processPayment() { }
}

class BitcoinPayment implements PaymentMethod {
    public void processPayment() { }
}

class PaymentProcessor {
    void processPayment(PaymentMethod method) {
        method.processPayment();
    }
}

Importance:

  • Reduces risk when adding new functionality.

  • Ensures system stability.

  • Improves flexibility for adding future requirements.


3. Liskov Substitution Principle (LSP)

Definition:
Objects of a superclass should be replaceable by objects of subclasses without breaking the system’s correctness.

Example:
You have a hierarchy of birds:

Violation Example:

class Bird {
    void fly() { }
}

class Penguin extends Bird {
    void fly() {
        throw new UnsupportedOperationException("Penguin can't fly");
    }
}

Good Example (LSP applied):

class Bird { }

class FlyingBird extends Bird {
    void fly() { }
}

class Sparrow extends FlyingBird {
    void fly() { }
}

class Penguin extends Bird {
    void swim() { }
}

Importance:

  • Ensures polymorphism is correctly implemented.

  • Prevents unexpected behaviors and runtime errors.

  • Improves maintainability and readability.


4. Interface Segregation Principle (ISP)

Definition:
Clients should not be forced to depend upon interfaces they don’t use. Keep interfaces small, specific, and tailored to client needs.

Example:
Printer devices example.

Violation Example:

interface Printer {
    void print();
    void scan();
    void fax();
}

class OldPrinter implements Printer {
    public void print() { }
    public void scan() { throw new UnsupportedOperationException(); }
    public void fax() { throw new UnsupportedOperationException(); }
}

Good Example (ISP applied):

interface Printer {
    void print();
}

interface Scanner {
    void scan();
}

interface Fax {
    void fax();
}

class OldPrinter implements Printer {
    public void print() { }
}

class MultiFunctionPrinter implements Printer, Scanner, Fax {
    public void print() { }
    public void scan() { }
    public void fax() { }
}

Importance:

  • Avoids forcing irrelevant methods onto clients.

  • Reduces complexity and enhances clarity.

  • Promotes more modular and maintainable code.


5. Dependency Inversion Principle (DIP)

Definition:
High-level modules should not depend directly on low-level modules. Both should depend on abstractions (interfaces or abstract classes). Abstractions shouldn’t depend on details; details should depend on abstractions.

Example:
Consider database operations:

Violation Example:

class MySQLDatabase {
    void saveData(String data) { }
}

class UserService {
    private MySQLDatabase database = new MySQLDatabase();
    void saveUser(String data) {
        database.saveData(data);
    }
}

Good Example (DIP applied):

interface Database {
    void saveData(String data);
}

class MySQLDatabase implements Database {
    public void saveData(String data) { }
}

class MongoDB implements Database {
    public void saveData(String data) { }
}

class UserService {
    private Database database;

    UserService(Database database) {
        this.database = database;
    }

    void saveUser(String data) {
        database.saveData(data);
    }
}

Importance:

  • Decouples software modules, leading to highly maintainable code.

  • Easier to replace or upgrade components (database, network service, etc.).

  • Simplifies testing through mock implementations.


Why SOLID Principles Are Important in Software Projects

  • Maintainability: Easier to update, debug, and extend.

  • Readability: Clean and well-structured code improves readability.

  • Testability: Each class can be independently tested without excessive dependencies.

  • Flexibility and Extensibility: New features can be added without significant modifications.

  • Reduced Cost: Reduces complexity, lowering maintenance and future enhancements costs.

  • Scalability: Facilitates the development of larger and more complex systems, supporting agile methodologies.

Applying SOLID principles promotes creating software that's not only functional but also robust, efficient, and scalable.

Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Dependency Inversion Principle (DIP) in SOLID with Java Example

The Dependency Inversion Principle (DIP) is one of the SOLID principles of object-oriented design. It promotes loose coupling between high-level and low-level modules by introducing abstractions. Here's a simple explanation with an example in Java.


Definition

High-level modules should not depend on low-level modules. Both should depend on abstractions.

Abstractions should not depend on details. Details should depend on abstractions.


 Why Use DIP?

Without DIP:

  • High-level classes are tightly coupled to low-level classes.
  • Difficult to change or replace low-level implementations.
  • Harder to test (e.g., unit testing with mocks).

With DIP:

  • Use interfaces or abstract classes to depend on abstractions.
  • Concrete classes implement those interfaces.
  • High-level modules work with interfaces, not concrete implementations.

 Java Example Without DIP (Bad)

class Keyboard {
    public void input() {
        System.out.println("Keyboard input");
    }
}

class Computer {
    private Keyboard keyboard;

    public Computer() {
        this.keyboard = new Keyboard(); // Tight coupling
    }

    public void use() {
        keyboard.input();
    }
}

Here, the Computer is tightly coupled to the Keyboard.


 Java Example With DIP (Good)

// Abstraction
interface InputDevice {
    void input();
}

// Low-level module
class Keyboard implements InputDevice {
    public void input() {
        System.out.println("Keyboard input");
    }
}

// High-level module
class Computer {
    private InputDevice inputDevice;

    public Computer(InputDevice inputDevice) {
        this.inputDevice = inputDevice; // Dependency Injection
    }

    public void use() {
        inputDevice.input();
    }
}

 Usage

public class Main {
    public static void main(String[] args) {
        InputDevice keyboard = new Keyboard();
        Computer computer = new Computer(keyboard);
        computer.use();
    }
}

 Summary

Before DIP After DIP
Tight coupling Loose coupling
Hard to test Easy to test
Direct dependency Depend on abstraction
Difficult to extend Easy to extend/replace

Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Interface Segregation Principle (ISP) in SOLID with Java Example

 The Interface Segregation Principle (ISP) is one of the five SOLID principles of object-oriented design and development. In Java, the ISP promotes the idea that:

"No client should be forced to depend on methods it does not use."

This means interfaces should be specific and fine-grained rather than large and general. Clients should not be required to implement methods they don't need.


🔧 Why It Matters

If an interface has too many methods, implementing classes may end up with empty or meaningless method implementations, which leads to rigid, fragile, and hard-to-maintain code.


✅ Good Example – Following ISP

interface Printer {
    void print(String content);
}

interface Scanner {
    void scan(String document);
}

class CanonPrinter implements Printer {
    @Override
    public void print(String content) {
        System.out.println("Printing: " + content);
    }
}

class CanonScanner implements Scanner {
    @Override
    public void scan(String document) {
        System.out.println("Scanning: " + document);
    }
}

Here, a class only implements the interface it actually needs, promoting separation of concerns.


❌ Bad Example – Violating ISP

interface MultiFunctionDevice {
    void print(String content);
    void scan(String document);
    void fax(String document);
}

class OldPrinter implements MultiFunctionDevice {
    @Override
    public void print(String content) {
        System.out.println("Printing: " + content);
    }

    @Override
    public void scan(String document) {
        // Not supported
        throw new UnsupportedOperationException("Scan not supported");
    }

    @Override
    public void fax(String document) {
        // Not supported
        throw new UnsupportedOperationException("Fax not supported");
    }
}

Here, OldPrinter is forced to implement methods it doesn't support. This violates ISP.


✅ Solution with ISP using Interface Composition

interface Printer {
    void print(String content);
}

interface Scanner {
    void scan(String document);
}

interface Fax {
    void fax(String document);
}

class ModernPrinter implements Printer, Scanner, Fax {
    @Override
    public void print(String content) {
        System.out.println("Printing: " + content);
    }

    @Override
    public void scan(String document) {
        System.out.println("Scanning: " + document);
    }

    @Override
    public void fax(String document) {
        System.out.println("Faxing: " + document);
    }
}

Summary

  • ISP encourages creating smaller, specific interfaces.
  • Helps in building decoupled, modular, and easy-to-maintain code.
  • Supports flexibility and clean architecture.

Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Open-Closed Principle (OCP) in SOLID with Java Example

 The Open-Closed Principle (OCP) is one of the five SOLID principles of object-oriented design. It states that:

"Software entities (classes, modules, functions, etc.) should be open for extension but closed for modification."

Explanation

  • Open for extension: You should be able to add new functionality without changing the existing code.
  • Closed for modification: You should not modify existing code when adding new features.

This principle helps write flexible, maintainable, and scalable code, reducing the risk of introducing bugs when modifying existing functionality.


Example of Violating the Open-Closed Principle

Here’s an example of a class that violates the Open-Closed Principle: We modify the DiscountCalculator class every time a new customer type is added.

Bad Example (Violating OCP)

class DiscountCalculator {
    public double calculateDiscount(String customerType, double amount) {
        if (customerType.equals("Regular")) {
            return amount * 0.1;  // 10% discount for regular customers
        } else if (customerType.equals("Premium")) {
            return amount * 0.2;  // 20% discount for premium customers
        }
        return 0;
    }
}

Problems:

  • If a new customer type (e.g., "VIP") needs to be added, we must modify this class.
  • The calculateDiscount method has to be edited every time a new customer type is introduced, violating OCP.
  • More modifications mean a higher chance of breaking existing functionality.

Applying the Open-Closed Principle

To follow the OCP, we use polymorphism and abstraction. Instead of modifying an existing class, we create new classes that extend the functionality.

Good Example (Following OCP)

// Step 1: Define an interface for discount strategy
interface DiscountStrategy {
    double applyDiscount(double amount);
}

// Step 2: Implement different discount strategies
class RegularCustomerDiscount implements DiscountStrategy {
    @Override
    public double applyDiscount(double amount) {
        return amount * 0.1;  // 10% discount
    }
}

class PremiumCustomerDiscount implements DiscountStrategy {
    @Override
    public double applyDiscount(double amount) {
        return amount * 0.2;  // 20% discount
    }
}

// Step 3: Use the strategy without modifying the existing class
class DiscountCalculator {
    public double calculateDiscount(DiscountStrategy strategy, double amount) {
        return strategy.applyDiscount(amount);
    }
}

// Step 4: Usage
public class Main {
    public static void main(String[] args) {
        DiscountCalculator calculator = new DiscountCalculator();

        DiscountStrategy regularDiscount = new RegularCustomerDiscount();
        DiscountStrategy premiumDiscount = new PremiumCustomerDiscount();

        double regularAmount = calculator.calculateDiscount(regularDiscount, 1000);
        double premiumAmount = calculator.calculateDiscount(premiumDiscount, 1000);

        System.out.println("Regular Customer Discount: " + regularAmount);
        System.out.println("Premium Customer Discount: " + premiumAmount);
    }
}

Advantages of Following OCP:

- No modifications to existing classes when adding a new discount type.
- Extensible design - You can add a new customer type (e.g., VIPCustomerDiscount) by creating a new class implementing DiscountStrategy.
- Better maintainability and readability.
- Follows the Single Responsibility Principle (SRP) by separating concerns.


Extending the System

Now, if a new type of discount needs to be added, you just create a new class:

class VIPCustomerDiscount implements DiscountStrategy {
    @Override
    public double applyDiscount(double amount) {
        return amount * 0.3;  // 30% discount for VIP customers
    }
}

No need to modify the DiscountCalculator class! 🎉

This is how the Open-Closed Principle helps write extensible and maintainable code in Java. 🚀

Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Single Responsibility Principle (SRP) in SOLID with Java Example

Writing clean, maintainable, and scalable code is crucial in software development. One key principle that helps achieve this is the Single Responsibility Principle (SRP), one of the five SOLID principles of object-oriented design.


What is the Single Responsibility Principle?

The Single Responsibility Principle states that:

"A class should have only one reason to change."

This means that each class should have only one responsibility and one focus. If a class handles multiple responsibilities, it becomes more complex, more challenging to test, and more difficult to maintain.

Following SRP, we can keep our code modular, making it easier to understand, test, and extend.


Example: Violating the Single Responsibility Principle

Let’s consider an example where a class violates the Single Responsibility Principle:

class Employee {
    private String name;
    private double salary;

    public Employee(String name, double salary) {
        this.name = name;
        this.salary = salary;
    }

    public String getName() {
        return name;
    }

    public double getSalary() {
        return salary;
    }

    // Responsibility 1: Calculating employee's salary
    public double calculateBonus() {
        return salary * 0.10; // 10% bonus
    }

    // Responsibility 2: Saving employee details to a file
    public void saveToFile() {
        System.out.println("Saving employee data to a file...");
    }
}

What is wrong with this code?

The Employee class has two responsibilities:

  1. Business logic (Calculating salary and bonus)
  2. Persistence logic (Saving data to a file)

If we need to change how the salary is calculated, we modify the same class that handles file storage. This violates SRP and makes the class harder to maintain.


Applying the Single Responsibility Principle

To follow SRP, we should separate the concerns. We can create two separate classes:

  1. Employee – Only contains employee-related data
  2. SalaryCalculator – Handles salary calculations
  3. EmployeePersistence – Handles saving employee data

Here’s the refactored code:

// Employee class now has only one responsibility: storing employee details
class Employee {
    private String name;
    private double salary;

    public Employee(String name, double salary) {
        this.name = name;
        this.salary = salary;
    }

    public String getName() {
        return name;
    }

    public double getSalary() {
        return salary;
    }
}

// SalaryCalculator is responsible for salary-related operations
class SalaryCalculator {
    public double calculateBonus(Employee employee) {
        return employee.getSalary() * 0.10; // 10% bonus
    }
}

// EmployeePersistence is responsible for saving employee data
class EmployeePersistence {
    public void saveToFile(Employee employee) {
        System.out.println("Saving employee " + employee.getName() + " data to a file...");
    }
}

Benefits of Applying the Single Responsibility Principle

  1. Improved Maintainability

    • Changes to salary calculations do not affect file storage logic.
  2. Better Readability and Modularity

    • Code is easier to understand and modify.
  3. Easier Unit Testing

    • We can test salary calculations separately from persistence operations.
  4. Scalability

    • If we need to store employee data in a database instead of a file, we only modify EmployeePersistence, leaving other classes unchanged.

Summary

The Single Responsibility Principle (SRP) helps keep our Java applications modular, clean, and easy to maintain. By ensuring that each class has only one reason to change, we can write better, more scalable, and testable software.

Applying SRP reduces complexity, improves reusability, and enhances collaboration in software projects. Always keep in mind:

"A class should do one thing and do it well."


Would you like me to add more real-world examples or expand on any section? 🚀

Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Tower of Hanoi Problem in Java: Best Approaches with Details

 The Tower of Hanoi is a classic problem that has fascinated mathematicians and computer scientists for decades. It is often used to illustrate recursive problem-solving techniques, and it can also be a valuable tool for learning about algorithms and recursion.

In this blog, we will explore the Tower of Hanoi Problem, focusing on its best approaches. We will also provide a detailed breakdown of the recursive solution and an iterative approach.

What is the Tower of Hanoi Problem?

The Tower of Hanoi involves three pegs and a set of disks of different sizes. The objective is to move all the disks from one peg to another, following these rules:

  1. Only one disk can be moved at a time.
  2. A disk may only be placed on an empty peg or on top of a larger disk.
  3. All disks start on one peg, and the goal is to move them to another peg while following the rules.

Problem Setup

We have:

  • Three pegs: Source, Auxiliary, and Destination.
  • Disks of different sizes are initially arranged on the source peg with the largest disk at the bottom.

The task is to move all disks from the source peg to the destination peg, following the rules.

Recursive Approach

The recursive approach is the most common way to solve the Tower of Hanoi problem. The general strategy is as follows:

  1. Move the n-1 disks from the source peg to the auxiliary peg.
  2. Move the nth disk (the largest disk) directly from the source peg to the destination peg.
  3. Move the n-1 disks from the auxiliary peg to the destination peg.

This is a natural recursive process where each smaller sub-problem mirrors the original problem. The base case for the recursion is when only one disk is left to move.

Java Code for Recursive Solution

public class TowerOfHanoi {

    // Recursive function to solve the Tower of Hanoi problem
    public static void solveTowerOfHanoi(int n, char source, char auxiliary, char destination) {
        if (n == 1) {
            // Base case: if there's only one disk, move it to the destination
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        
        // Move n-1 disks from source to auxiliary
        solveTowerOfHanoi(n - 1, source, destination, auxiliary);

        // Move the nth disk from source to destination
        System.out.println("Move disk " + n + " from " + source + " to " + destination);

        // Move n-1 disks from auxiliary to destination
        solveTowerOfHanoi(n - 1, auxiliary, source, destination);
    }

    public static void main(String[] args) {
        int n = 3; // Number of disks
        System.out.println("The sequence of moves to solve the Tower of Hanoi for " + n + " disks are:");
        solveTowerOfHanoi(n, 'A', 'B', 'C'); // A is source, B is auxiliary, C is destination
    }
}

Explanation of the Recursive Code

  1. Base Case: If only one disk is left to move (n == 1), we simply move it directly to the destination peg.
  2. Recursive Case: If n > 1, we:
    • Recursively move the n-1 disks from the source to the auxiliary peg.
    • Move the nth disk (the largest disk) from the source to the destination peg.
    • Recursively move the n-1 disks from the auxiliary peg to the destination peg.

This recursive solution works efficiently and directly follows the structure of the problem.

Iterative Approach

The iterative approach to the Tower of Hanoi problem is not as intuitive as the recursive approach, but it is still possible to solve it without recursion. This approach generally involves using a stack or keeping track of the states of the disks and pegs. For simplicity, we will discuss a strategy that uses binary operations to simulate the recursive steps iteratively.

Steps for the Iterative Approach

  1. Number of Moves: The minimum number of moves required to solve the Tower of Hanoi problem is 2^n - 1, where n is the number of disks.
  2. Binary Representation: The iterative approach simulates the sequence of moves using binary representation. Each move is encoded as a binary number, with each bit corresponding to a disk and the state representing the peg to which the disk should be moved.
  3. Rules for Move: The sequence of moves follows the same logic as recursion but is derived iteratively, usually using an alternating move pattern and careful management of disk positions.

Pseudocode for Iterative Solution

public class TowerOfHanoiIterative {

    // Iterative function to solve the Tower of Hanoi problem
    public static void solveTowerOfHanoiIteratively(int n, char source, char auxiliary, char destination) {
        int totalMoves = (int) Math.pow(2, n) - 1; // Total number of moves
        char temp;
        
        // Determine the peg to move the disks
        if (n % 2 == 0) {
            temp = destination;
            destination = auxiliary;
            auxiliary = temp;
        }

        // Loop through each move
        for (int move = 1; move <= totalMoves; move++) {
            int disk = findDiskToMove(move, n);
            char from = getFromPeg(disk, source, auxiliary, destination);
            char to = getToPeg(disk, source, auxiliary, destination);

            System.out.println("Move disk " + disk + " from " + from + " to " + to);
        }
    }

    // Find which disk to move based on the binary representation of the move
    private static int findDiskToMove(int move, int n) {
        for (int i = 1; i <= n; i++) {
            if ((move & (1 << (i - 1))) != 0) {
                return i;
            }
        }
        return 0;
    }

    // Get the "from" peg based on the disk
    private static char getFromPeg(int disk, char source, char auxiliary, char destination) {
        if (disk % 3 == 1) return source;
        if (disk % 3 == 2) return auxiliary;
        return destination;
    }

    // Get the "to" peg based on the disk
    private static char getToPeg(int disk, char source, char auxiliary, char destination) {
        if (disk % 3 == 1) return destination;
        if (disk % 3 == 2) return source;
        return auxiliary;
    }

    public static void main(String[] args) {
        int n = 3; // Number of disks
        System.out.println("The sequence of moves to solve the Tower of Hanoi iteratively for " + n + " disks are:");
        solveTowerOfHanoiIteratively(n, 'A', 'B', 'C'); // A is source, B is auxiliary, C is destination
    }
}

Explanation of the Iterative Approach

  • Binary Representation: The findDiskToMove function uses the binary representation of the current move to determine which disk to move. The moves alternate between the three pegs, mimicking recursive logic.
  • Looping: Instead of recursive function calls, the program loops through each move, making the process iterative while ensuring the correct disk-to-peg moves.

Comparing the Approaches

  1. Recursive Approach:
    • Simple and elegant.
    • Easy to understand and implement.
    • Has a time complexity of O(2^n), as each recursive call performs two subproblems.
  2. Iterative Approach:
    • More complex and less intuitive.
    • Useful for understanding binary operations and simulating recursion.
    • Also has a time complexity of O(2^n), but with a different implementation method.

Summary

Both methods have the same time complexity, but understanding both is beneficial for developing a well-rounded understanding of algorithms in computer science.

Thanks for reading! ðŸŽ‰ I'd love to know what you think about the article. Did it resonate with you? ðŸ’­ Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! ðŸ‘‡ðŸš€. Happy coding! ðŸ’»✨

Fixing Problematic Code: Optimizing Employee Management in Java

Problem Statement:

The given code snippet represents an employee management system in which employees are stored in a list and can be added or retrieved by name. The code has several issues that can impact the application's performance, safety, and maintainability.

Key Issues:

  1. Incorrect String Comparison: The code uses == for comparing employee names, which compares object references instead of the actual content of the strings.
  2. Inefficient Search Mechanism: The employee search method uses a linear search, which can become inefficient as the list of employees grows larger.
  3. Lack of Input Validation: The employee constructor does not validate whether the employee’s name is null or empty or whether the age is a valid positive number.
  4. Use of Raw Types in Generics: The list used to store employees lacks type safety by using raw types for the ArrayList.
  5. No Null Checks: There are no null checks when retrieving an employee, which could result in NullPointerException when accessing the employee’s properties.
  6. Public Member Variables: The name and age fields in the Employee class are public, which exposes the object's internal state and violates the principles of encapsulation.
  7. Thread Safety Concerns: The employees list is not thread-safe, potentially causing issues in a multi-threaded environment.
  8. Scalability Issues: The current approach might not scale well with many employees due to inefficient data structures and operations.

Problematic Code

import java.util.ArrayList;
import java.util.List;

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

public class Company {
    List<Employee> employees;
    
    public Company() {
        employees = new ArrayList<Employee>();
    }
    
    public void addEmployee(Employee employee) {
        employees.add(employee);
    }
    
    public Employee getEmployee(String name) {
        for (Employee e : employees) {
            if (e.name == name) {
                return e;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Company company = new Company();
        company.addEmployee(new Employee("John", 30));
        company.addEmployee(new Employee("Jane", 25));
        
        Employee emp = company.getEmployee("John");
        System.out.println(emp.name + " is " + emp.age + " years old.");
    }
}

List of Problems & Fixes

1. Using == for String Comparison

Issue: In the getEmployee method, the == operator is used to compare String values. This compares object references rather than the content of the strings.

Fix: Use .equals() for string comparison.

if (e.name.equals(name)) {
    return e;
}

2. Lack of Proper Null Check for getEmployee Method

Issue: If getEmployee returns null, it can cause a NullPointerException when accessing the name or age properties.

Fix: Check if the returned Employee is null before trying to access its fields.

Employee emp = company.getEmployee("John");
if (emp != null) {
    System.out.println(emp.name + " is " + emp.age + " years old.");
} else {
    System.out.println("Employee not found.");
}

3. Use of Raw Types with Generics

Issue: The employees list is initialized with raw types (ArrayList<Employee>), which is not ideal for type safety.

Fix: Ensure that generic types are used consistently.

employees = new ArrayList<>();

4. Inefficient Search Logic in getEmployee

Issue: The getEmployee method performs a linear search for each employee. This is inefficient, especially as the list grows.

Fix: Use a HashMap for faster lookups.

private Map<String, Employee> employeeMap = new HashMap<>();

public void addEmployee(Employee employee) {
    employeeMap.put(employee.name, employee);
}

public Employee getEmployee(String name) {
    return employeeMap.get(name);
}

5. Lack of Validation on Input Data

Issue: The Employee constructor does not validate input values (like age). Negative ages or null names would pass through silently.

Fix: Add validation logic to the constructor.

public Employee(String name, int age) {
    if (name == null || name.isEmpty()) {
        throw new IllegalArgumentException("Name cannot be null or empty");
    }
    if (age < 0) {
        throw new IllegalArgumentException("Age cannot be negative");
    }
    this.name = name;
    this.age = age;
}

6. Inconsistent Naming Conventions

Issue: The variable name emp is used for the employee, but more descriptive variable names should be used.

Fix: Use more descriptive variable names.

Employee employee = company.getEmployee("John");

7. Potential Thread Safety Issues with List

Issue: The employees list is not thread-safe. If the Company class is accessed concurrently, it could lead to race conditions.

Fix: Use a CopyOnWriteArrayList or synchronize access.

private List<Employee> employees = new CopyOnWriteArrayList<>();

8. Lack of Logging and Error Handling

Issue: There is no logging or error handling when things go wrong (like adding an employee with an invalid name or age).

Fix: Add logging and error handling to provide better diagnostics.

private static final Logger logger = LoggerFactory.getLogger(Company.class);

public void addEmployee(Employee employee) {
    try {
        employees.add(employee);
    } catch (Exception e) {
        logger.error("Failed to add employee: " + employee.name, e);
    }
}

9. Inappropriate Use of public for Variables

Issue: The name and age fields in Employee are public. This exposes internal state directly and is considered bad practice in OOP.

Fix: Make the fields private and provide getters/setters for them.

private String name;
private int age;

public String getName() {
    return name;
}

public int getAge() {
    return age;
}

10. Possible Scalability Issues with addEmployee

Issue: The addEmployee method is simply appending employees to the list. If this method is called frequently in large systems, it could lead to performance bottlenecks.

Fix: If scalability becomes an issue, consider adding employees in batches or using an optimized data structure like LinkedList.

employees = new LinkedList<>();

Full Fixed Code:

import java.util.HashMap;
import java.util.Map;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

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

    // Constructor with input validation
    public Employee(String name, int age) {
        if (name == null || name.isEmpty()) {
            throw new IllegalArgumentException("Name cannot be null or empty");
        }
        if (age < 0) {
            throw new IllegalArgumentException("Age cannot be negative");
        }
        this.name = name;
        this.age = age;
    }

    // Getter methods
    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

public class Company {
    private Map<String, Employee> employeeMap = new HashMap<>();
    private static final Logger logger = LoggerFactory.getLogger(Company.class);

    // Method to add an employee
    public void addEmployee(Employee employee) {
        try {
            employeeMap.put(employee.getName(), employee);
        } catch (Exception e) {
            logger.error("Failed to add employee: " + employee.getName(), e);
        }
    }

    // Method to retrieve an employee by name
    public Employee getEmployee(String name) {
        return employeeMap.get(name);
    }

    public static void main(String[] args) {
        Company company = new Company();
        
        // Adding employees
        company.addEmployee(new Employee("John", 30));
        company.addEmployee(new Employee("Jane", 25));

        // Retrieving and printing employee details
        Employee employee = company.getEmployee("John");
        if (employee != null) {
            System.out.println(employee.getName() + " is " + employee.getAge() + " years old.");
        } else {
            System.out.println("Employee not found.");
        }
    }
}

Key Fixes & Optimizations:

  1. String Comparison: Replaced == with .equals() for string comparison in the getEmployee method.
  2. Null Safety: Checked if the Employee object is null before accessing its fields.
  3. Use of Generics: Replaced raw types with generics (Map<String, Employee>).
  4. Optimized Search: Switched to a HashMap for constant-time lookups instead of linear search.
  5. Input Validation: Added validation in the Employee constructor for name and age.
  6. Logging & Error Handling: Integrated SLF4J logger for better error handling and diagnostics.
  7. Encapsulation: Made name and age fields private and added getters for access.
  8. Improved Variable Naming: Renamed emp to employee for better clarity.
  9. Thread Safety: Though not explicitly fixed in this code, we can consider adding thread safety if needed (e.g., CopyOnWriteArrayList or synchronized blocks).
  10. Scalability: By using a HashMap, we handle larger datasets efficiently with O(1) lookup times.

This code version demonstrates best practices for Java development, improving performance, readability, and maintainability.

Thanks for reading! 🎉 I'd love to know what you think about the article. Did it resonate with you? 💭 Any suggestions for improvement? I’m always open to hearing your feedback so that I can improve my posts! 👇🚀. Happy coding! 💻✨