Flipkart Interview Questions

Prepare for success with our curated collection of interview questions. Designed to help students practice and build confidence, these questions cover a range of topics and real-world scenarios to get you ready for your next interview.
  • DSA
  • LLD
  • HLD
Q1: Maximum Frequency Stack (FreqStack)

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack. The FreqStack class should support push(int val) which pushes an integer val onto the top of the stack, and pop() which removes and returns the most frequent element. If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned. This problem tests knowledge of hash maps, frequency tracking, and stack operations combined. The optimal solution requires two hash maps: one tracking element frequencies and another maintaining stacks of elements at each frequency level. When pushing an element, increment its frequency and add it to the stack at that frequency level. When popping, remove from the highest frequency stack and decrement that element’s frequency. Both operations achieve O(1) time complexity with this design. This data structure is useful in scenarios requiring priority-based element retrieval with recency as a tiebreaker, such as cache replacement policies or event processing systems.

 

Example:

Input: [“FreqStack”,”push”,”push”,”push”,”push”,”push”,”push”,”pop”,”pop”,”pop”,”pop”]

[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]

Output: [null,null,null,null,null,null,null,5,7,5,4]

Explanation: After pushes, frequency of 5 is 3, frequency of 7 is 2, frequency of 4 is 1. Pop returns 5 (highest freq), then 7 (remaining), then 5 again, then 4.

Description: You have a set which contains all positive integers [1, 2, 3, 4, 5, …]. Implement the SmallestInfiniteSet class with three methods: SmallestInfiniteSet() initializes the object to contain all positive integers, int popSmallest() removes and returns the smallest integer contained in the infinite set, and void addBack(int num) adds a positive integer num back into the infinite set if it is not already in the set. This problem tests understanding of data structures for maintaining ordered elements and set operations. The efficient approach uses a min heap to track added-back numbers and a variable to track the current smallest unpopped number. When popping, if the heap is not empty and its minimum is less than the current smallest, pop from heap; otherwise return and increment the current smallest. When adding back, only add to heap if the number is less than current smallest. Time complexity is O(log n) for both operations where n is the number of added-back elements. This type of data structure is useful in resource allocation systems where resources need to be recycled and reassigned efficiently.

 

Example:

 

Input: [“SmallestInfiniteSet”,”addBack”,”popSmallest”,”popSmallest”,”popSmallest”,”addBack”,”popSmallest”,”popSmallest”,”popSmallest”]

[[],[2],[],[],[],[1],[],[],[]]

 

Output: [null,null,1,2,3,null,1,4,5]

 

Explanation: Initially set contains all positive integers. addBack(2) does nothing since 2 is already there. popSmallest() returns 1, 2, 3 in sequence. addBack(1) adds 1 back. Then popSmallest() returns 1, 4, 5.

Description: Given a positive integer n such that n > 2, divide numbers from 1 to n into k groups such that the absolute difference of sum of each group is minimum. Print the k groups with their elements. This problem extends the classic partition problem to multiple groups and tests greedy algorithms and priority queue usage. The approach involves calculating the total sum and target sum per group, then using a priority queue (min heap) to track group sums. Start by adding the largest numbers to the smallest-sum groups iteratively. Use a min heap where each element is (current_sum, group_index). For each number from n down to 1, pop the group with minimum sum, add the number to that group, and push back with updated sum. This greedy approach ensures balanced distribution. Time complexity is O(N * LogK) where N is the number of elements and K is the number of groups. The solution works because adding larger numbers first to smaller groups tends to balance the distribution. This type of problem appears in load balancing scenarios, task distribution among workers, or resource allocation systems.

 

Example:

Input: n = 10, k = 3

Output: [[10, 1], [9, 2], [8, 3, 4, 5, 6, 7]]

Explanation: Sum of group 1: 11, Sum of group 2: 11, Sum of group 3: 33. The algorithm tries to minimize the difference between maximum and minimum group sums.

Given an array of integers representing the processing times of n tasks, calculate the minimum idle time when processing tasks in optimal order. After processing each task, the idle time at that moment is defined as: max(processing time so far) – min(processing time so far). The total idle time is the sum of idle times after processing each task. Find the arrangement that minimizes the total idle time. This problem tests understanding of greedy algorithms and sorting techniques. The key insight is that sorting the array and processing from the middle outward minimizes the cumulative difference between max and min. Use two pointers starting from the middle: one moving left, one moving right. Process elements alternately from middle to edges. This approach keeps the max-min difference growing slowly. Time complexity is O(N log N) for sorting plus O(N) for processing. Alternative approach: sort and process in order that maintains smallest possible range at each step. This problem relates to real-world scheduling scenarios where system idle time or waiting time needs optimization, such as CPU task scheduling or manufacturing process planning.

 

Example:

Input: [1, 2, 2, 2, 3, 3]

Output: 4

Explanation: Process as [2], [2, 2], [2, 2, 2], [2, 2, 2, 3], [2, 2, 2, 3, 3], [1, 2, 2, 2, 3, 3]. Idle times are 0, 0, 0, 1, 1, 2, totaling 4.

Description: Given a binary tree where each node is assigned a value, find the number of uniquely rooted subtrees. Two rooted subtrees are considered the same if they have the same structure and the same node values at corresponding positions. This problem tests tree traversal, serialization techniques, and hash

ing with sets. The solution uses post-order tree traversal combined with serialization. For each node, recursively get serialized strings of left and right subtrees, then create a serialized string for the current subtree by combining node value with left and right serializations using a delimiter. Store each serialization in a hash map, counting occurrences. The number of unique subtrees is the size of the hash map. Time complexity is O(N^2) in worst case due to string operations, but can be optimized to O(N) using hashing techniques. This problem is relevant to pattern recognition in tree structures, duplicate detection in hierarchical data, and compiler optimization where similar expression trees need to be identified.

 

Example:

Input: Tree with nodes [1,2,3,2,3,null,null,null,null]

Output: 5

Explanation: Subtree [null], [3], [2,null,null], [2,3,null], and [1,2,3,2,3] are unique. Count is 5.

Description: Given a complete binary tree, find the rightmost leaf node in the last level. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. This problem tests understanding of binary tree properties, level order traversal, and binary search techniques. The optimal solution leverages the properties of complete binary trees using binary search on tree levels. Calculate tree height in O(log N) by going left. Then use binary search on the last level to find the rightmost node. For each mid position, check if node exists by traversing from root using the binary representation of the position. Time complexity is O((log N)^2) which is better than O(N) level order traversal. This technique is useful in scenarios involving heap implementations, perfect binary tree manipulations, or any system where complete binary trees are used for efficient storage and retrieval.

 

Example:

Input: Complete binary tree [1,2,3,4,5,6,7,8,9]

Output: 9

Explanation: The last level has nodes 8, 9. The rightmost is 9.

Description: Given an unsorted integer array nums, find the smallest missing positive integer. The algorithm must run in O(N) time and use O(1) auxiliary space. This classic problem tests array manipulation and in-place algorithm design. The key insight is to use the array itself as a hash table. Iterate through the array and place each positive integer x at index x-1 if it’s within range [1, N]. After rearrangement, iterate again to find the first index where nums[i] != i+1, that index+1 is the answer. If all positions are correct, answer is N+1. The algorithm handles duplicates and out-of-range values correctly. This problem relates to resource allocation where you need to find the first available resource ID, memory management, or process ID assignment in operating systems where gaps need to be filled efficiently.

 

Example:

Input: [3,4,-1,1]

Output: 2

Explanation: After rearrangement [1,-1,3,4], index 1 has -1 instead of 2, so answer is 2.

Description: Given a list of words, return a Map/Dictionary of words which can be formed by concatenating other words that exist in the same list. For each compound word, provide all possible ways it can be formed from the dictionary words. This problem tests dynamic programming, trie data structures, and backtracking. The solution involves building a trie from all words for efficient prefix checking. For each word, use dynamic programming to check if it can be formed from other words. Use a DP array where dp[i] indicates if substring [0…i] can be formed from dictionary words. During DP computation, track which words form each position for reconstruction. Backtrack to find all possible formations. Time complexity is O(N * L^2) where N is number of words and L is average length. This problem applies to text compression, compound word detection in natural language processing, and search query optimization.

 

Example:

Input: [“happy”, “rise”, “for”, “set”, “sunrise”,”sun”, “su”, “nset”, “sunset”, “mind”, “happymind”]

Output: {“happymind”: [[“happy”, “mind”]], “sunrise”: [[“su”, “n”, “rise”], [“sun”, “rise”]]}

Description: There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi before course ai. Return the ordering of courses you should take to finish all courses. If there are multiple valid answers, return any of them. If it’s impossible to finish all courses, return an empty array. This problem tests graph theory, specifically topological sorting using either DFS or BFS (Kahn’s algorithm). The BFS approach uses in-degree counting: calculate in-degree for each node, add zero in-degree nodes to queue, process queue by removing nodes and decrementing neighbors’ in-degrees, adding new zero in-degree nodes. If all nodes are processed, valid topological order exists. Time complexity is O(V + E). DFS approach uses colors to detect cycles and post-order traversal for ordering. This problem models dependency resolution in build systems, task scheduling with prerequisites, or package installation order determination.

 

Example:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [0,1,2,3] or [0,2,1,3]

Explanation: Course 0 has no prerequisites, can be taken first. Then courses 1 and 2 depend on 0. Course 3 depends on both 1 and 2.

Description: Design a stack which supports push, pop, and an operation to increment the bottom k elements of the stack by a given value. Implement the CustomStack class with CustomStack(int maxSize) to initialize with maximum size, void push(int x) to add x to top if stack hasn’t reached maxSize, int pop() to remove and return top element or -1 if empty, and void increment(int k, int val) to increment bottom k elements (or all if k > stack size) by val. The naive O(K) increment is inefficient. Optimal solution uses lazy propagation: maintain an auxiliary array to store pending increments. When incrementing k elements, add val to inc[k-1]. When popping, add pending increment to result and propagate to element below. This achieves O(1) for all operations. Time complexity: O(1) for push, pop, increment. Space complexity: O(N). Useful in scenarios requiring bulk updates, undo-redo systems, or managing configurations with hierarchical modifications.

 

Example:

Input: [“CustomStack”,”push”,”push”,”pop”,”push”,”push”,”push”,”increment”,”increment”,”pop”,”pop”,”pop”,”pop”]

[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

Output: [null,null,null,2,null,null,null,null,null,103,202,201,-1]

Description: There is a car with capacity empty seats. The vehicle only drives east (one direction). You are given an array trips where trips[i] = [numPassengers, from, to] indicates that the ith trip has numPassengers passengers and they will travel from location from to location to. Return true if it is possible to pick up and drop off all passengers for all trips, otherwise false. This problem tests event-based simulation and efficient data structure usage. Solution approaches include: (1) Using difference array technique where pickup locations add passengers and dropoff locations subtract them, then check if any accumulated sum exceeds capacity. (2) Using priority queue/min heap to track ongoing trips sorted by dropoff location, processing pickup/dropoff events in order. Time complexity is O(N log N) for sorting events. This problem models real-world ride-sharing optimization, bus route capacity planning, or elevator scheduling systems.

 

Example:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4

Output: false

Explanation: At location 3, we have 2 passengers from trip 1 and pick up 3 from trip 2, total 5 exceeds capacity 4.

Description: On a horizontal number line, we have gas stations at positions stations[0], stations[1], …, stations[N-1] where N = stations.length. You can add K more gas stations anywhere on the number line. Return the smallest possible value of D such that the maximum distance between adjacent gas stations is at most D. The answer should be accurate within 10^-6. This problem tests binary search on answer space and greedy validation. The approach is to binary search on the maximum distance D. For each candidate D, check if K stations suffice by calculating required stations between each adjacent pair (distance/D – 1). If total required stations <= K, D is achievable. Search in range [0, max_gap]. Time complexity is O(N log(max_gap/precision)). This problem relates to facility location optimization, resource distribution problems, or network coverage planning where uniform service quality is desired.

 

Example:

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9

Output: 0.500000

Explanation: By adding 9 stations, we can make the max distance 0.5.

Description: The main road in a city is a straight line from south to north with coordinates measured in meters. There are n friends standing at different points on the road. The i-th friend is at position xi meters and can move with speed up to vi meters per second in either direction. Find the minimum time needed to gather all n friends at some meeting point on the road. The meeting point doesn’t need to have integer coordinates. This problem combines binary search on answer with greedy validation. Binary search on the time T, and for each T, check if there’s a valid meeting point. For each friend, calculate the range [xi – vi*T, xi + vi*T] they can reach in time T. The valid meeting points are the intersection of all ranges. If intersection is non-empty, T is sufficient. Time complexity is O(N log(max_distance/precision)). This problem models scenarios like emergency response coordination, drone delivery optimization, or any situation requiring efficient spatial convergence of multiple moving entities with different capabilities.

 

Example:

Input: positions = [1, 2, 3], speeds = [1, 1, 1]

Output: 1.0

Explanation: All three can meet at position 2 in 1 second.

Description: Find the length of the longest strictly increasing subsequence in an array. This classic dynamic programming problem tests understanding of DP state definition and optimization. The O(N^2) approach uses dp[i] representing LIS ending at index i. For each position, check all previous elements and update if current is greater. The optimal O(N log N) solution uses binary search with a tails array where tails[i] stores the smallest tail element for LIS of length i+1. For each element, binary search to find position and update. Applications include version control systems, data compression, and bioinformatics for DNA sequence analysis.

Example: [10,9,2,5,3,7,101,18] → Output: 4 (subsequence [2,3,7,101])

Description: Merge k sorted linked lists into one sorted list. This problem tests heap data structures and understanding of time complexity optimization. Naive approach of merging lists pairwise takes O(kN) time. Optimal solution uses min-heap of size k, maintaining one node from each list. Extract minimum, add to result, push next node from same list. Time O(N log k) where N is total nodes. Space O(k) for heap. Variations include merging k sorted arrays and external sorting. Real-world applications in database query optimization, distributed system data aggregation, and log file merging from multiple servers.

Example: [[1,4,5],[1,3,4],[2,6]] → Output: [1,1,2,3,4,4,5,6]

Description: Given elevation map where width of each bar is 1, compute how much water can be trapped after raining. Tests understanding of two-pointer technique and prefix/suffix arrays. Key insight: water level at position i equals min(max_left[i], max_right[i]) – height[i]. Three solutions: (1) Precompute left and right max arrays O(N) space, (2) Two pointers from both ends O(1) space, (3) Stack-based monotonic decreasing stack. Applications in terrain analysis, water resource management, and similar problems like container with most water.

Example: [0,1,0,2,1,0,1,3,2,1,2,1] → Output: 6 (water trapped in valleys)

Description: Design algorithm to serialize binary tree to string and deserialize string back to tree structure. Tests tree traversal, string parsing, and design skills. Use pre-order traversal with null markers (e.g., “#”). Serialization builds string recursively: root value, serialize left, serialize right. Deserialization uses queue/index to track position, recursively builds tree. Handle edge cases: empty tree, single node, skewed trees. Applications in data persistence, network transmission of tree structures, and caching complex data structures. Alternative approaches use level-order traversal or custom encoding schemes.

Example: Tree [1,2,3,null,null,4,5] → “1,2,#,#,3,4,#,#,5,#,#” → Reconstructed tree

Description: Given begin word, end word, and dictionary, find all shortest transformation sequences where each transformed word must exist in dictionary and differs by exactly one letter. Tests BFS for shortest path, backtracking for path reconstruction, and graph modeling. Use BFS to find shortest distance to each word, track predecessors. Then use DFS/backtracking from endWord to construct all paths. Optimization: bidirectional BFS. Time complexity O(N*M^2) where N is dictionary size, M is word length. Applications in spell checkers, word games, natural language processing, and mutation analysis in genetics.

Example: beginWord=”hit”, endWord=”cog”, wordList=[“hot”,”dot”,”dog”,”lot”,”log”,”cog”] → [[“hit”,”hot”,”dot”,”dog”,”cog”],[“hit”,”hot”,”lot”,”log”,”cog”]]

Description: Given array and sliding window of size k, find maximum in each window position. Tests monotonic deque data structure. Maintain deque of indices in decreasing order of values. For each position, remove indices outside window, remove smaller elements from back, add current index, front element is maximum. Time O(N), space O(k). Naive approach O(NK) using max search per window. Applications in time-series analysis, stock price monitoring, real-time data stream processing, and network traffic analysis.

Example: nums=[1,3,-1,-3,5,3,6,7], k=3 → Output:[3,3,5,5,6,7]

Description: Given string, partition it such that every substring is a palindrome, return all possible partitions. Tests backtracking, dynamic programming for palindrome checking, and recursion. Precompute palindrome status using DP table. Use backtracking: try all possible cuts, recursively partition remaining string. Optimization: memorize results for substrings. Time complexity O(N*2^N) worst case. Applications in text processing, DNA sequence analysis, pattern recognition, and string compression algorithms. Extension: minimum cuts needed for palindrome partitioning uses DP.

Example: “aab” → [[“a”,”a”,”b”],[“aa”,”b”]]

Description: Implement regular expression matching with ‘.’ matching any single character and ‘*’ matching zero or more of preceding element. Tests dynamic programming and string matching algorithms. Define dp[i][j] as whether s[0..i-1] matches p[0..j-1]. Handle cases: exact match, ‘.’, ‘*’ with zero match, ‘*’ with one or more matches. Time O(MN) space O(MN). Applications in text editors, search engines, input validation, log parsing, and compiler design for lexical analysis.

Example: s=”aa”, p=”a*” → true; s=”ab”, p=”.*” → true



Description: Find median of two sorted arrays in O(log(min(m,n))) time. Tests binary search on answer space and understanding of partitioning. Use binary search on smaller array to find partition point where left elements of both arrays ≤ right elements. Check conditions: maxLeft1 ≤ minRight2 and maxLeft2 ≤ minRight1. Median is average of max(maxLeft1, maxLeft2) and min(minRight1, minRight2) for even total length. Applications in statistics, data analysis, and database query optimization for distributed sorted data.

Example: nums1=[1,3], nums2=[2] → 2.0; nums1=[1,2], nums2=[3,4] → 2.5

Description: Find length of longest valid parentheses substring. Tests stack-based algorithms and dynamic programming. Three approaches: (1) Stack storing indices, push -1 initially and ‘(‘ indices, calculate length when ‘)’ found. (2) DP where dp[i] represents length ending at i. (3) Two-pass scan left-to-right and right-to-left counting. Time O(N), space O(N) or O(1). Applications in compiler design for expression parsing, code editors for bracket matching, and HTML/XML validation.

Example: “(()” → 2; “)()())” → 4

Description: Implement wildcard pattern matching with ‘?’ matching any single character and ‘*’ matching any sequence (including empty). Tests dynamic programming and greedy algorithms. DP approach: dp[i][j] represents if s[0..i-1] matches p[0..j-1]. Handle ‘*’ by trying empty match and one or more character matches. Greedy optimization uses backtracking with star positions. Time O(MN), space can be optimized to O(N). Applications in file system glob patterns, search functionality, and URL routing systems.

Example: s=”adceb”, p=”*a*b” → true; s=”acdcb”, p=”a*c?b” → false

Description: Find minimum operations (insert, delete, replace) to convert one string to another. Classic DP problem testing optimal substructure. Define dp[i][j] as edit distance between first i characters of word1 and first j characters of word2. Recurrence: if chars match, dp[i][j]=dp[i-1][j-1]; else min(insert, delete, replace) + 1. Time O(MN), space O(MN) optimizable to O(N). Applications in spell checkers, DNA sequence alignment, plagiarism detection, and fuzzy string matching in search engines.

Example: word1=”horse”, word2=”ros” → 3 (replace h→r, remove o, remove e)

Description: Given n balloons with coins, burst balloons to maximize coins where coins gained = nums[left]*nums[i]*nums[right]. Tests interval DP and thinking in reverse. Key insight: instead of which balloon to burst first, think which to burst last. Add virtual balloons with value 1 at boundaries. Define dp[i][j] as max coins bursting balloons between i and j. Try each balloon k as last burst in range. Time O(N^3), space O(N^2). Applications in optimization problems, resource allocation, and game theory.

Example: [3,1,5,8] → 167

Description: Find contiguous subarray with maximum sum. Tests understanding of greedy algorithms and dynamic programming equivalence. Kadane’s algorithm maintains running sum, resets to 0 when negative. Alternative DP: dp[i] represents max sum ending at i. Time O(N), space O(1). Variants include circular array, finding subarray itself, and 2D maximum subarray. Applications in stock trading (maximum profit), signal processing, data analysis for trend detection, and financial analysis.

Example: [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1])

Description: Place N queens on N×N chessboard such that no two queens attack each other. Tests backtracking, constraint propagation, and optimization. Use backtracking placing queen row by row, checking column, diagonal, anti-diagonal conflicts. Optimize using bit manipulation to track occupied positions. Time O(N!), space O(N). Return all solutions or count. Applications in constraint satisfaction problems, scheduling with conflicts, resource allocation, and algorithm visualization for teaching.

Example: N=4 → [[“..Q.”,”.Q..”,”…Q”,”Q…”],[“…Q”,”Q…”,”..Q.”,”.Q..”]]

Description: Given array where each element represents maximum jump length from that position, find minimum jumps to reach last index. Tests greedy algorithm and BFS-like thinking. Maintain current reach and next reach, increment jumps when current position reaches current reach boundary. Time O(N), space O(1). Alternative BFS approach treats as graph shortest path. Applications in navigation systems, game AI pathfinding, compiler optimization for control flow, and network routing.

Example: [2,3,1,1,4] → 2 (jump 1 step to index 1, then 3 steps to last index)

Description: Find longest palindromic substring in given string. Tests multiple techniques: expand around center, dynamic programming, Manacher’s algorithm. DP approach: dp[i][j] represents if substring s[i..j] is palindrome. Expand around center: try each position as center, expand while characters match. Manacher’s algorithm achieves O(N) time using symmetry properties. Applications in DNA sequence analysis, pattern recognition, text compression, and string processing.

Example: “babad” → “bab” or “aba”; “cbbd” → “bb”

Description: Given strings s and t, find minimum window in s containing all characters of t including duplicates. Tests sliding window with hash map. Use two pointers for window, expand right to include characters, contract left when valid window found. Track character frequencies with maps. Time O(M+N), space O(1) for fixed alphabet. Applications in text search, pattern matching, log analysis for error patterns, and bioinformatics for sequence analysis.

Example: s=”ADOBECODEBANC”, t=”ABC” → “BANC”

Description: Find maximum path sum in binary tree where path can start and end at any node. Tests tree recursion and global variable management. For each node, calculate maximum path through it considering left subtree, right subtree, or both. Maintain global maximum. Handle negative values by choosing not to include subtrees. Time O(N), space O(H) for recursion stack. Applications in network flow optimization, transportation cost analysis, and decision tree evaluation in AI.

Example: Tree [1,2,3] → 6 (path 2→1→3); [-10,9,20,null,null,15,7] → 42 (path 15→20→7)

Description: Given string s and dictionary, determine if s can be segmented into space-separated sequence of dictionary words. Tests dynamic programming and trie data structures. DP approach: dp[i] represents if substring s[0..i-1] can be segmented. For each position, try all possible previous positions and check if substring is in dictionary. Optimization: use trie for dictionary lookup. Time O(N^2*M) where M is max word length. Applications in NLP, spell checkers, search query segmentation, and compound word detection.

Example: s=”leetcode”, wordDict=[“leet”,”code”] → true

Description: Design and implement an LRU (Least Recently Used) cache supporting get and put operations with O(1) time complexity. Implement using HashMap for O(1) lookup and Doubly Linked List for LRU ordering. When capacity exceeded, evict least recently used item. When item accessed, move to head. Time complexity O(1) for all operations, space O(capacity). Variations include LFU cache (least frequently used), thread-safe cache, distributed cache consistency. Consider memory constraints, cache coherency in multi-threaded environments, and optimal eviction policies. Applications in CPU caches, CDN cache management, database query result caching, browser caches, and distributed systems.

Example: LRUCache(2) -> put(1,1), put(2,2) -> get(1) returns 1 -> put(3,3) removes key 2 -> get(2) returns -1

Description: Given a signed 32-bit integer, reverse its digits handling overflow. Return 0 if overflow occurs. Tests bit manipulation, integer constraints, and edge case handling. Iteratively extract last digit using modulo, check for overflow before multiplying by 10, append digit to result. Handle negative numbers by maintaining sign. Time O(log n) where n is number of digits, space O(1). Variations include reversing strings, reversing arrays, handling leading zeros. Applications in number manipulation, data transformation, encoding/decoding schemes.

Example: x=123 -> 321; x=-123 -> -321; x=120 -> 21; x=0 -> 0

Description: Given array of integers and target sum, find two numbers adding to target returning their indices. Classic two-pointer or hash map approach. Hash map: store value-index pairs, check if complement exists. Time O(n), space O(n). Two pointer for sorted array: start from ends, move based on sum. Time O(n), space O(1) if array pre-sorted. Variations include 3Sum, 4Sum, k-Sum problems with different constraints. Applications in subset finding, balance checking, threshold detection, matching problems in optimization.

Example: nums=[2,7,11,15], target=9 -> [0,1]

Description: Given array of heights representing container walls, find two lines forming container with maximum area. Area = width * min(height[i], height[j]). Use two pointers from ends, move smaller height inward (better chance finding larger container). Time O(n), space O(1). Key insight: larger width disadvantageous if height limited by shorter wall. Variants include 3D container, irregular shapes. Applications in reservoir optimization, capacity planning, resource allocation with geometric constraints.

Example: height=[1,8,6,2,5,4,8,3,7] -> 49 (between index 1 and 8)

Description: Convert integer to Roman numeral representation or vice versa. For int-to-roman: use value-symbol mapping in descending order with subtractive cases (IV=4, IX=9). For roman-to-int: iterate through string, sum values, subtract when smaller value precedes larger. Time O(1) for bounded integers, space O(1). Handle all cases: I(1), V(5), X(10), L(50), C(100), D(500), M(1000), and combinations. Applications in date representation, numbering systems, historical data encoding.

Example: 58 -> “LVIII”; “MCMXCIV” -> 1994

Description: Reverse bits of unsigned 32-bit integer. Extract each bit using AND with 1, accumulate in result by shifting. Process all 32 bits. Time O(32) = O(1), space O(1). Optimization: dynamic bit length iteration. Variations include byte reversal, bit string reversal. Applications in low-level programming, hardware operations, bit manipulation algorithms, network byte order conversion.

Example: input=43261596 (00000010100101000001111010011100) -> output=964176192 (00111001011110000010100101000000)

Description: Determine if number is happy where happy number reaches 1 by repeatedly replacing with sum of squares of digits. Unhappy numbers loop endlessly. Detect cycle using set or Floyd’s cycle detection. Time O(log n) average, space O(log n) for set or O(1) for Floyd. Variations include checking multiple sequences, path analysis. Applications in number theory, cycle detection algorithms, sequence analysis.

Example: n=19 -> 1^2 + 9^2 = 82 -> 8^2 + 2^2 = 68 -> … -> 1 (happy); n=2 -> cycles (unhappy)

Q1: Ecommerce Loyalty Program with Gamification

Description: Design a service that adds gamification elements to an e-commerce platform, tracking user transactions and allowing users to purchase products, redeem points during purchases, and earn new points from transactions. The service must implement a tiered level system (Bronze, Silver, Gold) based on accumulated points, calculate points earned per transaction based on user level, implement redemption rules with level-specific limits, and track user statistics. This is a classic machine coding problem testing object-oriented design, proper entity modeling, and extensibility. The solution requires designing classes for User, Level, Transaction, PointsCalculator, and RedemptionValidator. Key design patterns include Strategy Pattern for different point calculation strategies, State Pattern for user levels, and Builder Pattern for complex object creation. The system must handle concurrent transactions, provide transaction history, and allow dynamic level upgrades. Implement test cases covering tier transitions, edge cases in redemption limits, discount calculations, and concurrent purchase scenarios. The evaluators assess code modularity, design patterns application, proper abstraction levels, separation of concerns, and ability to explain design decisions and potential scalability improvements.

 

Example:

User purchases items worth 5000 rupees at Silver level: Points earned = (5000/100)*12.5 = 625 points. If user redeems 300 points during purchase, amount becomes 4700. Points earned on remaining = (4700/100)*12.5 = 587.5 points.

Description: Design a system enabling peer-to-peer parcel delivery similar to Dunzo. The system must support onboarding customers and drivers, placing and canceling orders, auto-assigning orders to available drivers, tracking order and driver status, showing delivered orders, implementing concurrency and thread-safety, and handling order timeout (auto-cancel after 30 minutes if unpicked). This is an advanced LLD problem testing concurrent programming, state management, queue implementations, and system reliability. Key components include Customer, Driver, Order, OrderStatus, DriverStatus, OrderManager, DriverManager, and NotificationService. Implement assignment strategy using queue or priority queue for fairness. Handle race conditions when orders transition states, ensure driver availability is managed correctly, and implement notification system (email/SMS) for updates. Design the system to handle scenarios like duplicate order placement, cancellation of picked-up orders being invalid, notification delivery failures, driver becoming unavailable mid-delivery. Test cases should verify correct order state transitions, proper driver assignment, timeout handling, concurrent updates, and edge cases. The evaluation focuses on correct concurrency implementation, proper exception handling, extensibility for new delivery types, and performance optimization strategies.

 

Example:

Customer orders parcel, system finds available driver and assigns order. Driver picks up order (order state = PICKED_UP, driver state = BUSY). If no driver picks up within 30 minutes, order auto-cancels and drivers are notified to release reservation.

Description: Implement a simplified food ordering system where users can search restaurants, browse menus, place orders, and receive order status updates. The system must support restaurant onboarding with menu and capacity, dynamic menu price updates, order placement with availability and capacity validation, order dispatch, tracking items served per restaurant, and processing timestamped commands in order. Design the system using solid OOP principles with proper entity modeling including Restaurant, MenuItem, Order, and RestaurantSelectorStrategy. Implement a strategy pattern for restaurant selection algorithms (e.g., LowestTotalPrice, HighestRating, FastestDelivery). The CommandProcessor should parse and execute commands sorted by timestamp. Key design decisions include in-memory data structures for storage, proper validation for order acceptance (all items available and capacity allows), and extensibility for adding new selection strategies. Handle edge cases like duplicate orders, partial item availability, restaurant capacity limits, and command execution order. Test with various scenarios including normal ordering, capacity exhaustion, menu updates, and multiple concurrent orders. Evaluation criteria include code quality, proper design pattern usage, validation logic, error handling, and ability to extend the system for new features like discounts or loyalty programs.

 

Example:

Command: “5, place-order, order1, item1, item2”. System checks availability of item1 and item2, verifies restaurant capacity, and either confirms order or rejects with reason. Each successfully placed order is dispatched, freeing restaurant capacity for new orders.

Description: Design an MVP for an in-memory message streaming service supporting multiple topics, producers, and consumers similar to Apache Kafka. The system must maintain message order within partitions, support multiple consumers reading from same partition with independent offsets, handle producer sending to specific partitions or using round-robin, enable consumer groups for distributed processing, ensure thread-safety for concurrent access, and provide offset management. Implement Topic, Partition, Message, Producer, Consumer, and ConsumerGroup classes. Use BlockingQueue or similar concurrent data structures for message buffering. Each partition maintains independent message queue with offset tracking per consumer. Implement proper synchronization using locks or concurrent collections. Key features include partition-based ordering, consumer group coordination, offset commit mechanism, and message retention policies. Handle edge cases like consumer lag, partition rebalancing, null messages, invalid offsets, and concurrent producer-consumer scenarios. The solution should be extensible for future features like message filtering, compression, and replication. Test cases verify message order preservation, correct offset tracking, concurrent access safety, consumer group fairness, and performance under load. Evaluation considers correct concurrency implementation, clean separation of concerns, proper abstraction, documentation, and design decision justification.

 

Example:

Producer sends message to topic “user-events” partition 0. Multiple consumers in group read from partition 0 with independent offsets. Consumer 1 at offset 5, Consumer 2 at offset 8. New message appends to partition queue, both consumers receive independently based on their offsets.

Description: Design parking lot supporting multiple vehicle types (car, bike, truck) with different slot sizes, entry/exit management, fee calculation, and availability tracking. System must handle concurrent requests, implement pricing strategy, generate tickets, and track parking duration. Design entities: ParkingLot, Floor, ParkingSpot, Vehicle, Ticket, ParkingStrategy. Use Strategy pattern for vehicle-to-spot assignment (nearest, random). Implement Factory pattern for vehicle creation. Handle edge cases: no available spots, invalid ticket, spot size mismatch. Use synchronization for concurrent access. Implement fee calculation based on duration and vehicle type with possibility for hourly, daily rates. Design should be extensible for new vehicle types, additional floors, different pricing models. Applications include real-world parking management systems, smart city infrastructure, and resource allocation algorithms.

Description: Implement shopping cart system with add/remove items, quantity updates, price calculation, discount application, and inventory management. Support guest and registered users with cart persistence. Design entities: Cart, CartItem, Product, User, DiscountCoupon, InventoryManager. Implement Observer pattern for price changes. Use Decorator pattern for discounts (percentage, fixed, buy-one-get-one). Handle concurrent cart operations, inventory locking, cart abandonment. Implement cart merge on user login. Support multiple currencies, tax calculation based on location. Design checkout process with payment integration. Consider scalability for millions of users, caching strategies for product data. Applications in e-commerce platforms, marketplace systems, and retail management software.

Description: Design system for hotel booking with room search, reservation, cancellation, and availability management. Support multiple room types, date-based pricing, customer profiles, payment processing. Entities: Hotel, Room, RoomType, Booking, Customer, Payment. Implement Command pattern for booking operations (create, cancel, modify). Use State pattern for booking states (pending, confirmed, cancelled, completed). Handle concurrency for room booking conflicts using pessimistic locking. Implement search with filters (price, amenities, location). Support overbooking strategy, waitlist management, loyalty programs. Design notification system for booking confirmations. Consider seasonal pricing, dynamic pricing based on demand. Applications in hospitality industry, vacation rentals, and resource scheduling systems.

Description: Design elevator control system for multi-floor building handling requests efficiently. Implement request scheduling, direction management, and optimization for waiting time. Entities: Elevator, Floor, Request, ElevatorController, Scheduler. Use Strategy pattern for scheduling algorithms (FCFS, SCAN, LOOK). Implement State pattern for elevator states (idle, moving_up, moving_down, door_open). Handle edge cases: emergency requests, maintenance mode, power failure. Optimize for factors: minimize wait time, energy efficiency, even elevator utilization. Support external and internal requests. Design display systems showing elevator positions. Consider load balancing across multiple elevators, peak hour optimization. Applications in building management systems, simulation software, and real-time scheduling algorithms.

Description: Implement rate limiting service to control request rates per user/IP with configurable limits. Support multiple strategies: fixed window, sliding window, token bucket, leaky bucket. Entities: RateLimiter, TokenBucket, SlidingWindow, Rule, User. Use Strategy pattern for different algorithms. Implement distributed rate limiting using Redis. Handle concurrent requests with proper synchronization. Support per-user, per-IP, per-API-key limits. Design rule configuration with time windows (per second, minute, hour). Implement graceful degradation returning 429 status. Consider storage for rate limit data, cleanup of expired entries. Support burst traffic handling. Applications in API gateways, DDoS protection, resource throttling, and cost management for cloud services.

Description: Design ATM machine system handling cash withdrawal, balance inquiry, deposit, PIN change with account management. Entities: ATM, Card, Account, Bank, Transaction, CashDispenser. Implement State pattern for ATM states (idle, card_inserted, PIN_verified, transaction_in_progress). Use Chain of Responsibility for cash dispensing with different denominations. Handle security: PIN encryption, transaction limits, card blocking after failed attempts. Implement transaction logging, audit trails. Design synchronization with bank servers, offline mode handling. Support multiple accounts per card, different transaction types. Consider cash inventory management, error handling for insufficient funds/cash. Applications in banking systems, self-service kiosks, and financial transaction processing.

Description: Design library system managing books, members, borrowing, returns, fines, and reservations. Entities: Library, Book, Member, Librarian, BorrowRecord, Fine, Reservation. Implement Observer pattern for book availability notifications. Use Strategy pattern for fine calculation (per day, graduated). Handle book copies, edition management, catalog search. Implement reservation queue for popular books. Design member tiers with different borrowing limits. Support barcode scanning, RFID integration. Handle late returns, damaged book fees, membership renewal. Consider scalability for large collections, efficient search algorithms. Applications in educational institutions, public libraries, and resource management systems.

Description: Implement snake and ladder board game supporting multiple players, dice rolls, game state management. Entities: Game, Board, Player, Snake, Ladder, Dice. Implement game loop, turn management, position tracking. Use Strategy pattern for dice (normal, biased for testing). Handle special rules: exact roll to win, multiple snakes/ladders at position. Design board configuration from file/database. Implement game history, undo functionality. Support save/load game state. Consider multiplayer synchronization, animation sequences. Design extensible for rule variations (multiple dice, special squares). Applications in gaming industry, simulation software, educational tools for teaching probability and game theory.

Description: Design vending machine dispensing products with payment processing, inventory management, change return. Entities: VendingMachine, Product, Inventory, Payment, Coin, CashRegister. Implement State pattern (idle, product_selected, payment_pending, dispensing). Handle coin insertion, note acceptance, card payment. Design product selection with code input. Implement change calculation with available coins. Handle out-of-stock, insufficient payment, cancellation. Support inventory alerts, sales reporting. Consider coin/note denominations, change optimization. Design maintenance mode, admin interface. Applications in retail automation, micro-markets, and unattended retail systems.

Description: Implement chess game with move validation, game state management, check/checkmate detection. Entities: Board, Piece (King, Queen, Rook, etc.), Player, Move, Game. Use Strategy pattern for piece-specific move rules. Implement move validation considering piece type, board state, check situations. Handle special moves: castling, en passant, pawn promotion. Design game history, undo/redo moves. Implement check detection, checkmate/stalemate algorithms. Support game saving, PGN format. Consider AI opponent using minimax algorithm. Design for chess variants. Applications in gaming, AI research, educational software for teaching chess strategies.

Description: Design system managing tables, orders, menu, kitchen, billing for restaurant. Entities: Restaurant, Table, Order, MenuItem, Customer, Chef, Bill. Implement Observer pattern for order status updates. Use Chain of Responsibility for order preparation pipeline. Handle table reservation, waiting list management. Design menu with categories, prices, availability. Implement order routing to kitchen, preparation tracking. Support split bills, tips, multiple payment methods. Handle concurrent table assignments, order modifications. Design inventory deduction on orders, low stock alerts. Applications in hospitality industry, food service management, and POS systems.

Description: Implement URL shortening service generating short links, redirecting, and tracking analytics. Entities: URL, ShortURL, User, Analytics. Design short URL generation (base62 encoding, hash-based, counter-based). Implement collision handling, custom URLs. Handle scalability: sharding strategies, caching popular URLs. Design redirect mechanism with HTTP 301/302. Implement analytics: click count, geographic data, referrers. Support expiration dates, URL validation. Handle security: malicious URL detection, rate limiting. Consider storage: SQL for metadata, NoSQL for analytics. Design API with authentication. Applications in social media, marketing campaigns, link management services.

Description: Design meeting scheduler handling availability checking, scheduling, conflicts, invitations, reminders. Entities: Calendar, Event, User, Room, Invitation, Reminder. Implement conflict detection using interval overlap. Use Strategy pattern for meeting room allocation. Handle recurring events (daily, weekly, custom patterns). Design notification system for invitations, reminders. Support multiple calendars per user, shared calendars. Implement time zone handling. Handle event updates, cancellations with attendee notifications. Design free/busy time aggregation. Consider scalability for large organizations, efficient conflict detection algorithms. Applications in productivity tools, enterprise scheduling, resource booking systems.

Description: Design notification system supporting multiple channels (email, SMS, push), priorities, templates, scheduling. Entities: Notification, NotificationChannel, Template, User, Schedule. Use Strategy pattern for channel-specific sending. Implement Factory pattern for notification creation. Design retry mechanism for failures, exponential backoff. Handle batching for efficiency, rate limiting per channel. Implement template engine with variable substitution. Support user preferences, opt-out management. Design delivery tracking, read receipts. Handle priority queues, immediate vs delayed notifications. Consider scalability: message queue, distributed workers. Applications in user engagement platforms, alerting systems, communication services.

Description: Implement cache with eviction policies supporting get, put operations with O(1) complexity. Design LRU using HashMap + Doubly Linked List. LFU using HashMap + Doubly Linked List of frequencies. Entities: Cache, CacheEntry, EvictionPolicy. Use Strategy pattern for policies. Handle capacity management, thread safety. Implement TTL (time-to-live) for entries, background cleanup. Support cache statistics: hit rate, miss rate. Design write-through, write-back, write-around strategies. Handle distributed caching with consistent hashing. Consider memory limits, serialization for complex objects. Applications in database systems, web servers, CDN, in-memory data stores.

Description: Implement tic-tac-toe game supporting multiple board sizes, win detection, AI opponent. Entities: Game, Board, Player, Move. Design extensible for N×N board, K-in-a-row to win. Implement win detection efficiently checking row, column, diagonals. Use Strategy pattern for AI difficulty levels (random, minimax). Handle game states (in_progress, won, draw). Support multiplayer, save game state. Design move validation, undo functionality. Consider optimal data structures for large boards. Implement alpha-beta pruning for AI. Design for game variants (3D tic-tac-toe, misere variant). Applications in gaming industry, AI education, algorithm visualization.

Description: Design expense sharing app managing group expenses, split methods, settlements, balance tracking. Entities: User, Group, Expense, Split, Transaction. Support split types: equal, exact amounts, percentages, shares. Implement balance calculation, debt simplification algorithm. Design group management, expense categories. Handle multiple currencies with exchange rates. Implement settlement suggestions minimizing transactions using graph algorithms. Support recurring expenses, itemized splitting. Design notification for new expenses, reminders. Handle expense updates, deletions with balance recalculation. Applications in personal finance, travel expense management, shared living cost management.

Description: Design core ride matching system pairing riders with drivers based on location, availability, preferences. Entities: Rider, Driver, Ride, Location, Vehicle. Implement geo-spatial indexing (quadtree, geohash) for nearby driver search. Use Strategy pattern for matching algorithms (nearest, highest rated, pool matching). Handle real-time location updates, ETA calculation. Design fare calculation with surge pricing. Implement ride states (requested, matched, started, completed). Handle cancellations, ratings, payments. Consider scalability: sharding by geography, caching hot areas. Design for ride pooling optimization. Applications in ride-sharing platforms, delivery services, logistics optimization.

Description: Design flexible logging library supporting multiple log levels, outputs, formats, rotation. Entities: Logger, LogLevel, Appender, Formatter, Filter. Use Chain of Responsibility for log processing pipeline. Implement appenders: file, console, database, remote. Design log rotation by size, date, custom policy. Support structured logging, JSON format. Handle async logging with buffering, thread-safety. Implement log filtering by level, package, custom rules. Design configuration from files, programmatic setup. Handle performance: lazy evaluation, sampling. Consider distributed tracing, correlation IDs. Applications in application monitoring, debugging, audit trails, compliance logging.

Description: Design news feed system generating personalized feed from followed users, pages, groups. Entities: User, Post, Feed, Follow, Like, Comment. Implement feed generation: fan-out on write for active users, fan-out on read for celebrities. Use ranking algorithm based on recency, engagement, relevance. Design post creation with media uploads, mentions, hashtags. Handle like/comment with counters, pagination. Implement real-time updates using WebSocket/long polling. Design content moderation, spam filtering. Handle scalability: feed storage (timeline cache), database sharding by user. Consider EdgeRank-like algorithms, machine learning for personalization. Applications in social networks, content platforms, community forums.

Description: Design carpooling system matching riders with drivers heading same direction, optimizing cost sharing and route. Entities: Rider, Driver, Trip, Matching Engine, Payment. Implement matching algorithm considering: start location, destination, time flexibility, cost preference. Use geospatial indexing for nearby matching. Handle constraints: capacity per vehicle, detour limits, timing flexibility. Implement cost splitting algorithm considering distance, time, vehicle efficiency. Design for dynamic ride updates, passenger drops, alternative routes. Handle cancellations with penalty. Applications in ride-sharing optimization, traffic reduction, environmental benefits.

Description: Design nested comment system supporting threaded discussions, likes, deletion, editing. Entities: Comment, User, Reply, Reaction. Implement tree structure for nesting or flat structure with parent references. Design pagination for large comment threads, lazy loading of replies. Handle comment deletion (mark as deleted vs physical deletion). Implement sorting options: newest first, most liked, nested depth. Support real-time updates, notifications for replies. Design content moderation, spam filtering. Consider performance for deeply nested comments, caching strategies.

Description: Design search suggestion system providing autocomplete as users type queries. Entities: Trie, Suggestion, Ranking. Build Trie from popular searches for O(m) search time where m is word length. Rank suggestions by frequency, recency, relevance. Implement caching for common prefixes. Handle typos with fuzzy matching. Support multi-language, region-specific suggestions. Design real-time index updates, new trend detection. Implement frequency decay over time. Applications in search engines, command-line tools, IDE autocomplete.

Description: Implement file system supporting directory structure, file operations (create, read, write, delete), permissions. Entities: File, Directory, User, Permission. Design using tree structure with directories as nodes, files as leaf nodes. Implement path resolution, file locking for concurrent access. Support attributes: size, creation time, modification time, permissions (read, write, execute). Handle symbolic links, hard links. Implement garbage collection for deleted files. Design for efficient search, size calculation. Consider security: access control lists, user permissions.

Description: Design database connection pool for efficient resource management in multi-threaded applications. Entities: Connection, Pool, Waiter Queue. Maintain pool of pre-initialized connections. When requested, return available connection or wait if full. Implement connection validation, timeout handling. Support idle connection cleanup, connection reset on errors. Design for thread-safety using locks. Implement metrics: active connections, wait time, utilization. Handle connection leaks detection. Support dynamic pool size adjustment. Applications in database drivers, web application servers, distributed systems.

Description: Enhanced autocomplete supporting prefix queries on documents, phrase suggestions, word count tracking. Support prefix query returning top-k frequent documents. Use Trie with frequency counts at each node. For phrase search, implement inverted index. Design exact match, phrase match, wildcard matching. Support real-time index updates for new documents. Implement result ranking combining relevance and popularity. Handle synonyms, spell correction. Design scalability for millions of documents. Applications in document search, code search in IDEs, content discovery.

Description: Design competitive leaderboard tracking player scores, rankings, percentiles for gaming/sports platforms. Entities: Player, Score, Leaderboard, TimeWindow. Support different time windows: all-time, monthly, weekly, daily. Implement efficient ranking without sorting all players using Fenwick tree or segment tree. Handle score updates, deletions. Calculate percentile rank efficiently. Design tied scores handling. Support player compare functionality. Implement caching for top-N players. Handle distributed leaderboards across regions. Applications in gaming platforms, sports ranking, competitive applications.



Q1: Movie Ticket Booking System (BookMyShow Clone)

Description: Design a scalable ticket booking platform similar to BookMyShow that handles movie search by name and theater, ticket booking and cancellation, showing upcoming movies, and managing concurrent bookings. The system must serve millions of users, handle high concurrency during popular movie releases, prevent double-booking of seats, ensure ACID properties for transactions, provide low-latency search, and scale horizontally. Architecture should include API Gateway for request routing, microservices for Movies, Theaters, Bookings, Payments, and Notifications, database sharding based on geographical location or theater ID, Redis/Memcached for caching popular movies and theater availability, message queues (RabbitMQ/Kafka) for asynchronous operations, and distributed locking (Redis) for seat reservation. Database design includes normalized schema with Movies, Theaters, Shows, Seats, Bookings tables with proper indexing. Implement distributed transactions using Saga pattern or 2PC for booking-payment flow. Handle race conditions during seat selection using pessimistic/optimistic locking. Scale considerations include CDN for static content, read replicas for database, horizontal pod autoscaling, rate limiting, circuit breakers for fault tolerance, and monitoring with Prometheus/Grafana. Security aspects cover authentication/authorization, PCI compliance for payments, and data encryption. Capacity planning involves estimating QPS, database size, cache hit ratio, and network bandwidth. The solution demonstrates understanding of distributed systems, consistency models, scalability patterns, and production readiness.

 

Example: During Avengers release, 100K users try booking. System uses distributed locks on seats, processes bookings through queue, handles payment asynchronously, sends confirmation via notification service, releases unpaid bookings after timeout.

Description: Design a relational database management system from scratch handling SQL queries, ACID transactions, indexing, query optimization, and concurrent access. Core components include Query Parser for SQL parsing, Query Optimizer for execution plan generation, Storage Engine for data persistence, Transaction Manager for ACID guarantees, Lock Manager for concurrency control, Buffer Pool Manager for memory management, and Index Manager for B-tree/Hash indexes. Implement functional requirements like CREATE/INSERT/UPDATE/DELETE operations, SELECT with WHERE/JOIN/GROUP BY, transactions with BEGIN/COMMIT/ROLLBACK, and index creation. Non-functional requirements include ACID compliance using Write-Ahead Logging, MVCC for read consistency, 2PL or optimistic concurrency control, crash recovery, and horizontal scalability through replication. Architecture decisions involve log-structured merge trees vs B-trees for storage, row-based vs columnar storage, master-slave replication vs multi-master, and query optimization using cost-based optimizer. Handle edge cases like deadlock detection and resolution, long-running transactions, disk failures, network partitions, and concurrent schema modifications. Performance optimizations include query result caching, index hints, partition pruning, and parallel query execution. The design demonstrates deep understanding of database internals, distributed consensus protocols (Raft/Paxos), replication strategies, and trade-offs between consistency and performance.

 

Example: Query “SELECT * FROM users WHERE age > 25 AND city = ‘NYC'” goes through parser, optimizer generates execution plan using indexes on age and city, storage engine fetches pages from disk/buffer pool, lock manager ensures consistency, result returned.

Description: Design a global music streaming platform handling millions of concurrent users, supporting music upload, search and discovery, streaming, playlist management, social features, and recommendations. System must provide low-latency audio streaming globally, handle peak loads during new releases, personalize recommendations, ensure high availability, and scale cost-effectively. Architecture components include API Gateway with rate limiting, microservices for User Management, Music Catalog, Streaming, Playlists, Social, Recommendations, CDN (CloudFront/Akamai) for audio content delivery, Object Storage (S3) for audio files in multiple bitrates, NoSQL database (Cassandra/DynamoDB) for scalable metadata storage, Search service (Elasticsearch) for music discovery, Cache layer (Redis) for frequently accessed data, Message Queue (Kafka) for event streaming, ML Pipeline for recommendations, and Analytics pipeline for user behavior tracking. Audio streaming uses adaptive bitrate streaming (HLS/DASH) with multiple quality levels. Implement content delivery optimization with edge caching, regional POPs, and predictive prefetching. Handle concurrent writes to playlists using eventual consistency model. Implement social feed using fan-out on write for popular artists, fan-out on read for regular users. Recommendation system uses collaborative filtering, content-based filtering, and deep learning models trained on user interactions. Scale considerations include database partitioning by user ID, read-heavy optimization with replica sets, horizontal scaling of stateless services, and cost optimization with reserved instances. The solution demonstrates understanding of global distributed systems, CAP theorem trade-offs, content delivery networks, and machine learning integration.

 

Example: User searches “workout songs”, Elasticsearch returns results, user plays song, CDN serves from nearest edge location, play event sent to Kafka, analytics pipeline updates user profile, recommendation service retrains model asynchronously.

Description: Design an ultra-fast delivery platform delivering groceries and essentials in 10-15 minutes, handling real-time inventory, order routing to nearest dark store, rider allocation, and delivery tracking. System must optimize for delivery time, handle inventory synchronization across dark stores, provide accurate ETAs, scale to thousands of orders per minute, and ensure operational efficiency. Key components include API Gateway, microservices for Inventory, Order Management, Rider Management, Routing, Payments, Notifications, real-time location services (Redis Geospatial), route optimization engine, inventory management with real-time sync, and ML models for demand forecasting. Architecture uses event-driven design with Kafka for order flow, Cassandra for order history, PostgreSQL for inventory with row-level locking, Redis for cache and real-time data, and WebSocket for live tracking. Implement intelligent order routing using distance calculation, dark store capacity, and inventory availability. Rider allocation uses matching algorithm considering rider location, current load, and route optimization. Handle concurrent inventory updates using optimistic locking with version numbers. Implement circuit breakers for payment failures, retry mechanisms for external calls, and fallback strategies for routing service downtime. Scale dark stores based on demand heatmaps and historical data. Real-time tracking uses GPS coordinates published to message bus, consumed by tracking service, and pushed to user via WebSockets. Performance optimizations include database connection pooling, async processing for non-critical operations, batch updates for inventory, and CDN for static content. The design demonstrates understanding of logistics optimization, real-time systems, geo-spatial indexing, and operational scalability.

 

Example: User orders milk from location A, system finds nearest dark store with stock, calculates 12-min ETA, assigns nearest available rider optimizing for route, rider picks order, updates status, GPS coordinates stream to user app showing live tracking, order delivered in 11 minutes.

Description: Design a real-time leaderboard system for a racing game handling millions of concurrent players, updating scores during races, pushing notifications, and displaying global/friend rankings with zero lag. System must handle massive writes during races, provide real-time rank updates, scale globally, ensure consistency, and optimize for read-heavy patterns during non-race times. Architecture includes API Gateway, Game Service for race logic, Leaderboard Service with Redis Sorted Sets for O(log N) operations, Database (PostgreSQL) for persistent storage, Cache layer for frequently accessed leaderboards, WebSocket servers for push notifications, Message Queue (Kafka) for score updates, and Analytics service for historical data. Implement leaderboard using Redis ZADD for score updates and ZRANGE for rankings. Handle race-time write spikes using write-through cache with async database persistence. For friend leaderboards, maintain separate sorted sets per user-group. Global leaderboard uses sharding by region with aggregation service. Implement notification system using pub-sub pattern with fan-out to connected players. Optimize reads with materialized views for top 100 players, updated periodically. Handle edge cases like score ties, player disconnections during races, network partitions, and cache invalidation. Implement consistency using eventual consistency model with conflict resolution. Scale using Redis Cluster for distributed sorted sets, database replication for read scaling, and horizontal scaling of WebSocket servers with sticky sessions or broadcast mechanism. Performance optimizations include score batching, delta updates instead of full state, connection pooling, and CDN for static assets. The solution demonstrates understanding of real-time systems, gaming backend architecture, Redis data structures, and push notification systems.

Description: Design scalable search engine crawling, indexing, ranking web pages. Components: Web Crawler, Indexer, Ranker, Query Processor, Cache. Crawler uses BFS to traverse web, respects robots.txt, handles politeness. Indexer builds inverted index mapping terms to documents. Ranker implements PageRank algorithm, TF-IDF scoring, considering backlinks, content quality. Query processor handles query expansion, spell correction, suggestion. Store indexed data in distributed file system. Use caching for popular queries. Handle 100M pages, billions of searches daily. Scalability: sharding by document ID, distributed crawling, MapReduce for indexing. Consider freshness (incremental crawling), spam detection, personalization. Applications: information retrieval, knowledge bases, enterprise search.

Description: Design platform handling video upload, processing, streaming, recommendations at global scale. Components: Upload Service, Video Processing (transcoding), Content Delivery Network (CDN), Storage, Search, Recommendations. Upload uses chunked transfer, resume capability. Processing converts to multiple resolutions (1080p, 720p, 480p, 240p) using FFmpeg. CDN distributes content globally with edge caching. Store video metadata in SQL, video content in blob storage (S3). Search uses Elasticsearch for titles, descriptions. Recommendations use collaborative filtering, content-based filtering. Handle 500M users, 1000 hours uploaded/minute. Scale: microservices architecture, horizontal scaling, database replication. Consider live streaming, 360 video support, DRM. Applications: video sharing, streaming platforms, broadcasting.

Description: Design email system handling compose, send, receive, storage, search at scale. Components: SMTP server, Mail Transfer Agent (MTA), Storage, Search, Notification. SMTP handles email reception, validation, spam filtering. MTA routes emails between servers. Storage stores messages (40KB average) in distributed system with compression, deduplication. Search indexes email content for full-text search. Notification alerts users of new emails. Handle 1B users, 300B emails/day. Scalability: database sharding by user ID, distributed storage, horizontal scaling of MTAs. Implement: quotas (15GB free), labels, filters, conversation threading, attachments, encryption. Consider: spam detection, virus scanning, backup/recovery, archival policies. Applications: communication platforms, collaboration tools.

Description: Design mapping service providing directions, location search, traffic information globally. Components: Geocoding Service, Routing Engine, Traffic Service, Map Rendering, Search. Geocoding converts addresses to coordinates using databases (Nominatim-like). Routing finds shortest path using Dijkstra/A* on road graph. Traffic aggregates real-time GPS data. Map rendering tiles map into zoomable quadtree. Search uses spatial indexing (quadtree, geohash) for location queries. Handle 1B daily active users. Scalability: partition world into tiles, distributed routing servers, caching popular routes/tiles. Implement: alternate routes, ETA calculation, traffic-aware routing, turn-by-turn navigation. Consider: offline maps, real-time traffic, user privacy. Applications: navigation, ride-sharing, location-based services.

Description: Design social platform for tweets, followers, timelines, trending topics at billion user scale. Components: Post Service, Timeline Service, Social Graph Service, Search, Trending Service, Notification. Post Service stores tweets (140 characters) with metadata. Timeline Service generates user feed using fan-out architecture. Social Graph tracks followers (adjacency list). Search indexes tweets with Elasticsearch. Trending Service ranks hashtags by frequency. Notification alerts for mentions, likes, follows. Handle 500M daily active users, 100K tweets/second. Scalability: sharding by user ID, timeline cache, eventual consistency for counts. Implement: retweets, likes, replies, direct messages, media sharing. Consider: abuse prevention, shadow banning, content moderation. Applications: social networking, microblogging platforms.

Description: Design platform for photo sharing, following, discovery, feed generation. Components: Photo Service, Feed Generator, Search, Recommendations, Notification. Photo Service handles upload, storage, resizing. Feed Generator creates personalized timelines using engagement metrics. Search uses visual recognition + text search. Recommendations suggest new accounts using collaborative filtering. Notification alerts for likes, comments, follows. Handle 2B users, 2M photos/minute. Scalability: distributed storage (S3-like), CDN for images, feed sharding by user. Implement: stories (temporary photos), reels (short videos), hashtags, geolocation tagging. Consider: content moderation, recommendation quality, feed ranking ML models. Applications: social media, content sharing platforms.

Description: Design platform for professional profiles, job postings, connections, recommendations. Components: Profile Service, Job Service, Connection Service, Search, Recommendation. Profile Service stores user experience, skills, endorsements. Job Service manages listings, applications, matching. Connection Service handles connection requests, messaging. Search uses Elasticsearch for profile, job search. Recommendation suggests jobs, connections, content. Handle 1B users, 100M job postings. Scalability: database sharding, microservices, caching profiles. Implement: recommendations, endorsements/skills, messaging, job applications, content feed. Consider: recruiter tools, talent assessment, verification. Applications: professional networking, recruiting platforms.

Description: Design video streaming service with personalization, licensing, playback optimization. Components: Content Delivery, Playback Service, Recommendation Engine, Account Management, Payment. Content Delivery uses CDN with adaptive bitrate streaming. Playback Service manages playback state, resume position, offline download. Recommendation uses Watch history, ratings, collaborative filtering. Account handles subscriptions, profiles (for families), payment. Handle 300M subscribers, 100M concurrent viewers. Scalability: edge caching, content duplication, autonomous systems by region. Implement: offline viewing, multiple devices, parental controls, A/B testing for recommendations. Consider: licensing negotiations, regional content, simultaneous streams. Applications: streaming platforms, content distribution services.

Description: Design short-term accommodation booking system with listings, search, bookings, payments. Components: Listing Service, Search Service, Booking Service, Payment, Messaging, Review. Listing Service manages property details, availability calendar, pricing rules. Search uses location-based queries with filters (price, amenities, rating). Booking Service handles reservation, cancellation, refunds. Payment processes transactions securely. Messaging enables host-guest communication. Review collects ratings, feedback. Handle 1M listings, 1M daily bookings. Scalability: database sharding by geography, cache popular listings. Implement: host dashboards, booking management, cancellation policies, instant booking, experiences. Consider: fraud detection, host verification, guest reviews, dynamic pricing. Applications: accommodation platforms, hospitality marketplaces.

Description: Design payment processing system handling transactions, settlements, fraud detection securely. Components: Payment Gateway, Fraud Detection, Settlement Service, Webhook Service, Reporting. Payment Gateway validates cards, routes to acquirers. Fraud Detection uses ML to identify suspicious transactions. Settlement reconciles transactions, transfers funds. Webhook Service notifies merchants of payment status. Reporting provides transaction analytics. Handle 100M transactions/day globally. Scalability: payment sharding, decoupling, PCI DSS compliance. Implement: refunds, chargebacks, retry logic, idempotency, encryption. Consider: PCI compliance, 3D Secure authentication, regional acquirers. Applications: payment platforms, e-commerce, SaaS billing.

Description: Design large-scale e-commerce platform with catalog, inventory, shopping cart, checkout, delivery. Components: Catalog Service, Inventory Service, Cart Service, Order Service, Payment, Delivery. Catalog manages products, descriptions, prices, reviews. Inventory tracks stock across warehouses. Cart manages items added by users. Order Service processes purchases, creates shipments. Payment integrates with payment gateway. Delivery tracks packages. Handle 500M products, 100M daily orders. Scalability: product sharding, inventory distribution, order parallelization. Implement: recommendations, reviews, wishlists, subscription boxes, seller marketplace. Consider: inventory prediction, fulfillment optimization, supply chain management. Applications: retail platforms, marketplace systems.

Description: Design real-time messaging platform with channels, direct messages, notifications, file sharing. Components: Message Service, Presence Service, Notification Service, File Storage, Search. Message Service stores messages with ordering guarantees. Presence Service tracks online/offline status. Notification Service sends alerts for mentions, DMs. File Storage handles document uploads. Search enables full-text search on messages. Handle 100M daily active users, 1M messages/second. Scalability: message sharding by channel, distributed WebSocket servers, eventual consistency for presence. Implement: threads (message replies), reactions, slash commands, apps/integrations, email integration. Consider: message retention, encryption, compliance, performance optimization. Applications: team communication, enterprise messaging.

Description: Design cloud file storage with sync, sharing, versioning, access control. Components: File Service, Sync Service, Sharing Service, Version Control. File Service stores files in distributed storage. Sync Service keeps devices synchronized using delta sync. Sharing Service manages access tokens, permissions. Version Control tracks file versions, enables rollback. Handle 1B users, 100M concurrent uploads. Scalability: block-level deduplication, geo-distributed storage, eventual consistency. Implement: file recovery, selective sync, team folders, access controls, audit logs. Consider: encryption at rest/transit, bandwidth optimization, device trust. Applications: cloud storage platforms, collaboration tools.

Description: Design ride-sharing system with matching, routing, pricing, payments at scale. Components: Matching Service, Location Service, Pricing Service, Payment, Notification. Matching Service pairs riders-drivers using algorithms. Location Service handles real-time GPS updates. Pricing calculates dynamic fares. Payment processes transactions. Notification alerts users. Handle 50M users, 10M daily rides. Scalability: location indexing (geohash sharding), matching at edge, eventual consistency. Implement: surge pricing, ride pooling, ratings, driver verification, safety features. Consider: battery consumption optimization, network efficiency, regional variations. Applications: ride-sharing platforms, transportation services.

Description: Design secure end-to-end encrypted messaging at global scale. Components: Message Service, Encryption Service, Notification Service, Media Storage. Message Service stores messages with ordering. Encryption uses Signal protocol for E2EE. Notification sends messages to offline users. Media Storage handles photos, videos. Handle 2B users, 100B messages/day. Scalability: message sharding, distributed queue, geo-local servers. Implement: group chats, status updates, calls (audio/video), backup, read receipts. Consider: encryption, privacy, message deletion, backup encryption. Applications: messaging platforms, communication apps.

Description: Design content aggregation platform with subreddits, posts, comments, voting, ranking. Components: Post Service, Comment Service, Voting Service, Feed Service, Search. Post Service stores submitted content. Comment Service manages threaded discussions. Voting tracks upvotes/downvotes for ranking. Feed Service generates user feed based on subscriptions. Search uses full-text indexing. Handle 500M monthly active users, 1M posts/day. Scalability: sharding by subreddit, cache hot communities. Implement: moderation tools, awards, custom styling, live chat, user profiles. Consider: spam filtering, bot detection, content moderation, mobile experience. Applications: content aggregation, community platforms.

Description: Design visual discovery platform for saving, sharing, discovering pins and boards. Components: Pin Service, Board Service, Search Service, Recommendation, Feed. Pin Service stores pin metadata, images. Board Service manages user collections. Search uses visual recognition + metadata. Recommendation suggests pins using collaborative filtering. Feed generates personalized content. Handle 500M monthly users, 1B pins. Scalability: image caching on CDN, pin sharding, recommendation caching. Implement: close-up search, lenses (visual search), taste profile, trending pins. Consider: image optimization, recommendation quality, visual search ML. Applications: visual discovery platforms, e-commerce integration.

Description: Design live streaming platform with real-time video broadcast, chat, recommendations. Components: Streaming Service, Chat Service, Recommendation, Analytics. Streaming Service ingests, transcodes, distributes video. Chat Service handles real-time messages from viewers. Recommendation suggests streamers to watch. Analytics tracks viewership. Handle 15M concurrent viewers, 10M monthly streamers. Scalability: CDN for video distribution, chat sharding by channel. Implement: raids, cheers (donations), emotes, moderation, VODs (video-on-demand). Consider: latency optimization (10-20s), bandwidth management, streamer monetization. Applications: streaming platforms, gaming broadcasts.

Description: Design food delivery platform with restaurant listings, order management, delivery tracking. Components: Restaurant Service, Menu Service, Order Service, Delivery Service, Payment, Search. Restaurant Service manages restaurant profiles. Menu Service stores food items, prices. Order Service processes food orders. Delivery Service allocates riders, tracking. Payment handles transactions. Search enables restaurant discovery. Handle 1M restaurants, 1M daily orders. Scalability: restaurant sharding by location, order sharding, delivery fleet optimization. Implement: user ratings, order tracking, estimated delivery time, loyalty programs, subscription. Consider: restaurant SLA, surge pricing, fulfillment optimization, marketing analytics. Applications: food delivery platforms, restaurant aggregators.

Description: Design multi-sided platform connecting restaurants, delivery drivers, customers. Components: Restaurant Onboarding, Menu Management, Delivery Network, Consumer App, Analytics. Restaurant Onboarding integrates POS systems, accepts payments. Menu Management syncs with restaurants. Delivery Network optimizes driver assignments. Consumer App provides discovery, ordering. Analytics tracks performance metrics. Handle 500M users, 100M merchants, 1M drivers. Scalability: geographic partitioning, microservices architecture, real-time optimization. Implement: customer loyalty, business intelligence for restaurants, drive-through support. Consider: cost per delivery, driver retention, customer acquisition, marketplace economics. Applications: multi-platform marketplaces, aggregation services.

Description: Design system collecting, processing, storing user analytics data at petabyte scale. Components: Event Collection, Stream Processing, Data Warehouse, Query Engine, Visualization. Event Collection ingests user events from apps via SDK. Stream Processing cleans, transforms, deduplicates events using Kafka, Spark. Data Warehouse stores in columnar format (Parquet) on distributed storage. Query Engine executes analytical queries using distributed SQL. Visualization layer shows dashboards, reports. Handle 1B events/day, support real-time + batch analysis. Implement data retention policies, archival. Design schema evolution, backward compatibility. Applications in business intelligence, user behavior analysis, performance monitoring.

Description: Design ML-powered recommendation system suggesting videos based on user preferences, watch history, engagement. Components: User Profile Service, Content Understanding, Recommendation Model, Ranking Service. User Profile aggregates behavior: watch history, likes, search queries, time spent. Content Understanding extracts features: tags, duration, creators, categories. Recommendation Model uses collaborative filtering, content-based filtering, hybrid approach. Ranking Service applies business rules: freshness, diversity, novelty, user preferences. Handle cold start problem for new users/items. Design A/B testing framework for model improvements. Implement feedback loop for continuous learning. Applications in entertainment platforms, personalization engines.

Description: Design real-time system detecting fraudulent transactions combining rule-based and ML approaches. Components: Data Pipeline, Feature Engineering, Model Training, Real-time Detection, Investigation Tools. Data Pipeline ingests transaction, user, merchant data. Feature Engineering creates features: amount, frequency, location, device patterns. Model Training builds ensemble models detecting anomalies. Real-time Detection scores transactions, flags suspicious ones. Investigation Tools help analysts review, whitelist, blacklist. Handle false positives, minimize customer friction. Support explainability for model decisions. Design distributed inference for latency < 100ms. Applications in financial services, e-commerce, payment platforms.

Description: Design messaging system supporting group chats, one-to-one messaging, file sharing, read receipts at scale. Components: Message Service, Presence Service, Notification Service, Media Service, Search. Message Service handles message routing, delivery guarantees, ordering. Presence Service tracks online/offline status. Notification Service alerts offline users. Media Service stores photos, videos, documents. Search enables full-text search on messages. Handle 10M concurrent users, 1M messages/second. Implement end-to-end encryption for privacy. Design consistency model for message delivery. Implement message sync across devices. Applications in team communication, gaming chat, social messaging.

Description: Design global CDN delivering static content (images, videos, CSS, JS) with low latency from edge locations worldwide. Components: Origin Server, Edge Servers, Routing Service, Cache Management. Edge Servers cache content near users. Routing Service directs users to nearest edge using DNS/Anycast. Cache Management handles cache invalidation, update propagation. Support large file delivery using progressive download, range requests. Implement traffic optimization, bandwidth management. Handle content protection, DRM. Design for high availability, handling edge failures. Support video streaming with adaptive bitrate. Applications in web acceleration, video distribution, software delivery.

Description: Design real-time video conferencing supporting multiple participants, screen sharing, recording, chat. Components: Signaling Server, Media Router, STUN/TURN Servers, Recording Service, Transcoding. Signaling handles connection establishment, participant management. Media Router uses selective forwarding unit (SFU) or full mesh for optimal bandwidth. STUN/TURN help traverse firewalls, NAT. Recording captures conference for later playback. Transcoding converts formats for compatibility. Handle 100-1000 concurrent conferences, 1M participants daily. Implement quality adaptation based on bandwidth. Support mobile clients. Design screen sharing with optimal codec selection. Applications in remote meetings, online classes, telehealth.

Get SDE Ready

Learning often happens in classrooms
but it doesn’t have to.

+919625806829

 

support@getsdeready.com
WhatsApp Icon
close menu icon

Hi Instagram Fam!
Get a FREE Cheat Sheet on System Design.

close menu icon

Hi LinkedIn Fam!
Get a FREE Cheat Sheet on System Design

close menu icon

Loved Our YouTube Videos? Get a FREE Cheat Sheet on System Design.