20 Most Asked Data Structures Interview Questions

Data structures questions appear in every technical interview round at Indian IT companies, from service-tier tests at TCS and Infosys to product-company design screens.

Knowing the right answer is only part of the challenge. Interviewers also expect you to justify the choice: why a linked list instead of an array, why a heap instead of a sorted list, why DFS instead of BFS. The 20 questions below are grouped by structure type so the trade-off logic is easier to follow.

What Are Data Structures and Why Interviewers Test Them

A data structure organises and stores data in memory. The choice of structure determines an algorithm’s time and space complexity, which is why interviewers treat it as a proxy for how a candidate reasons under constraint.

In Indian placement rounds, DSA questions range from “define and differentiate” at service-tier companies (TCS, Infosys, Wipro) to “write the code and analyse its complexity” at product companies and MNCs. This article covers both levels. For the official course material behind these concepts, the NPTEL Data Structures and Algorithms course from IIT is a free, authoritative reference.

Arrays and Linked Lists

Q1: What is the difference between an array and a linked list?

• Array: contiguous block of memory. Index access is O(1) because element addresses are computed directly (base address + index * element size). Size is typically fixed at declaration.
• Linked list: nodes scattered anywhere in memory, each holding data and a pointer to the next node. Access is O(n); insertion and deletion at a known pointer are O(1).
• Prefer a linked list when: insertions and deletions at the front or middle are frequent, or when the total number of elements is unknown in advance.
• Prefer an array when: random access by index is needed, or cache performance matters (arrays benefit from spatial locality; linked lists do not).

For hands-on practice with the core operations, the array insert, delete, and search tutorial walks through each step with working code.

Q2: How do you detect a cycle in a linked list?

• Use Floyd’s cycle-detection algorithm (the “tortoise and hare” method).
• Maintain two pointers: slow advances one node per step, fast advances two nodes per step.
• If the list has a cycle, fast will eventually lap slow and they will point to the same node.
• If fast or fast.next becomes null, no cycle exists.
• Time: O(n). Space: O(1).

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

Q3: Why can binary search not be applied to a sorted linked list?

• Binary search requires O(1) index access to jump to the midpoint.
• In a linked list, reaching the middle node requires O(n/2) traversal — there is no arithmetic shortcut to an arbitrary position.
• Each “jump” in a binary-search pass therefore costs O(n), making the full pass O(n log n): slower than a plain linear scan.

Q4: What is the difference between a singly and a doubly linked list?

• Singly linked list: each node stores data and a next pointer. Traversal is forward only.
• Doubly linked list: each node stores data, a next pointer, and a prev pointer. Traversal works in both directions.
• Trade-off: doubly linked lists use more memory per node (one extra pointer), but allow O(1) deletion when you have a direct pointer to the node, without needing to traverse backwards to find the previous node.

Q5: Write the C struct for a singly linked list node.

struct node {
    int data;
    struct node *next;
};

For array traversal practice that complements the linked-list questions above, the guide to finding the smallest and largest element in an array covers linear scan patterns used in both structures.

Stacks and Queues

Q6: What is a stack and where is it used?

• A stack is a linear structure that follows Last In First Out (LIFO) ordering.
• Core operations: push (add to top), pop (remove from top), peek (read top without removing). All are O(1).
• Applications:
  • Runtime call stack (function calls and recursion frames)
  • Undo and redo in text editors
  • Infix-to-postfix expression conversion
  • Backtracking algorithms (iterative DFS)
  • Matching parentheses and bracket validation

Q7: How do you implement a queue using two stacks?

• Use stack1 for all enqueue operations (push directly onto stack1).
• For dequeue: if stack2 is empty, pop every element from stack1 into stack2 (this reverses the insertion order, restoring FIFO). Then pop from stack2.
• As long as stack2 is non-empty, dequeue pops directly from it without touching stack1.
• Amortised cost: each element moves from stack1 to stack2 at most once. Per-operation amortised cost is O(1) for both enqueue and dequeue.

Q8: What is a priority queue and how is it different from a regular queue?

• A regular queue is FIFO: elements are served in the order they arrive.
• A priority queue serves the element with the highest (or lowest) priority first, regardless of insertion order.
• Standard implementation: a binary heap. Min-heap for smallest-first; max-heap for largest-first.
• Insert: O(log n). Extract-min or extract-max: O(log n). Peek at root: O(1).
• Use cases: CPU scheduling, Dijkstra’s shortest-path algorithm, Huffman coding, and A* search.

Q9: Convert the infix expression (A + B) * C to postfix.

• Infix: (A + B) * C
• Postfix result: A B + C *
• Step-by-step using the shunting-yard algorithm:
  • Read (: push to operator stack
  • Read A: output A
  • Read +: push to operator stack (after the open parenthesis)
  • Read B: output A B
  • Read ): pop operators until matching (, output: A B +
  • Read *: push * to operator stack
  • Read C: output A B + C
  • End of input: pop remaining operators, output: A B + C *
• Why postfix: the notation eliminates parentheses entirely. A stack can evaluate any postfix expression in a single left-to-right pass.

Trees and Binary Search Trees

Q10: What are the three binary tree traversal orders?

• In-order (Left, Root, Right): for a valid BST, in-order traversal produces nodes in ascending sorted order.
• Pre-order (Root, Left, Right): useful for copying or serialising a tree; the root is always output first.
• Post-order (Left, Right, Root): useful for deleting a tree or evaluating expression trees, because children are processed before their parent.

Q11: What is a Binary Search Tree and why is search efficient?

• A BST is a binary tree satisfying: every node’s left subtree contains only values smaller than the node; the right subtree contains only values larger.
• Search algorithm: compare the target to the current node; go left if smaller, go right if larger, return if equal. Each comparison eliminates half the remaining tree.
• Average time: O(log n), because each step halves the search space.
• Worst case: O(n), when sorted data is inserted without rebalancing, collapsing the tree into a linked-list shape.

Q12: How do you verify that a binary tree is a valid BST?

• Method 1 (in-order traversal): traverse in-order and record the sequence. If the output is strictly ascending, the tree is a BST. Simple to implement; O(n) time and O(n) space for the output list.
• Method 2 (min/max bounds, preferred): pass an allowed range (min, max) recursively. At the root the range is (-infinity, +infinity). For a left child, the upper bound tightens to the parent’s value; for a right child, the lower bound tightens. O(n) time, O(h) space (h = tree height). Correctly handles duplicate-value edge cases.

Q13: What is a balanced BST? Name two common implementations.

• A balanced BST maintains height at O(log n) by rebalancing after insertions and deletions, preventing worst-case O(n) search.
• AVL tree: the oldest self-balancing BST. Maintains the invariant that the height difference between left and right subtrees (the balance factor) is at most 1 at every node. Rebalances via single or double rotations.
• Red-Black tree: allows up to roughly twice the height of the shorter path. Fewer rotations than AVL on average, making insertions and deletions faster in practice. Used internally by Java’s TreeMap and C++ STL’s std::map and std::set.

Q14: Which data structure is best suited for implementing recursion?

• The stack, because recursive call sequencing is LIFO by nature.
• Each function call pushes a new activation record (local variables, return address, parameters) onto the runtime call stack; returning pops it.
• Iterative recursion simulation: replace the implicit system call stack with an explicit one. This gives the programmer control over stack depth and prevents stack-overflow errors on deep inputs. The same LIFO logic, without the OS limit.

Graphs, Hash Tables, and Memory

Q15: How is a graph represented in memory? Compare the two main approaches.

• Adjacency matrix: a 2D array where matrix[i][j] = 1 (or the edge weight) if an edge exists from vertex i to vertex j.
  • Space: O(V squared). Edge lookup: O(1). Best for dense graphs where most pairs of vertices are connected.
• Adjacency list: each vertex holds a list of its neighbours.
  • Space: O(V + E). Edge lookup: O(degree of vertex). Best for sparse graphs where most pairs have no edge.
• Interview shortcut: adjacency matrices waste space on sparse graphs. Adjacency lists waste time on repeated edge-existence queries. Name both and pick based on the given graph density.

Q16: What is the difference between BFS and DFS?

• BFS (Breadth-First Search): uses a queue. Explores all neighbours at depth k before advancing to depth k + 1. Finds the shortest path in unweighted graphs. Time: O(V + E). Space: O(V) for the frontier queue.
• DFS (Depth-First Search): uses a stack or recursion. Goes as deep as possible along one path before backtracking. Used for cycle detection, topological sorting, and connected-component finding. Time: O(V + E). Space: O(V) for the recursion stack or explicit stack.
• When to use each: BFS for shortest-path and level-order problems; DFS for exhaustive traversal, maze-solving, and topological ordering.

Q17: What is a hash table, and how does it handle collisions?

• A hash table maps keys to values using a hash function that converts a key into a bucket index. Average O(1) for insert, delete, and lookup.
• Two collision-resolution strategies:
  • Chaining: each bucket holds a linked list of entries that share the same hash. Handles high load factors gracefully but adds pointer overhead and reduces cache friendliness.
  • Open addressing: on a collision, probe for the next available slot (linear probing, quadratic probing, or double hashing). More cache-friendly than chaining, but the load factor must stay low (typically below 0.7) to maintain O(1) performance.
• In interviews: naming both strategies and explaining the trade-off (memory overhead vs. cache performance) is what separates a complete answer from a partial one.

Q18: What is a memory leak, and how do you prevent it in C and C++?

• A memory leak occurs when dynamically allocated memory is never freed. The block stays claimed for the process lifetime, reducing available heap memory over time without any warning or error at the point of loss.
• In C: every malloc call must have a matching free. Tools like Valgrind detect leaked blocks at runtime.
• In C++: every new must have a matching delete (or delete[] for arrays). Prefer smart pointers: unique_ptr for single ownership, shared_ptr for shared ownership. Both automatically call the destructor and release memory when the object goes out of scope, with no manual delete required.

Coding Problems to Practise Before Your Interview

Q19: Find the Nth node from the end of a linked list.

• Approach (two-pointer technique, single pass):
  • Advance a fast pointer N steps ahead from the head.
  • Then advance both fast and slow together, one step at a time.
  • When fast reaches null (end of list), slow points to the Nth node from the end.
• Time: O(n). Space: O(1). No second traversal needed.

def nth_from_end(head, n):
    fast, slow = head, head
    for _ in range(n):
        if not fast:
            return None  # list is shorter than n
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    return slow

Q20: Find the kth smallest element in an unsorted array.

• Naive approach: sort the array, return the element at index k - 1. Time: O(n log n).
• Better approach (QuickSelect): partial quicksort. Partition the array around a pivot. If the pivot lands at index k - 1, return it. If k falls in the left partition, recurse left; otherwise, recurse right.
  • Average time: O(n). Worst case: O(n squared) with poor pivot selection. Randomised pivot reduces worst-case probability to near zero in practice.

The array insert, delete, and search tutorial covers the foundational array mechanics behind both the naive sort-based approach and the partition logic in QuickSelect.

The two-pointer technique from Q19 appears in string problems too. The guide to checking if a string is a palindrome applies the same converging-pointer logic to character arrays, which is a common follow-up question in the same interview round.

The BFS, DFS, and hash-table lookup patterns from Q15 to Q17 in this article reappear in AI system design: transformer attention layers model token relationships as weighted directed graphs, and embedding lookups are hash-table probes at scale. To see those patterns running in actual language models, TinkerLLM is the entry point at ₹299, before committing to a longer programme.