Skip to content
Data Structures and Algorithms
All coursesPlacement Report
‹ Back to previous sectionCourse homeAll page URLs

Top 50 Most Asked Data Structures and Algorithms Interview Questions

The questions that appear most often across company-wise sets — master these first.

Why start here

We count how often each question appears across the 20 company-wise Data Structures and Algorithms practice sets on this site and show the 50 most common. They are the safest questions to master first.

Solved — top 50Start practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
3 questions free Unlock the rest in seconds
01

Merge K sorted linked lists using a min-heap.

Heaps, Priority Queues and GreedyIn 13 company setsMedium
Save to ▾
Show answer
import heapq def merge_k_lists(lists): heap = [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) # i breaks ties dummy = tail = ListNode() while heap: val, i, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next # O(N log K) for N total nodes
02

Find the lowest common ancestor of two nodes in a binary tree.

Trees and Binary Search TreesIn 12 company setsMedium
Save to ▾
Show answer
def lca(root, p, q): if root is None or root is p or root is q: return root left = lca(root.left, p, q) right = lca(root.right, p, q) if left and right: # p and q are on different sides return root return left or right # O(n) time, O(h) space; assumes both nodes exist in the tree
03

Find the minimum number of coins needed to make an amount.

Dynamic ProgrammingIn 11 company setsMedium
Save to ▾
Show answer
def coin_change(coins, amount): INF = amount + 1 dp = [0] + [INF] * amount # dp[x] = min coins for amount x for x in range(1, amount + 1): for c in coins: if c <= x and dp[x - c] + 1 < dp[x]: dp[x] = dp[x - c] + 1 return dp[amount] if dp[amount] != INF else -1 # coin_change([1, 3, 4], 6) -> 2 (3 + 3) # O(amount * len(coins)) time, O(amount) space
04

Design a simple scheduler that gives each job a fixed time slice in turn.

Linked Lists, Stacks and QueuesIn 10 company setsMedium
Save to ▾
Show answer
Round-robin scheduling fits a queue. Put all jobs in a FIFO queue. Repeatedly dequeue a job, run it for one time slice, and if it is not finished, enqueue it at the back with its remaining time. Each step is O(1). For priorities, keep one queue per priority level or use a priority queue. A circular buffer works well if the number of jobs is bounded, avoiding allocations.
05

A recursive DFS in Python crashes with RecursionError on a deep input. How do you fix it?

Complexity Analysis and RecursionIn 9 company setsMedium
Save to ▾
Show answer
CPython limits recursion depth to about 1000 by default. Raising the limit with sys.setrecursionlimit works for moderate depth but can crash the interpreter on very deep inputs because the C stack is limited. The reliable fix is to rewrite the DFS iteratively with an explicit stack, pushing nodes and processing them in a loop. In Java the same issue appears as StackOverflowError and has the same solution.
06

Generate all subsets of a list of distinct numbers.

Complexity Analysis and RecursionIn 9 company setsMedium
Save to ▾
Show answer
def subsets(nums): result = [] current = [] def backtrack(i): if i == len(nums): result.append(current[:]) return current.append(nums[i]) # include nums[i] backtrack(i + 1) current.pop() # exclude nums[i] backtrack(i + 1) backtrack(0) return result # 2^n subsets, each up to n long: O(n * 2^n) time
07

Return an array where each element is the product of all other elements, without using division.

Arrays, Strings and HashingIn 8 company setsHard
Save to ▾
Show answer
def product_except_self(nums): n = len(nums) out = [1] * n prefix = 1 for i in range(n): # product of everything to the left out[i] = prefix prefix *= nums[i] suffix = 1 for i in range(n - 1, -1, -1): # multiply by everything to the right out[i] *= suffix suffix *= nums[i] return out # [1,2,3,4] -> [24,12,8,6]; O(n) time, O(1) extra space besides output
08

A trading application needs a stack that also returns the current minimum in O(1). How would you design it?

Linked Lists, Stacks and QueuesIn 8 company setsMedium
Save to ▾
Show answer
Keep a second stack of minimums. On push, push the value onto the main stack and push the smaller of the value and the current minimum onto the min stack. On pop, pop both. getMin returns the top of the min stack in O(1). To save space, push onto the min stack only when the new value is less than or equal to the current minimum, and pop it only when the popped value equals it.
09

Detect whether a linked list has a cycle and return the node where the cycle begins.

Linked Lists, Stacks and QueuesIn 8 company setsMedium
Save to ▾
Show answer
def detect_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # cycle found slow = head while slow is not fast: # move both one step slow = slow.next fast = fast.next return slow # start of the cycle return None # O(n) time, O(1) space
10

Implement 0/1 knapsack using a one-dimensional DP array.

Dynamic ProgrammingIn 8 company setsMedium
Save to ▾
Show answer
def knapsack(weights, values, capacity): dp = [0] * (capacity + 1) # dp[w] = best value with capacity w for wt, val in zip(weights, values): for w in range(capacity, wt - 1, -1): # go downwards: each item once dp[w] = max(dp[w], dp[w - wt] + val) return dp[capacity] # knapsack([1, 3, 4], [15, 20, 30], 4) -> 35 # O(n * W) time, O(W) space
11

Packages with given weights must be shipped in order within D days. How do you find the minimum ship capacity?

Sorting, Searching and BacktrackingIn 8 company setsMedium
Save to ▾
Show answer
The capacity lies between the heaviest package and the total weight, and if a capacity works, any larger one also works, so binary search the answer. For a candidate capacity, greedily load packages day by day, starting a new day when the next package does not fit, and count days. If the days are within D, try smaller; otherwise try larger. Time is O(n log of total weight).
12

Find the first and last position of a target in a sorted array.

Sorting, Searching and BacktrackingIn 8 company setsMedium
Save to ▾
Show answer
from bisect import bisect_left, bisect_right def search_range(nums, target): lo = bisect_left(nums, target) # first index >= target if lo == len(nums) or nums[lo] != target: return [-1, -1] hi = bisect_right(nums, target) - 1 # last index <= target return [lo, hi] # [5,7,7,8,8,10], 8 -> [3, 4]; two binary searches: O(log n)
13

Generate all permutations of a list of distinct numbers using backtracking.

Sorting, Searching and BacktrackingIn 8 company setsMedium
Save to ▾
Show answer
def permutations(nums): result, path = [], [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): result.append(path[:]) return for i, x in enumerate(nums): if used[i]: continue used[i] = True path.append(x) backtrack() path.pop() # undo the choice used[i] = False backtrack() return result # n! permutations: O(n * n!) time
14

An interviewer asks you to reduce your solution's extra space from O(n) to O(1). How do you approach it?

Complexity Analysis and RecursionIn 7 company setsMedium
Save to ▾
Show answer
I check what the extra structure stores and whether the input itself can hold that information. Common techniques: use two pointers instead of a hash set on sorted data, keep only the last few DP values instead of a full table, modify the input in place, such as marking visited indices by negating values, or use bit manipulation like XOR to find a missing number. I state any trade-offs, such as mutating input.
15

A report generation function loops over all users and, for each user, scans all orders. It was fine at launch but is now very slow. How do you explain and fix it?

Complexity Analysis and RecursionIn 7 company setsHard
Save to ▾
Show answer
The loop is O(users times orders), so when both grow ten times, the work grows a hundred times. I would explain this with numbers and a quick profile. The fix is to group orders by user ID once using a hash map, making the total O(users plus orders), or to push the grouping into a database query with an index. I would add a performance test with production-scale data.
16

A hash map lookup in your service suddenly becomes very slow under certain traffic. What could cause it?

Arrays, Strings and HashingIn 7 company setsHard
Save to ▾
Show answer
If many keys produce the same hash, they pile into a few buckets and operations degrade toward O(n). This can come from a poor custom hashCode, such as returning a constant or using only one field, or from attackers sending crafted keys. Fixes include a better hash function combining all fields, randomised hashing, which Python uses for strings, and tree-based buckets as in Java 8 HashMap, which caps the worst case at O(log n).
17

Rotate an array to the right by k steps in place.

Arrays, Strings and HashingIn 7 company setsMedium
Save to ▾
Show answer
def rotate(nums, k): n = len(nums) k %= n def reverse(l, r): while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 reverse(0, n - 1) # reverse all reverse(0, k - 1) # reverse first k reverse(k, n - 1) # reverse the rest # [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]; O(n) time, O(1) space
18

Write a function to validate a binary search tree.

Trees and Binary Search TreesIn 7 company setsMedium
Save to ▾
Show answer
def is_valid_bst(root, low=float('-inf'), high=float('inf')): if not root: return True if not (low < root.val < high): return False return (is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)) # Passing bounds checks the whole-subtree property, not just children. # O(n) time, O(h) space.
19

Given meeting start and end times for a day, how do you find the minimum number of rooms needed?

Heaps, Priority Queues and GreedyIn 7 company setsMedium
Save to ▾
Show answer
Sort meetings by start time and keep a min-heap of end times for rooms in use. For each meeting, if the earliest ending room is free by its start time, pop it; then push this meeting's end time. The heap size at the end, or its maximum, is the answer. This is O(n log n). An alternative sorts start and end times separately and sweeps with two pointers, counting overlaps.
20

How would you generate friend suggestions as friends of friends in a social network?

Graphs and Graph AlgorithmsIn 7 company setsMedium
Save to ▾
Show answer
Run a BFS limited to depth 2 from the user. For every friend, look at their friends, skip the user and existing friends, and count how many mutual friends each candidate has using a hash map. Rank candidates by mutual friend count and other signals. For users with thousands of friends this gets expensive, so production systems precompute suggestions offline in batch jobs and cache them.
21

A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?

Graphs and Graph AlgorithmsIn 7 company setsMedium
Save to ▾
Show answer
Model services as a directed graph and run DFS with three colours. When DFS reaches a node that is still on the current stack, it has found a back edge, and walking the parent pointers from the current node back to that node gives the exact cycle to report, such as A to B to C to A. Running this check in CI before every build prevents the problem, and Kahn's algorithm can list all nodes involved.
22

Your knapsack DP has n equal to 100 items but capacity up to 10 to the power 9, so the table does not fit in memory. What do you do?

Dynamic ProgrammingIn 7 company setsHard
Save to ▾
Show answer
A table indexed by capacity is impossible, so I change the state. If item values are small, use dp[v] as the minimum weight needed to achieve value v, then pick the largest v whose weight fits the capacity; that is O(n times total value). If n is about 40, meet in the middle: enumerate subsets of each half, sort one side and binary search. Otherwise approximation or branch and bound are options.
23

You need to build a tool that shows the differences between two versions of a file line by line. What algorithm would you use?

Dynamic ProgrammingIn 7 company setsMedium
Save to ▾
Show answer
The core is the longest common subsequence over lines: lines in the LCS are unchanged, and the rest are additions or deletions. Hash each line first so comparisons are fast. Classic LCS DP is O(m times n), which is too slow for large files, so real diff tools use Myers' algorithm, which runs in O((m plus n) times d), where d is the number of differences, fast when versions are similar.
24

Implement merge sort.

Sorting, Searching and BacktrackingIn 7 company setsMedium
Save to ▾
Show answer
def merge_sort(a): if len(a) <= 1: return a mid = len(a) // 2 left = merge_sort(a[:mid]) right = merge_sort(a[mid:]) out, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # <= keeps the sort stable out.append(left[i]); i += 1 else: out.append(right[j]); j += 1 out.extend(left[i:]) out.extend(right[j:]) return out # O(n log n) time, O(n) extra space
25

Explain the sliding window technique with fixed and variable windows.

Arrays, Strings and HashingIn 6 company setsMedium
Save to ▾
Show answer
A sliding window keeps a contiguous range and updates its result incrementally instead of recomputing. A fixed window of size k, such as the maximum sum of k consecutive elements, adds the new element and removes the old one each step in O(n). A variable window grows the right end and shrinks the left end while a condition is violated, as in the longest substring without repeating characters. Both turn O(n squared) into O(n).
26

You have a 100 GB file of integers and only 4 GB of RAM. How would you find the duplicates?

Arrays, Strings and HashingIn 6 company setsHard
Save to ▾
Show answer
The data does not fit in memory, so I would partition it. Read the file in streaming fashion and write each number to one of, say, 50 bucket files based on hash of the number modulo 50, so equal numbers land in the same bucket. Each bucket of about 2 GB fits in memory, where a hash set finds duplicates. Alternatively use external merge sort and scan adjacent values. A Bloom filter can pre-screen candidates.
27

An array of size 100000 must answer 100000 queries asking for the sum between two indices. What approach would you use?

Arrays, Strings and HashingIn 6 company setsMedium
Save to ▾
Show answer
Recomputing each sum is O(n) per query, about 10 to the power 10 operations in total, which is too slow. Since the array does not change, I would build a prefix sum array once in O(n) and answer each query in O(1) as pre[r+1] minus pre[l], giving O(n plus q) overall. If the array also receives updates, I would switch to a Fenwick tree or segment tree for O(log n) updates and queries.
28

You must merge two sorted arrays where the first array has enough empty space at the end for the second. How would you do it in place?

Arrays, Strings and HashingIn 6 company setsMedium
Save to ▾
Show answer
Merging from the front would overwrite unread elements, so merge from the back. Use three pointers: the last real element of the first array, the last element of the second, and the last slot of the first array. Repeatedly place the larger of the two candidates at the write position and move pointers left. When the second array is exhausted, the rest is already in place. This takes O(m plus n) time and O(1) space.
29

You must build autocomplete for a search box over one million product names. Which data structure would you use?

Trees and Binary Search TreesIn 6 company setsMedium
Save to ▾
Show answer
I would use a trie where each node stores, besides children, the top few most popular completions under that prefix. Then typing a prefix walks L nodes and returns precomputed suggestions instantly, without exploring the whole subtree. Memory can be reduced with a compressed radix trie. For typo tolerance or ranking by many signals, a search engine with prefix indexes is more practical at large scale.
30

An application needs sorted data with frequent inserts, deletes and range queries such as all orders between two timestamps. Which structure fits?

Trees and Binary Search TreesIn 6 company setsMedium
Save to ▾
Show answer
A balanced BST, such as Java TreeMap or a sorted container in Python, gives O(log n) insert and delete and O(log n plus k) range queries using floor, ceiling or subMap operations. A sorted array has fast range queries but O(n) inserts, and a hash map cannot do ranges at all. If the data lives in a database, a B-tree index on the timestamp column solves the same problem.
31

Serialize a binary tree to a string and deserialize it back.

Trees and Binary Search TreesIn 6 company setsHard
Save to ▾
Show answer
def serialize(root): out = [] def dfs(node): if not node: out.append('#') return out.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ','.join(out) def deserialize(data): vals = iter(data.split(',')) def build(): v = next(vals) if v == '#': return None node = TreeNode(int(v)) node.left = build() node.right = build() return node return build() # Preorder with null markers uniquely encodes the tree: O(n) both ways.
32

A network has 10 million devices and connections are added continuously. You must answer whether two devices are connected in real time. How?

Graphs and Graph AlgorithmsIn 6 company setsHard
Save to ▾
Show answer
Running BFS for every query is too slow. Since connections are only added, Union-Find is ideal: each new link is a union, and each query compares find results, both nearly O(1) amortised with path compression and union by size. Memory is two integer arrays of 10 million entries, about 80 MB. If links can also be removed, the problem becomes much harder and needs offline processing or specialised dynamic connectivity structures.
33

Implement Union-Find with path compression and union by size.

Graphs and Graph AlgorithmsIn 6 company setsHard
Save to ▾
Show answer
class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] # path halving x = self.parent[x] return x def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] return True # Nearly O(1) amortised per operation
34

A sorted array has been rotated at an unknown point. How can you still search it in O(log n)?

Sorting, Searching and BacktrackingIn 6 company setsMedium
Save to ▾
Show answer
At every step of binary search, at least one half around mid is sorted. Compare nums[low] with nums[mid]: if the left half is sorted and the target lies within its range, search left, otherwise search right. If the right half is sorted, apply the same check on the right. This keeps O(log n). With duplicates allowed, equal values can hide which half is sorted, and the worst case becomes O(n).
35

A Sudoku solver using plain backtracking is too slow on hard puzzles. How would you speed it up?

Sorting, Searching and BacktrackingIn 6 company setsHard
Save to ▾
Show answer
Add stronger pruning and better choice ordering. Keep bitmasks of used digits for each row, column and box, so validity checks are O(1). Always fill the empty cell with the fewest candidates first, the minimum remaining values heuristic, which shrinks the search tree dramatically. Apply constraint propagation, filling cells with a single candidate before guessing. For the hardest cases, exact cover with Dancing Links is very fast.
36

What is amortised analysis? Explain it with dynamic array append.

Complexity Analysis and RecursionIn 5 company setsMedium
Save to ▾
Show answer
Amortised analysis averages the cost of an operation over a long sequence, even if a few individual operations are expensive. A dynamic array such as Java ArrayList or Python list doubles its capacity when full, which costs O(n) for that append. But doubling happens rarely, and the total copying over n appends is under 2n, so each append costs O(1) amortised. Hash table resizing works the same way.
37

Find the length of the longest substring without repeating characters.

Arrays, Strings and HashingIn 5 company setsMedium
Save to ▾
Show answer
def length_of_longest_substring(s): last = {} # char -> last index seen left = best = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1) return best # 'abcabcbb' -> 3, 'bbbbb' -> 1, 'pwwkew' -> 3; O(n) time
38

Design a rate limiter that allows at most 100 requests per user in any rolling 60-second window.

Linked Lists, Stacks and QueuesIn 5 company setsHard
Save to ▾
Show answer
For each user keep a deque of request timestamps. On a request, pop timestamps older than now minus 60 seconds from the front, then allow the request only if fewer than 100 remain, pushing the new timestamp at the back. This sliding window log is exact but uses memory per request. At scale I would use a sliding window counter or token bucket stored in Redis with atomic operations to save memory and work across servers.
39

How does Dijkstra's algorithm work and why does it fail with negative edge weights?

Graphs and Graph AlgorithmsIn 5 company setsMedium
Save to ▾
Show answer
Dijkstra keeps a min-heap of tentative distances. It repeatedly pops the closest unvisited vertex, marks its distance final and relaxes its outgoing edges, giving O((V plus E) log V). It relies on the fact that once a vertex is popped, no shorter path can appear later. A negative edge breaks that assumption because a longer path could later become cheaper. For negative weights use Bellman-Ford.
40

What is topological sorting and how is it done?

Graphs and Graph AlgorithmsIn 5 company setsMedium
Save to ▾
Show answer
A topological order lists the vertices of a DAG so every edge goes from earlier to later, such as an order to take courses. Kahn's algorithm computes in-degrees, pushes zero in-degree vertices into a queue and repeatedly removes them while decreasing neighbours' in-degrees; if not all vertices are output, a cycle exists. The DFS method adds a vertex to a list after visiting its descendants and reverses the list. Both are O(V plus E).
41

A learning platform has courses with prerequisites. How do you find a valid order, and what if none exists?

Graphs and Graph AlgorithmsIn 5 company setsMedium
Save to ▾
Show answer
Model courses as vertices with an edge from each prerequisite to the course that needs it, then run topological sort with Kahn's algorithm. Courses with no pending prerequisites enter a queue first, and taking one reduces the in-degree of dependent courses. If the output has fewer courses than the total, there is a cycle, so no valid order exists, and I would report the courses involved so the content team can fix them.
42

Implement Dijkstra's algorithm with a priority queue.

Graphs and Graph AlgorithmsIn 5 company setsMedium
Save to ▾
Show answer
import heapq def dijkstra(graph, src): # graph: {node: [(neighbour, weight), ...]} dist = {src: 0} heap = [(0, src)] while heap: d, u = heapq.heappop(heap) if d > dist.get(u, float('inf')): continue # stale entry for v, w in graph.get(u, []): nd = d + w if nd < dist.get(v, float('inf')): dist[v] = nd heapq.heappush(heap, (nd, v)) return dist # O((V + E) log V); weights must be non-negative
43

Tell me about a time you worked with people from other teams to solve a complex problem.

Graphs and Graph AlgorithmsIn 5 company setsMedium
Save to ▾
Show answer
Situation: delivery route suggestions in our app were slow and the data team blamed the backend while we blamed the data. Task: find the real issue. Action: I set up a joint session, we traced one slow request end to end and found the graph was rebuilt from raw tables on every call. I proposed caching the adjacency lists, and the data team added change notifications. Result: response time dropped from 3 seconds to 200 milliseconds.
44

Compute the length of the longest common subsequence of two strings.

Dynamic ProgrammingIn 5 company setsMedium
Save to ▾
Show answer
// Java static int lcs(String a, String b) { int m = a.length(), n = b.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } return dp[m][n]; } // lcs(abcde, ace) = 3; O(m * n) time and space
45

Compute the edit distance between two words.

Dynamic ProgrammingIn 5 company setsHard
Save to ▾
Show answer
def edit_distance(a, b): m, n = len(a), len(b) prev = list(range(n + 1)) # distances from empty prefix of a for i in range(1, m + 1): cur = [i] + [0] * n for j in range(1, n + 1): if a[i - 1] == b[j - 1]: cur[j] = prev[j - 1] else: cur[j] = 1 + min(prev[j], # delete cur[j - 1], # insert prev[j - 1]) # replace prev = cur return prev[n] # edit_distance('horse', 'ros') -> 3; O(m * n) time, O(n) space
46

You must sort a 10 GB file of records on a machine with 1 GB of RAM. How would you do it?

Sorting, Searching and BacktrackingIn 5 company setsHard
Save to ▾
Show answer
Use external merge sort. Read the file in chunks of about 800 MB, sort each chunk in memory and write it to disk as a sorted run, giving around 13 runs. Then perform a K-way merge: open all runs, keep a min-heap with the current record from each, repeatedly output the smallest and refill from that run, using buffered I/O. Total work is O(n log n) with roughly two passes over the data.
47

Search for a target in a rotated sorted array.

Sorting, Searching and BacktrackingIn 5 company setsHard
Save to ▾
Show answer
def search_rotated(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # left half sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1 # [4,5,6,7,0,1,2], 0 -> 4; O(log n)
48

Your solution passes the sample tests but gets Time Limit Exceeded on large inputs. How do you analyse and fix it?

Complexity Analysis and RecursionIn 4 company setsHard
Save to ▾
Show answer
First I estimate the complexity of my code against the constraints and find the dominant loop. Often a nested loop or repeated search inside a loop makes it O(n squared). I then look for a better pattern such as a hash map for lookups, sorting plus two pointers, prefix sums or memoisation of repeated subproblems. I also check hidden costs like string concatenation in loops or list.pop(0) in Python.
49

How does a hash table work, and how are collisions handled?

Arrays, Strings and HashingIn 4 company setsMedium
Save to ▾
Show answer
A hash table computes a hash of the key and maps it to a bucket index, giving average O(1) insert, lookup and delete. A collision happens when two keys map to the same bucket. Separate chaining stores a list or tree in each bucket, which Java HashMap uses and converts to a tree after 8 entries. Open addressing probes other slots, which Python dict uses. Tables resize when the load factor grows too high.
50

Your brute-force solution for the longest substring without repeating characters is O(n cubed). How would you improve it?

Arrays, Strings and HashingIn 4 company setsMedium
Save to ▾
Show answer
I would use a variable sliding window. Keep a map from character to its last index and a left pointer. Move the right pointer through the string; when the current character was seen at an index at or after left, move left to that index plus one. Update the best length at each step. Each character is processed a constant number of times, giving O(n) time and O(alphabet size) space.

Frequently asked questions

How is this list made?

We count how often each question appears across the 20 company-wise Data Structures and Algorithms practice sets on this site and show the 50 most common. They are the safest questions to master first.

Is this enough to clear an interview?

It is the best starting point, not the finish line. After these, practise the company pages for your target employers and the sheets for your weaker topics.

More ways to practise

Company-wise Data Structures and Algorithms questionsExperience-wise Data Structures and Algorithms questionsRole-wise Data Structures and Algorithms questionsCity-wise Data Structures and Algorithms questionsScenario-based questionsPractical / hands-on questionsHR & behavioural questionsData Structures and Algorithms mock interviewOnline assessment questionsTechnical round questionsManagerial round questionsData Structures and Algorithms topic sheets