DSA / Hashmaps Interview Questions 2026

Implement a function that checks if a string of brackets is valid. Brackets: (), [], {}. Must handle nested brackets.

Design an in-memory rate limiter that allows at most N requests per user per minute. Given a stream of {userId, timestamp} requests, return true if the request should be allowed or false if it should be throttled. Implement using JavaScript.

Given an array of intervals, merge all overlapping intervals. Return the minimum number of intervals after merging. Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

Implement an LRU (Least Recently Used) cache with O(1) get and O(1) put. Explain why a naive HashMap alone doesn't solve this.

You have a log file where each line has a timestamp and user ID. Find the K users who appear most frequently in the last N minutes. The file is 100GB and is being written to in real-time.

Design a data structure that supports push, pop, and getMin in O(1) time and O(1) space (beyond the stack itself).

Given a binary tree, find the longest path between any two nodes (not necessarily through root). You have 30 minutes.

You're implementing a rate limiter using a sliding window algorithm. Given a stream of timestamps (Unix milliseconds), return true if a request is within the limit of 100 requests per minute. The stream can have 1 billion events.

Given a binary tree, check if it's a valid Binary Search Tree. Consider all possible edge cases.

You have a function that runs in O(n²) time and your interviewer says 'this is too slow for n=10 million.' The function finds all pairs of numbers in an array that sum to a target. Optimize it to O(n).

Implement a min-heap data structure from scratch. Show insert and extractMin operations.

Design an algorithm to find the shortest path through a maze represented as a 2D grid. 0 = open, 1 = wall. Start at top-left, end at bottom-right.

Find the first missing positive integer in an unsorted array. Must be O(n) time and O(1) extra space.

Implement a stack using only two queues. Then implement a queue using only two stacks.

Given an array of n integers, find all triplets that sum to zero. Remove duplicates from the result.

Implement a function that detects duplicate transaction IDs within a 5-minute time window. Given an array of {id, timestamp} objects, return all IDs that appear more than once within any 5-minute rolling window. What data structure would you use and why?

Given a string with brackets, check if it's valid. Valid: every open bracket has a matching close bracket in correct order.

Implement merge sort and explain its advantages over quicksort.

Implement binary search on a rotated sorted array (e.g., [4,5,6,7,0,1,2]).

Write a function that checks if two strings are anagrams of each other. Handle Unicode characters.

Given a list of payment events, each with a merchant ID and an amount, use a HashMap to return the top 3 merchants by total transaction volume. How would you handle ties? Write the complete solution.

Given a binary tree, return the level-order traversal as a list of lists.

Write a function to detect if a linked list has a cycle. Can you do it without extra space?

How would you design and implement an autocomplete system? Focus on the data structure and ranking.

Implement a stack that supports push, pop, top, and getMin in O(1) time.

Write a function to compute the power set (all subsets) of a given set.

Given an array of integers, find two numbers that sum to a target. Optimize for O(n) time and O(n) space.

Implement a function that finds the longest common subsequence (LCS) of two strings.

Implement LRU Cache with O(1) get and put operations.

Given a 2D grid, find the shortest path from start to end avoiding obstacles.

Write a function to find the longest palindromic substring in a string. What is the optimal approach?

Explain and implement the Dutch National Flag algorithm for sorting an array with only 3 distinct values.

Write a function to find all valid parentheses combinations for n pairs.

Implement topological sort on a directed acyclic graph (DAG). What's the real-world use case?

Given a string, find the length of the longest substring without repeating characters.

Write a function to check if a binary tree is a valid Binary Search Tree (BST).

Implement a min-heap from scratch. What are the time complexities of insert and extractMin?

Given an array, find the maximum sum subarray (Kadane's algorithm). Explain the dynamic programming insight.

Write an algorithm to serialize and deserialize a binary tree.

Given an array, find the maximum sum of a subarray (Kadane's algorithm). Then extend: return the actual subarray indices, not just the sum.

Implement a Trie (prefix tree) with insert, search, and startsWith methods.

Design a data structure for a phone directory that supports: addNumber, removeNumber, getAny (return any available number). All operations O(1).

Given a matrix of 0s and 1s, find the number of islands (connected components of 1s).

Given a string, find the minimum number of characters to insert to make it a palindrome.

Implement a function to find the kth largest element in an unsorted array. Optimize for O(n) average case.

Design a data structure that supports insert, delete, and getRandom in O(1) average time. Walk through your approach.

Implement a function to check if a number is a power of 2 without using loops or recursion.

You have N tasks, each with a deadline and profit. You can do at most one task per unit of time. Maximize total profit. (Job Scheduling with deadlines)

Implement Dijkstra's algorithm for shortest path. A city has 1000 nodes and 5000 edges. What data structure gives best performance?

Given a matrix of 0s and 1s, find the largest rectangle containing only 1s.

Implement a function that, given an integer n, returns all valid combinations of n pairs of parentheses.

You have a stream of integers. At any point, you can be asked for the median. Implement a data structure that supports add(num) in O(log n) and getMedian() in O(1).

Find the longest increasing subsequence in an array. Must be O(n log n).

Implement a function to serialize and deserialize a binary tree. The serialized format must allow perfect reconstruction.

Given a list of intervals sorted by start time, insert a new interval and merge if necessary. Return the updated list.

Implement a function to check if two strings are anagrams of each other. Then solve for: given a string and a pattern, find all anagram substrings.

You have a graph of cities with flight prices between them. Find the cheapest flight from source to destination with at most K stops.

How does quicksort choose a pivot and what makes it O(n²) in the worst case?

Implement a function that returns all permutations of a string. If string has duplicates, return unique permutations only.

Write a function to validate if a given string is a valid IP address (both IPv4 and IPv6).

Given an m x n grid of integers, find the path from top-left to bottom-right that maximizes the sum. You can only move right or down.

Explain the time and space complexity of hash table operations. What happens when load factor is too high?

Given a large dependency graph of build targets, design an algorithm to compute the minimal set of targets that need to be rebuilt after a file changes, and explain how you would parallelize the rebuild across workers respecting dependency order.

Implement a trie data structure. Your implementation must support: insert, search, and startsWith. Then optimize space for a dictionary with 1 million words.

What is the difference between DFS and BFS? When does each find the optimal solution?

You have an array of stock prices. Find the maximum profit from at most 2 transactions (buy-sell cycles). You must sell before buying again.

Implement Dijkstra's shortest path algorithm. What graph type is it NOT suitable for?

Given a binary search tree, find the k-th smallest element. Can you do it without building a sorted array?

Implement a function to detect a cycle in a linked list. What is Floyd's cycle detection algorithm and why is it O(1) space?

Given an array of ride fare amounts collected over a day, find the maximum sum of any contiguous subarray of exactly k rides (a sliding window problem). Walk through the O(n) approach.

Given a string, find the length of the longest substring without repeating characters. 'abcabcbb' → 3 ('abc').

Find the median of a stream of numbers. Numbers arrive one at a time. After each addition, you must be able to return the current median in O(log n) time.