Data Structures Interview Questions for Freshers: 60 Theory Questions with Answers

Data structures theory is the most predictable part of a fresher technical interview. Whether it is a TCS Digital or Infosys Specialist Programmer interview, an off-campus round at a mid-size product company, or follow-up questions after a coding test at a startup, the same sixty-odd concepts come up. The difference between an average and a strong fresher is not knowing more structures; it is explaining the familiar ones precisely, with costs, trade-offs and a real example.

Each answer below is written the way you should say it: definition, key property, complexity, use case. Where interviewers usually ask you to write code, a compact version is included. For the problem-solving side of each structure, follow the links to our pattern guides.

How Data Structures Theory Is Asked in Fresher Interviews

Data Structures Complexity Cheat Sheet

If any entry here is not obvious to you, read our Big-O explainer first; interviewers will ask "why" for at least one of these.

Arrays and Strings: Questions 1-10

Q1. What is a data structure, and what is the difference between linear and non-linear structures?

A data structure is a way of organizing data in memory so that the operations you need are efficient. Linear structures arrange elements in a sequence where each has at most one predecessor and successor: arrays, linked lists, stacks, queues. Non-linear structures allow branching or arbitrary connections: trees and graphs. A good extra line: the "right" structure depends on which operations dominate, such as lookup by key versus ordered traversal.

Q2. What is an array and why is access O(1)?

An array is a fixed-size collection of elements of the same type stored in contiguous memory. The address of element i is computed directly: base + i × size_of_element. One multiplication and one addition, regardless of i, so access is O(1). Contiguity also makes arrays cache-friendly: reading a[i] loads neighbours into the CPU cache.

Q3. Why do arrays start at index 0?

Because the index is an offset from the base address. Element 0 is at base + 0. Starting at 1 would need an extra subtraction on every access. It is a convention inherited from C and its pointer arithmetic, where a[i] is defined as *(a + i).

Q4. What is a dynamic array, and why is append amortized O(1)?

A dynamic array (C++ vector, Java ArrayList, Python list) wraps a fixed array and, when full, allocates a bigger one (typically 1.5x or 2x) and copies elements across. A single resize costs O(n), but with doubling, n appends cause copies totalling about 1 + 2 + 4 + ... + n < 2n, so the average cost per append is O(1). That averaging over a sequence of operations is what "amortized" means.

Follow-up: "Why not grow by a fixed 10 elements?" Then n appends cost about n²/20 copies, which is O(n) per append. Geometric growth is what makes it amortized O(1).

Q5. What are the disadvantages of arrays?

Fixed size for static arrays (you over-allocate or run out), costly insertion and deletion in the middle (shifting O(n) elements), and a need for one large contiguous block, which can fail when memory is fragmented even if total free memory is sufficient.

Q6. How is a 2D array stored in memory?

In row-major order (C, C++, Java's rows, Python NumPy default): row 0 fully, then row 1. The address of a[i][j] in an R × C array is base + (i × C + j) × size. Fortran and MATLAB use column-major order. This explains why iterating row by row is faster than column by column in C++: you walk memory sequentially. In Java, a 2D array is actually an array of references to separate row arrays.

Q7. What is the difference between an array and an ArrayList / vector?

A plain array has a fixed length set at creation. An ArrayList or vector resizes automatically and offers methods like add and remove. In Java, arrays can hold primitives directly, whereas ArrayList holds objects, so ArrayList<Integer> boxes each int, costing memory. Our Java collections guide and C++ STL guide cover these trade-offs in detail.

Q8. Why are strings immutable in Java and Python?

Immutability makes strings safe to share between threads and to use as hash map keys (the hash cannot change after insertion), allows caching of hash codes, and enables string pooling (Java's string constant pool). The cost: every "modification" creates a new string, so concatenating in a loop is O(n²) overall. Use StringBuilder in Java or "".join(parts) in Python.

Q9. What is a sparse matrix and how do you store it?

A matrix where most elements are zero. Storing it as a full 2D array wastes memory. Alternatives: a list of (row, col, value) triplets, a hash map from (row, col) to value, or compressed sparse row (CSR) format used in scientific computing. A 10,000 × 10,000 matrix with 50,000 non-zeros needs 100 million cells as a 2D array but only 50,000 triplets.

Q10. How would you find a duplicate in an array, and what are the trade-offs?

Three answers, in increasing sophistication: compare all pairs (O(n²) time, O(1) space); sort and check neighbours (O(n log n) time, modifies the input); use a hash set (O(n) time, O(n) space). For the special case of n + 1 numbers in the range 1..n, Floyd's cycle detection finds the duplicate in O(n) time and O(1) space without modifying the array. Naming the trade-off at each step is exactly what interviewers want. More patterns in our arrays problems guide.

Linked Lists: Questions 11-19

Q11. What is a linked list and what are its types?

A linked list is a sequence of nodes, each holding data and a pointer to the next node. Types: singly linked (next only), doubly linked (next and prev, allowing backward traversal and O(1) deletion given just the node), and circular (the last node points back to the first, useful for round-robin scheduling).

Q12. Array vs linked list: when would you choose each?

Choose an array when you access by index or iterate a lot; choose a linked list when you insert and remove at known positions frequently, such as an LRU cache's recency list or an OS free-memory list. A mature caveat: because of caching, arrays often beat linked lists in practice even for moderate middle insertions.

Q13. Write code to reverse a singly linked list.

Walk the list once, flipping each next pointer to point backward. Keep three pointers: prev, curr and next.

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    while (curr != nullptr) {
        Node* next = curr->next;   // save the rest of the list
        curr->next = prev;         // flip the pointer
        prev = curr;               // advance prev
        curr = next;               // advance curr
    }
    return prev;                   // new head
}

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

def reverse_list(head):
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

Dry run on 1 → 2 → 3: start prev = null, curr = 1. Step 1: 1.next = null, prev = 1, curr = 2. Step 2: 2.next = 1, prev = 2, curr = 3. Step 3: 3.next = 2, prev = 3, curr = null. Return 3, giving 3 → 2 → 1. O(n) time, O(1) space. (In the Python one-liner, the right side is evaluated fully before assigning left to right, so curr.next is set before curr moves.)

Q14. How do you detect a loop in a linked list?

Floyd's cycle detection (tortoise and hare): move slow one step and fast two steps. If there is a cycle, fast eventually laps slow and they meet; if fast reaches null, there is no cycle. O(n) time, O(1) space. To find where the cycle starts, reset one pointer to the head and move both one step at a time; they meet at the cycle's start. The reason: if the distance from head to cycle start is a, the meeting point is a steps (mod cycle length) short of the start.

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

An alternative is storing visited nodes in a hash set: O(n) time but O(n) space. Mention both.

Q15. How do you find the middle of a linked list in one pass?

Same slow and fast pointers: when fast reaches the end, slow is at the middle. For an even-length list, the loop condition decides whether you get the first or second middle. With while fast and fast.next starting both at head, you get the second middle.

Q16. How would you delete a node when you are given only a pointer to that node?

Copy the next node's data into this node and delete the next node instead. It fails for the last node, which cannot be deleted this way in a singly linked list. Interviewers ask this to see if you notice that edge case.

Q17. What are the advantages of a doubly linked list, and its costs?

You can traverse backwards and delete a node in O(1) given only a pointer to it, since you can reach its predecessor. The cost is an extra pointer per node and more pointer updates on every insert and delete, which means more chances for bugs. Uses: browser back/forward history, LRU caches (doubly linked list plus hash map, see LRU cache explained), and undo/redo stacks in editors.

Q18. What is a sentinel (dummy) node?

A dummy node placed before the real head so that the empty list and head-insertion cases need no special code. In interviews, starting a merge or deletion with dummy = Node(0); dummy.next = head and returning dummy.next eliminates a whole class of null-pointer bugs.

Q19. How do you find the intersection point of two linked lists?

Run two pointers, one from each head; when one reaches the end, redirect it to the other list's head. Both pointers then travel the same total distance (lenA + lenB) and meet at the intersection, or both reach null together if there is none. O(m + n) time, O(1) space. The length-difference method (advance the longer list by the difference first) is equally valid. More linked list patterns in our linked list problems guide.

Stacks and Queues: Questions 20-29

Q20. What is a stack and where is it used?

A stack is a LIFO (last in, first out) structure with push, pop and peek, all O(1). Uses: the function call stack, undo in editors, browser back button, expression evaluation, balanced bracket checking, DFS, and backtracking. A stack overflow happens when recursion goes too deep and the call stack exceeds its limit.

Q21. Check if brackets are balanced.

#include <stack>
#include <string>

bool isBalanced(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char open = st.top();
            st.pop();
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) return false;
        }
    }
    return st.empty();   // leftover openers mean unbalanced
}

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
        elif c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack

Dry run on "{[()]}": push {, push [, push (; ")" pops ( which matches; "]" pops [; "}" pops {; stack empty, so balanced. On "(]" the "]" pops "(", mismatch, false. Edge cases to mention: empty string (balanced), a closing bracket first (false), only openers (false).

Q22. What are infix, prefix and postfix expressions, and why use postfix?

Infix places operators between operands (A + B * C), prefix before (+ A * B C), postfix after (A B C * +). Postfix needs no parentheses or precedence rules during evaluation: scan left to right, push operands, and on an operator pop two operands, apply it, and push the result. Compilers convert infix to postfix with the shunting-yard algorithm, which uses an operator stack. Converting (A + B) * C gives A B + C *.

Q23. What is a queue and where is it used?

A queue is FIFO (first in, first out): enqueue at the rear, dequeue from the front, both O(1). Uses: BFS, CPU and printer job scheduling, request buffering in web servers, message queues between services (for example, payment events processed in order), and the waiting list in IRCTC-style booking systems.

Q24. What is a circular queue and why is it needed?

In a simple array queue, the front moves forward as you dequeue, leaving unusable space at the start. A circular queue wraps indices with modulo: rear = (rear + 1) % capacity. A classic interview detail is distinguishing full from empty, since in both cases front can equal rear. Common solutions: keep a count variable, or leave one slot empty and treat (rear + 1) % capacity == front as full.

class CircularQueue:
    def __init__(self, capacity):
        self.buf = [None] * capacity
        self.cap = capacity
        self.front = 0
        self.count = 0

    def enqueue(self, x):
        if self.count == self.cap:
            raise OverflowError("queue full")
        rear = (self.front + self.count) % self.cap
        self.buf[rear] = x
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise IndexError("queue empty")
        x = self.buf[self.front]
        self.front = (self.front + 1) % self.cap
        self.count -= 1
        return x

Q25. What is a deque?

A double-ended queue supports insertion and removal at both ends in O(1). It can act as both a stack and a queue. Uses: the sliding window maximum problem (a monotonic deque), work-stealing schedulers, and palindrome checking. In Python use collections.deque, not a list, because list.pop(0) is O(n).

Q26. What is a priority queue? Is it a queue?

A priority queue serves the element with the highest (or lowest) priority first, not the earliest arrival. It is an abstract data type, usually implemented with a binary heap: insert and extract in O(log n), peek in O(1). Uses: Dijkstra's algorithm, task scheduling by priority, merging k sorted lists, and finding the top k items.

Q27. How do you implement a queue using two stacks?

Push incoming elements onto an in stack. To dequeue, if the out stack is empty, pop everything from in and push onto out, which reverses the order; then pop from out. Each element is moved at most once, so dequeue is amortized O(1) even though a single dequeue can be O(n).

Q28. How do you implement a stack using queues?

With one queue: on push, enqueue the new element and then rotate the queue by dequeuing and re-enqueuing the previous n - 1 elements, so the newest is at the front. Push becomes O(n) and pop O(1). It is mostly a thinking exercise; say so and give the complexity.

Q29. Stack vs queue vs heap memory: are they related?

Mostly a naming coincidence, but freshers are often asked. The call stack memory region does behave like a stack (frames are pushed on calls and popped on return). Heap memory is the region for dynamic allocation (new, malloc) and has nothing to do with the heap data structure. Clarifying this distinction unprompted earns credit.

Hashing: Questions 30-37

Q30. What is hashing and what is a hash table?

Hashing maps a key to an integer with a hash function, and a hash table uses that integer modulo the table size as an index into an array of buckets. Lookup, insert and delete are O(1) on average because you jump straight to the bucket. Examples: HashMap in Java, unordered_map in C++, dict in Python.

Q31. What makes a good hash function?

It is deterministic (same key, same hash), fast to compute, and spreads keys uniformly across buckets so similar keys do not cluster. It must be consistent with equality: equal keys must produce equal hashes. That is why in Java, if you override equals() you must override hashCode(), or two "equal" objects land in different buckets and lookups fail.

Q32. What is a collision and how is it handled?

A collision is two keys mapping to the same bucket. It is unavoidable when there are more possible keys than buckets (pigeonhole principle). Two main strategies:

• Separate chaining: each bucket holds a list (or tree) of entries. Simple, degrades gracefully. Used by Java's HashMap and typical C++ unordered_map implementations.
• Open addressing: store everything in the array itself and on collision probe for another slot: linear probing (next slot), quadratic probing (1, 4, 9 slots away) or double hashing (a second hash decides the step). Cache-friendly but sensitive to load factor. Python's dict uses open addressing.

Q33. What is load factor and rehashing?

Load factor = number of entries / number of buckets. As it grows, chains get longer or probes get longer. When it crosses a threshold (0.75 by default in Java's HashMap), the table is resized, usually doubled, and every entry is rehashed into the new array. A single resize is O(n), but amortized over insertions it is O(1), just like dynamic arrays.

Q34. What is the worst-case time of a hash table lookup, and how does Java mitigate it?

O(n), if all keys collide into one bucket, either due to a poor hash function or deliberate attack (hash flooding). Since Java 8, a HashMap bucket whose chain reaches 8 entries is converted into a red-black tree (when the table has at least 64 buckets), so the worst case for that bucket becomes O(log n). Mentioning this detail is a reliable way to stand out in a fresher interview.

Q35. What is clustering in linear probing?

Primary clustering: occupied slots form long contiguous runs, and any key hashing into a run has to probe to its end, making the run longer still. Quadratic probing reduces primary clustering but causes secondary clustering (keys with the same initial hash follow the same probe sequence). Double hashing avoids both. Also, deletions in open addressing need tombstones, because simply emptying a slot would break probe chains for other keys.

Q36. HashMap vs TreeMap (or unordered_map vs map)?

Hash-based maps give O(1) average operations but no ordering. Tree-based maps (red-black trees) give O(log n) operations with keys kept sorted, so you can iterate in order, find the floor or ceiling of a key, or take a range. Use a tree map for "find the nearest price below X" or a leaderboard; use a hash map for plain lookups.

Q37. Where is hashing used in real systems?

Caches, database hash indexes, symbol tables in compilers, deduplication, password storage (cryptographic hashes with salts, a different family of hash function), consistent hashing to spread keys across cache servers, and Bloom filters. Interview problems built on hashing (two sum, group anagrams, longest consecutive sequence) are covered in our hashing problems guide.

Trees and Binary Search Trees: Questions 38-49

Q38. What is a tree? Define root, leaf, height and depth.

A tree is a connected acyclic graph, usually drawn as a hierarchy. The root has no parent; a leaf has no children. The depth of a node is the number of edges from the root to it; the height of a tree is the number of edges on the longest root-to-leaf path. A tree with n nodes always has exactly n - 1 edges. Some textbooks count height in nodes instead of edges; state your convention.

Q39. What are full, complete, perfect and balanced binary trees?

• Full: every node has 0 or 2 children.
• Complete: every level is completely filled except possibly the last, which is filled from left to right. Heaps are complete trees, which is why they fit in an array.
• Perfect: all internal nodes have 2 children and all leaves are at the same level. A perfect tree of height h has 2^h+1 - 1 nodes.
• Balanced: the heights of the left and right subtrees of every node differ by at most a small amount (1 for AVL), which keeps height O(log n).

Q40. What is the maximum number of nodes at level i, and the minimum height of a binary tree with n nodes?

At most 2ⁱ nodes at level i (root at level 0). A binary tree with n nodes has height at least ⌊log₂ n⌋ (a complete tree) and at most n - 1 (a skewed tree, which is effectively a linked list).

Q41. What are the tree traversals?

Depth-first: inorder (left, root, right), preorder (root, left, right), postorder (left, right, root). Breadth-first: level order, which visits level by level using a queue. For the tree with root 1, left child 2 (children 4, 5) and right child 3: inorder 4 2 5 1 3, preorder 1 2 4 5 3, postorder 4 5 2 3 1, level order 1 2 3 4 5. Inorder of a BST gives sorted order; preorder is used to copy or serialize a tree; postorder to delete a tree or evaluate expression trees.

Q42. Write level order traversal.

#include <queue>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> levels;
    if (!root) return levels;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();                  // nodes on the current level
        std::vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        levels.push_back(level);
    }
    return levels;
}

from collections import deque

def level_order(root):
    if not root:
        return []
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):          # snapshot of this level's size
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels

O(n) time; O(w) space where w is the maximum width of the tree, up to about n/2 for the last level of a complete tree. More traversal problems in our binary tree problems guide.

Q43. Can you reconstruct a binary tree from traversals?

Yes from inorder plus preorder or inorder plus postorder, provided values are unique: preorder (or postorder) tells you the root, and inorder splits the remaining nodes into left and right subtrees. Preorder plus postorder alone is not enough in general, because a node with one child is ambiguous (left or right?); it works only for full binary trees.

Q44. What is a binary search tree?

A binary tree where, for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. Search, insert and delete take O(h): compare and go left or right. A common trap is checking only the immediate children; the property applies to whole subtrees. A tree where 10 has left child 5, and 5 has right child 12, fails even though each parent-child pair looks fine locally.

Q45. How do you delete a node from a BST?

Three cases. A leaf: just remove it. One child: replace the node with its child. Two children: replace its value with its inorder successor (smallest key in the right subtree) or inorder predecessor, then delete that successor, which has at most one child. All O(h).

Q46. What is the worst case of a BST and how do you avoid it?

Inserting sorted keys (1, 2, 3, 4, ...) makes every node a right child: a skewed tree of height n - 1, so operations become O(n). Self-balancing BSTs fix this by restructuring with rotations after inserts and deletes: AVL trees keep subtree heights within 1 (stricter balance, faster lookups), red-black trees use node colouring rules that keep height under 2 log₂(n + 1) (fewer rotations, faster writes). Java's TreeMap and C++'s std::map are typically red-black trees.

Q47. What is a B-tree and why do databases use it?

A B-tree is a balanced search tree where each node holds many keys and has many children, so the tree is very shallow. Each node is sized to a disk page. Since reading a page from disk is far slower than comparing keys in memory, a tree with fanout of hundreds needs only 3 or 4 page reads to find a key among millions of rows. B+ trees, a variant storing all values in linked leaf nodes, are used by MySQL InnoDB and PostgreSQL indexes. See B-tree indexing explained.

Q48. How do you check whether a binary tree is a valid BST?

Recurse with a valid range: each node must lie strictly between a lower and upper bound, starting with (-∞, +∞); going left tightens the upper bound to the node's value, going right tightens the lower bound. Alternatively, do an inorder traversal and check the sequence is strictly increasing. Both are O(n).

Q49. What is the lowest common ancestor?

The deepest node that has both given nodes as descendants (a node counts as its own descendant). In a BST, walk from the root: if both keys are smaller go left, if both larger go right, otherwise the current node is the LCA, O(h). In a general binary tree, recurse: if the current node is one of the targets return it; if the targets are found in different subtrees, the current node is the LCA. Full treatment in LCA explained.

Heaps and Tries: Questions 50-54

Q50. What is a binary heap and how is it stored?

A complete binary tree where every parent is smaller than its children (min-heap) or larger (max-heap). Because it is complete, it is stored in an array with no pointers: for index i (0-based), the children are at 2i + 1 and 2i + 2, and the parent at ⌊(i - 1) / 2⌋. Insert appends and sifts up; extract moves the last element to the root and sifts down. Both are O(log n).

Q51. Why is building a heap O(n) and not O(n log n)?

Bottom-up heapify calls sift-down on each non-leaf node from the last one up to the root. Most nodes are near the bottom and sift down only a short distance: about n/4 nodes move at most 1 level, n/8 at most 2, and so on. The sum n/4 × 1 + n/8 × 2 + n/16 × 3 + ... converges to O(n). Inserting elements one at a time would be O(n log n).

Q52. Heap vs BST: which would you use?

A heap gives O(1) access to the min or max and O(log n) insert and extract, with a compact array and fast build, but searching for an arbitrary key is O(n) and it is not sorted. A balanced BST gives O(log n) for search, insert, delete, min, max, plus ordered iteration and range queries. If you only ever need "the next smallest", use a heap; if you need lookups or ordering, use a BST. Practice problems in heap and priority queue problems.

Q53. How do you find the k largest elements in a stream?

Keep a min-heap of size k. For each new element, push it; if the heap exceeds k, pop the smallest. The heap always holds the k largest seen so far, and its root is the kth largest. O(n log k) time and O(k) space, much better than sorting when k is small, and it works on streams that do not fit in memory.

Q54. What is a trie?

A trie (prefix tree) stores strings character by character along paths from the root, with a flag marking word endings. Insert and search take O(L) where L is the word length, independent of how many words are stored, and all words with a given prefix sit in one subtree. Uses: autocomplete, spell checkers, IP routing (longest prefix match). The cost is memory: each node may hold up to 26 child pointers for lowercase English. See trie problems.

Graphs: Questions 55-60

Q55. What is a graph and what are the types?

A graph G = (V, E) is a set of vertices and edges connecting them. Graphs can be directed (one-way edges, like Twitter follows) or undirected (two-way, like Facebook friendships), weighted (road distances) or unweighted, cyclic or acyclic. A directed acyclic graph (DAG) models dependencies such as course prerequisites or build steps. A tree is a connected acyclic undirected graph.

Q56. Adjacency matrix vs adjacency list?

A social network with 100 million users and a few hundred friends each is extremely sparse; a matrix would need 10¹⁶ cells. That is why adjacency lists are the default.

Q57. BFS vs DFS?

BFS explores level by level with a queue and finds the shortest path in an unweighted graph. DFS goes as deep as possible with a stack or recursion, and is natural for cycle detection, topological sort, connected components and backtracking. Both are O(V + E) time with an adjacency list. BFS memory grows with the graph's width; DFS memory grows with its depth, and deep recursion can overflow the stack.

from collections import deque

def bfs_shortest_path(graph, src):
    """graph: dict node -> list of neighbours. Returns distance (in edges) from src."""
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:          # mark when enqueued, not when dequeued
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

g = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_shortest_path(g, "A"))   # {'A': 0, 'B': 1, 'C': 1, 'D': 2}

Mention the comment in the code: marking a node visited when it is enqueued prevents the same node from being added multiple times. Deeper practice in our BFS and DFS problems guide.

Q58. How do you detect a cycle in a graph?

In an undirected graph: DFS and look for a visited neighbour that is not the parent, or use union-find (an edge whose endpoints are already in the same set closes a cycle). In a directed graph: DFS with three colours (unvisited, in the current recursion stack, finished); reaching a node that is on the current stack means a back edge, hence a cycle. Alternatively, Kahn's topological sort fails to process all nodes when a cycle exists.

Q59. What is topological sorting?

A linear ordering of a DAG's vertices such that for every edge u → v, u comes before v. Used for build systems, course scheduling, and task pipelines. Kahn's algorithm repeatedly removes nodes with in-degree zero using a queue; the DFS approach adds nodes to the front of the order after finishing them. Both O(V + E). It exists only for DAGs. See topological sort problems.

Q60. Name the shortest path and minimum spanning tree algorithms and when each applies.

• BFS: unweighted graphs, O(V + E).
• Dijkstra: non-negative weights, O((V + E) log V) with a binary heap. Fails with negative edges because it finalizes nodes greedily.
• Bellman-Ford: handles negative weights and detects negative cycles, O(V × E).
• Floyd-Warshall: all pairs, O(V³), fine for a few hundred vertices.
• MST: Kruskal's (sort edges, add the cheapest that does not form a cycle, using union-find) or Prim's (grow from a vertex using a min-heap). An MST connects all vertices with minimum total weight, like laying fibre cable between cities at least cost.

Our shortest path guide has code and dry runs for each.

How to Answer Like a Strong Fresher

• Volunteer the worst case. Saying "O(1) average, but O(n) if many keys collide" before being asked shows depth.
• Draw it. For trees, heaps and linked lists, sketch three or four nodes on paper while explaining. It slows you down in a good way and catches pointer mistakes.
• Know your language's built-ins. If you use C++, know that std::map is a balanced tree and std::unordered_map is a hash table. In Java, know ArrayDeque is preferred over Stack.
• Connect to your project. "In my college project I used a hash map from roll number to student record" makes theory concrete and invites friendly follow-ups.
• Do not bluff. If you do not remember red-black tree rules, say you know they keep height O(log n) through colouring and rotations, and move on.

Once these sixty answers feel easy, move to applying them: our DSA roadmap sequences the problem patterns that build on each structure, which is what the coding rounds after the theory interview will test.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.