Machine Coding Problem

Pastebin (LLD)

macoAllweb-servicesttlbase62-encoding
Commonly Asked By:GoogleDropboxAmazon

Functional Scope (In-Scope)

  • Monotonic Base62 Shortening Key Engine: Translates unique numeric IDs to a 7-character alphanumeric string.
  • Dynamic TTL & Expiry Controller: Ensures expiration limits are fully validated on read operations, rejecting accesses to out-of-date pastes.
  • Content Hash Deduplicator: Evaluates identical raw pastes dynamically using SHA-256 to reuse short keys.
  • Visibility Configurations: Restricts permissions cleanly across Public, Private, and Unlisted access lists.

Explicit Boundaries (Out-of-Scope)

  • Physical Web Frontend Content Renderers: Omits syntax highlight libraries, text layout widgets, and browser extensions.
  • Direct DNS Server Route Registries: Skips concrete reverse proxy routing setups, load balancers, and CDN networks.

Production reference implementations demonstrating content deduplication, Base62 encoders, and lazy evictions in Java and Python:

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantReadWriteLock;

enum Visibility {
    PUBLIC, PRIVATE, UNLISTED
}

class Paste {
    private final long id;
    private final String shortKey;
    private final String content;
    private final String creatorId;
    private final long expiryTimeMs; // -1 if never expires
    private final Visibility visibility;
    private final long creationTimeMs;

    public Paste(long id, String shortKey, String content, String creatorId, long expiryTimeMs, Visibility visibility, long creationTimeMs) {
        this.id = id;
        this.shortKey = shortKey;
        this.content = content;
        this.creatorId = creatorId;
        this.expiryTimeMs = expiryTimeMs;
        this.visibility = visibility;
        this.creationTimeMs = creationTimeMs;
    }

    public long getId() { return id; }
    public String getShortKey() { return shortKey; }
    public String getContent() { return content; }
    public String getCreatorId() { return creatorId; }
    public long getExpiryTimeMs() { return expiryTimeMs; }
    public Visibility getVisibility() { return visibility; }
    public long getCreationTimeMs() { return creationTimeMs; }

    public boolean isExpired(long now) {
        return expiryTimeMs != -1 && now > expiryTimeMs;
    }
}

class Base62Encoder {
    private static final String BASE62_CHARACTERS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public static String encode(long value) {
        StringBuilder sb = new StringBuilder();
        while (value > 0) {
            int remainder = (int) (value % 62);
            sb.append(BASE62_CHARACTERS.charAt(remainder));
            value /= 62;
        }
        while (sb.length() < 7) {
            sb.append('0'); // Pad to 7 characters
        }
        return sb.reverse().toString();
    }

    public static long decode(String shortKey) {
        long value = 0;
        for (int i = 0; i < shortKey.length(); i++) {
            char c = shortKey.charAt(i);
            int index = BASE62_CHARACTERS.indexOf(c);
            if (index == -1) continue;
            value = value * 62 + index;
        }
        return value;
    }
}

class PasteService {
    private final Map<String, Paste> pasteStore = new HashMap<>();
    private final Map<String, String> contentHashToKey = new HashMap<>(); // Deduplication
    private final AtomicLong globalIdGenerator = new AtomicLong(1000000000L); // High seed for 7 chars
    private final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final ScheduledExecutorService sweeperExecutor = Executors.newSingleThreadScheduledExecutor();

    public PasteService() {
        // Start background Expiry sweep task
        sweeperExecutor.scheduleAtFixedRate(this::purgeExpiredPastes, 30, 30, TimeUnit.SECONDS);
    }

    public String createPaste(String content, String creatorId, long ttlSeconds, Visibility visibility) {
        long now = System.currentTimeMillis();
        long expiryTimeMs = ttlSeconds > 0 ? now + (ttlSeconds * 1000L) : -1L;
        String contentHash = computeSHA256(content);

        rwLock.writeLock().lock();
        try {
            // Content Deduplication logic using SHA-256
            String existingKey = contentHashToKey.get(contentHash);
            if (existingKey != null) {
                Paste existingPaste = pasteStore.get(existingKey);
                if (existingPaste != null && !existingPaste.isExpired(now) 
                    && Objects.equals(existingPaste.getCreatorId(), creatorId) 
                    && existingPaste.getVisibility() == visibility) {
                    return existingPaste.getShortKey(); // Reuse key
                }
            }

            // Create new paste
            long uniqueId = globalIdGenerator.incrementAndGet();
            String shortKey = Base62Encoder.encode(uniqueId);

            Paste paste = new Paste(uniqueId, shortKey, content, creatorId, expiryTimeMs, visibility, now);
            pasteStore.put(shortKey, paste);
            contentHashToKey.put(contentHash, shortKey);

            return shortKey;
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    // Lazy Expiry check on read
    public Paste getPaste(String shortKey) {
        long now = System.currentTimeMillis();
        
        rwLock.readLock().lock();
        try {
            Paste paste = pasteStore.get(shortKey);
            if (paste == null) return null;
            if (!paste.isExpired(now)) {
                return paste;
            }
        } finally {
            rwLock.readLock().unlock();
        }

        // Handle expired paste under write lock (lazy eviction)
        rwLock.writeLock().lock();
        try {
            Paste paste = pasteStore.get(shortKey);
            if (paste != null && paste.isExpired(now)) {
                pasteStore.remove(shortKey);
                String contentHash = computeSHA256(paste.getContent());
                contentHashToKey.remove(contentHash);
                return null;
            }
            return paste;
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    public void deletePaste(String shortKey, String requesterId) {
        rwLock.writeLock().lock();
        try {
            Paste paste = pasteStore.get(shortKey);
            if (paste != null) {
                if (paste.getCreatorId() != null && !paste.getCreatorId().equals(requesterId)) {
                    throw new IllegalStateException("Only creator can delete this paste.");
                }
                pasteStore.remove(shortKey);
                String contentHash = computeSHA256(paste.getContent());
                contentHashToKey.remove(contentHash);
            }
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    public void purgeExpiredPastes() {
        long now = System.currentTimeMillis();
        rwLock.writeLock().lock();
        try {
            List<String> toRemove = new ArrayList<>();
            pasteStore.forEach((key, paste) -> {
                if (paste.isExpired(now)) {
                    toRemove.add(key);
                }
            });
            for (String key : toRemove) {
                Paste p = pasteStore.remove(key);
                if (p != null) {
                    contentHashToKey.remove(computeSHA256(p.getContent()));
                }
            }
            if (!toRemove.isEmpty()) {
                System.out.println("[Sweeper] Purged " + toRemove.size() + " expired pastes.");
            }
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    private String computeSHA256(String content) {
        try {
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] hash = digest.digest(content.getBytes(StandardCharsets.UTF_8));
            StringBuilder hexString = new StringBuilder();
            for (byte b : hash) {
                String hex = Integer.toHexString(0xff & b);
                if (hex.length() == 1) hexString.append('0');
                hexString.append(hex);
            }
            return hexString.toString();
        } catch (Exception e) {
            throw new RuntimeException("SHA-256 failed", e);
        }
    }

    public void shutdown() {
        sweeperExecutor.shutdown();
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        System.out.println("=== JAVA PASTEBIN SYSTEM DEMO ===");
        PasteService pasteService = new PasteService();
        
        // 1. Create standard paste
        String key1 = pasteService.createPaste("Hello World from Java Blueprint!", "alice", -1, Visibility.PUBLIC);
        System.out.println("Created paste 1. Short key: " + key1);
        
        // 2. Fetch paste 1
        Paste p1 = pasteService.getPaste(key1);
        System.out.println("Fetched paste 1: '" + p1.getContent() + "' [Creator: " + p1.getCreatorId() + "]");
        
        // 3. Deduplication Check
        String key2 = pasteService.createPaste("Hello World from Java Blueprint!", "alice", -1, Visibility.PUBLIC);
        System.out.println("Created duplicate paste. Reused key: " + key2 + " (Matches key1: " + key1.equals(key2) + ")");
        
        // 4. Temporary paste with short TTL (1 second)
        String key3 = pasteService.createPaste("Highly confidential ephemeral credentials", "bob", 1, Visibility.PRIVATE);
        System.out.println("Created TTL paste with key: " + key3);
        System.out.println("Immediate fetch: " + (pasteService.getPaste(key3) != null ? "Found" : "Expired"));
        
        System.out.println("Sleeping for 1.2 seconds to allow TTL expiration...");
        Thread.sleep(1200);
        System.out.println("Post-sleep fetch: " + (pasteService.getPaste(key3) != null ? "Found" : "Expired/Not Found"));
        
        // 5. Delete authorization test
        try {
            System.out.println("Attempting unauthorized deletion of Alice's paste by Bob...");
            pasteService.deletePaste(key1, "bob");
        } catch (Exception e) {
            System.out.println("Deletion failed as expected: " + e.getMessage());
        }
        
        pasteService.deletePaste(key1, "alice");
        System.out.println("Alice's paste deleted successfully. Try fetching: " + (pasteService.getPaste(key1) != null ? "Found" : "Not Found"));
        
        // 6. High concurrency simulation
        System.out.println("Spawning concurrent threads to write pastes simultaneously...");
        ExecutorService executor = Executors.newFixedThreadPool(5);
        List<Future<String>> futures = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            final int index = i;
            futures.add(executor.submit(() -> pasteService.createPaste("Unique payload #" + index, "user_" + index, 10, Visibility.PUBLIC)));
        }
        
        for (int i = 0; i < futures.size(); i++) {
            System.out.println("Thread " + i + " generated key: " + futures.get(i).get());
        }
        
        executor.shutdown();
        pasteService.shutdown();
        System.out.println("=== END OF JAVA DEMO ===");
    }
}