Flipkart

PART 1: ALGORITHMIC PROBLEM - RATE LIMITING ALGORITHMS BASE PROBLEM You are implementing the core logic for a server-side API rate limiter to protect your endpoints from being overwhelmed by bursts of traffic. Task: Design a class RateLimiter that initializes with a max request count L and a time window W in milliseconds. Implement a method isAllowed(clientId, timestamp) that returns a boolean indicating whether the current request from clientId should be processed or dropped. What data structures will you use to achieve O(1) time complexity per request while preventing memory leaks from stale timestamps? FOLLOW-UP 1 The basic sliding window log approach stores every single timestamp, which consumes too much memory for high-traffic clients. How can you optimize the space complexity by transitioning to a Sliding Window Counter or Token Bucket algorithm, and what accuracy trade-offs do these optimizations introduce? FOLLOW-UP 2 Different users now have different API tiers (e.g., Free users get 10 requests/minute, Premium users get 1000 requests/minute). Furthermore, certain expensive endpoints require their own independent limits. How do you redesign your internal state to support configurable rate limits per client per endpoint? PART 2: SYSTEM DESIGN - DISTRIBUTED RATE LIMITER BASE PROBLEM Your single-server API has grown into a globally distributed microservices architecture. The rate limit must now be enforced across hundreds of independent application servers. Design a distributed rate limiting system. FOLLOW-UP 1 If you use a centralized datastore (like Redis) to track request counts across servers, you introduce network latency and potential race conditions. How do you handle concurrency (e.g., utilizing atomic operations or Lua scripts) to prevent race conditions when multiple servers increment the same client's counter simultaneously? FOLLOW-UP 2 The centralized Redis cluster goes down. Your system must decide whether to fail-open (let all traffic through) or fail-closed (reject all traffic). Discuss the trade-offs of both approaches. How would you implement a local fallback mechanism with adjusted limits and a circuit breaker pattern to keep the API functional without melting your backend? PART 3: AI / LLM DISCUSSION QUESTIONS What is LLM System Design and why is it important? LLM System Design refers to the end-to-end architecture for deploying large language models in production. It is important because it covers the critical infrastructure, optimizes inference pipelines for latency reduction, manages integration with tools, and handles scalability for high traffic. How do you optimize LLM inference for efficiency? A primary technique is Quantization, which reduces model weights from 32-bit floats to smaller formats like 8-bit integers. This yields faster inference and significantly lower memory requirements, though it introduces a slight accuracy drop on benchmarks. What are key Non-Functional Requirements (NFRs) for an LLM system? Two primary NFRs are latency and cost. For real-time applications like chat, latency must typically be kept under one second. Cost optimization involves selecting model sizes proportional to task complexity, such as routing simpler tasks to cheaper models. How do you handle LLM limitations like hallucinations in a production system? Hallucinations can be mitigated through Retrieval-Augmented Generation (RAG) to ground answers in factual data, appending disclaimers during post-processing, and maintaining audit logs for sensitive queries.