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!

5. Implement a Multi-threaded Producer-Consumer Problem in Java: FAANG Interviews

The Producer-Consumer problem is a classic concurrency challenge often asked in interviews. It involves two types of threads: producers and consumers. The producers create data, and the consumers consume it. Both types of threads share a common buffer (usually a queue) that stores the data, but they must access the buffer safely to prevent issues such as race conditions, deadlocks, and inconsistent data.

This problem can be efficiently solved by utilizing Java's concurrency tools such as thread synchronization, condition variables, and the wait-notify mechanism. Let's dive into the core concepts and the solution to the Producer-Consumer problem.

Key Concepts:

  1. Thread Synchronization: Thread synchronization ensures that only one thread accesses shared data at a time, preventing race conditions.
  2. Condition Variables and wait-notify: The wait and notify methods allow threads to wait for certain conditions to be met before proceeding, which helps coordinate producers and consumers.
  3. Deadlock Prevention: Deadlocks occur when threads are waiting on each other indefinitely. Proper synchronization and control flow can help prevent this.
  4. Thread Safety and Atomic Operations: Atomic operations ensure that a particular operation on a shared resource happens atomically, preventing interruptions from other threads.

Solution Overview:

In the producer-consumer problem, we’ll use a shared buffer (a queue) that is accessed by both producers and consumers. The producers will add data to the buffer, and the consumers will remove data. We need to ensure that when a producer adds data, the buffer is not full, and when a consumer removes data, the buffer is not empty. Additionally, we must ensure that threads do not interfere with each other in unsafe ways.

We’ll implement this solution using synchronized blocks for synchronization and a BlockingQueue for thread-safe queue operations.

Example Code:

import java.util.LinkedList;
import java.util.Queue;

// Shared Buffer
class Buffer {
    private final Queue<Integer> queue = new LinkedList<>();
    private final int capacity = 10; // Maximum buffer size

    // Producer adds an item to the buffer
    public synchronized void produce(int item) throws InterruptedException {
        while (queue.size() == capacity) {
            wait();  // Wait until space becomes available
        }
        queue.add(item);
        System.out.println("Produced: " + item);
        notify();  // Notify consumers that there's something to consume
    }

    // Consumer removes an item from the buffer
    public synchronized int consume() throws InterruptedException {
        while (queue.isEmpty()) {
            wait();  // Wait until the buffer is not empty
        }
        int item = queue.poll();
        System.out.println("Consumed: " + item);
        notify();  // Notify producers that there's space available
        return item;
    }
}

// Producer thread
class Producer extends Thread {
    private final Buffer buffer;

    public Producer(Buffer buffer) {
        this.buffer = buffer;
    }

    @Override
    public void run() {
        try {
            for (int i = 0; i < 20; i++) {
                buffer.produce(i);
                Thread.sleep(100);  // Simulate time taken to produce an item
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

// Consumer thread
class Consumer extends Thread {
    private final Buffer buffer;

    public Consumer(Buffer buffer) {
        this.buffer = buffer;
    }

    @Override
    public void run() {
        try {
            for (int i = 0; i < 20; i++) {
                buffer.consume();
                Thread.sleep(150);  // Simulate time taken to consume an item
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

public class ProducerConsumerExample {
    public static void main(String[] args) {
        Buffer buffer = new Buffer();
        
        // Create and start the producer and consumer threads
        Thread producerThread = new Producer(buffer);
        Thread consumerThread = new Consumer(buffer);
        
        producerThread.start();
        consumerThread.start();
    }
}

Explanation of the Code:

  1. Buffer Class:

    • The Buffer class acts as a shared resource for both producers and consumers. It uses a Queue<Integer> to hold the items being produced and consumed.
    • The produce() method adds an item to the queue if there is space available (it waits if the buffer is full).
    • The consume() method removes an item from the queue if the buffer is not empty (it waits if the buffer is empty).

  2. Producer Class:

    • The Producer class is a thread that produces items and adds them to the buffer. It will produce 20 items and simulate a delay of 100 milliseconds between productions.

  3. Consumer Class:

    • The Consumer class is a thread that consumes items from the buffer. It will consume 20 items and simulate a delay of 150 milliseconds between consumptions.

  4. Thread Synchronization:

    • Both the produce() and consume() methods are synchronized to ensure that only one thread accesses the shared buffer at a time.
    • The wait() and notify() methods are used to make threads wait for a condition (e.g., waiting for space or items in the buffer) and to notify the other threads when the condition has changed.

  5. Deadlock Prevention:

    • The synchronized blocks in both produce() and consume() ensure that access to the shared resource is controlled. By using wait() and notify(), we avoid situations where threads wait indefinitely for each other, thereby preventing deadlocks.

  6. Atomic Operations:

    • The operations on the buffer (adding and removing items) are atomic in the sense that once a thread enters a synchronized block, no other thread can interfere until the operation completes.

Conclusion:

This example demonstrates a simple and effective way to solve the Producer-Consumer problem in Java using thread synchronization, the wait-notify mechanism, and atomic operations. By utilizing synchronization and careful control over the flow of execution, we ensure that both the producer and consumer can operate safely without causing race conditions, deadlocks, or inconsistencies in the shared resource. 

This solution can be extended or modified to fit more complex scenarios, such as having multiple producers and consumers or using other concurrency tools like Locks and Condition variables.

Please stay tune, I will update Point 6 of FANNG Interview series, Please check top 10 interview questions here.

4. Design a Parking Lot System in Java: FAANG Interviews

Designing a parking lot system is a common problem in system design interviews that tests your understanding of object-oriented principles, data structures, and problem-solving skills. In this article, we’ll walk through the design of a parking lot system that can manage different vehicle types, allocate parking spots, and retrieve them efficiently using Java.

Key Concepts

  • Object-Oriented Design: We’ll be using a class hierarchy to represent different components in the parking lot system.
  • Polymorphism and Abstraction: Different vehicle types (e.g., motorcycle, compact, and large vehicles) will be handled through a common interface or abstract class.
  • Efficient Data Structures: We’ll use a HashMap to store and look up available parking spots efficiently.

Problem Overview

We are tasked with designing a parking lot system that:

  • Can accommodate multiple vehicle types.
  • Efficiently allocates and deallocates parking spots.
  • Allows the system to find available spots in an optimal way.

Class Hierarchy

Our system will consist of a few key entities:

  1. Vehicle - Represents a generic vehicle.
  2. Motorcycle, CompactCar, LargeCar - Specialized types of vehicles.
  3. ParkingSpot - Represents a parking spot in the lot.
  4. ParkingLot - Manages the entire parking lot, including spot allocation and retrieval.

Let’s break down each component.

Step 1: Defining the Vehicle Class

The Vehicle class will be an abstract class or an interface. It will serve as the base class for all vehicle types. It will include the method signatures that every vehicle class will implement.

abstract class Vehicle {
    protected String vehicleId;
    protected int size;

    public Vehicle(String vehicleId, int size) {
        this.vehicleId = vehicleId;
        this.size = size;
    }

    public String getVehicleId() {
        return vehicleId;
    }

    public int getSize() {
        return size;
    }

    public abstract void park(ParkingLot parkingLot);
}

Step 2: Implementing Specific Vehicle Types

Now, let's create specific vehicle types that inherit from Vehicle. For this example, we'll define Motorcycle, CompactCar, and LargeCar.

class Motorcycle extends Vehicle {
    public Motorcycle(String vehicleId) {
        super(vehicleId, 1); // Motorcycle requires 1 unit of space
    }

    @Override
    public void park(ParkingLot parkingLot) {
        parkingLot.allocateSpot(this);
    }
}

class CompactCar extends Vehicle {
    public CompactCar(String vehicleId) {
        super(vehicleId, 2); // Compact car requires 2 units of space
    }

    @Override
    public void park(ParkingLot parkingLot) {
        parkingLot.allocateSpot(this);
    }
}

class LargeCar extends Vehicle {
    public LargeCar(String vehicleId) {
        super(vehicleId, 3); // Large car requires 3 units of space
    }

    @Override
    public void park(ParkingLot parkingLot) {
        parkingLot.allocateSpot(this);
    }
}

Step 3: Creating the ParkingSpot Class

A ParkingSpot class will represent a single parking spot in the lot. It will store information about whether it is occupied and which vehicle is parked in it.

class ParkingSpot {
    private int spotId;
    private boolean isOccupied;
    private Vehicle vehicle;

    public ParkingSpot(int spotId) {
        this.spotId = spotId;
        this.isOccupied = false;
    }

    public boolean isOccupied() {
        return isOccupied;
    }

    public void park(Vehicle vehicle) {
        if (!isOccupied) {
            this.vehicle = vehicle;
            isOccupied = true;
        }
    }

    public void leave() {
        isOccupied = false;
        vehicle = null;
    }

    public int getSpotId() {
        return spotId;
    }
}

Step 4: Managing the Parking Lot

The ParkingLot class manages the allocation and deallocation of parking spots. It will include a map (HashMap) of parking spots and will be responsible for parking vehicles and checking available spots.

import java.util.HashMap;
import java.util.Map;

class ParkingLot {
    private Map<Integer, ParkingSpot> spots;

    public ParkingLot(int totalSpots) {
        spots = new HashMap<>();
        for (int i = 1; i <= totalSpots; i++) {
            spots.put(i, new ParkingSpot(i));
        }
    }

    public boolean allocateSpot(Vehicle vehicle) {
        for (Map.Entry<Integer, ParkingSpot> entry : spots.entrySet()) {
            ParkingSpot spot = entry.getValue();
            if (!spot.isOccupied() && spot.getSpotId() >= vehicle.getSize()) {
                spot.park(vehicle);
                System.out.println(vehicle.getVehicleId() + " parked in spot " + spot.getSpotId());
                return true;
            }
        }
        System.out.println("No available spot for " + vehicle.getVehicleId());
        return false;
    }

    public void deallocateSpot(int spotId) {
        ParkingSpot spot = spots.get(spotId);
        if (spot != null && spot.isOccupied()) {
            spot.leave();
            System.out.println("Spot " + spotId + " is now available.");
        }
    }
}

Step 5: Testing the Parking Lot System

Here’s how we can use the above classes to simulate a parking lot.

public class ParkingLotSystem {
    public static void main(String[] args) {
        ParkingLot lot = new ParkingLot(10); // Parking lot with 10 spots

        Vehicle bike = new Motorcycle("M1");
        Vehicle compactCar = new CompactCar("C1");
        Vehicle largeCar = new LargeCar("L1");

        bike.park(lot);       // Motorcycle parks in the lot
        compactCar.park(lot); // Compact car parks in the lot
        largeCar.park(lot);   // Large car parks in the lot

        lot.deallocateSpot(1); // Motorcycle leaves
    }
}

Summary

This design provides a simple and effective way to manage a parking lot system that can handle different types of vehicles. We have used the power of object-oriented design principles, like inheritance, polymorphism, and abstraction, to allow the system to scale easily by adding new vehicle types.

By utilizing efficient data structures, such as HashMap, we ensure that we can quickly find and manage parking spots. This approach guarantees that the system can efficiently allocate and deallocate parking spots while maintaining readability and scalability for future enhancements.

Please stay tune, I will update Point 5 of FANNG Interview series, Please check top 10 interview questions here.

3. LRU Cache Implementation in Java : FAANG Interviews

In this article, we will walk through the implementation of an LRU (Least Recently Used) cache in Java. LRU caches are widely used in scenarios where data needs to be cached, but the available storage is limited. When the cache reaches its limit, it evicts the least recently used item to free up space for new entries. This is a common problem faced in technical interviews and is a valuable pattern to understand for optimizing memory management.

Key Concepts

To build an efficient LRU cache, we need to utilize data structures that allow for quick retrieval and modification of the cache elements. The most suitable data structures for this task are:

  1. HashMap: This provides constant time (O(1)) access to cache entries by their keys. A HashMap allows us to quickly check if a key exists in the cache and retrieve its associated value.

  2. Doubly Linked List: This allows us to maintain the order of cache entries, specifically the order in which they were last accessed. A doubly linked list provides efficient removal and insertion operations from both ends, which is crucial for the eviction process.

With these two data structures in place, we can efficiently implement both the get and put operations in constant time (O(1)).

LRU Cache Design

1. Data Structures

To implement the LRU cache, we'll use:

  • HashMap: This will store key-value pairs for fast lookup.
  • Doubly Linked List: This will maintain the order of items by their recent usage. The most recently used item will be at the front of the list, and the least recently used item will be at the end of the list.

2. Cache Operations

  • get(key): This operation checks if the key exists in the cache. If it does, we move the key to the front of the list to mark it as the most recently used. If the key does not exist, we return -1.
  • put(key, value): This operation adds a key-value pair to the cache. If the key already exists, we update the value and move the key to the front of the list. If the cache exceeds its capacity, we evict the least recently used item, which is located at the tail of the doubly linked list.

Code Implementation

import java.util.HashMap;

public class LRUCache {

    // Doubly Linked List Node
    class Node {
        int key, value;
        Node prev, next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer, Node> cache;
    private int capacity;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        
        // Create dummy head and tail nodes
        head = new Node(0, 0);
        tail = new Node(0, 0);
        
        // Connect head and tail
        head.next = tail;
        tail.prev = head;
    }

    // Move the node to the front (most recently used)
    private void moveToFront(Node node) {
        removeNode(node);
        addToFront(node);
    }

    // Add a node right after the head (most recently used)
    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        
        head.next.prev = node;
        head.next = node;
    }

    // Remove a node from the list
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // Get the value of a key from the cache
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1; // Key not found
        }

        Node node = cache.get(key);
        moveToFront(node); // Move the accessed node to the front
        return node.value;
    }

    // Put a key-value pair into the cache
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // Update the existing node and move it to the front
            Node node = cache.get(key);
            node.value = value;
            moveToFront(node);
        } else {
            // If the cache is full, remove the least recently used node
            if (cache.size() >= capacity) {
                cache.remove(tail.prev.key); // Remove the least recently used node
                removeNode(tail.prev);
            }

            // Add the new node to the front of the list
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToFront(newNode);
        }
    }
}

Explanation of the Code

  1. Doubly Linked List Node (Node): Each node contains a key, value, and pointers to the previous and next nodes. This allows us to traverse the list efficiently in both directions.

  2. HashMap (cache): This stores the key-node pairs for quick access to the cache entries. The key is the identifier for the cache entry, and the node stores the associated value.

  3. Head and Tail Nodes: These are dummy nodes used to simplify the code. The head is always the most recently used item, and the tail is the least recently used item.

  4. Operations:

    • get(key): Looks up a key in the cache. If found, it moves the corresponding node to the front to mark it as the most recently used.
    • put(key, value): Adds a new key-value pair. If the key already exists, it updates the value and moves the node to the front. If the cache exceeds its capacity, it evicts the least recently used item (tail).

Time Complexity

  • get(key): O(1) – The key lookup and movement of the node are done in constant time.
  • put(key, value): O(1) – Both insertion and deletion operations are done in constant time using the doubly linked list and HashMap.

Cache Eviction Strategy

The eviction strategy in this implementation follows the LRU principle. When the cache reaches its capacity, the node at the tail (the least recently used item) is removed. This ensures that the most recently used items stay in the cache and the least recently used ones are evicted when necessary.

Summary

An LRU Cache is a powerful technique for managing limited memory in systems where data access patterns follow the "use it or lose it" principle. By combining a HashMap with a doubly linked list, we can ensure both time and space efficiency. This implementation guarantees that both the get and put operations are executed in constant time, O(1), which is essential for high-performance applications.

This approach provides a great example of combining multiple data structures to solve a real-world problem efficiently, and it's an important concept to master for both technical interviews and system design.

Please stay tune, I will update Point 4 of FANNG Interview series, Please check top 10 interview questions here.

2. Design a Distributed File System in Java: FAANG Interviews

A distributed file system (DFS) is an essential component of modern large-scale computing systems. It allows multiple machines to store and retrieve files efficiently, ensuring scalability, fault tolerance, and high performance. This article provides a step-by-step design and implementation of a DFS in Java, covering key concepts such as sharding, data consistency, fault tolerance, and metadata management.

Requirements for a Distributed File System

Functional Requirements:

  • Store files across multiple machines.

  • Retrieve files efficiently.

  • Provide redundancy to prevent data loss.

  • Support scalability to handle growing data volumes.

Non-Functional Requirements:

  • High availability.

  • Fault tolerance.

  • Efficient metadata management.

Key Concepts

1. Sharding and Partitioning of Data

Data is split into chunks and distributed across multiple machines to balance the load.

Implementation:

  • Assign a unique identifier (ID) to each file.

  • Use consistent hashing to determine which node stores a specific file chunk.

public class ConsistentHashing {
    private final List<String> nodes;
    private final int numberOfReplicas;

    public ConsistentHashing(List<String> nodes, int numberOfReplicas) {
        this.nodes = nodes;
        this.numberOfReplicas = numberOfReplicas;
    }

    public String getNode(String key) {
        int hash = key.hashCode() % nodes.size();
        return nodes.get(hash);
    }
}

2. Data Consistency and Availability (CAP Theorem)

The CAP theorem states that a distributed system can only achieve two of the three guarantees:

  • Consistency: All nodes have the same data at any given time.

  • Availability: Every request gets a response (success/failure).

  • Partition Tolerance: The system works despite network failures.

In our design, we aim to balance these constraints based on the use case.

3. Distributed File Storage Mechanisms

Distributed file systems like HDFS or Google File System split files into fixed-size blocks and distribute them across nodes.

File Storage Example:

  • Split a file into chunks of 64 MB each.

  • Store chunks across multiple machines.

public class FileChunk {
    private String chunkId;
    private byte[] data;

    public FileChunk(String chunkId, byte[] data) {
        this.chunkId = chunkId;
        this.data = data;
    }

    public String getChunkId() {
        return chunkId;
    }

    public byte[] getData() {
        return data;
    }
}

4. Fault Tolerance and Replication

Replication ensures that copies of each chunk are stored on multiple machines to prevent data loss in case of node failure.

Implementation:

  • Use a replication factor to determine how many copies of a chunk to store.

  • Distribute replicas across different nodes.

public class ReplicationManager {
    private final int replicationFactor;

    public ReplicationManager(int replicationFactor) {
        this.replicationFactor = replicationFactor;
    }

    public List<String> replicate(String chunkId, List<String> availableNodes) {
        List<String> replicas = new ArrayList<>();
        for (int i = 0; i < replicationFactor; i++) {
            replicas.add(availableNodes.get(i % availableNodes.size()));
        }
        return replicas;
    }
}

5. Metadata Management and Index Structures

Metadata contains information about file locations, chunk mappings, and replicas. A central metadata server efficiently manages this information.

public class ReplicationManager {
    private final int replicationFactor;

    public ReplicationManager(int replicationFactor) {
        this.replicationFactor = replicationFactor;
    }

    public List<String> replicate(String chunkId, List<String> availableNodes) {
        List<String> replicas = new ArrayList<>();
        for (int i = 0; i < replicationFactor; i++) {
            replicas.add(availableNodes.get(i % availableNodes.size()));
        }
        return replicas;
    }
}

Implementation in Java

Main Distributed File System Class

import java.util.*;

public class DistributedFileSystem {
    private MetadataServer metadataServer;
    private ReplicationManager replicationManager;
    private ConsistentHashing consistentHashing;

    public DistributedFileSystem(List<String> nodes, int replicationFactor) {
        this.metadataServer = new MetadataServer();
        this.replicationManager = new ReplicationManager(replicationFactor);
        this.consistentHashing = new ConsistentHashing(nodes, replicationFactor);
    }

    public void storeFile(String fileName, byte[] data) {
        List<FileChunk> chunks = splitFile(fileName, data);
        List<String> chunkIds = new ArrayList<>();

        for (FileChunk chunk : chunks) {
            String node = consistentHashing.getNode(chunk.getChunkId());
            List<String> replicas = replicationManager.replicate(chunk.getChunkId(), Collections.singletonList(node));
            chunkIds.add(chunk.getChunkId());
            // Store chunk on node and replicas (simulate with a print statement)
            System.out.println("Storing chunk " + chunk.getChunkId() + " on nodes: " + replicas);
        }

        metadataServer.addFile(fileName, chunkIds);
    }

    public void retrieveFile(String fileName) {
        List<String> chunkIds = metadataServer.getChunks(fileName);
        for (String chunkId : chunkIds) {
            String node = consistentHashing.getNode(chunkId);
            // Simulate retrieval
            System.out.println("Retrieving chunk " + chunkId + " from node: " + node);
        }
    }

    private List<FileChunk> splitFile(String fileName, byte[] data) {
        List<FileChunk> chunks = new ArrayList<>();
        int chunkSize = 64 * 1024 * 1024; // 64 MB

        for (int i = 0; i < data.length; i += chunkSize) {
            int end = Math.min(data.length, i + chunkSize);
            byte[] chunkData = Arrays.copyOfRange(data, i, end);
            String chunkId = fileName + "_chunk_" + (i / chunkSize);
            chunks.add(new FileChunk(chunkId, chunkData));
        }

        return chunks;
    }

    public static void main(String[] args) {
        List<String> nodes = Arrays.asList("Node1", "Node2", "Node3");
        DistributedFileSystem dfs = new DistributedFileSystem(nodes, 3);

        byte[] fileData = new byte[128 * 1024 * 1024]; // 128 MB dummy file
        dfs.storeFile("myFile", fileData);
        dfs.retrieveFile("myFile");
    }
}

Advanced Features

  • Compression and Encryption: Compress and encrypt file chunks before storage.

  • Versioning: Maintain versions of files for recovery and auditing.

  • Monitoring: Use monitoring tools to track system health and usage.

Summary

Designing a distributed file system involves understanding distributed systems' core principles, including data partitioning, consistency, and fault tolerance. We can create a robust and efficient DFS suitable for large-scale applications by implementing the above concepts in Java.

Please stay tune, I will update Point 3 of FANNG Interview series, Please check top 10 interview questions here.

1. Designing a URL Shortener in Java: FAANG Interviews

 

Designing a URL shortener is a classic system design problem that combines data structures, algorithms, and scalability considerations. In this article, we will explore how to design and implement a URL shortener in Java.

Requirements for a URL Shortener

Functional Requirements:

  • Generate a short and unique URL for a given long URL.

  • Redirect users from the short URL to the original long URL.

Non-Functional Requirements:

  • Handle millions of URL mappings efficiently.

  • Minimize latency in URL resolution.

  • Ensure high availability and scalability.

Key Concepts

1. Data Structures

To map long URLs to short URLs efficiently, we use a HashMap:

  • Key: The short URL identifier.

  • Value: The original long URL.

Map<String, String> urlMap = new HashMap<>();

2. Collision Resolution Strategies

We need a strategy to generate unique identifiers to avoid collisions:

  • Base62 Encoding: Use alphanumeric characters ([a-zA-Z0-9]) to encode unique IDs.

    public String encode(int id) {
    String chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    StringBuilder sb = new StringBuilder();
    while (id > 0) {
        sb.append(chars.charAt(id % 62));
        id /= 62;
    }
    return sb.reverse().toString();
}

  • Hashing: Use a hashing algorithm like MD5 or SHA-256 to generate a hash of the long URL, and take a subset of the hash to create the short URL.

    public String generateHash(String url) throws NoSuchAlgorithmException {
    MessageDigest md = MessageDigest.getInstance("SHA-256");
    byte[] hash = md.digest(url.getBytes(StandardCharsets.UTF_8));
    return Base64.getUrlEncoder().withoutPadding().encodeToString(hash).substring(0, 8);
}

3. Scalability and Performance Considerations

  • Load Balancing: Distribute traffic among multiple servers to ensure high availability.

  • Horizontal Scaling: Add more servers for data storage and request handling.

  • Sharding: Partition data based on the first few characters of the short URL.

4. Database Design

For storing mappings between long and short URLs, a relational database schema might look like this:

ColumnData TypeDescription
id  BIGINT   Primary key, auto-increment
short_url  VARCHAR(10)  Unique short URL identifier
long_url  TEXT  Original long URL
created_at TIMESTAMP  Timestamp for creation

Indexes on

short_url
and
long_url
 will optimize lookups.

Alternatively, use NoSQL databases like MongoDB for scalability:

{
  "short_url": "abc123",
  "long_url": "https://example.com/very/long/url",
  "created_at": "2025-01-01T12:00:00Z"
}

5. Cache Management

Use caching to speed up lookups for frequently accessed short URLs:

  • Use Redis or Memcached.

  • Implement a Time-to-Live (TTL) to manage cache expiration.

import redis.clients.jedis.Jedis;
Jedis jedis = new Jedis("localhost");
jedis.set("abc123", "https://example.com/very/long/url");

Implementation in Java

URL Shortening Service

import java.util.*;

public class URLShortener {
    private Map&lt;String, String&gt; urlMap;
    private Map&lt;String, String&gt; reverseMap;
    private static final String DOMAIN = "https://short.ly/";
    private static final String CHARSET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int BASE = 62;

    public URLShortener() {
        urlMap = new HashMap&lt;&gt;();
        reverseMap = new HashMap&lt;&gt;();
    }

    public String shortenURL(String longUrl) {
        if (reverseMap.containsKey(longUrl)) {
            return DOMAIN + reverseMap.get(longUrl);
        }
        String shortUrl = generateShortUrl();
        urlMap.put(shortUrl, longUrl);
        reverseMap.put(longUrl, shortUrl);
        return DOMAIN + shortUrl;
    }

    public String expandURL(String shortUrl) {
        String key = shortUrl.replace(DOMAIN, "");
        return urlMap.getOrDefault(key, "URL not found");
    }

    private String generateShortUrl() {
        Random random = new Random();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            sb.append(CHARSET.charAt(random.nextInt(BASE)));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        URLShortener shortener = new URLShortener();
        String shortUrl = shortener.shortenURL("https://example.com/very/long/url");
        System.out.println("Short URL: " + shortUrl);
        System.out.println("Original URL: " + shortener.expandURL(shortUrl));
    }
}

Advanced Features

  • Custom Short URLs: Allow users to define their custom alias.

  • Analytics: Track click counts and geographical data.

  • Expiration: Set expiration for short URLs.

Conclusion

By leveraging the above strategies, you can design a scalable and efficient URL shortener in Java. This problem demonstrates the importance of data structures, hashing, database design, and performance optimization.

Please stay tune, I will update Point 2 of FANNG Interview series, Please check top 10 interview questions here.