Data Structures interview questions

An adjacency list is a way of storing a graph in which each node keeps a list of the nodes it connects to, using memory in proportion to its nodes and edges.

An adjacency list stores only the edges that exist, using O(V + E) memory, and is best for sparse graphs. An adjacency matrix stores a cell for every pair of nodes, using O(V^2) memory, but checks whether any edge exists in O(1), which suits small or dense graphs.

It is O(V + E): one entry per vertex plus one entry per edge in a directed graph, or two per edge in an undirected graph, since each edge is recorded at both ends.

The simplest form is a map from each node to an array of neighbors, such as a Python dict of lists or a JavaScript Map of arrays. When nodes are numbered from 0 to V - 1, an array of arrays works too and is slightly faster.

A B-tree is a self-balancing search tree whose nodes hold many sorted keys and children, which keeps it shallow so lookups need very few disk or page reads.

A binary search tree node holds one key and has at most two children, so a large tree is many levels deep. A B-tree node holds many keys and has many children, which keeps the tree only a few levels deep and minimizes slow reads from storage.

In a B-tree, keys and their values can live in any node. In a B+ tree, internal nodes only guide the search and all values live in the leaves, which are linked in sorted order, making range scans faster; most database indexes are B+ trees.

Nobody knows for sure. Rudolf Bayer and Edward McCreight, who invented it around 1970, never defined it, and popular guesses include balanced, broad, Bayer, and Boeing, where they worked at the time.

Backtracking is a search technique that builds a solution one choice at a time and undoes the latest choice when it hits a dead end, then tries another option.

Depth-first search traverses the nodes of an existing graph or tree. Backtracking applies the same depth-first order to a tree of choices that it generates as it goes, and it abandons a branch as soon as the partial solution breaks a rule.

In the worst case it is exponential, or even factorial, because it may explore every combination of choices. Pruning cuts the work dramatically in practice, but the worst-case bound usually stays exponential.

Typical examples are sudoku and other constraint puzzles, the N-queens problem, generating all permutations or combinations, finding paths through a maze, and scheduling problems with many rules.

A balanced tree is a tree that keeps its height close to log n by rebalancing after changes, so search, insert, and delete stay O(log n) even in the worst case.

A tree is balanced when its height stays proportional to log n, which usually means that for every node the left and right subtrees have similar heights. Each kind of balanced tree defines this precisely; an AVL tree, for example, allows a height difference of at most one.

Both are self-balancing binary search trees with O(log n) operations. AVL trees are balanced more strictly, so lookups are slightly faster, while red-black trees allow a little more imbalance and need fewer rotations when data changes, which suits workloads with many inserts and deletes.

A hash table is faster for exact-key lookups, O(1) on average, but it keeps no order. A balanced tree keeps keys sorted, so it can efficiently answer range queries, find the next larger key, and list items in order.

Binary search is an algorithm that finds a value in a sorted list by repeatedly halving the search range, taking O(log n) time instead of checking every item.

Binary search decides which half to discard by comparing the target with the middle item. That decision is only correct if everything to the left is smaller and everything to the right is larger, which is true only for sorted data.

Binary search runs in O(log n) time in the worst and average case, and O(1) in the best case, when the middle item is the target. The loop-based version uses O(1) extra memory, while a recursive version uses O(log n) for the call stack.

Sorting costs O(n log n), so it only pays off if you search the same data many times. For a single lookup, a linear search in O(n) is faster, and for many exact-key lookups a hash table is often better still.

A binary search tree is a binary tree in which each node's left subtree holds smaller values and its right subtree larger ones, enabling fast ordered lookups.

Search, insert, and delete take O(h) time, where h is the tree's height. That is O(log n) when the tree is balanced, but it degrades to O(n) when the tree becomes a long chain, for example after inserting values in sorted order.

A binary tree only limits each node to at most two children. A binary search tree adds the rule that left descendants are smaller and right descendants are larger, which is what makes fast searching possible.

It is a BST that automatically restructures itself with rotations after inserts and deletes so that its height stays proportional to log n. AVL trees and red-black trees are the best-known examples, and both guarantee O(log n) search, insert, and delete.

A Bloom filter is a compact probabilistic data structure that tells you an item is definitely not in a set or probably is, while using very little memory.

No. If an item was added, all of its bits are set to 1, so the filter always reports it as possibly present. Only false positives are possible, when other items happen to have set all the same bits.

It depends on how many items you expect and what false positive rate you can accept. As a rule of thumb, about 10 bits per item with 7 hash functions gives a rate just under 1 percent, and each extra 5 bits per item cuts it roughly tenfold.

A hash set stores every item and answers membership exactly, but it needs memory for all the items. A Bloom filter stores only bits, so it is far smaller, but it can return false positives and can't list or, in its basic form, remove items.

Breadth-first search is a graph traversal algorithm that visits nodes in order of their distance from the start, exploring all neighbors before going deeper.

BFS explores all nodes at the current distance before moving farther away, using a queue. DFS follows one path as deep as possible before backtracking, using a stack or recursion. Both run in O(V + E) time, but only BFS finds shortest paths by edge count.

It finds the path with the fewest edges, which is the shortest path when all edges have the same cost. When edges have different weights, such as road distances, use Dijkstra's algorithm instead.

With an adjacency list, BFS runs in O(V + E) time, because it processes each vertex and each edge a constant number of times. With an adjacency matrix, it takes O(V^2), since finding each node's neighbors means scanning a whole row.