Practice DSA interview questions

You are on the Search Experience team. We need to build the backend data structure for the search bar type-ahead feature. Implement a class to insert words and efficiently check if any stored word starts with a given prefix.

You are on the Data Infrastructure team at X. A real-time stream of hashtags is coming in. Write an algorithm to find the top K most frequent hashtags from a list of N tags without fully sorting the array.

A user opens Instagram and follows K accounts. The backend fetches the latest posts from each account, which are already sorted by timestamp. Merge these K sorted lists into a single chronological feed.

You are protecting Stripe APIs from spam. Given a string of incoming requests (characters), find the length of the longest continuous sequence of unique requests before a duplicate IP/user hits the system.

You are building the syntax highlighter for a new web IDE. Write a function that takes a string of brackets and determines if the code blocks are properly opened and closed in the correct order.

You are a graphics engineer. An image is represented by a 2D matrix of integers (colors). Given a starting pixel (sr, sc) and a new color, change the color of the connected region sharing the original color.

Our database is overloaded. Build an in-memory cache of capacity C. It should support get(key) and put(key, value) in O(1) time. When capacity is reached, it must evict the least recently used item.

A city map is a directed graph where edges represent roads and weights represent traffic times. Find the minimum time required for a signal (or driver) to reach all nodes from a given starting node.

You are loading an Amazon delivery truck with weight capacity W. Given an array of package weights, determine if the packages can be partitioned into two subsets with equal total weight to balance the truck.

You are building the shuffle feature for a Spotify playlist. Write an algorithm that takes an array of song IDs and randomly shuffles it such that every permutation is equally likely.

You are building a version control system like Git. Given the commit tree, write an algorithm to find the lowest common ancestor of two distinct branches to determine the merge base.

You are writing the formula evaluation engine for Microsoft Excel. Users can reference other cells in their formulas. Write an algorithm to detect if there is a circular reference (e.g., A1 depends on B1, which depends on A1) that would cause an infinite loop.

You are a UI engineer on the Google Chrome team. Implement the browser history system that allows a user to visit new URLs, navigate 'back' up to a certain number of steps, and navigate 'forward'.

You are a backend engineer at Zoom. Given a massive list of scheduled video meeting time intervals (start and end times), determine the minimum number of server instances (or meeting rooms) required to host all simultaneous calls without dropping connections.

You are building the location services for Zomato. Given a user's GPS coordinates (treated as the origin [0,0]) and a list of restaurant coordinates, find the K closest restaurants to the user to display on their app.

You are working on Airbnb's host dashboard. A host has manually entered availability blocks that are overlapping and messy. Write an algorithm to consolidate all overlapping date ranges into a clean list of continuous available blocks.

You are programming a Kiva robot in an Amazon fulfillment center. The warehouse is a grid where 0 represents an open path and 1 represents a shelf blocking the path. Find the shortest path from the starting dock to the target shipping bay.

You are analyzing LinkedIn's social graph. You are given an N x N matrix representing direct connections between users. Write an algorithm to calculate the total number of distinct, isolated professional networks (connected components) on the platform.

You are building a quantitative trading bot. Given an array where the i-th element is the price of a given stock on day i, write an algorithm to find the maximum profit you can achieve with exactly one buy and one sell operation.

A massive codebase has a bug. You know the latest commit is bad, and an old commit was good. Each commit is built upon the previous one. Write the algorithm that powers 'git bisect' to find the exact first bad commit with the absolute minimum number of API calls.

You are building the 'Did you mean?' suggestion feature for Google Docs. Given a misspelled word and a dictionary word, calculate the minimum number of character insertions, deletions, or substitutions required to convert the typo into the correct word.

A web crawler retrieves a URL string where all spaces have been removed (e.g., 'astraplatformrocks'). Given a dictionary of valid English words, write an algorithm to determine if the string can be cleanly segmented into a sequence of dictionary words.

You are building the routing engine for Skyscanner. Given a list of flights with prices, a starting city, a destination, and a maximum number of layovers (K), find the absolute cheapest flight route that satisfies the layover constraint.

You are building the core ticket reservation logic for Ticketmaster. A user tries to book an event from start_time to end_time. Write a class that validates the booking, returning true if the time slot is perfectly open, or false if it overlaps with an existing reservation.

You are building a time-series feature for a NoSQL database. Write a data structure that can store multiple values for the same key at different timestamps, and retrieve the key's value at a specific timestamp (or the closest preceding timestamp).

You are analyzing server logs for a bank. You have an array representing daily transaction deltas (positive for deposits, negative for withdrawals). Write an algorithm to find the total number of continuous periods (subarrays) where the net transaction sum equals exactly zero.

You are building an accessibility tool simulating an old Nokia T9 phone keyboard. Given a string containing digits from 2-9, return all possible letter combinations (words) that the number sequence could represent.

You are building the ad insertion engine for YouTube. The video timeline is represented as a list of non-overlapping ad blocks (intervals). A new sponsor buys an ad block. Insert this new ad into the timeline, merging it with existing ads if the times overlap.

A Discord server has millions of members, but only a few are constantly active. Design a Least Frequently Used (LFU) cache to keep the data of the most active users in memory. If memory is full, evict the user with the lowest message count.

You are a physics engine developer for a 2D side-scrolling game. You are given an array representing the height map of a rocky terrain. Write an algorithm to calculate exactly how many units of rainwater will be trapped in the valleys after a heavy storm.