Oct 12, 2024

Classic Data Structures

Data structures help you organize and work with data efficiently. If you've done coding interviews, you know that interviewers love testing how well you understand them. They want to see if you can pick the right tool for the job and explain why it works.

This guide covers the data structures you'll encounter most often in interviews. Each section includes practice problems that come up frequently, so you can build your skills step by step.

One-dimensional Data Structures

Arrays

Arrays store elements in consecutive memory slots. You can grab any element instantly if you know its position, which makes them great for random access. The trade-off is that inserting or deleting in the middle means shifting everything around.

Here are the array problems you'll probably see:

  1. Subarray Sum Equals K: You're given an array of integers and a target sum k. Count how many continuous subarrays add up to exactly k.

  2. Maximum Product Subarray: Find the contiguous subarray within an array that has the largest product when you multiply its elements together. Return that product.

  3. Container With Most Water: You have vertical lines at different heights. Pick two lines that together with the x-axis form a container holding the most water.

  4. Jump Game: Each position in the array tells you how far you can jump. Starting from the first position, can you reach the last one?

  5. Product of Array Except Self: Return an array where each position contains the product of all numbers except the one at that position. Do it in O(n) time without using division.

Strings

Strings are essentially arrays of characters, so many array techniques apply. The problems here test your ability to manipulate characters, find patterns, and work with substrings.

  1. Longest Palindromic Substring: Find the longest substring that reads the same forward and backward.

  2. Group Anagrams: Group strings together if they're anagrams of each other. "eat", "tea", and "ate" would go in the same group.

  3. Minimum Window Substring: Given two strings s and t, find the smallest window in s that contains all characters from t.

  4. Word Ladder: Start with a begin word and change one letter at a time until you reach the end word. Each intermediate word must exist in the dictionary. What's the shortest sequence?

  5. Edit Distance: How many single-character changes (insert, delete, or replace) does it take to turn one word into another?

  6. Longest Substring Without Repeating Characters: Find the longest substring where no character repeats.

Heaps

A heap is a tree where the parent node always holds the largest value (max heap) or the smallest value (min heap) compared to its children. The root always contains the extreme value, which makes heaps perfect for priority queues and problems where you constantly need the "best" element.

  1. Kth Largest Element in an Array: Find the kth largest element in an unsorted array. You need an efficient approach since sorting the whole array would be wasteful.

  2. Find Median from Data Stream: Numbers keep coming in one at a time. After each new number, what's the median of all numbers seen so far?

  3. Merge K Sorted Lists: You have k sorted linked lists. Merge them into one sorted list.

  4. Top K Frequent Words: Return the k most common words in an array. When words have the same frequency, shorter words come first.

  5. Sliding Window Median: A window of size k slides across an array. After each move, what's the median of the current window?

Linked Lists

A linked list chains nodes together, where each node points to the next one. Unlike arrays, you can't jump directly to the middle, you have to walk through from the head. The upside is that inserting or deleting a node is fast once you're at the right position.

  1. Reverse Linked List: Flip a singly linked list around so the head becomes the tail and vice versa.

  2. Remove Nth Node From End of List: Delete the nth node from the end of the list and return the new head.

  3. Detect Cycle in a Linked List: Check if a linked list loops back on itself somewhere.

  4. Merge K Sorted Lists: Combine k sorted linked lists into one sorted list.

  5. Copy List with Random Pointer: Each node has a next pointer and a random pointer that can point to any node or null. Clone the entire list.

Queues

A queue follows First In, First Out, the first element you add is the first one you remove. Think of a line at a store. Queues show up in breadth-first search, task scheduling, and anywhere you need to process things in the order they arrived.

Common operations:

Some useful variations:

Here are some queue problems:

  1. Task Scheduler: You have tasks that need cooling time between identical tasks. How many time units until everything finishes?

  2. Rotting Oranges: Fresh oranges rot adjacent oranges each minute. How long until all fresh oranges rot or determine it's impossible?

  3. Binary Tree Right Side View: Looking at a binary tree from the right, what nodes do you see?

  4. Jump Game VI: You can jump up to k steps forward. What's the maximum score you can collect?

  5. Shortest Path in Binary Matrix: Find the shortest path through a grid where you can only move through zeros.

Stacks

A stack is Last In, First Out, the last thing you add is the first one you remove. It's like a stack of plates. Stacks work well for problems involving matching, balancing, or tracking history.

  1. Valid Parentheses: Check if a string of brackets is properly balanced and nested.

  2. Evaluate Reverse Polish Notation: Calculate the value of an expression written in postfix notation (operators come after their operands).

  3. Simplify Path: Convert an absolute Unix-style file path to its simplified canonical form.

  4. Largest Rectangle in Histogram: Given bar heights, what's the largest rectangle that fits under the histogram?

  5. Basic Calculator II: Evaluate a simple arithmetic expression with +, -, *, and /.

Two-dimensional Data Structures

Two-dimensional Arrays

These are grids or matrices. Problems often involve traversing in spirals, rotating layers, or working with rows and columns together.

  1. Rotate Image: Turn a square matrix 90 degrees clockwise.

  2. Set Matrix Zeroes: If a cell is zero, set its entire row and column to zero. Do this in place.

  3. Spiral Matrix: Return all elements of a matrix in spiral order, starting from the top-left and working your way inward.

  4. Word Search: Can you find a word in a grid by moving horizontally or vertically through adjacent letters?

  5. Search a 2D Matrix: Search for a value in a matrix where each row is sorted and the first element of each row is greater than the last element of the previous row.

Hashtables

Hashtables store key-value pairs and let you look up values in constant time on average. The trick is handling collisions and choosing a good hash function.

  1. Two Sum: Find two numbers in an array that add up to a target. Return their indices.

  2. Subarray Sum Equals K: Count continuous subarrays that sum to k.

  3. Longest Consecutive Sequence: Find the length of the longest sequence of consecutive integers in an unsorted array.

  4. Top K Frequent Elements: Return the k most common elements.

  5. Group Anagrams: Group strings that are anagrams of each other.

Hierarchical Data Structures

Trees

Trees branch out from a root node. Binary trees (each node has at most two children) show up most often in interviews.

  1. Binary Tree Inorder Traversal: Visit left subtree, then root, then right subtree. Return the node values.

  2. Construct Binary Tree from Preorder and Inorder Traversal: Rebuild the tree from its preorder and inorder traversals.

  3. Serialize and Deserialize Binary Tree: Convert a tree to a string and back again.

  4. Binary Search Tree Iterator: Implement an iterator that returns nodes in ascending order without building the entire tree upfront.

  5. Lowest Common Ancestor: Find the lowest node that has two given nodes as descendants.

Tries

A trie stores characters at each level, with paths from root to leaf representing words. They're perfect for prefix searches and autocomplete systems.

Common uses:

Trie problems:

  1. Autocomplete System: Suggest words that match a given prefix.

  2. Spell Checker: Find misspellings and suggest corrections.

  3. Word Search II: Find all dictionary words in a character grid.

  4. Replace Words: Replace words with their shortest root from a dictionary.

  5. Longest Word in Dictionary: Find the longest word that can be built character by character using other words in the dictionary.

  6. Maximum XOR of Two Numbers: Find the maximum XOR value of any two numbers in an array.

Advanced Structures

B+ Trees

B+ trees keep data sorted and allow fast searches, inserts, and deletes. They're self-balancing, so performance stays consistent even as data grows.

Key characteristics:

If an interviewer asks about handling data too big for memory, B+ trees come up naturally because their structure minimizes disk reads.

Skip Lists

Skip lists use multiple layers of linked lists to speed up searches. The bottom layer has everything, and higher layers skip over groups of elements, like express lanes on a highway.

Operations:

Skip lists are simpler than balanced trees and work well when you need average-case O(log n) performance without the complexity of tree rebalancing.

Graphs

Graphs model relationships using nodes (vertices) and connections (edges). Edges can be directed (one-way) or undirected (two-way).

Common representations:

Graph problems:

  1. Course Schedule: Can you finish all courses given prerequisites?

  2. Network Delay Time: How long until all nodes receive a signal from a source?

  3. Word Ladder: Find the shortest path from start word to end word, changing one letter at a time.

  4. Redundant Connection: Remove one edge to make a graph into a tree.

  5. Critical Connections: Find bridges, edges whose removal disconnects the network.