10. Design a Notification System in Java : FAANG Interviews

Designing a scalable notification system is a typical problem encountered during FAANG interviews. This system aims to send notifications to users in real-time, support different notification types such as email, SMS, and in-app, and ensure delivery reliability. This article will discuss key design concepts, tools, and practices for building such a notification system using Java, including handling message queues, user preferences, delivery acknowledgment, and retries.

Key Components of the Notification System

1. Message Queues: A message queue such as Apache Kafka or RabbitMQ helps manage the flow of notifications to different services, ensuring that messages are processed asynchronously and efficiently. These tools allow the notification system to scale horizontally by decoupling the message producers from the consumers.

2. User Preferences: A notification system needs to respect user preferences regarding the types of notifications they want to receive and the delivery channels (email, SMS, in-app, etc.). This requires storing user preferences and filtering the notifications accordingly before sending them.

3. Delivery Acknowledgment and Retries: Notifications need to be reliably delivered. In case of failures, such as network errors or service downtime, the system should be able to acknowledge the failure and retry sending the notification.

4. Scalability: The system should be designed to scale as the user base grows. This can be achieved by distributing the load across multiple servers, leveraging message queues, and using stateless services to handle increased traffic.

---

Architecture Overview

Let’s break down the architecture of the system and the components involved:

1. Producer: The producer is responsible for generating notifications, which may come from various sources, such as events, user actions, or system alerts. These notifications are added to a message queue (e.g., Kafka or RabbitMQ) for further processing.

2. Consumer: Consumers process notifications from the queue. Each consumer can handle a specific type of notification (email, SMS, in-app) and can be deployed as a distributed service.

3. User Preferences Service: This service stores user preferences (e.g., which notifications they want to receive and via which channels). When a notification is ready to be sent, the system checks the user's preferences to determine whether it should be delivered and through which channel.

4. Notification Dispatcher: This service sends notifications to the appropriate channels, whether via email, SMS, or in-app. It interacts with external services like email providers or SMS gateways.

5. Acknowledgment and Retry Mechanism: Each notification sent will need to be acknowledged by the respective external service (e.g., an email service). If the notification fails to be delivered, the system will retry sending it based on a predefined policy.

---

Example Implementation in Java

Dependencies

For our implementation, we will use Apache Kafka for the message queue and Java Mail API to send emails. Let’s first include the necessary dependencies:

<dependencies>
    <!-- Apache Kafka dependency -->
    <dependency>
        <groupId>org.apache.kafka</groupId>
        <artifactId>kafka-clients</artifactId>
        <version>3.0.0</version>
    </dependency>
    
    <!-- JavaMail for email notifications -->
    <dependency>
        <groupId>javax.mail</groupId>
        <artifactId>javax.mail-api</artifactId>
        <version>1.6.2</version>
    </dependency>
    
    <!-- Spring Boot for general structure -->
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter</artifactId>
    </dependency>
</dependencies>

---

Kafka Producer (Sending Notifications)

First, let’s create a Kafka producer to send notifications to the message queue.

import org.apache.kafka.clients.producer.*;
import org.apache.kafka.common.serialization.StringSerializer;

import java.util.Properties;

public class NotificationProducer {
    
    private final KafkaProducer<String, String> producer;
    
    public NotificationProducer() {
        Properties properties = new Properties();
        properties.put(ProducerConfig.BOOTSTRAP_SERVERS_CONFIG, "localhost:9092");
        properties.put(ProducerConfig.KEY_SERIALIZER_CLASS_CONFIG, StringSerializer.class.getName());
        properties.put(ProducerConfig.VALUE_SERIALIZER_CLASS_CONFIG, StringSerializer.class.getName());
        
        this.producer = new KafkaProducer<>(properties);
    }
    
    public void sendNotification(String message) {
        ProducerRecord<String, String> record = new ProducerRecord<>("notification_topic", message);
        
        producer.send(record, (metadata, exception) -> {
            if (exception != null) {
                System.out.println("Error sending message: " + exception.getMessage());
            } else {
                System.out.println("Message sent to topic: " + metadata.topic());
            }
        });
    }

    public static void main(String[] args) {
        NotificationProducer producer = new NotificationProducer();
        producer.sendNotification("New Event Notification for User");
    }
}

Kafka Consumer (Processing Notifications)

Next, let’s create a Kafka consumer that processes the messages from the queue. Based on the notification type, it will route the message to the correct delivery method (email, SMS, or in-app).

import org.apache.kafka.clients.consumer.*;
import org.apache.kafka.common.serialization.StringDeserializer;

import java.util.Properties;

public class NotificationConsumer {

    private final KafkaConsumer<String, String> consumer;

    public NotificationConsumer() {
        Properties properties = new Properties();
        properties.put(ConsumerConfig.BOOTSTRAP_SERVERS_CONFIG, "localhost:9092");
        properties.put(ConsumerConfig.GROUP_ID_CONFIG, "notification_group");
        properties.put(ConsumerConfig.KEY_DESERIALIZER_CLASS_CONFIG, StringDeserializer.class.getName());
        properties.put(ConsumerConfig.VALUE_DESERIALIZER_CLASS_CONFIG, StringDeserializer.class.getName());

        this.consumer = new KafkaConsumer<>(properties);
    }

    public void consumeMessages() {
        consumer.subscribe(List.of("notification_topic"));

        while (true) {
            ConsumerRecords<String, String> records = consumer.poll(100);
            for (ConsumerRecord<String, String> record : records) {
                String notificationMessage = record.value();
                // Here, we could add logic to process the message based on user preferences
                System.out.println("Received message: " + notificationMessage);
                sendNotification(notificationMessage);
            }
        }
    }

    public void sendNotification(String notificationMessage) {
        // Add logic for sending the notification (email, SMS, or in-app)
        System.out.println("Sending notification: " + notificationMessage);
    }

    public static void main(String[] args) {
        NotificationConsumer consumer = new NotificationConsumer();
        consumer.consumeMessages();
    }
}

Handling Delivery Acknowledgments and Retries

In a real-world scenario, after attempting to send a notification (email, SMS, etc.), the system should acknowledge the delivery (e.g., by receiving a response from the email provider). If the delivery fails, the system will retry according to a predefined policy (e.g., exponential backoff).

Here's a basic retry logic in Java:

public class NotificationRetryService {

    private static final int MAX_RETRIES = 5;
    
    public boolean sendWithRetry(Notification notification) {
        int retries = 0;
        while (retries < MAX_RETRIES) {
            try {
                // Send the notification (email, SMS, etc.)
                sendNotification(notification);
                return true; // If successful
            } catch (Exception e) {
                retries++;
                if (retries >= MAX_RETRIES) {
                    System.out.println("Failed to deliver notification after " + retries + " attempts");
                    return false; // Delivery failed after retries
                }
                try {
                    Thread.sleep((long) Math.pow(2, retries) * 1000); // Exponential backoff
                } catch (InterruptedException ex) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        return false;
    }

    public void sendNotification(Notification notification) {
        // Actual implementation for sending a notification
        System.out.println("Sending notification: " + notification.getMessage());
    }
}

---

Summary

In this article, we have designed a scalable and efficient notification system using Java and Apache Kafka. We covered the following concepts:

1. Message Queues (Kafka) for decoupling the message producers from consumers.
2. User preferences are used to ensure notifications are sent according to user preferences.
3. Delivery Acknowledgment and Retries to ensure reliable delivery of notifications.
4. Scalability through horizontal scaling of consumers and message queues.

This system can be expanded to handle more complex notification types, integrate additional channels, and implement advanced features like prioritization and filtering based on user preferences.

Please stay tuned. I will update Point 5 of the FANNG Interview series. The top 10 interview questions are listed here.

Read More

9. Find the kth Largest Element in an Unsorted Array in Java : FAANG Interviews

In many real-world scenarios, you may need to find the k-th largest element in an unsorted array. A common approach to this problem involves using efficient algorithms and data structures to avoid unnecessary computations, such as sorting the entire array. This problem is often used to assess familiarity with sorting algorithms and efficient searching.

Problem Statement

Given an unsorted array of integers, your task is to find the kth largest element in the array, where k is a positive integer and does not exceed the array size.

Key Concepts

1. Quickselect Algorithm (O(n) Average Time Complexity)
2. Heap Data Structures (Min-Heap for kth Largest)
3. Time Complexity Analysis

Let's examine two of the most commonly used approaches to solving this problem: Quickselect and Heap Data Structures.

---

1. Quickselect Algorithm

The Quickselect algorithm is an efficient approach based on the well-known Quicksort algorithm. While Quicksort sorts the entire array, Quickselect only partially sorts the array to find the kth largest element, making It faster on average.

How it Works

1. Choose a Pivot: Like Quicksort, select a pivot element from the array.
2. Partitioning: Partition the array into two parts — one with elements greater than the pivot and one with elements smaller.
3. Recursive Search: Depending on the position of the pivot, recursively apply the algorithm to the side where the kth element lies.

Time Complexity

• Average Case: O(n), where n is the length of the array.
• Worst Case: O(n^2), which occurs when the pivot is consistently chosen as the smallest or largest element (though this can be mitigated with strategies like random pivot selection).

Java Implementation

import java.util.Random;

public class KthLargestQuickselect {

    // Partition the array
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] >= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    // Swap two elements in the array
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Quickselect function
    public static int quickSelect(int[] arr, int low, int high, int k) {
        if (low <= high) {
            int pivotIndex = partition(arr, low, high);

            if (pivotIndex == k - 1) {
                return arr[pivotIndex];
            } else if (pivotIndex > k - 1) {
                return quickSelect(arr, low, pivotIndex - 1, k);
            } else {
                return quickSelect(arr, pivotIndex + 1, high, k);
            }
        }
        return -1;
    }

    // Main function to test Quickselect
    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 4; // kth largest element

        System.out.println(k + "th largest element is: " + quickSelect(arr, 0, arr.length - 1, k));
    }
}

In the example above, the Quickselect algorithm is used to find the 4th largest element in the array {7, 10, 4, 3, 20, 15}.

---

2. Heap Data Structures (Min-Heap for kth Largest)

A Min-Heap is a binary tree data structure in which the parent node is smaller than its children. This property is useful when we need to keep track of the top k largest elements in an array. By maintaining a min-heap of size k, the root of the heap will always be the smallest element in the heap, representing the kth largest element in the entire array array.

How it Works

1. Build a Min-Heap of Size k: Insert the first k elements from the array into a min-heap.
2. Iterate through the Rest of the Array: For each remaining element, if it is larger than the root of the heap (which is the smallest element in the heap), replace the root with the new element and reheapify.
3. Return the Root: After processing all elements, the root of the heap will be the kth largest element.

Time Complexity

• Building the Heap: O(k)
• Inserting Elements: O((n - k) * log k)
• Total Time Complexity: O(n * log k)

Java Implementation

import java.util.PriorityQueue;

public class KthLargestHeap {

    // Function to find the kth largest element
    public static int findKthLargest(int[] nums, int k) {
        // Min-Heap to store k largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        // Build the heap
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek(); // The root of the heap is the kth largest element
    }

    // Main function to test Heap approach
    public static void main(String[] args) {
        int[] nums = {7, 10, 4, 3, 20, 15};
        int k = 4; // kth largest element

        System.out.println(k + "th largest element is: " + findKthLargest(nums, k));
    }
}

In this example, we use a Min-Heap to find the 4th largest element in the array {7, 10, 4, 3, 20, 15}.

---

Summary

Both the Quickselect algorithm and Min-Heap data structure are effective ways to solve the problem of finding the kth largest element in an unsorted array.

• Quickselect is an average-case O(n) solution that provides a more optimal approach regarding time complexity.
• Min-Heap provides an O(n * log k) solution and is generally easier to implement, especially when you need to repeatedly retrieve the kth largest element.

The choice of algorithm depends on the problem constraints and whether you prefer a more straightforward approach or are willing to explore more advanced algorithms, such as Quickselect.

Please stay tuned. I will update Point 5 of the FANNG Interview series. The top 10 interview questions are listed here.

Read More

8. Merge Intervals in Java : FAANG Interviews

In many real-world scenarios, we encounter situations where we need to manage a series of time intervals, such as booking appointments, processing ranges of values, or scheduling events. One common problem in this area is the Merge Intervals problem. The challenge is to collect intervals and merge any overlapping ones.

Problem Definition

You are given a collection of intervals. Each interval is represented as a pair of integers [start, end], where start is the beginning of the interval, and end is the end of the interval. Your task is to merge all overlapping intervals.

For example:

Input:

[[1, 3], [2, 4], [5, 7], [6, 8]]

Output:

[[1, 4], [5, 8]]

Approach

To solve the problem efficiently, we can break it down into the following steps:

1. Sorting: Sort the intervals by their start times.
2. Merging: Iterate through the sorted intervals and merge overlapping ones.

Step 1: Sorting Intervals

The first step is to sort the intervals based on their start times. This ensures that we can easily compare each interval with the next one. The overlapping intervals will be adjacent in the sorted list, making identifying and merging them easier.

Step 2: Merging Intervals

Once the intervals are sorted, we can iterate through them and merge the overlapping ones. Specifically, for each interval:

• If it does not overlap with the previous interval, add it to the result.
• If it overlaps with the previous interval, merge the two intervals by updating the end of the previous interval to the maximum of the two intervals' ends.

Time Complexity Optimization

Sorting the intervals takes $O(n \log n)$, where $n$ is the number of intervals. After sorting, the merge operation can be performed in a single pass through the list, taking $O(n)$. Therefore, the overall time complexity of the solution is $O(n \log n)$.

Java Code Implementation

Let's now look at the Java implementation of the solution.

import java.util.*;

public class MergeIntervals {

    public static List<int[]> mergeIntervals(List<int[]> intervals) {
        // Step 1: Sort intervals by start times
        intervals.sort((a, b) -> Integer.compare(a[0], b[0]));

        // List to store merged intervals
        List<int[]> merged = new ArrayList<>();

        // Iterate through sorted intervals
        for (int[] interval : intervals) {
            // If merged is empty or current interval doesn't overlap with the last merged one, add it
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Merge the current interval with the last one in the merged list
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }

        return merged;
    }

    public static void main(String[] args) {
        // Example input
        List<int[]> intervals = new ArrayList<>();
        intervals.add(new int[]{1, 3});
        intervals.add(new int[]{2, 4});
        intervals.add(new int[]{5, 7});
        intervals.add(new int[]{6, 8});

        // Merging the intervals
        List<int[]> mergedIntervals = mergeIntervals(intervals);

        // Output the merged intervals
        for (int[] interval : mergedIntervals) {
            System.out.println(Arrays.toString(interval));
        }
    }
}

Explanation of the Code

1. Sorting: We use intervals.sort((a, b) -> Integer.compare(a[0], b[0])) to sort the intervals based on their start time. This ensures we can process the intervals in order and efficiently check for overlaps.

2. Merging: We initialize an empty list merged to store the merged intervals. For each interval in the sorted list:

   • If the list is empty or the current interval does not overlap with the last merged interval (i.e., the end of the last merged interval is less than the start of the current interval), we simply add the current interval to the result.
   • If the current interval overlaps with the last merged interval, we update the end of the last merged interval to the maximum of the two intervals' end values.

3. Output: Finally, we print out the merged intervals.

Example Walkthrough

Let's walk through the provided example:

Input:

[[1, 3], [2, 4], [5, 7], [6, 8]]

1. Sorting: The intervals are sorted by their start times:

   [[1, 3], [2, 4], [5, 7], [6, 8]]
   

2. Merging:

   • Start with the first interval [1, 3]. It's added to the merged list.
   • The next interval [2, 4] overlaps with the last merged interval [1, 3], so we merge them into [1, 4].
   • The next interval [5, 7] does not overlap with [1, 4], so we add it to the merged list.
   • The last interval [6, 8] overlaps with [5, 7], so we merge them into [5, 8].

Output:

[[1, 4], [5, 8]]

Time Complexity

• Sorting: $O(n \log n)$
• Merging: $O(n)$ Thus, the total time complexity is $O(n \log n)$, where $n$ is the number of intervals.

Summary

The Merge Intervals problem is an excellent example of how sorting and interval comparison can help efficiently solve overlapping range problems. The solution here leverages sorting and a single pass through the intervals to achieve optimal time complexity. Understanding this approach helps solve this specific problem and builds a foundation for working with other range-based issues in Java.

Please stay tuned; I will update Point 6 of the FANNG Interview series; please check the top 10 interview questions here.

Read More

7. Design a Real-time Chat System in Java : FAANG Interviews

Building a real-time chat system is challenging yet rewarding. It involves handling multiple users, real-time messaging, user presence, and message persistence. In this article, we will discuss the key concepts required to design such a system using Java, including the Pub/Sub pattern, database design, message queues, user authentication, session management, and scalability considerations.

1. Pub/Sub Pattern for Real-Time Communication

The Pub/Sub (Publish/Subscribe) pattern is essential for enabling real-time messaging between users. In this pattern, publishers (users sending messages) send messages to a topic, and subscribers (other users in the chat room) receive messages from that topic in real time. This decouples the sender from the receiver, allowing for efficient communication in distributed systems.

Implementation in Java:

• Publisher: Sends a message to a channel or topic.
• Subscriber: Listens to the channel/topic and receives messages.

Using libraries such as Redis Pub/Sub, RabbitMQ, or Kafka can make the implementation of this pattern more scalable.

Example using Redis Pub/Sub in Java:

public class ChatPublisher {
    private Jedis jedis;

    public ChatPublisher() {
        jedis = new Jedis("localhost");
    }

    public void sendMessage(String channel, String message) {
        jedis.publish(channel, message);
    }
}

public class ChatSubscriber {
    private Jedis jedis;

    public ChatSubscriber() {
        jedis = new Jedis("localhost");
    }

    public void subscribeToChannel(String channel) {
        jedis.subscribe(new JedisPubSub() {
            @Override
            public void onMessage(String channel, String message) {
                System.out.println("Received message: " + message);
            }
        }, channel);
    }
}

2. Database Design for Storing Messages

Storing messages for persistence is crucial, especially in a chat system where users expect to see historical conversations. A relational database like MySQL or a NoSQL database like MongoDB can be used to store messages, depending on the structure of your application.

Basic Database Schema:

• Users Table: Stores user information like username, password, and online status.
• Messages Table: Stores message details like sender, receiver, timestamp, and message content.

Here is an example schema for MySQL:

CREATE TABLE users (
    id INT AUTO_INCREMENT PRIMARY KEY,
    username VARCHAR(255) NOT NULL,
    password VARCHAR(255) NOT NULL,
    online_status BOOLEAN DEFAULT FALSE
);

CREATE TABLE messages (
    id INT AUTO_INCREMENT PRIMARY KEY,
    sender_id INT,
    receiver_id INT,
    message TEXT,
    timestamp TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    FOREIGN KEY (sender_id) REFERENCES users(id),
    FOREIGN KEY (receiver_id) REFERENCES users(id)
);

3. Message Queues for Asynchronous Communication

Message queues are a great way to decouple the sender and receiver, making the system more robust and scalable. They handle asynchronous communication, ensuring that even if the receiver is temporarily offline, the message is stored and delivered later.

Popular message queue systems:

• RabbitMQ
• Kafka
• Amazon SQS

Using these systems, messages can be processed in background jobs, reducing latency and improving system performance.

Example using RabbitMQ in Java:

public class MessageQueueSender {
    private final static String QUEUE_NAME = "chatQueue";

    public static void sendMessage(String message) throws Exception {
        ConnectionFactory factory = new ConnectionFactory();
        factory.setHost("localhost");
        try (Connection connection = factory.newConnection(); 
             Channel channel = connection.createChannel()) {
            channel.queueDeclare(QUEUE_NAME, false, false, false, null);
            channel.basicPublish("", QUEUE_NAME, null, message.getBytes());
            System.out.println("Sent: " + message);
        }
    }
}

public class MessageQueueReceiver {
    private final static String QUEUE_NAME = "chatQueue";

    public static void receiveMessages() throws Exception {
        ConnectionFactory factory = new ConnectionFactory();
        factory.setHost("localhost");
        try (Connection connection = factory.newConnection(); 
             Channel channel = connection.createChannel()) {
            channel.queueDeclare(QUEUE_NAME, false, false, false, null);
            DeliverCallback deliverCallback = (consumerTag, delivery) -> {
                String message = new String(delivery.getBody(), "UTF-8");
                System.out.println("Received: " + message);
            };
            channel.basicConsume(QUEUE_NAME, true, deliverCallback, consumerTag -> {});
        }
    }
}

4. User Authentication and Session Management

Handling user authentication and session management is crucial in a real-time chat system. Using secure authentication mechanisms such as JWT (JSON Web Tokens) or OAuth2 can ensure that only authenticated users can access chat functionalities.

Session Management:

• Track user sessions to manage online/offline status.
• Store sessions in memory or in a database to quickly retrieve user information during communication.

For authentication in Java, we can use frameworks like Spring Security to secure user endpoints and manage session states.

Example using JWT for authentication in Java:

public class JwtTokenUtil {
    private String secretKey = "your_secret_key";

    public String generateToken(String username) {
        return Jwts.builder()
            .setSubject(username)
            .setIssuedAt(new Date())
            .setExpiration(new Date(System.currentTimeMillis() + 86400000)) // 1 day
            .signWith(SignatureAlgorithm.HS512, secretKey)
            .compact();
    }

    public Claims extractClaims(String token) {
        return Jwts.parser()
            .setSigningKey(secretKey)
            .parseClaimsJws(token)
            .getBody();
    }

    public boolean isTokenExpired(String token) {
        return extractClaims(token).getExpiration().before(new Date());
    }
}

5. Handling Large Volumes of Data and Scaling

A real-time chat system needs to handle large volumes of data and users. To achieve this, the system should be designed to scale horizontally and handle spikes in traffic.

Scalability Techniques:

• Sharding: Divide the database into smaller parts to distribute the load.
• Load Balancing: Distribute user traffic across multiple servers to avoid bottlenecks.
• Caching: Use a caching layer like Redis to store frequently accessed data (e.g., user status, active chats) and reduce database load.

Scaling with Kubernetes: Use Kubernetes for container orchestration and Docker to containerize the application for easy deployment and scaling across multiple instances.

Summary

Designing a scalable real-time chat system in Java involves understanding and integrating key concepts like the Pub/Sub pattern, message queues, database design, authentication, session management, and scalability. By utilizing tools like Redis, RabbitMQ, JWT, and Kubernetes, we can create a system that efficiently handles real-time communication and ensures reliability and performance as it scales.

With these concepts and techniques, developers can build robust chat applications capable of handling many users and messages, providing a smooth and responsive user experience.

---

Related Articles:

• Building Real-Time Applications with Java and WebSockets
• Message Queues: How to Use RabbitMQ for Asynchronous Messaging
• Optimizing Chat Applications for Scale

Please stay tuned; I will update Point 6 of the FANNG Interview series; please check the top 10 interview questions here.

Read More

6. Find the Longest Substring Without Repeating Characters in Java : FAANG Interviews

 Finding the longest substring without repeating characters is a widespread coding problem. This challenge effectively tests your understanding of strings and ability to apply the sliding window algorithm. In this article, we will explore an efficient solution that utilizes the sliding window technique and a HashMap to keep track of the frequency of characters.

Problem Overview

Given a string, you are tasked with finding the length of the longest substring that contains no repeating characters. For example:

• Input: "abcabcbb"
• Output: 3 (The answer is "abc" with length 3.)

Key Concepts

Before diving into the code, let's outline the key concepts that will help us solve the problem:

1. Sliding Window Algorithm:
   • The sliding window technique involves maintaining a "window" of valid elements, which dynamically adjusts as we traverse the string.
   • As we iterate through the string, we try to extend the window by including new characters, but we also shrink the window from the left if we encounter a repeating character.
2. HashMap for Character Frequency Counting:
   • We utilize a HashMap, or a similar data structure, to store the frequency of characters within the current window. This allows us to quickly determine if a character is already in the window and make adjustments as needed.
3. Time Complexity Optimization (O(n)):
   • A brute force approach would involve checking every possible substring, resulting in a time complexity of O(n²). However, by employing the sliding window technique, we can achieve a linear time complexity of O(n), where n represents the length of the input string. This improvement allows us to handle even large strings efficiently.

Solution Approach

    The core concept of this solution involves using two pointers (or indices) to represent the left and right ends of a sliding window. The right pointer expands the window by adding new characters, while the left pointer shrinks the window whenever a repeating character is encountered.

Here’s the step-by-step breakdown of the approach:

1. Use a HashMap to store the most recent index of each character in the string.
2. Iterate through the string using a right pointer, extending the window.
3. If a character repeats, move the left pointer just past the last occurrence of that character to maintain a substring with unique characters.
4. Keep track of the maximum length of the substring without repeating characters.

Code Implementation

Below is the Java code that implements the solution:

import java.util.HashMap;

public class LongestSubstringWithoutRepeatingCharacters {

    public static int lengthOfLongestSubstring(String s) {

        // HashMap to store the last position of each character.

        HashMap<Character, Integer> map = new HashMap<>();

        
        // Initialize pointers for the sliding window.

        int left = 0; // Left pointer

        int maxLength = 0; // To keep track of the maximum length

        
        // Iterate through the string with the right pointer.

        for (int right = 0; right < s.length(); right++) {

            char currentChar = s.charAt(right);


            // If the character is already in the HashMap and its position is greater than or equal to 'left',

            // move 'left' pointer to the right of the last occurrence of the current character.

            if (map.containsKey(currentChar) && map.get(currentChar) >= left) {

                left = map.get(currentChar) + 1;

            }


            // Update the last seen position of the current character.

            map.put(currentChar, right);

            
            // Calculate the maximum length of the substring without repeating characters.

            maxLength = Math.max(maxLength, right - left + 1);

        }

        
        return maxLength;

    }

    public static void main(String[] args) {

        String input = "abcabcbb";

        System.out.println("Length of Longest Substring Without Repeating Characters: " + lengthOfLongestSubstring(input));

    }

}

Explanation of the Code

1. HashMap Initialization:
   • We create a HashMap<Character, Integer> to store the last seen index of each character in the string.
2. Sliding Window Logic:
   • We maintain two pointers: left and right. The right pointer moves from the start to the end of the string.
   • If we encounter a repeating character within the window, the left pointer is moved to the right of the last occurrence of that character.
3. Update Maximum Length:
   • After processing each character, we calculate the current length of the substring as right-left + 1. The maxLength is updated with the maximum of its current value and the new substring length.
4. Edge Cases:
   • The code handles cases where the string is empty or contains only one character.

Time and Space Complexity

• Time Complexity: O(n)
  • We iterate over the string once with the right pointer and move the left pointer as needed, each only once. Hence, the time complexity is linear in terms of the string size.
• Space Complexity: O(min(n, m))
  • The space complexity depends on the size of the HashMap, which stores the last seen index of each character. The maximum size of the map is determined by the number of distinct characters in the string (m), which could be at most n if all characters are unique.

Summary

   This approach effectively addresses the problem of finding the longest substring without repeating characters using the sliding window technique. By employing a HashMap to track the last seen index of each character, we ensure that the solution operates in linear time, making it suitable for significant inputs. This method exemplifies how to optimize solutions for string manipulation challenges.

Please stay tuned; I will update Point 6 of the FANNG Interview series; please check the top 10 interview questions here.

Happy coding!

Read More