Common Data Structures and Algorithms Asked in Technical Interviews

Linked Lists

Linked lists consist of nodes where each node holds data and a pointer to the next node (and sometimes a previous node for doubly linked lists). They allow O(1) insertion and deletion at the head or tail once the node is located, but access is O(n) because you must traverse from the head. Classic interview problems include detecting cycles (Floyd’s cycle detection), reversing a linked list in place, finding the middle node, and merging two sorted lists. Linked lists are also used to implement stacks and queues. Be prepared to handle null references and to manipulate pointers correctly during recursion or iteration.

Stacks

A stack follows the Last-In-First-Out (LIFO) principle. Operations: push (insert), pop (remove top), peek (view top). Stacks are used in expression evaluation (postfix, prefix), undo features in editors, function call management (call stack), and depth-first search. Common interview questions include implementing a stack that supports push, pop, and retrieving the minimum element in constant time; checking balanced parentheses; and evaluating Reverse Polish Notation. Stacks can be implemented with arrays or linked lists; choose the one that best fits the problem constraints.

Queues

A queue follows First-In-First-Out (FIFO). Essential in breadth-first search, task scheduling, print spooling, and buffering. Variations include deque (double-ended queue), priority queue (each element has a priority, often implemented with a heap), and circular queue to efficiently reuse space. Interview problems often involve implementing a queue using two stacks, designing a BFS on a graph, or using a priority queue for merging k sorted lists. Understanding enqueue and dequeue time complexities is crucial: for a queue implemented with a linked list, both are O(1); for an array-based queue, careful handling of front/rear pointers can also achieve O(1) amortized.

Hash Tables

Hash tables (also called hash maps) store key-value pairs and provide average O(1) insertion, deletion, and lookup. They are used to implement caches, symbol tables, and more. Collisions are resolved via chaining (linked list per bucket) or open addressing. In interviews, hash tables appear in problems like finding two numbers that sum to a target (Two Sum), counting character frequencies, detecting duplicates, or building an in-memory index. You should know how to design a hash function, understand load factor and rehashing, and be aware of the trade-offs between memory and speed. Many languages provide built-in hash tables (e.g., HashMap in Java, dict in Python), but you may be asked to implement one from scratch.

Trees

Trees come in many forms: binary trees, binary search trees (BST), balanced BSTs (AVL, Red-Black), heaps, tries, segment trees, and more. Tree problems test recursive thinking, traversal techniques (in-order, pre-order, post-order, level-order), and balancing. Typical interview questions: validate if a binary tree is a BST, find the lowest common ancestor, serialize/deserialize a tree, compute tree height, or perform a level-order traversal. Heaps (min-heap and max-heap) are used for priority queues and sorting (heap sort). Tries are excellent for string operations like autocomplete or spell checking. Knowing the height O(log n) for balanced trees versus O(n) for skewed ones is key.

Graphs

Graphs consist of nodes (vertices) and edges. They can be directed or undirected, weighted or unweighted, with possible cycles. Graphs model social networks, maps, dependency resolution, and many real-world systems. Core algorithms: BFS (shortest path in unweighted graph), DFS (connectivity, cycle detection, topological sort), and Dijkstra’s algorithm (shortest path with non-negative weights). Other prominent graph algorithms include Bellman-Ford (negative weights), Floyd-Warshall (all-pairs shortest path), and Union-Find (disjoint sets) for detecting cycles in undirected graphs. Interview problems often involve representing a graph using adjacency lists or matrices, then applying BFS/DFS to solve problems like word ladder, island count, or course scheduling.

Common Algorithms

Algorithms are step-by-step procedures for solving problems. Interviewers evaluate not only correctness but also efficiency and clarity of reasoning. Here we cover the algorithm categories that appear most frequently.

Sorting Algorithms

Knowing when to use Quick Sort (average O(n log n), O(log n) stack space, but worst-case O(n²)), Merge Sort (O(n log n) guaranteed, but O(n) extra space), and Heap Sort (O(n log n) in-place) is essential. Bubble Sort and Insertion Sort are less efficient (O(n²)) but may appear as a starting point for optimization discussions. Be able to implement a stable sort and understand divide-and-conquer. Many problems can be solved more easily after sorting the input (e.g., merging intervals, finding the k-th largest element). Also, understand counting sort and radix sort for special cases with integer keys.

Searching Algorithms

Binary Search is one of the most powerful tools: works on sorted arrays in O(log n) time. You must be comfortable with iterative and recursive implementations and handling edge cases (duplicates, empty arrays, overflow when calculating mid). Beyond standard binary search, variations like searching in rotated sorted arrays, finding the first/last occurrence, and searching in a 2D matrix are common. Linear Search is O(n) and rarely optimal, but it can be a fallback for unsorted data or as a subroutine. Try to think if a problem can be reduced to search in a monotonic condition (binary search on answer) – a very common pattern.

Recursion

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. It is fundamental for tree and graph traversal, divide-and-conquer algorithms, and backtracking. Many interview candidates struggle with recursion because of complexity in managing state and base cases. Practice converting recursion to iteration (and vice versa), understanding the call stack, and analyzing recursion depth. Classic recursion problems: factorial, Fibonacci (naive vs. memoized), generating permutations/combinations, Tower of Hanoi, and solving N-Queens. Ensure you can write a clean recursive function with a well-defined base case and avoid stack overflow by considering tail recursion or iterative solutions when depth is large.

Dynamic Programming

Dynamic programming (DP) optimizes recursive solutions by storing results of subproblems to avoid recomputation – either via top-down recursion with memoization or bottom-up tabulation. DP problems often have an optimal substructure and overlapping subproblems. Common categories: 0/1 knapsack, longest common subsequence, edit distance, coin change, longest increasing subsequence, and matrix chain multiplication. Master the DP pattern: identify the state and recurrence, handle base cases, and choose between iterative and recursive approaches. Interviewers often ask you to first describe a brute-force recursive solution, then optimize it with DP. Practice problems on platforms like LeetCode that specifically mark DP (medium to hard). Recognize that not every problem with a recurrence is DP; some can be solved with greedy or divide and conquer.

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step with the hope of finding a global optimum. They work for problems with a matroid structure, like activity selection, Huffman coding, or Dijkstra’s algorithm. However, they can lead to suboptimal solutions if applied incorrectly. Interview questions that test greedy thinking include: minimum number of coins (only certain denominations), job sequencing with deadlines, interval scheduling maximization, and gas station problem. You must justify why the greedy choice leads to an optimal solution, often by proving that the problem exhibits the greedy choice property and optimal substructure.

Graph Algorithms

We already mentioned graph traversal under data structures, but the algorithms themselves deserve separate attention. BFS finds the shortest path in unweighted graphs and is used in many problems (print all nodes level by level). DFS is used for topological sorting in directed acyclic graphs (DFS with stack), detecting cycles, and solving maze-like puzzles. Dijkstra’s algorithm uses a priority queue and works only with non-negative weights; Bellman-Ford handles negative weights and detects negative cycles. Floyd-Warshall provides all-pairs shortest paths in O(V³). Union-Find is a data structure that efficiently tracks connected components and is used in Kruskal’s algorithm for minimum spanning tree. Be ready to implement these algorithms from memory, handling edge cases such as disconnected graphs, multiple edges, and self-loops.

Complexity Analysis

Understanding time and space complexity (Big O notation) is non-negotiable. Every interview question expects you to analyze your solution’s runtime in terms of worst-case, average, and best-case. You should be comfortable computing complexities for recursive algorithms using recurrence relations and the Master Theorem for divide-and-conquer. Also evaluate space complexity: recursive call stack depth, auxiliary data structures, and in-place vs. out-of-place modifications. Practice explaining complexities clearly: “This algorithm runs in O(n log n) time and O(1) extra space” gives the interviewer confidence that you consider efficiency.

How to Approach Data Structure and Algorithm Problems

Having a systematic problem-solving process can dramatically improve interview performance. A common framework is: 1) Understand the problem – ask clarifying questions about input size, edge cases, expected output format. 2) Choose an approach – consider brute force first, then look for patterns (two-pointer, sliding window, binary search, DP, etc.). 3) Write clean code – use meaningful variable names, handle edge cases (null, empty input). 4) Test your solution – run through a few test cases, including boundary conditions. 5) Optimize – identify bottlenecks, trade off space for time if needed. Practice speaking aloud as you code; the interviewer wants to follow your thought process, not just see the final answer.

Study Plan and Resources

Consistent practice is more effective than cramming. Aim to solve a mix of easy, medium, and hard problems across different topics. Use these resources:

• LeetCode – Extensive collection of interview questions with solution discussions. Recommended to filter by data structure or algorithm tag.
• HackerRank – Good for practicing in different domains (algorithms, data structures, C, Java, Python).
• GeeksforGeeks – Excellent for theory and problem examples. See for example their data structures page.
• InterviewBit – Curated track for coding interview preparation.
• Books – “Cracking the Coding Interview” by Gayle Laakmann McDowell remains a standard reference. “Introduction to Algorithms” (CLRS) for deeper theory.

Schedule daily or weekly practice sessions. Focus on one data structure or algorithm at a time. Track your progress by creating a spreadsheet of problems solved, with notes on the pattern used and runtime complexity. After solving a problem, read others’ solutions to see different perspectives.

Common Mistakes to Avoid

• Jumping to code too quickly – Always take time to think and outline your approach.
• Ignoring edge cases – Off-by-one errors, empty input, null values, duplicate elements, large inputs causing overflow.
• Overcomplicating the solution – Simpler code is easier to maintain and debug; if your solution uses a complex data structure when an array suffices, reconsider.
• Forgetting about space complexity – Especially when using recursion or copying arrays.
• Not practicing on a whiteboard or shared editor – In interviews you won’t have an IDE with autocomplete; practice writing code by hand or in a plain text editor.
• Neglecting communication – Talk through your reasoning, ask for clarification, and show the interviewer how you approach problem-solving, not just the code.

Conclusion

Mastering data structures and algorithms is a journey that requires dedicated practice, understanding of core concepts, and the ability to adapt to new problems. Focus on the structures and algorithms listed above, analyze their trade-offs, and apply a systematic problem-solving method. By incorporating the tips and resources provided, you will build the confidence and skill needed to excel in technical interviews. Remember that the goal is not just to memorize solutions but to develop a deep intuition that allows you to tackle any problem that comes your way. Keep coding, keep learning, and success will follow.