CS Fundamentals · Fresher-relevant
Data structures interview questions on arrays, linked lists, trees, graphs, stacks, and queues — mandatory for every engineering role at Indian tech companies.
When would you use an array vs a linked list?
Tip: Arrays give O(1) random access and cache-friendly contiguous memory but O(n) insertion/deletion in the middle. Linked lists give O(1) insert/delete given a node but O(n) access and poor cache locality. Use arrays for indexing-heavy work, linked lists for frequent middle insertions.
How does a hash table work and how are collisions handled?
Tip: A hash function maps keys to bucket indices for average O(1) lookup. Collisions are resolved by chaining (linked list/tree per bucket) or open addressing (linear/quadratic probing). Load factor triggers resizing/rehashing. Worst case degrades to O(n) with poor hashing.
What is the difference between a stack and a queue?
Tip: A stack is LIFO (push/pop at one end) — used for function calls, undo, and DFS. A queue is FIFO (enqueue rear, dequeue front) — used for scheduling and BFS. Both support O(1) insert/remove.
Compare BFS and DFS on a graph.
Tip: BFS uses a queue, explores level by level, and finds shortest paths in unweighted graphs; memory grows with the frontier width. DFS uses a stack/recursion, goes deep first, uses less memory on wide graphs, and suits cycle detection and topological sort. Both are O(V+E).
What is a binary search tree and when does it degrade?
Tip: A BST keeps left < node < right, giving O(log n) search/insert when balanced. Inserting sorted data degrades it into a linked list (O(n)). Self-balancing trees (AVL, Red-Black) keep height logarithmic by rotating on insert/delete.
What is a heap and what is it used for?
Tip: A binary heap is a complete tree where each parent is ≤ (min-heap) or ≥ (max-heap) its children, stored in an array. It gives O(1) peek and O(log n) insert/extract — used for priority queues, Dijkstra, and finding the top-K elements.
What is a trie and when is it the right choice?
Tip: A trie (prefix tree) stores strings by shared prefixes, giving O(L) lookup/insert where L is word length, independent of the number of words. Ideal for autocomplete, prefix search, and dictionary/spell-check — at the cost of higher memory.
How do you detect a cycle in a linked list?
Tip: Floyd's cycle detection (tortoise and hare): advance one pointer by 1 and another by 2; if they meet, there is a cycle. It uses O(1) extra space vs a hash set's O(n). To find the cycle start, reset one pointer to head and advance both by 1.
InterviewEra generates role-specific questions using your actual projects and skills. Get scored feedback on technical depth, clarity, and structure — free to start.