88 Algorithm Design and Optimization Interview Questions

All 88 questions

Design and implement an LRU cache with O(1) get and put operations.
Asked in 4 of 374 interviews · last asked Sep 10 · Write code · Mid-level
Show answer
I use a hash map and a doubly linked list for average O(1) get and put operations. Each successful get or put moves the key to the most recently used end. When capacity is exceeded, I remove the least recently used key. Python's OrderedDict provides this structure.
- Hash map operations take O(1) time on average; cache space is O(capacity).
- A missing key returns -1 and does not change the cache.
- Updating an existing key changes its value and recency without increasing the cache size.
- A cache with zero capacity stores no entries.
Python
```
from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.capacity, self.items = max(0, capacity), OrderedDict()
    def get(self, key):
        if key not in self.items: return -1
        self.items.move_to_end(key); return self.items[key]
    def put(self, key, value):
        self.items[key] = value; self.items.move_to_end(key)
        if len(self.items) > self.capacity: self.items.popitem(last=False)
```
What the interviewer checks: The interviewer checks whether you can combine fast lookup with recency tracking and handle updates and eviction correctly.
Other ways it was asked
- “How would you design and implement an LRU cache?”
- “Design and implement an LRU cache with get(key) and put(key, value) operations.”
- “Design an LRU cache with get(key) and put(key, value) operations that run in O(1) time.”
Given that some cache responses are large, and recently used or recently added entries tend to be used again soon, what cache eviction approach makes sense?
Asked once · last asked Jul 27 · Scenario · Mid-level
Other ways it was asked
- “Given limited cache capacity, some large responses, and a pattern where recently used or added entries are likely to be used again soon, what cache eviction approach would you use to keep good performance?”
What are the time and space complexities of the `allow` operation in a rolling-window rate limiter?
Asked once · last asked Sep 6 · Concept · Mid-level
Other ways it was asked
- “Why is the `allow` operation in a rolling-window rate limiter amortized O(1), and what are its time and space complexities?”
How would you detect conflicting robot paths and use that information to optimize traffic?
Asked once · last asked Sep 25 · Design · Senior
Other ways it was asked
- “How would you detect conflicting robot paths in a traffic-control service?”
How would you prevent one robot from waiting a long time for another robot to complete its entire route?
Asked once · last asked Sep 25 · Scenario · Senior
Other ways it was asked
- “How would you prevent one robot from waiting until another robot completes its entire route?”
What data structure ensures fairness in checkout processing, and how do we prevent the payment system from overloading?
Asked once · last asked Oct 6 · Design · Mid-level
Other ways it was asked
- “What data structure would you use to ensure fair first-come-first-served processing for checkout payments while preventing the payment system from being overloaded?”
How would you modify an API client to retrieve an account's complete transaction history rather than just one time range?
Asked once · last asked Mar 5 · Scenario · Mid-level
When retrieving transaction history in batches while moving backward through time, should an empty batch stop further requests?
Asked once · last asked Mar 5 · Scenario · Mid-level
If an account's opening date is unavailable, how would you retrieve its transaction history?
Asked once · last asked Mar 5 · Scenario · Mid-level
How would you optimize transaction-history retrieval if the system has been running for 20 years but the account is only one year old?
Asked once · last asked Mar 5 · Scenario · Senior
Implement a thread-safe in-memory cache storing companies with names and candidates with passport numbers and scores; generate unique integer company IDs, support company lookup by ID, efficiently find all candidates by passport number, and update a candidate's score within a specified company.
Asked once · last asked Mar 6 · Write code · Senior
Other ways it was asked
- “Implement a thread-safe in-memory cache for recruiting companies. Each company has a name and candidates, and each candidate has a passport number and score. Generate a unique integer ID when storing a company, support lookup by ID, index candidates by passport number, and allow a candidate's score to be updated within a specified company.”
How would you design passport-number lookups and candidate score updates to avoid searching every company?
Asked once · last asked Mar 6 · Design · Senior
How would you design a thread-safe collection structure for a company-and-candidate cache, and what should a passport-number index map to to support future updates?
Asked once · last asked Mar 6 · Design · Senior
How would you find and display nearby restaurants based on a customer's location?
Asked once · last asked Mar 10 · Scenario · Mid-level
Other ways it was asked
- “How would you determine whether a restaurant is near a customer's location?”
How would you design a thread-safe LRU cache that supports `get(key)` and `put(key, value)` in O(1) average time? What core data structures would you combine, and what would need locking?
Asked once · last asked Mar 16 · Design · Senior
A robot is blocked by a wide hill, its sensors detect an obstacle, its camera has only 3 cm of depth vision, and it cannot back up. What fallback navigation algorithm would you use to reach the goal on the other side?
Asked once · last asked Mar 30 · Scenario · Senior
How would you sanitize a JSON notification message before sending it by replacing sensitive values, such as passwords or tokens, including in nested data?
Asked once · last asked Mar 31 · Write code · Mid-level
How does a search work in OpenSearch, from receiving a query to producing results?
Asked once · last asked Apr 27 · Concept · Senior
How would you implement a program to distinguish apples from oranges using traditional methods, and how would you approach it with machine learning?
Asked once · last asked May 7 · Scenario · Mid-level
Given a single-threaded batch binary that performs the same operation over 100 TB or 1 PB of data, how would you estimate its runtime and decide whether to run, stop, or refactor it?
Asked once · last asked May 19 · Scenario · Senior
How can you implement similarity search without a vector database?
Asked once · last asked May 22 · Scenario · Mid-level
You have a very large file that cannot fit in memory, with one URL per line and possible duplicates. How would you process it to produce a file containing each unique URL and its number of appearances?
Asked once · last asked May 25 · Write code · Senior
Create an algorithm that adjusts the ingredient amounts in the JSON recipe so the pancakes contain as close as possible to 350 kilocalories. You may preprocess or edit the data if needed.
Asked once · last asked Jun 26 · Write code
Why not simply concatenate all 4,000 transactions into one string?
Asked once · last asked Jul 8 · Concept · Junior
Would concatenating all transactions into one string be more efficient in terms of time or memory?
Asked once · last asked Jul 8 · Concept · Junior
How does a network using Nakamoto consensus determine which of two parallel branches is valid after a fork?
Asked once · last asked Jul 8 · Concept · Mid-level
How would you calculate the mean of a column in a dataset that is too large to fit in memory?
Asked once · last asked Jul 21 · Scenario · Mid-level
In backend code, where do different algorithmic time complexities arise, and how can you accidentally introduce quadratic complexity?
Asked once · last asked Jul 23 · Concept · Mid-level
What are some algorithms designed for the NISQ era?
Asked once · last asked Jul 25 · Concept · Mid-level
How would you keep the cache efficient when entries need to be evicted and the cache has limited size?
Asked once · last asked Jul 27 · Scenario · Mid-level
In a bounded LRU cache, what should the setter do when adding or updating an entry?
Asked once · last asked Jul 27 · Write code · Mid-level
In an LRU cache, what should the getter do when retrieving an entry?
Asked once · last asked Jul 27 · Write code · Mid-level
When setting a value in an LRU cache, how should you handle a key that already exists?
Asked once · last asked Jul 27 · Write code · Mid-level
What problem does a ride-relocation algorithm solve, and how does it work?
Asked once · last asked Aug 4 · Concept · Mid-level
How would you prioritize riders for assignment to instant deliveries?
Asked once · last asked Aug 4 · Scenario · Mid-level
How would you determine the relative weights of factors in a rider-assignment algorithm?
Asked once · last asked Aug 4 · Concept · Mid-level
If five available riders are within the geofence, how would a ride-assignment algorithm choose among them?
Asked once · last asked Aug 4 · Scenario · Mid-level
How would you set a minimum rider income threshold in a ride-assignment system, and handle riders whose income falls below it?
Asked once · last asked Aug 4 · Scenario · Mid-level
Other ways it was asked
- “What minimum income threshold should a ride-assignment system enforce for riders, and how should it handle assignments that fall below that threshold?”
Design an in-memory, thread-safe cache using an LRU or LFU eviction policy.
Asked once · last asked Aug 10 · Design · Senior
In a Python service, when would you choose a list, set, dict, or collections.deque for a hot path, and what time-complexity trade-offs are you optimizing for?
Asked once · last asked Aug 13 · Concept · Mid-level
How would you implement an LRU cache in Python with O(1) average-time get and put operations, and what invariants would you maintain?
Asked once · last asked Aug 13 · Write code · Senior
When implementing an LRU cache, how do you handle put(key, value) when the key already exists versus when capacity is exceeded, and what pointer updates are required?
Asked once · last asked Aug 13 · Write code · Senior
When an LRU cache exceeds its capacity, which node do you evict, and how do you remove it from both the linked list and hash map while keeping the list well formed?
Asked once · last asked Aug 13 · Write code · Senior
How would you design an account number generator for a bank account?
Asked once · last asked Aug 14 · Design · Mid-level
How would you generate a unique account number using the current millisecond timestamp?
Asked once · last asked Aug 14 · Scenario · Mid-level
How do you decide whether to optimize an O(n²) section by changing the algorithm versus micro-optimizing constants, and what evidence do you gather first?
Asked once · last asked Aug 14 · Scenario · Senior
In a tight loop over a large list, what kinds of changes typically improve performance without changing complexity, such as reducing allocations or changing data structures or branch behavior?
Asked once · last asked Aug 14 · Concept · Senior
Why would you choose the token bucket algorithm over other rate-limiting algorithms?
Asked once · last asked Aug 19 · Concept · Senior
Other ways it was asked
- “Why would you choose only the token bucket algorithm for a rate limiter?”
How would you structure the matcher for fuzzy data points like transaction amounts and card numbers?
Asked once · last asked Aug 26 · Design · Senior
What would you recommend we do if we get through a couple of layers of searching and find two transactions that match our reduced criteria?
Asked once · last asked Aug 26 · Scenario · Senior
How do we decide between two transactions if they have the same number of matching fields but different values?
Asked once · last asked Aug 26 · Scenario · Senior
Which data structures should you avoid sharing between threads without proper synchronization?
Asked once · last asked Sep 1 · Concept · Mid-level
Can you implement a call-with-retry function with exponential backoff, jitter, max retry count, and non-retryable error handling?
Asked once · last asked Sep 4 · Write code · Senior
Design a data structure for a rolling window rate limiter.
Asked once · last asked Sep 6 · Write code · Senior
What approach would you use for a rolling-window rate limiter, and what trade-offs would you consider?
Asked once · last asked Sep 6 · Design · Senior
For a rolling-window rate limiter that stores exact request timestamps, how does a worst-case burst affect memory use and per-request cost, and does the operation remain O(1)?
Asked once · last asked Sep 6 · Scenario · Senior
How would you design and build a type-ahead search feature?
Asked once · last asked Sep 7 · Design · Senior
Why would you use hash maps and a doubly linked list to implement an LRU cache?
Asked once · last asked Sep 9 · Concept · Mid-level
Other ways it was asked
- “Why are you using hash maps and a doubly linked list for the LRU cache?”
Can you describe a situation where your understanding of data structures and algorithms significantly improved the performance or efficiency of a project you were working on?
Asked once · last asked Sep 10 · Behavioral · Mid-level
Other ways it was asked
- “Can you describe a specific example of how a data structure improved performance in a software project?”
Describe a difficult coding or puzzle problem you solved that had multiple plausible approaches. What were its key constraints?
Asked once · last asked Sep 15 · Write code · Mid-level
How would you test a parallel architecture that uses parallel processing and a genetic algorithm?
Asked once · last asked Sep 22 · Scenario · Mid-level
How would you detect whether a robot's path conflicts with another robot or with a shape on the map?
Asked once · last asked Sep 25 · Scenario · Senior
How would you plan routes for multiple robots, and which algorithms would you consider?
Asked once · last asked Sep 25 · Design · Senior
How would you plan robot routes so a traffic controller can make robots wait safely?
Asked once · last asked Sep 25 · Design · Senior
Which route-planning algorithms would let a traffic controller assign robot waiting points and traffic windows?
Asked once · last asked Sep 25 · Design · Senior
After detecting route conflicts, how would you plan and sequence robot routes?
Asked once · last asked Sep 25 · Design · Senior
How could a deadlock occur when scheduling robots across three routes?
Asked once · last asked Sep 25 · Scenario · Senior
Using only local optimization, how would you ensure robots keep making progress without deadlocking?
Asked once · last asked Sep 25 · Design · Senior
How would you handle a traffic conflict if a robot's already-dispatched route needed to be reversed because another robot was closer?
Asked once · last asked Sep 25 · Scenario · Senior
What features can a fleet management system use to prevent robot collisions and manage traffic?
Asked once · last asked Sep 25 · Design · Senior
How would you handle close intersections and prevent deadlocks when robots rotate or turn near buffers?
Asked once · last asked Sep 25 · Scenario · Senior
How would you manage robot traffic in shared spaces with pedestrians or forklifts?
Asked once · last asked Sep 25 · Scenario · Senior
How would you detect nearby obstacles and safely slow a robot down?
Asked once · last asked Sep 25 · Scenario · Senior
How does autoencoder-based compression compare with ZIP compression, and what are the pros and cons of each?
Asked once · last asked Sep 29 · Concept · Mid-level
Other ways it was asked
- “How does an autoencoder compare with the ZIP algorithm, including the pros and cons?”
What is the most algorithmically challenging bug or performance issue you have solved in a SaaS or open-source project, and what made it difficult?
Asked once · last asked Oct 4 · Behavioral · Mid-level
What is the time complexity of keyset pagination?
Asked once · last asked Oct 19 · Concept · Mid-level
Other ways it was asked
- “What is the time complexity of this keyset pagination approach?”
When handling a stream of data that must be stored securely, how would you manage memory and choose data structures?
Asked once · last asked Jan 23 · Scenario · Mid-level
What are the trade-offs of static memory allocation and hash maps when securely storing a stream of incoming data?
Asked once · last asked Jan 23 · Concept · Mid-level
What algorithms can be used in an AI-powered product search system?
Asked once · last asked Mar 27 · Concept · Mid-level
Other ways it was asked
- “How can AI be used to improve a product search system?”
- “What techniques or modules can be used to implement AI-powered product search?”
Describe a challenging constrained coding problem you solved, other than a shortest-path problem.
Asked once · last asked Sep 15 · Write code · Mid-level
Other ways it was asked
- “Describe a harder constrained coding problem you solved other than a shortest-path problem.”
- “Describe a harder constrained coding problem you solved other than a shortest-path problem, including its constraints and a less obvious invariant or reduction.”
What is the sliding-window rate-limiting pattern?
Asked once · last asked Feb 11 · Concept · Mid-level
When navigating around an obstacle, how far should a robot continue searching for a route, and when should it stop?
Asked once · last asked Mar 30 · Scenario · Mid-level
Can you tell me what path planning is?
Asked once · last asked Apr 16 · Concept · Junior
How do you choose an implementation approach during a live-coding exercise, and how do you compare it with alternatives?
Asked once · last asked Jul 31 · Scenario
How is an inverted index represented?
Asked once · last asked Aug 3 · Concept · Junior
How could you improve the efficiency of the Minesweeper algorithm?
Asked once · last asked Aug 28 · Scenario · Mid-level
Other ways it was asked
- “How could you reduce the number of cells the Minesweeper algorithm checks?”
How do you break down a coding problem and explain your reasoning?
Asked once · last asked Sep 15 · Scenario
What is diffing?
Asked once · last asked Oct 21 · Concept · Junior

How this list is made

Every question here was asked by a real interviewer in a real job interview that a candidate ran MeetAssist in. After the call, the interviewer's questions are pulled from the transcript. Practice sessions, tests, exams and anything that was not a job interview are dropped.

Questions are rewritten so they make sense on their own: names of people, employers and clients are removed, and speech-to-text mistakes are fixed. Small talk, logistics and questions about one candidate's own résumé are left out. Rephrasings of the same question are merged, and the count is the number of different interviews it came up in.

The interviews come from candidates who use MeetAssist, so they lean towards software, data and AI roles: the shares describe these interviews, not every Data Structures and Algorithms interview. Answers to the most asked questions are written and checked by an editor; a "common mistake" is shown only when reviews of real answers in these interviews show it, with the count.

374 interviews, 269 candidates, Sep 2025 to Oct 2026. Updated every month with new interviews.

All 88 questions

Design and implement an LRU cache with O(1) get and put operations.

Given that some cache responses are large, and recently used or recently added entries tend to be used again soon, what cache eviction approach makes sense?

What are the time and space complexities of the `allow` operation in a rolling-window rate limiter?

How would you detect conflicting robot paths and use that information to optimize traffic?

How would you prevent one robot from waiting a long time for another robot to complete its entire route?

What data structure ensures fairness in checkout processing, and how do we prevent the payment system from overloading?

How would you modify an API client to retrieve an account's complete transaction history rather than just one time range?

When retrieving transaction history in batches while moving backward through time, should an empty batch stop further requests?

If an account's opening date is unavailable, how would you retrieve its transaction history?

How would you optimize transaction-history retrieval if the system has been running for 20 years but the account is only one year old?

Implement a thread-safe in-memory cache storing companies with names and candidates with passport numbers and scores; generate unique integer company IDs, support company lookup by ID, efficiently find all candidates by passport number, and update a candidate's score within a specified company.

How would you design passport-number lookups and candidate score updates to avoid searching every company?

How would you design a thread-safe collection structure for a company-and-candidate cache, and what should a passport-number index map to to support future updates?

How would you find and display nearby restaurants based on a customer's location?

How would you design a thread-safe LRU cache that supports `get(key)` and `put(key, value)` in O(1) average time? What core data structures would you combine, and what would need locking?

A robot is blocked by a wide hill, its sensors detect an obstacle, its camera has only 3 cm of depth vision, and it cannot back up. What fallback navigation algorithm would you use to reach the goal on the other side?

How would you sanitize a JSON notification message before sending it by replacing sensitive values, such as passwords or tokens, including in nested data?

How does a search work in OpenSearch, from receiving a query to producing results?

How would you implement a program to distinguish apples from oranges using traditional methods, and how would you approach it with machine learning?

Given a single-threaded batch binary that performs the same operation over 100 TB or 1 PB of data, how would you estimate its runtime and decide whether to run, stop, or refactor it?

How can you implement similarity search without a vector database?

You have a very large file that cannot fit in memory, with one URL per line and possible duplicates. How would you process it to produce a file containing each unique URL and its number of appearances?

Create an algorithm that adjusts the ingredient amounts in the JSON recipe so the pancakes contain as close as possible to 350 kilocalories. You may preprocess or edit the data if needed.

Why not simply concatenate all 4,000 transactions into one string?

Would concatenating all transactions into one string be more efficient in terms of time or memory?

How does a network using Nakamoto consensus determine which of two parallel branches is valid after a fork?

How would you calculate the mean of a column in a dataset that is too large to fit in memory?

In backend code, where do different algorithmic time complexities arise, and how can you accidentally introduce quadratic complexity?

What are some algorithms designed for the NISQ era?

How would you keep the cache efficient when entries need to be evicted and the cache has limited size?

In a bounded LRU cache, what should the setter do when adding or updating an entry?

In an LRU cache, what should the getter do when retrieving an entry?

When setting a value in an LRU cache, how should you handle a key that already exists?

What problem does a ride-relocation algorithm solve, and how does it work?

How would you prioritize riders for assignment to instant deliveries?

How would you determine the relative weights of factors in a rider-assignment algorithm?

If five available riders are within the geofence, how would a ride-assignment algorithm choose among them?

How would you set a minimum rider income threshold in a ride-assignment system, and handle riders whose income falls below it?

Design an in-memory, thread-safe cache using an LRU or LFU eviction policy.

In a Python service, when would you choose a list, set, dict, or collections.deque for a hot path, and what time-complexity trade-offs are you optimizing for?

How would you implement an LRU cache in Python with O(1) average-time get and put operations, and what invariants would you maintain?

When implementing an LRU cache, how do you handle put(key, value) when the key already exists versus when capacity is exceeded, and what pointer updates are required?

When an LRU cache exceeds its capacity, which node do you evict, and how do you remove it from both the linked list and hash map while keeping the list well formed?

How would you design an account number generator for a bank account?

How would you generate a unique account number using the current millisecond timestamp?

How do you decide whether to optimize an O(n²) section by changing the algorithm versus micro-optimizing constants, and what evidence do you gather first?

In a tight loop over a large list, what kinds of changes typically improve performance without changing complexity, such as reducing allocations or changing data structures or branch behavior?

Why would you choose the token bucket algorithm over other rate-limiting algorithms?

How would you structure the matcher for fuzzy data points like transaction amounts and card numbers?

What would you recommend we do if we get through a couple of layers of searching and find two transactions that match our reduced criteria?

How do we decide between two transactions if they have the same number of matching fields but different values?

Which data structures should you avoid sharing between threads without proper synchronization?

Can you implement a call-with-retry function with exponential backoff, jitter, max retry count, and non-retryable error handling?

Design a data structure for a rolling window rate limiter.

What approach would you use for a rolling-window rate limiter, and what trade-offs would you consider?

For a rolling-window rate limiter that stores exact request timestamps, how does a worst-case burst affect memory use and per-request cost, and does the operation remain O(1)?

How would you design and build a type-ahead search feature?

Why would you use hash maps and a doubly linked list to implement an LRU cache?

Can you describe a situation where your understanding of data structures and algorithms significantly improved the performance or efficiency of a project you were working on?

Describe a difficult coding or puzzle problem you solved that had multiple plausible approaches. What were its key constraints?

How would you test a parallel architecture that uses parallel processing and a genetic algorithm?

How would you detect whether a robot's path conflicts with another robot or with a shape on the map?

How would you plan routes for multiple robots, and which algorithms would you consider?

How would you plan robot routes so a traffic controller can make robots wait safely?

Which route-planning algorithms would let a traffic controller assign robot waiting points and traffic windows?

After detecting route conflicts, how would you plan and sequence robot routes?

How could a deadlock occur when scheduling robots across three routes?

Using only local optimization, how would you ensure robots keep making progress without deadlocking?

How would you handle a traffic conflict if a robot's already-dispatched route needed to be reversed because another robot was closer?

What features can a fleet management system use to prevent robot collisions and manage traffic?

How would you handle close intersections and prevent deadlocks when robots rotate or turn near buffers?

How would you manage robot traffic in shared spaces with pedestrians or forklifts?

How would you detect nearby obstacles and safely slow a robot down?

How does autoencoder-based compression compare with ZIP compression, and what are the pros and cons of each?

What is the most algorithmically challenging bug or performance issue you have solved in a SaaS or open-source project, and what made it difficult?

What is the time complexity of keyset pagination?

When handling a stream of data that must be stored securely, how would you manage memory and choose data structures?

What are the trade-offs of static memory allocation and hash maps when securely storing a stream of incoming data?

What algorithms can be used in an AI-powered product search system?