Data Structures

How to answer in an interview

A data structure is a specialized format for organizing, storing, and managing data so it can be accessed and modified efficiently. The choice of data structure affects the time and space complexity of operations like searching, inserting, and deleting, so selecting the right one is key to writing efficient programs.

Explain like I am 5

A data structure is like choosing the right container for your stuff — a toolbox for tools, a filing cabinet for papers — so you can find and use things quickly.

How to answer in an interview

An array stores elements in contiguous memory locations, allowing constant-time random access via an index but requiring costly shifting for insertions or deletions in the middle. A linked list stores elements as nodes connected via pointers, allowing efficient insertion and deletion but only sequential access, since there's no direct indexing.

Explain like I am 5

An array is like a row of numbered lockers right next to each other — you can jump straight to any one. A linked list is like a treasure hunt where each clue points to the next location, so you have to follow the chain.

How to answer in an interview

A stack is a linear data structure that follows Last-In-First-Out (LIFO) order, supporting push (add) and pop (remove) operations at one end. It's used in scenarios like function call management (the call stack), undo features in editors, and expression evaluation.

Explain like I am 5

A stack is like a pile of plates — you can only add or remove the plate from the top, so the last one you put down is the first one you take off.

How to answer in an interview

A queue is a linear data structure following First-In-First-Out (FIFO) order, where elements are added at the rear (enqueue) and removed from the front (dequeue). Variants include circular queues, which reuse freed space efficiently, and priority queues, where elements are dequeued based on priority rather than order of insertion.

Explain like I am 5

A queue is like a line at a ticket counter — the first person to join the line is the first person served.

How to answer in an interview

A singly linked list has nodes that only point to the next node, allowing traversal in one direction only. A doubly linked list has nodes with pointers to both the next and previous nodes, enabling traversal in both directions at the cost of extra memory per node.

Explain like I am 5

A singly linked list is like a one-way street where you can only move forward. A doubly linked list is like a two-way street where you can walk forward or backward.

How to answer in an interview

Big O notation describes the upper bound of an algorithm's time or space complexity as the input size grows, focusing on the worst-case scenario and ignoring constant factors. For example, O(1) means constant time regardless of input size, while O(n) means time grows linearly with input size, helping compare algorithm efficiency at scale.

Explain like I am 5

Big O is a way of saying 'how much slower does this get if I give it way more stuff to do?' — like whether doubling your chores takes twice as long or way, way longer.

How to answer in an interview

A list is an ordered collection that allows duplicate elements and preserves insertion order. A set is an unordered collection that automatically enforces uniqueness, disallowing duplicate values, and typically offers faster membership checks due to underlying hash-based implementation.

Explain like I am 5

A list is like a numbered to-do list where the same task can appear more than once and order matters. A set is like a bag of unique stickers where you can't have two of the exact same sticker.

How to answer in an interview

A binary search tree is a tree data structure where each node has at most two children, and for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property enables efficient search, insertion, and deletion, all averaging O(log n) time in a balanced tree, though worst case can degrade to O(n) if unbalanced.

Explain like I am 5

A binary search tree is like a filing system where anything smaller goes to the left drawer and anything bigger goes to the right, at every level, so you can find things quickly by always choosing left or right.

How to answer in an interview

A hash table stores key-value pairs by computing a hash of the key to determine which bucket to place it in, giving average O(1) time for lookups. Collisions, where two keys hash to the same bucket, are typically resolved through chaining, storing multiple entries in a linked list per bucket, or open addressing, which probes for the next available slot.

Explain like I am 5

A hash table is like assigning each item a locker number based on a formula. If two items get the same locker number by accident, chaining lets both items sit in that locker together, one behind the other.

How to answer in an interview

Arrays offer O(1) random access but O(n) insertion or deletion in the middle due to shifting elements. Linked lists offer O(1) insertion or deletion once you have a reference to the node, but O(n) access time since you must traverse from the head to reach a specific position.

Explain like I am 5

Arrays let you jump straight to any seat instantly but moving seats around means shifting everyone else. Linked lists let you slot a new person in easily without shifting anyone, but finding a specific person means walking down the row one by one.

How to answer in an interview

A heap is a complete binary tree that satisfies the heap property: in a min-heap, every parent node is smaller than or equal to its children, while in a max-heap, every parent is larger than or equal to its children. Heaps are commonly used to implement priority queues and algorithms like heap sort, offering O(log n) insertion and O(1) access to the min or max element.

Explain like I am 5

A heap is like a family tree where every parent is always shorter (or always taller) than their kids, so the shortest or tallest person is always right at the very top, easy to find.

How to answer in an interview

Graphs are commonly represented using an adjacency list, where each node stores a list of its neighboring nodes, which is memory-efficient for sparse graphs, or an adjacency matrix, a 2D array where each cell indicates whether an edge exists between two nodes, which is faster for edge lookups but uses more memory for sparse graphs.

Explain like I am 5

An adjacency list is like each person keeping a small notebook of just their friends. An adjacency matrix is like one giant chart showing every possible pair of people and whether they're friends or not, even if most pairs aren't.

How to answer in an interview

Breadth-First Search (BFS) explores a graph level by level using a queue, making it ideal for finding the shortest path in unweighted graphs. Depth-First Search (DFS) explores as far as possible along one branch before backtracking, typically implemented with a stack or recursion, and is useful for tasks like detecting cycles or topological sorting.

Explain like I am 5

BFS explores like ripples spreading out from a stone dropped in water, checking everything nearby before going further. DFS explores like following one hallway all the way to the end before backing up and trying another.

How to answer in an interview

A circular linked list is a variation where the last node points back to the first node instead of null, forming a loop. It's useful for applications requiring continuous cycling through elements, such as round-robin CPU scheduling or managing playlists that loop back to the beginning.

Explain like I am 5

A circular linked list is like people sitting in a circle passing a ball — after the last person, it just goes right back to the first person again instead of stopping.

How to answer in an interview

A priority queue is an abstract data structure where each element has an associated priority, and elements are served based on priority rather than insertion order, with higher (or lower) priority elements dequeued first. It's typically implemented using a heap, giving O(log n) insertion and removal.

Explain like I am 5

A priority queue is like an emergency room — patients aren't seen in the order they arrived, but based on how urgent their condition is.

How to answer in an interview

A trie, or prefix tree, is a tree-like data structure used to store strings where common prefixes are shared among nodes, enabling fast prefix-based searches. It's commonly used for implementing autocomplete features, spell checkers, and IP routing tables, offering O(m) search time where m is the length of the string.

Explain like I am 5

A trie is like a tree where each letter you type moves you down a branch, and words that start the same way share the same branches, making it quick to suggest words as you type.

How to answer in an interview

A balanced binary tree, like an AVL tree, maintains a height difference of at most one between the left and right subtrees of any node, ensuring operations remain O(log n) even in worst-case scenarios. AVL trees achieve this by performing rotations, such as left or right rotations, whenever an insertion or deletion causes the tree to become unbalanced.

Explain like I am 5

A balanced tree makes sure neither side gets too much taller than the other, kind of like keeping a seesaw level, so nobody has to walk too far down one long branch to find something.

How to answer in an interview

Memoization is an optimization technique that stores the results of expensive function calls, typically using a hash map or array, and returns the cached result when the same inputs occur again, avoiding redundant computation. It's a core technique in dynamic programming used to reduce exponential time complexity to polynomial time in problems with overlapping subproblems.

Explain like I am 5

Memoization is like writing down the answer to a math problem the first time you solve it, so next time someone asks the exact same question, you just read your notes instead of solving it all over again.

How to answer in an interview

Chaining resolves collisions by storing multiple key-value pairs that hash to the same bucket in a linked list or similar structure at that index. Open addressing resolves collisions by searching for the next available slot in the table itself, using strategies like linear probing, quadratic probing, or double hashing, avoiding extra memory for linked structures but requiring careful handling of deletions.

Explain like I am 5

Chaining is like stacking multiple letters in the same mailbox slot when two happen to have the same address. Open addressing is like finding the next empty mailbox nearby instead of stacking them together.

How to answer in an interview

Amortized time complexity averages the cost of an operation over a sequence of operations, rather than looking at any single worst case in isolation. For a dynamic array, most insertions are O(1), but occasionally the array must resize and copy all elements, an O(n) operation; because resizing happens infrequently and the cost is spread across many prior cheap insertions, the amortized cost per insertion remains O(1).

Explain like I am 5

Amortized cost is like saving a little money each month for an occasional big expense — most months are cheap, and even though one month is expensive, spread out over time it evens out to a small average cost.