Amazon Interview Questions
- DSA
- LLD
- HLD
Q1: LRU Cache
- Design and implement an LRU cache with given capacity.
- Discuss time and space complexities for get and put operations.
- Why is LinkedHashMap (or equivalent) often used? Can you implement without built-ins?
Q2: Longest Common Subsequence (LCS) Variant
- Given two strings, find the longest subsequence common to both.
- How would you optimize space complexity?
- How would you modify LCS to handle multiple strings?
Q3: Variants of LRU/LCS you could be asked
- LFU Cache design.
- Edit Distance (minimum operations to convert string A to B).
- Design a data structure for autocomplete with prefix queries.
Q4: Max consecutive 1s with at most k flips
Find the maximum length of consecutive 1s in a binary array if you are allowed to flip at most k zeros.
Q5: Generalized equal elements subarray
Given an integer array, you can change at most k elements to make them equal. Find the longest subarray of equal values.
Q6: Minimum flips for fixed-length subarray
In a binary array, determine the minimum number of flips needed so that at least one subarray of length m contains only 1s.
Q7: Circular array version
If the array is circular, compute the maximum number of consecutive 1s achievable by flipping at most k zeros.
Q8: Weighted job scheduling
Given jobs with startTime, endTime, and profit, find the maximum profit achievable without overlapping jobs.
Q9: Job scheduling with cooldown
Each job has a cooldown period after completion. Maximize profit while respecting this delay before starting the next job.
Q10: At most k jobs
You may select at most k jobs without overlap. Find the maximum profit possible.
Q11: Infinite repeatable jobs
If jobs can be repeated indefinitely (as long as they don’t overlap), find the maximum profit schedule.
Q12: Task scheduler with cooldown
Given tasks and cooldown n, find the minimum number of intervals required to finish all tasks.
Q13: Variable execution times
Extend Q9 where tasks have different execution durations, not just 1 unit.
Q14: Parallel execution
Up to k tasks can run simultaneously per interval. Find the minimum total time.
Q15: Streaming tasks
Tasks arrive in real-time. Design an online scheduler that respects cooldown n efficiently.
Q16: Basic calculator
Evaluate a string with integers, +, -, (, ), and spaces (no eval).
Q17: Add * and /*
Extend Q13 to also handle multiplication and division with precedence rules.
Q18: Add exponentiation
Include exponentiation (^) and handle parentheses correctly.
Q19: Streaming evaluation
Evaluate expressions as characters arrive in a stream, instead of full string upfront.
Q20: Reconstruct itinerary
Use all tickets exactly once starting from “JFK” to form the smallest lexicographical path.
Q21: Tickets reusable
If tickets can be reused, find the itinerary with the maximum number of flights from “JFK”.
Q22: Cycles allowed
Handle cycles in tickets while ensuring a valid itinerary with smallest lexical order.
Q23: Existence check
Instead of reconstructing the path, check if an itinerary exists that uses all tickets starting at “JFK”.
Q24: Smallest number after removing k digits
Remove exactly k digits from a number string to form the smallest integer.
Q25: Largest number
Modify Q21 to form the largest possible integer after removing k digits.
Q26: At most k removals
Allow removing up to k digits (not exactly). Find the smallest possible integer.
Q27: Streaming digits
Digits arrive one by one; decide online whether to keep or remove (at most k) to minimize the final number.
Q1. Bus Ticket Booking System
Design a scalable system with APIs and database schema to manage bus seat booking, handle seat allocation fairly, and ensure correctness under high concurrency (e.g., two users trying to book the same seat at the same time).
Q2. LRU Cache (Production-Ready)
Design and implement an LRU (Least Recently Used) cache as a reusable library. It should be thread-safe, efficient, and scalable for real-world applications.
Q3. Parking Lot System
Design a parking lot system supporting multiple vehicle types (car, bike, bus, etc.), flexible billing rules (hourly, daily), and efficient space allocation.
Q4. Online Food Ordering System
Design an end-to-end system for customers to browse restaurants, place orders, make payments, and track delivery. Include APIs, DB schema, and scalability considerations.
Q5. Ride Hailing App (Uber/Ola)
Design a system to handle ride requests, driver allocation (matching riders to nearby drivers), trip tracking, and payment processing.
Q6. Ticket Representation
Decide how to represent airline tickets in code (adjacency list, adjacency matrix, or custom structure) for efficient route reconstruction.
Q7. Multiple Tickets Between Cities
Handle cases where multiple tickets exist between the same source and destination. Ensure correct representation and traversal.
Q8. ItineraryBuilder Helper Class
Design a helper class that stores routes and builds the itinerary while maintaining lexicographical order as required.
Q9. NumberReducer Class
Implement a class with a method reduce(num, k) that removes k digits from a number to form the smallest possible integer.
Q10. Edge Case Testing for NumberReducer
Identify and test edge cases such as "100200", "10", "9", etc., ensuring correctness under all conditions.
Q11. Code Reusability (Strings & Integers)
Refactor the logic so that it works for both numeric strings and integer inputs in a clean, reusable way.
Q12. AllOne Class Implementation
Implement the AllOne data structure with proper encapsulation of Node and Bucket objects for O(1) increment, decrement, getMaxKey, and getMinKey operations.
Q13. Iterability
Extend the AllOne class to support iteration so that it can be used in a loop (for key in allOne:).
Q14. Persistence
Add persistence to the AllOne data structure so it can be saved to disk and reloaded across sessions.
Q15. SubarraySolver Utility Class
Create a clean API, e.g., SubarraySolver.maxSumWithDeletion(arr), that solves the maximum subarray sum problem with at most one deletion.
Q16. Unit Tests for SubarraySolver
Design test cases for tricky arrays like [1,-2,0,3], [1,-2,-2,3], [-1,-1,-1,-1] to validate correctness.
Q17. Return Indices of Subarray
Extend the class so that it not only returns the maximum sum but also the indices of the subarray achieving this sum.
Q18. DuplicateRemover Utility
Implement a utility class with method removeSmallest(s) that removes duplicate letters to return the smallest lexicographical string with unique characters.
Q19. Extended Input Set
Modify the function to also handle strings containing uppercase letters, digits, or special characters.
Q20. Unit Testing DuplicateRemover
Write test cases for tricky inputs such as "bcabc", "cbacdcbc", "aaaaa" to ensure correct behavior.
Q21. MatrixAnalyzer Class
Design a class MatrixAnalyzer with a method rowWithMaxOnes(mat) that finds the row containing the maximum number of 1s.
Q22. Unit Tests for MatrixAnalyzer
Write tests for scenarios like:
- All rows having equal number of ones.
- Only one row having maximum ones.
- A matrix with a single row or a single column.
Q23. Handling Ties
Extend the class so that instead of returning just one row, it can also return all rows that tie for the maximum number of 1s.
Q1. Book Recommendation System
Design a scalable and low-latency recommendation system that suggests books based on user preferences, history, and trends. Consider personalization, data storage, and real-time response.
Q2. URL Shortener (like bit.ly)
Design a system to shorten long URLs into unique short links with fast redirection. Handle scalability, analytics (clicks, geo data), and high availability.
Q3. Notification System
Build a notification system that supports Email, SMS, and Push notifications. Consider message queuing, retries, prioritization, and user preferences.
Q4. E-commerce Product Catalog
Design a product catalog system with efficient search, filtering, and sorting capabilities. Handle millions of products with scalability and quick retrieval.
Q5. File Storage System (like Google Drive)
Design a file storage and sharing system supporting uploads, access control, collaboration, and versioning. Ensure reliability, scalability, and efficient storage.
Q6. Airline Itinerary Planner
Design a system to compute itineraries from flight tickets at large scale (millions of records). Focus on route optimization and query efficiency.
Q7. Scaling Itinerary Searches
Modify the itinerary planner to handle thousands of concurrent user searches. Consider caching, indexing, and distributed computation.
Q8. Fault Tolerance in Itinerary Data
Add resilience to the itinerary planner when ticket data is missing, inconsistent, or delayed. Ensure correctness and graceful degradation.
Q9. Banking System Transaction IDs
If number reduction (removing digits for optimization) is part of a banking system, design how it would integrate securely and efficiently.
Q10. Continuous Number Streams
Adapt the number reduction logic to work with continuous incoming streams of digits instead of a single static input.
Q11. High Throughput Optimization
Ensure the number reduction system can handle millions of requests per second while maintaining accuracy and low latency.
Q12. Real-time Analytics (Word Frequency Counter)
Design an architecture to count word frequencies in real-time search queries, ensuring scalability and low-latency updates.
Q13. Distributed Data Structure
Distribute the key-value frequency data structure across multiple servers while keeping operations (increment, getMax, getMin) efficient.
Q14. Memory Limits with Huge Keys
Handle scenarios where the number of unique keys is extremely large by optimizing memory usage (e.g., compression, eviction, sharding).
Q15. Stock Trading Use Case
Apply the maximum subarray sum with one deletion logic to stock trading (ignoring at most one bad day). Ensure scalability for massive datasets.
Q16. Streaming Input Arrays
Adapt the max subarray sum algorithm to handle very large arrays coming as a continuous data stream.
Q17. Real-time Monitoring Dashboard
Integrate the max subarray sum computation into a live dashboard that updates continuously as new data arrives.
Q18. Compiler’s Lexer Optimization
Use duplicate-removal logic for compilers to remove redundant tokens while maintaining correct order in lexical analysis.
Q19. Real-time String Processing
Scale string de-duplication to handle millions of strings in real-time (e.g., logs, social media streams).
Q20. Multi-language Text (Unicode, Emojis)
Extend duplicate-removal logic to support complex characters including Unicode scripts and emojis.
Q21. Image Processing Use Case
Apply the “row with max ones” problem to image analysis, e.g., finding the row with the brightest pixels.
Q22. Very Large Matrices (Chunking)
Handle matrices too large to fit in memory by processing them in chunks or using streaming techniques.
Q23. Distributed Matrix Computation
Scale matrix analysis across multiple servers to efficiently handle very high-dimensional datasets.
