Data Structures & Algorithms Interview Questions and Answers

Big-O describes how the time or memory an algorithm needs grows as the input size n grows, keeping only the dominant term. If a routine is O(n), doubling the input roughly doubles the work; if it is O(n²), doubling the input roughly quadruples it.

It leaves out constant factors, cache behaviour and small inputs, so an O(n log n) method with tiny constants can beat an O(n) one with heavy per-item work at realistic sizes. It is also an upper bound, so say which case you mean: best, average or worst. Binary search is O(log n) in the worst case, yet it can finish on the very first probe.

What the interviewer is checking: Whether you can explain growth rates in plain words and know that Big-O is not a stopwatch.

Likely follow-up: A function loops over n items, and inside that loop runs another loop from 0 up to the current index. What is its complexity, and why?

An array stores elements side by side in memory, so reading position i is O(1) and scanning is fast because neighbouring items share cache lines. Inserting or deleting in the middle costs O(n) because the later items must shift.

A linked list stores each item in its own node with a pointer to the next. Splicing a node in or out is O(1) once you hold a reference to its neighbour, but reaching position i means walking i nodes, and every node pays for extra pointers. In practice arrays win for most workloads. I pick a linked list when I keep node references and splice constantly, such as the recency list inside a cache. "O(1) insertion" is only true after you have found the spot.

What the interviewer is checking: Whether you go beyond the textbook table and mention cache locality and the cost of finding the position.

Likely follow-up: Why does an LRU cache use a doubly linked list rather than a singly linked one?

Each in test on a list scans from the start until it finds a match, so one test is O(n) and the whole loop is O(n²). With 100,000 items that is up to billions of comparisons in the worst case, which is why the code feels fine in a demo and crawls in production.

Build a set once and test against it. Membership in a hash set is O(1) on average, so the loop becomes O(n) overall. The trade-offs are that elements must be hashable, the set uses more memory than a list, and it does not keep order; if I need insertion order as well, a dict keeps it. Related trap: list.pop(0) is also O(n), so use collections.deque for queues.

What the interviewer is checking: Whether you know the cost of common built-in operations and spot an accidental quadratic loop.

Likely follow-up: What happens if two different SKUs have the same hash value? Is the set still correct?

A hash table runs the key through a hash function to get an integer, then reduces it to a bucket index, usually with a modulo by the table size. Lookup, insert and delete are O(1) on average because you jump straight to the bucket instead of searching.

Two different keys can map to the same bucket, since there are more possible keys than buckets. That is a collision. The table resolves it by chaining (a small list per bucket) or by probing for another free slot, and then uses equality to find the right entry. If many keys collide, lookups degrade toward O(n). The snippet below shows that a terrible hash still gives a correct set; it only costs speed.

class Bad:
    def __init__(self, n):
        self.n = n
    def __hash__(self):
        return 1
    def __eq__(self, other):
        return self.n == other.n

s = {Bad(i) for i in range(1000)}
print(len(s), Bad(5) in s)

1000 True

What the interviewer is checking: Whether you separate correctness (equality) from performance (hash quality) and know the worst case.

Likely follow-up: Why must dictionary keys be immutable, or at least have a hash that never changes?

A stack is last-in, first-out. Undo history in an editor is one use: the latest action is the first to be reversed. Matching brackets in an expression is another: push each opener and pop when you see a closer. The function call stack and iterative depth-first search are the same idea.

A queue is first-in, first-out. A background job runner that processes uploads in arrival order is one use; breadth-first search is another, because it visits nodes in the order discovered. In Python a plain list works as a stack, but use collections.deque for a queue, since removing from the front of a list is O(n).

What the interviewer is checking: Whether you tie each structure to a concrete problem shape rather than reciting LIFO and FIFO.

Likely follow-up: How could you build a queue out of two stacks, and what is the amortised cost of each operation?

Recursion expresses self-similar problems, such as tree walks, divide and conquer and backtracking, in a few clear lines. A loop is usually cheaper, because every recursive call adds a stack frame that costs time and memory, and a deep recursion can overflow the call stack.

Python's default recursion limit is 1000 frames and it does not optimise tail calls, so a million-deep recursion raises RecursionError while the equivalent loop is fine. My rule: recurse when the depth is bounded by something small, like the height of a balanced tree, and switch to a loop or an explicit stack when depth can grow with the input. Any recursion can be rewritten with an explicit stack.

def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)

try:
    depth(10**6)
except RecursionError:
    print("too deep")

def depth_loop(n):
    count = 0
    while n:
        n -= 1
        count += 1
    return count

print(depth_loop(10**6))

too deep
1000000

What the interviewer is checking: Whether you understand the call-stack cost and can name a safe rule for choosing between the two.

Likely follow-up: How would you convert a recursive depth-first traversal into an iterative one?

The first three are depth-first and differ in when the node itself is visited. Pre-order visits the node, then left, then right: good for copying or serialising a tree, because parents come before children. In-order visits left, node, right: on a binary search tree it yields keys in sorted order. Post-order visits both children first: good for deleting a tree or evaluating an expression tree, where children must finish before the parent.

Level-order is breadth-first, using a queue, and visits nodes row by row. It is the natural choice for shortest depth or printing a tree by levels. All four visit each node once, so they are O(n) time; the depth-first ones need stack space proportional to tree height.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def inorder(n):
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []

def preorder(n):
    return [n.key] + preorder(n.left) + preorder(n.right) if n else []

root = None
for k in [50, 30, 70, 20, 40]:
    root = insert(root, k)
print(inorder(root))
print(preorder(root))

[20, 30, 40, 50, 70]
[50, 30, 20, 40, 70]

What the interviewer is checking: Whether you can connect each traversal order to a practical purpose, not just recite the orders.

Likely follow-up: Given only the pre-order and in-order lists of a binary tree with distinct keys, can you rebuild the tree?

A stable sort keeps items with equal keys in their original relative order. It matters when you sort by more than one criterion in passes. Say deliveries are already ordered by pickup time, and you now sort them by driver. With a stable sort, each driver's deliveries stay in pickup order; with an unstable one, that order may be scrambled.

Merge sort and insertion sort are stable. Quicksort and heapsort in their usual in-place forms are not. Python's built-in sorted and list.sort are stable, which is why you can sort by the secondary key first and the primary key last. Stability is irrelevant when the keys are unique or when equal items are indistinguishable.

What the interviewer is checking: Whether you can explain stability with a concrete multi-key example and name which algorithms have it.

Likely follow-up: How would you make an unstable sort behave stably if you could not change it?

Chaining keeps a small list per bucket, and a colliding key joins that list. It is simple, deletion is easy, and performance degrades gradually as the table fills, at the cost of extra pointers and weaker cache locality. Open addressing stores every entry in the array itself and probes other slots on collision (linear, quadratic or a second hash). It is compact and cache-friendly, but it clusters, and deletion needs tombstone markers so later probes do not stop early.

Load factor is entries divided by buckets. As it rises, collisions rise, so the table grows past a threshold: allocate a larger array and rehash every key. That one resize is O(n), but spread across the inserts it keeps the average cost O(1). Open addressing needs a lower threshold than chaining.

What the interviewer is checking: Whether you understand collision handling beyond the word chaining, including deletion and resizing.

Likely follow-up: Why can an attacker who knows your hash function slow your service down, and how do runtimes defend against it?

Most appends write into spare capacity and cost O(1). When the array is full, it allocates a bigger block and copies every element, which costs O(n). Amortised analysis averages over a whole sequence of operations rather than one: if capacity grows by a constant factor each time, the copying across n appends adds up to O(n) total, so the average per append is constant.

The growth must be multiplicative. If you added a fixed number of slots each time, the total copying would be O(n²). The catch is that amortised is not worst-case: one unlucky append is still O(n), which matters in latency-sensitive code. If you know the final size, reserve capacity up front to avoid the resizes.

What the interviewer is checking: Whether you can justify the constant average and say when the amortised guarantee is not enough.

Likely follow-up: If the array also shrinks when half empty, what can go wrong with a poorly chosen shrink threshold?

The O(log n) figure for a plain BST holds only when the tree stays roughly balanced, which is true on average for random insertion order. Insert keys that arrive already sorted, such as increasing order IDs, and every node becomes a right child. The tree is now a linked list and lookups cost O(n).

Balanced trees such as AVL and red-black trees do small local rotations on insert and delete to keep the height O(log n) in the worst case, so search, insert and delete are all guaranteed O(log n). Databases and file systems go further with B-trees, which store many keys per node so that one disk page read narrows the search a lot. The price of balancing is more complex code and a little extra work per update.

What the interviewer is checking: Whether you know the degenerate case and the purpose of rebalancing, not just the names of the trees.

Likely follow-up: What is the difference in how AVL and red-black trees trade lookup speed against update cost?

A heap keeps the smallest (or largest) element at the top, so peeking is O(1) and pushing or popping is O(log n). That makes it the standard way to build a priority queue. Typical uses are task schedulers, Dijkstra's algorithm, merging k sorted lists, and keeping the top k items from a stream with a min-heap of size k, which costs O(n log k) instead of sorting everything.

Building a heap from n existing items is O(n). Where a heap is bad is search: finding an arbitrary value is O(n), and it does not keep elements in sorted order, only the top is guaranteed. Python's heapq is a min-heap; for a max-heap, push negated values. If you need ordered iteration or range queries, use a sorted structure instead.

What the interviewer is checking: Whether you can match a heap to priority-style problems and state its limits honestly.

Likely follow-up: How would you use two heaps to maintain the median of a stream of numbers?

Both visit every reachable vertex in O(V + E) with an adjacency list. BFS uses a queue and explores in rings of increasing distance, so in an unweighted graph the first time it reaches a node is along a shortest path. DFS uses a stack or recursion and dives down one branch before backtracking.

I choose BFS for fewest-hops questions, such as the minimum number of transfers on a transit map. I choose DFS for exploring all paths, backtracking, connected components, cycle detection and topological ordering. Memory differs too: BFS holds the widest level, DFS holds the current path. In a graph with cycles, always track visited nodes or you will loop forever.

from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}

def bfs(start):
    seen, order, q = {start}, [], deque([start])
    while q:
        n = q.popleft()
        order.append(n)
        for m in graph[n]:
            if m not in seen:
                seen.add(m)
                q.append(m)
    return order

def dfs(n, seen=None):
    seen = seen if seen is not None else set()
    seen.add(n)
    order = [n]
    for m in graph[n]:
        if m not in seen:
            order += dfs(m, seen)
    return order

print(bfs("A"))
print(dfs("A"))

['A', 'B', 'C', 'D']
['A', 'B', 'D', 'C']

What the interviewer is checking: Whether you can justify the choice from the question being asked, not from habit.

Likely follow-up: On a grid with obstacles, how would you find the shortest route with BFS, and what is its time complexity?

The simple way is to walk the list and store visited nodes in a set; seeing a node twice means a cycle. That is O(n) time but O(n) space.

Floyd's tortoise and hare uses O(1) space. Move one pointer a step at a time and another two steps. If there is no cycle, the fast pointer reaches the end. If there is a cycle, both end up inside it, and each iteration the fast pointer closes the gap by one node, so they must meet. Compare nodes with identity (is), not by value, since values can repeat. This is also the basis for finding where the cycle begins.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

a, b, c = Node(1), Node(2), Node(3)
a.next, b.next = b, c
print(has_cycle(a))
c.next = b
print(has_cycle(a))

False
True

What the interviewer is checking: Whether you know both the obvious and the constant-space method, and can argue why the pointers must meet.

Likely follow-up: Once the pointers have met, how do you find the node where the cycle starts?

Both avoid recomputing overlapping subproblems. Memoization is top-down: write the natural recursion and cache each result by its arguments, so only the states you actually reach get computed. Tabulation is bottom-up: fill a table from the smallest subproblems upward in an order where dependencies are already done.

Memoization is quicker to write and skips unreachable states, but carries recursion overhead and can hit the recursion limit on deep inputs. Tabulation avoids recursion, is usually faster, and often lets you keep only the last row or two to save memory, but you must get the evaluation order right. The snippet finds the fewest coins for 10 with denominations 1, 5 and 6; greedy would pick 6 then four 1s, while both DP versions find 5 + 5.

from functools import lru_cache

COINS = (1, 5, 6)

@lru_cache(maxsize=None)
def fewest_top_down(amount):
    if amount == 0:
        return 0
    best = float("inf")
    for c in COINS:
        if c <= amount:
            best = min(best, 1 + fewest_top_down(amount - c))
    return best

def fewest_bottom_up(amount):
    table = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in COINS:
            if c <= a:
                table[a] = min(table[a], table[a - c] + 1)
    return table[amount]

print(fewest_top_down(10), fewest_bottom_up(10))

2 2

What the interviewer is checking: Whether you see these as two orderings of the same idea and can name a practical trade-off.

Likely follow-up: For the coin problem, what are the time and space complexities, and how would you recover which coins were used?

I look for the shape of the input and the question. Two pointers fits sorted data, or pairs and triples that must satisfy a condition: start at both ends and move the one that brings the sum closer to the target. A sliding window fits "longest, shortest or best contiguous subarray or substring" with some constraint, such as at most k distinct items or a sum under a limit.

The signal is a monotonic property: moving a pointer can only help or only hurt, so you never need to revisit. That replaces a nested O(n²) scan with a single O(n) pass. The window also needs state you can update incrementally when an element enters or leaves. Negative numbers often break sum-based windows, because growing the window no longer reliably increases the sum.

def pair_with_sum(sorted_prices, target):
    lo, hi = 0, len(sorted_prices) - 1
    while lo < hi:
        s = sorted_prices[lo] + sorted_prices[hi]
        if s == target:
            return (sorted_prices[lo], sorted_prices[hi])
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

print(pair_with_sum([2, 5, 8, 11, 15], 19))
print(pair_with_sum([2, 5, 8, 11, 15], 4))

(8, 11)
None

What the interviewer is checking: Whether you can spot the pattern from problem features and explain why it is correct, not just recall templates.

Likely follow-up: Why does the two-pointer pair search fail on an unsorted array, and what would you do instead?

The data must be sorted, or at least the condition you test must flip exactly once, from false to true. The classic bugs are off-by-one errors in the bounds, an infinite loop when mid never moves past the boundary, and returning the wrong duplicate. In fixed-width integer languages, (lo + hi) / 2 can overflow, so write lo + (hi - lo) / 2; Python integers do not overflow, but the habit is free.

I pick one convention and stick to it. With a half-open range [lo, hi) and the loop while lo < hi, set lo = mid + 1 or hi = mid. The snippet below finds the first index whose value is at least the target, which handles duplicates and the insert position in one routine.

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 3, 3, 3, 7]
print(lower_bound(a, 3), lower_bound(a, 4), lower_bound(a, 9))

1 4 5

What the interviewer is checking: Whether you have a disciplined invariant for the loop and know the duplicate and overflow traps.

Likely follow-up: How would you binary search the answer itself, for example the smallest capacity that lets a shipment finish in D days?

Quicksort averages O(n log n), sorts in place and is very cache-friendly, which is why it is fast in practice. Its worst case is O(n²) with consistently bad pivots, for example always taking the first element of already sorted data, and it is not stable. Merge sort is O(n log n) in every case and stable, but needs O(n) extra space for arrays. It suits linked lists and external sorting of data that does not fit in memory. Heapsort is O(n log n) worst case and in place, but it is unstable and has poor locality.

My pick depends on the constraints: stability or a guaranteed bound points to merge sort, tight memory points to quicksort or heapsort. Many library sorts are hybrids; Python's is Timsort, which is stable and exploits runs already in order. See the sorting algorithms course for the mechanics.

What the interviewer is checking: Whether you can pick an algorithm from stated constraints rather than naming a favourite.

Likely follow-up: How do you reduce the chance of quicksort hitting its worst case?

A hash map gives O(1) average lookups but no useful ordering. A balanced-tree map keeps keys sorted, so lookups, inserts and deletes are O(log n) with that bound guaranteed, and it supports operations a hash map cannot do cheaply: iterate in key order, find the smallest key above a value (ceiling), the largest below (floor), or fetch a range such as all bookings between two timestamps.

Choose the tree for range queries, ordered iteration, nearest-key lookups, or when you need a worst-case bound rather than an average. Choose the hash map for plain key-to-value lookups. Python has no built-in tree map; people use a sorted list with bisect, or a third-party sorted container. Java's TreeMap and C++'s std::map are the usual examples.

What the interviewer is checking: Whether you pick the structure from the operations required, not from the fastest-looking lookup.

Likely follow-up: How could you answer "which reservation starts right after 14:00?" using only a sorted list?

BFS finds shortest paths when every edge costs the same, since distance equals the number of hops. With different edge weights, the path with fewest hops is not always the cheapest, so BFS gives wrong answers. Dijkstra handles non-negative weights by always expanding the closest unfinalised node, using a min-heap. With a binary heap it runs in O((V + E) log V). With all weights equal, it behaves like BFS.

It breaks with negative edges: it assumes that once a node is popped, no later path can improve it, and a negative edge can violate that. Use Bellman-Ford instead, which is slower at O(VE) but handles negatives and detects negative cycles. In code, skip stale heap entries when the popped distance is larger than the best known.

import heapq

def shortest(graph, start):
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float("inf")):
            continue
        for nxt, w in graph[node]:
            nd = d + w
            if nd < dist.get(nxt, float("inf")):
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))
    return dist

roads = {
    "A": [("B", 1), ("C", 5)],
    "B": [("C", 2), ("D", 6)],
    "C": [("D", 1)],
    "D": [],
}
print(shortest(roads, "A"))

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

What the interviewer is checking: Whether you understand why Dijkstra's greedy choice is valid and exactly which assumption fails with negative weights.

Likely follow-up: How would you recover the actual route, not just its length?

I need two things in O(1): finding an entry by key, and tracking which entry was used least recently. A hash map gives the first. A doubly linked list gives the second: the head is most recent, the tail is the eviction candidate. The map stores key to list node, so a get finds the node, moves it to the head, and returns the value. A put updates or inserts at the head, and if capacity is exceeded, removes the tail node and its map entry.

The list must be doubly linked so a node can unlink itself in O(1) without searching for its predecessor. In Python, OrderedDict already pairs both ideas. Interviewers often add concurrency: a lock around the operations is the simple answer, since even a get mutates the order.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.cap:
            self.data.popitem(last=False)

cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")
cache.put("c", 3)
print(cache.get("b"), cache.get("a"), cache.get("c"))

-1 1 3

What the interviewer is checking: Whether you can combine two structures to meet a pair of complexity targets and justify each piece.

Likely follow-up: How would you change the design to support per-entry expiry times, or to make it safe for many threads?

Model tasks as a directed graph with an edge from each prerequisite to the task that needs it, then compute a topological order. Kahn's algorithm counts incoming edges per task, starts a queue with those at zero, and repeatedly removes a task from the queue, appending it to the order and decrementing the counts of tasks that depend on it. It runs in O(V + E).

A circular dependency shows up for free: if the output contains fewer tasks than the graph, some tasks never reached zero, so a cycle exists. The alternative is DFS with three colours (unvisited, in progress, done); meeting an in-progress node is a back edge, meaning a cycle. A valid order is generally not unique, so say whether the order needs to be deterministic.

from collections import deque

def build_order(deps):
    indeg = {t: len(p) for t, p in deps.items()}
    users = {t: [] for t in deps}
    for t, prereqs in deps.items():
        for p in prereqs:
            users[p].append(t)
    ready = deque(t for t, d in indeg.items() if d == 0)
    order = []
    while ready:
        t = ready.popleft()
        order.append(t)
        for u in users[t]:
            indeg[u] -= 1
            if indeg[u] == 0:
                ready.append(u)
    return order if len(order) == len(deps) else None

print(build_order({"deploy": ["test", "build"], "test": ["build"], "build": []}))
print(build_order({"a": ["b"], "b": ["a"]}))

['build', 'test', 'deploy']
None

What the interviewer is checking: Whether you can model a real dependency problem as a graph and handle the failure case, not only the happy path.

Likely follow-up: If several tasks can run in parallel, how would you compute the earliest finish time of the whole build?

Keep two heaps: a max-heap holding the smaller half and a min-heap holding the larger half. Insert each new number into the appropriate heap, then rebalance so the sizes differ by at most one. The median is then the top of the larger heap, or the average of both tops when the counts are equal.

Each insert is O(log n) and reading the median is O(1). Python's heapq only offers a min-heap, so store negated values in the lower half. Re-sorting the whole list on each arrival would cost O(n log n) per query, and inserting into a sorted list is O(n) because of shifting. The harder follow-up is a sliding window with removals, which needs lazy deletion or an order-statistics structure.

What the interviewer is checking: Whether you can invent a structure from requirements by combining a simple one, and quote per-operation costs.

Likely follow-up: What changes if the numbers are integers in a small known range, say 0 to 100?

A hash map answers "is this exact word present?" quickly, but it cannot answer "which words start with pre?" without scanning every key. A trie stores words along shared character paths, so reaching the node for a prefix costs O(L), where L is the prefix length, independent of how many words are stored. Collecting completions is then a walk of that subtree.

The costs are memory, since each node may hold a child map or array, and cache-unfriendly pointer chasing. Compressed tries (radix trees) merge single-child chains to save space. If you only need prefix search on a static list, a sorted array with binary search on the prefix range is a lean alternative. Ranking suggestions by popularity means storing counts at word-ending nodes.

What the interviewer is checking: Whether you choose the structure by the query pattern and can name its memory cost and cheaper alternatives.

Likely follow-up: How would you return only the top five suggestions for a prefix without walking the whole subtree each time?

Union-find, also called a disjoint-set structure, tracks which elements belong to the same group. find(x) returns the group's representative and union(a, b) merges two groups. It answers "are these two connected?" while edges are being added, without re-running a graph search each time.

Two optimisations make it fast: path compression, which flattens the tree during find, and union by size or rank, which attaches the smaller tree under the larger. Together the amortised cost per operation is nearly constant (the inverse Ackermann function). Typical uses are counting connected components, detecting a cycle in an undirected graph, and Kruskal's minimum spanning tree algorithm. Its limitation is that it supports adding connections, not removing them.

What the interviewer is checking: Whether you know the two optimisations by name and recognise the problem shape: connectivity under additions only.

Likely follow-up: How would Kruskal's algorithm use union-find to avoid creating a cycle in the spanning tree?

I check two properties. Optimal substructure: the best answer is built from best answers to smaller subproblems. Overlapping subproblems: the same subproblem is reached by many paths, so plain recursion repeats work, often exponentially. If subproblems do not overlap, ordinary divide and conquer is enough.

Greedy works only when a locally best choice is provably safe. Coin change with denominations 1, 5 and 6 for amount 10 is a standard counterexample: taking 6 first leads to five coins, while 5 + 5 uses two. My process is: define the state precisely, write the transition between states, set base cases, choose memoization or a fill order, then trim memory if only recent rows are needed. The dynamic programming course practises this routine.

What the interviewer is checking: Whether you can justify DP from its two properties and show why greedy fails, rather than pattern-matching on keywords.

Likely follow-up: For a 2D table where each cell depends only on the previous row, how do you cut the space from O(n·m) to O(m)?