Data Structures Interview Questions

Collision resolution techniques in a hash table are strategies used to handle situations where two keys hash to the same index. There are a few common methods. One is chaining, where each array element points to a linked list of key-value pairs that hash to the same index. Another technique is open addressing, which involves finding another open slot within the array through methods like linear probing, quadratic probing, or double hashing. Each technique has its own trade-offs related to performance and complexity, depending on the specific use case.

Big O notation is a way to express the time complexity and space complexity of an algorithm. It provides an upper bound on the time taken or space used by an algorithm in terms of the size of the input data. Big O notation essentially answers the question "how does the performance of an algorithm change as the size of its input grows?"

For example, if an algorithm has a time complexity of O(n), it implies that the execution time grows linearly as the input size grows. If the complexity is O(n^2), the time taken grows quadratically for an increasing input size.

So why is it important? Well, Big O notation helps in analyzing algorithms for efficiency. It's crucial in optimizing an algorithm and ensuring it can scale and perform well with larger data sets. It aids in making informed decisions about which algorithms are best suited for a given problem based on their time and space complexities, allowing us to balance efficiency, performance, and resource utilization.

Linked lists are used primarily for efficient insertion and deletion of elements from any position. In an array or an array-based data structure, inserting or deleting an element requires moving elements, which has a time complexity of O(n). However, in a linked list, these operations can be done in constant time, O(1), given that we have a reference to the node we are inserting or deleting from.

Linked lists also provide dynamic memory allocation. Unlike an array which has a fixed size, linked lists can be expanded or shrunk on demand at runtime, making them pretty flexible.

Additionally, they serve as the basis for several higher-level data structures like stacks, queues, and even more complex structures like hash tables. So understanding linked lists is really key to understanding many other important data structures.

A deque, short for double-ended queue, is a linear data structure where you can add or remove elements from both the front and the back.

Think of it as a mix of:

• a queue, FIFO
• a stack, LIFO

Because it supports both ends, it is more flexible than either one.

Common operations are:

• push_front()
• push_back()
• pop_front()
• pop_back()

There are also two restricted versions:

• Input-restricted deque, insertion happens at only one end, but deletion can happen at both ends
• Output-restricted deque, deletion happens at only one end, but insertion can happen at both ends

Why it is useful:

• sliding window problems
• palindrome checking
• task scheduling
• caching and buffering systems

So in one line, a deque is just a queue that lets you work from both ends efficiently.

Sure, suppose you're building a contact list application where you can add, remove, and search for contacts quickly. You'd have numerous entries, each with a name (as the key) and associated details like phone number, email, address etc. (as the value). Using an array or linked list to store and search through these contacts would result in linear time complexity O(n) in the worst case.

However, if you use a hash table, you could store the contacts in such a way that each contact's name is hashed into a unique integer, which would be used as an index where the corresponding details will be stored. This would allow the application to quickly jump directly to the data associated with a particular name during a search operation.

Importantly, hash tables provide average time complexity of O(1) for search, insert, and delete operations, thus making them highly effective for scenarios where we need to perform frequent, quick lookups for large sets of data.

Stacks are quite versatile and find use in various applications. One primary application is in the execution of function calls and recursion in programming languages. Each time a function is called, a new block of memory is reserved for its variables. These blocks form a stack, with each function call pushing a new block onto the top of the stack, and each return popping a block off.

Another key utility of stacks is in parsing and evaluating expressions. For example, they are used for checking balanced parentheses in an expression or converting an infix expression to postfix or prefix.

Stacks also play a role in backtracking algorithms - these are algorithms where you move forward only to discover that solution does not reside along the current path, forcing you to move back and make a different set of decisions. A classic example is Depth-First Search, a strategy that searches ‘deeper’ in a graph whenever possible, and uses a stack to remember to get back to exploring other paths once a dead-end is reached.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It begins at the root node (or an arbitrary node in graphs), and explores all the neighboring nodes at the present depth level before moving on to nodes on the next depth level.

Basically, BFS takes a 'wide' rather than 'deep' approach. If you picture a tree, BFS would explore all the nodes in one layer, from left to right, before descending down to the next layer.

It typically uses a queue data structure. The algorithm dequeues the initial node, explores the dequeued node's unvisited neighbors, and enqueues any neighboring nodes which have not yet been discovered. This continues until the queue is empty and all nodes reachable from the initial node have been discovered.

BFS is particularly useful in finding the shortest path between two nodes in an unweighted graph or determining whether a path exists between two nodes in a graph or a tree.

Merge sort is a divide-and-conquer algorithm that works by continuously splitting an array in half. If the array is empty or has one item, it is already sorted. If not, we recursively divide the array into two halves until we reach arrays that can be directly sorted.

After dividing, merge sort solves the problem by merging the smaller, sorted lists together into a larger one. The merging process involves taking two smaller sorted lists and combining them together into a larger sorted list. This is done by comparing the first elements of each list and adding the smaller one to the new list, then moving on to the next element in the list from which the element was taken.

The beauty of merge sort lies in its efficiency. Regardless of the input distribution, its worst case, best case, and average case time complexities are all O(n log n), making it one of the most efficient sorting algorithms for large data sets. However, it does have a space complexity of O(n) as it requires temporary space of the same size as the input array during the merge process.

Depth-First Search (DFS) is an algorithm used for traversing or searching tree or graph data structures. The algorithm starts at the root (for a tree) or an arbitrary node (for a graph) and explores as far as possible along each branch before backtracking.

So if you visualize a tree, DFS would start at the root, then go down the first child node, then go down that node's first child, and so on, until it reaches a node with no children. At that point, it will backtrack, moving up to the node's parent and over to the next child node if one exists, repeating the process.

DFS uses a stack data structure to remember to get back to the nodes to explore its remaining children. When it visits a node, it adds it to the stack and continues to the next unvisited node, repeating until it reaches a dead-end, at which point it backtracks by popping nodes off the stack and visiting the popped node's unvisited neighbors.

In essence, DFS dives deep into a problem before exploring the width, hence the term "depth-first". This makes DFS useful in tasks like topological sorting, detecting cycles, or finding paths between nodes.

A self-balancing binary search tree, also known as a height-balanced binary tree, is a binary search tree that automatically maintains its height as minimal as possible whenever insertions or deletions occur. The tree's height is minimal when the number of tree levels is logarithmic with the number of elements in the tree.

By keeping the tree balanced, all operations like insertion, deletion, and search can be performed faster, in logarithmic time complexity O(log n), rather than in linear time complexity in the case of an unbalanced tree.

Examples of self-balancing binary trees include AVL Trees, Red-Black Trees, and B-Trees. They use different balancing rules and rotations to maintain balance, ensuring better and consistent performance than an unbalanced binary search tree.

So, self-balancing binary search trees are particularly advantageous in scenarios where the input data might be sorted or nearly sorted, which would create unbalanced trees if not addressed.

Linear and non-linear data structures are classifications based on how elements within them are arranged and related to each other.

In a linear data structure, elements are arranged in a sequential manner, where each element is connected to its previous and next element. It forms a linear sequence, which makes the structure easier to understand and implement. Examples include arrays, linked lists, stacks, and queues. In these structures, traversal happens in a single run, from one end to another.

Non-linear data structures, on the other hand, do not follow a sequential order. Elements may be connected to two or more other elements, forming a more complex network of connections. In these structures, traversal might require visiting the same element more than once. Examples include trees and graphs. In these structures, data elements are not arranged in a sequential pattern, making them suitable for representing relationships among elements that don't fit neatly into a simple linear hierarchy or sequence.

Implementing a queue using two stacks is a classic data structure problem. Here's a simple way to do it:

In this method, we use two stacks, let's call them "input" and "output".

For the "enqueue" operation (which adds an element to the back of the queue), we simply push the elements into the "input" stack.

The "dequeue" operation (which removes an element from the front of the queue) is slightly more involved. If the "output" stack is empty, we pop all elements from the "input" stack and push them onto the "output" stack. By doing so, the order of the elements is reversed, aligning with the queue's FIFO order. Then, we simply pop the top element from the "output" stack. If the "output" stack is not empty, we directly pop an element from it.

The "enqueue" operation has a time complexity of O(1), and the "dequeue" operation has a worst-case time complexity of O(n) (when the "output" stack is empty), but an amortized time complexity of O(1) for successive calls.

In-order traversal is a specific way of visiting all the nodes in a binary tree. For an in-order traversal, the algorithm first visits the left subtree, then the root node, and finally the right subtree. This process is performed recursively for all subtrees.

When performed on a binary search tree, an in-order traversal will visit the nodes in ascending order (if the tree is ordered from smallest to largest), which can be quite useful. For example, if you have a binary search tree of numbers and want to print them out in sorted order, you would simply do an in-order traversal and print each node as you visit it.

So an in-order traversal allows us to visit the nodes of a binary search tree in the order that respects the property of binary search trees: all the values in the left subtree will be less than the root, and all the values in the right subtree will be greater.

In the context of data structures, a node is a fundamental unit that holds data and serves as a building block for data structures such as linked lists, trees, and graphs. It consists of two components: a data field to store the actual information, and references (or links) to point to other nodes in the structure.

In a singly linked list, a node will have one data field and one reference that points to the next node in the list. In a doubly linked list, a node will have an additional reference that points to the previous node.

In a tree or graph, nodes typically contain multiple references to connect with multiple other nodes. In the case of a binary tree, a node would have a reference to a left child and a right child.

So, overall, nodes serve as an essential component for storing data and defining relationships between data in most complex data structures.

A graph is a way to represent relationships between things.

• Vertices or nodes represent the things
• Edges represent the connections between them

You can have:

• Undirected graphs, where the connection goes both ways
• Directed graphs, where the connection has a direction
• Weighted graphs, where edges carry a value like cost, distance, or time

Where graphs are used:

• Social networks, people are nodes, friendships or follows are edges
• Maps and GPS, locations are nodes, roads are edges
• Computer networks, devices are nodes, communication links are edges
• Web page linking, pages are nodes, hyperlinks are edges
• Recommendation systems, users and products can be connected based on behavior
• Dependency tracking, like task scheduling, course prerequisites, or package management

Why they matter:

• They help model real-world connected systems
• They make it easier to solve problems like shortest path, connectivity, cycle detection, and routing

A simple example is Google Maps. Each location can be treated as a node, each road as an edge, and the graph helps find the shortest or fastest route between two places.

A priority queue is a special type of queue in which each element is associated with a priority. In a priority queue, elements are served (or dequeued) based on their priority, not their order of arrival. If elements with the same priority exist, they can be served according to their ordering in the queue, which may be either first-in-first-out or last-in-first-out, depending on how it's designed.

Priority queues are commonly implemented using heaps, as heaps are a very efficient way to keep track of the maximum or minimum of a group of numbers. A binary heap can insert elements and serve (remove and return) the highest priority element in logarithmic time, making it an excellent choice for implementing a priority queue.

In certain cases, other data structures such as balanced binary search trees, Fibonacci heaps, or a simple unordered list could be used, each with their own trade-offs in terms of time complexities of enqueue and dequeue operations. The choice depends on the specifics and requirements of the application.

Adding an element to a binary heap, also known as heap insertion, has a time complexity of O(log n), where n is the number of elements in the heap.

When you add an element to a heap, you typically add it at the end of the heap array, and then "sift" it upward if necessary to restore the heap property (max-heap or min-heap). This process involves comparing the new element with its parent and swapping them if they're out of order. This sifting process is done along the height of the tree, and since a binary heap is a complete binary tree, the height of the tree is log(n). Hence, the time complexity of the heap insertion operation is O(log n).

A ternary search tree is a special type of trie (prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two.

Each node in a ternary search tree stores a character and has three pointers: left, middle, and right. The left pointer points to the node containing characters less than the node character, the right pointer points to the node containing characters greater than the node character, and the middle pointer points to the node containing the next character in the string.

This kind of data structure combines the best of two worlds, the low space requirement of binary search trees and faster search/query of digital search trees. It's particularly well-suited for applications involving queries related to strings, like autocomplete suggestions, spell checks, etc.

A hash function is a way to turn a key, like a string, number, or object identifier, into an integer that a hash table can use.

How it works, at a high level:

1. You give it a key
   Example: "apple"

2. The function computes a numeric hash value
   It mixes the key's data in a deterministic way, meaning the same input always gives the same output.

3. That hash value is converted into an array index
   Often with something like hash % tableSize

4. The hash table uses that index to store or look up the value

What makes a good hash function:

• Fast to compute
• Distributes keys evenly
• Minimizes collisions
• Deterministic, same key, same hash

What is a collision?

• A collision happens when two different keys map to the same index.
• Example: "cat" and "tac" might end up in the same bucket.

Since collisions are unavoidable in practice, hash tables handle them using techniques like:

• Chaining, storing multiple entries in the same bucket
• Open addressing, probing for another empty slot

Simple example:

• Key: "dog"
• Hash function turns it into something like 9382
• If table size is 100, index becomes 9382 % 100 = 82
• The item gets stored at index 82

So the main idea is simple: a hash function gives you a quick, repeatable way to decide where data should go, which is why hash tables can support near constant-time lookup on average.

The primary difference between singly linked lists and doubly linked lists lies in the way they are structured and consequently navigated.

A singly linked list consists of nodes where each node has a data part and a reference (or link) to the next node in the sequence. This structure allows for traversal in one direction only, from the head (start) of the list to the end (tail).

On the other hand, a doubly linked list has nodes that contain two references, one to the next node and another to the previous node. This extra reference in each node allows traversal in both forward and backward directions.

The benefit of a doubly linked list is that it can be traversed in both directions and any node can be accessed directly from its predecessor or successor, making operations like insertion and deletion more efficient at any position in comparison to a singly linked list. However, it comes at a cost of additional memory for storing the previous reference and increased complexity in maintaining the previous links during add/remove operations.

Abstract Data Types (ADTs) are a way of classifying data structures based on how they are used and the behaviors they provide, rather than the concrete details of their implementation. In other words, an ADT defines what a data structure can do, not how it does it.

The importance of ADTs is in promoting encapsulation and information hiding, key principles in object-oriented programming. This allows developers to separate the interface (what a data structure does) from the implementation (how it does it). Changing the specific implementation of a data structure won't affect other parts of an application as long as the operations provided by the ADT stay consistent.

For example, a Stack ADT might define operations like push, pop, and isEmpty. These operations can be performed whether the stack is implemented using an array, a linked list, or some other data structure.

In essence, the use of ADTs leads to modular, reusable, and more maintainable code. It allows programmers to pick the most efficient data structure for a specific task, without affecting the overall functionality of the program.

A singly linked list consists of nodes where each node has a data part and a reference to the next node in the sequence. You can traverse it only in one direction—from the head to the end. On the other hand, a doubly linked list has nodes with three parts: the data, a reference to the next node, and a reference to the previous node. This allows traversal in both directions—from head to tail and vice versa.

Because a doubly linked list keeps references to its previous nodes, operations like deletion of a node or traversing backwards are more straightforward compared to a singly linked list. However, doubly linked lists consume more memory due to the extra reference per node and might be slightly slower for operations that involve frequent node creation and deletion due to the overhead of setting up and maintaining the backward links.

To implement a stack using arrays, you essentially need an array and an integer to keep track of the index of the top element. You start with an empty array and set the top index to -1, indicating that the stack is empty.

When you push an element onto the stack, you increment the top index and then place the new element at that index in the array. For popping an element, you simply return the element at the current top index and then decrement the top index. A couple of checks are necessary to avoid overflows (when pushing onto a full stack) and underflows (when popping from an empty stack), but that's basically how you do it.

A priority queue is a type of data structure where each element has a priority assigned to it, and elements are served based on their priority rather than just their order in the queue. Higher priority elements are dequeued before lower priority ones, regardless of when they were added. This contrasts with a regular queue, which operates in a first-in, first-out (FIFO) manner, meaning elements are dequeued in the exact order they were enqueued with no consideration for their priority.

In a priority queue, elements can be inserted with various levels of priority values, typically implemented using a heap for efficient access to the highest or lowest priority element. On the other hand, a regular queue might simply use a linked list or a dynamic array to manage its elements. This makes priority queues suitable for scenarios like scheduling tasks in operating systems, where certain tasks need to be addressed based on urgency rather than their arrival time.

Depth-first search (DFS) and breadth-first search (BFS) are two fundamental algorithms for traversing or searching through graphs and trees. DFS dives deep into a node’s descendants before backtracking, essentially exploring as far down one branch as possible before moving onto another branch. This means it uses a stack data structure, either implicitly via recursion or explicitly if managing the stack yourself.

BFS, on the other hand, explores all the neighbors of a node before moving on to their children, level by level. It uses a queue to keep track of the nodes yet to be explored. In essence, BFS is more level-oriented, which makes it preferable for finding the shortest path in an unweighted graph. DFS might be more memory-efficient in deeper or infinite graphs since it stores fewer states at any level, but it could get stuck going down a lengthy or infinite path without finding the desired node in certain situations.

A graph is a data structure that consists of a set of nodes, called vertices, and a set of edges connecting pairs of vertices. Graphs are used to model relationships between objects, such as routes between cities, links in a network, or dependencies in a task schedule.

Graphs can be represented in several ways. One common way is through an adjacency matrix, where you have a 2D array and each cell (i, j) indicates whether there is an edge between vertex i and vertex j. Another common method is an adjacency list, where each vertex has a list of other vertices to which it is directly connected. Adjacency matrices are more memory-intensive but allow faster edge lookups, while adjacency lists are more space-efficient and performant for sparse graphs.

Dijkstra’s algorithm is primarily used to find the shortest path between nodes in a graph, which may represent, for example, road networks. It works by starting from a source node and exploring all its neighbors, updating the shortest distances to each neighbor. It keeps track of the currently known shortest distance from the source to each node using a priority queue. Nodes are continuously marked as "visited" once the shortest path to them is confirmed, which means that the shortest distance to them has been found and will not change. The process repeats until the shortest path to the target node is determined or all nodes have been visited.

The algorithm is especially useful because it guarantees finding the shortest path in graphs with non-negative weights. However, it can become inefficient with larger graphs unless optimized with techniques like Fibonacci heaps.

An adjacency matrix represents a graph through a 2D array where both rows and columns correspond to the graph's vertices. If there's an edge between vertex i and vertex j, the cell at the ith row and jth column in the matrix is set to 1 (or the weight of the edge, for weighted graphs). If there's no edge, the cell remains 0. This method provides O(1) time complexity for edge lookups but can be memory-intensive for sparse graphs since it uses O(V^2) space, where V is the number of vertices.

A stack and a queue are both data structures used to store and manage collections of elements, but they operate in different ways. A stack follows the Last In, First Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. Think of it like a stack of plates: you add to the top and also take from the top.

On the other hand, a queue follows the First In, First Out (FIFO) principle. This means the first element added to the queue is the first one to be removed. This is similar to a line of people waiting for a service where the first person in line is the first to be served.

In terms of operations, for a stack you typically use "push" to add an item and "pop" to remove an item, whereas for a queue, you use "enqueue" to add an item and "dequeue" to remove an item.

A linked list is a data structure where each element is called a node. Each node contains two parts: the data and a reference (or pointer) to the next node in the sequence. This setup allows for efficient insertion and deletion of elements because you only need to adjust the pointers without reorganizing the entire structure.

There are different types of linked lists such as singly linked lists, where each node points to the next one, and doubly linked lists, where nodes have two pointers: one to the next node and one to the previous one. This makes traversing the list in both directions possible. The head node is the starting point of the list, and the list ends when a node's next pointer is null.

A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, where the desired value can be found. The idea is to distribute the keys uniformly across the buckets, which helps in achieving constant time complexity, O(1), for search, insertion, and deletion operations in the average case.

When an insertion is made, the hash function calculates an index from the key, and the value is stored in the array at that index. If a collision occurs, meaning two keys hash to the same index, a collision resolution scheme like chaining (where each bucket points to a list of entries) or open addressing (where a probe sequence is used to find the next free slot) is applied.

However, the hashing performance highly depends on the quality of the hash function and the load factor (filled capacity). If the load factor exceeds a certain threshold, rehashing may be necessary, where the array size is increased and all existing keys are hashed again to fit into the new array.

Implementing a queue using two stacks is a classic problem. You generally need two stacks: one for enqueue operations and one for dequeue operations. Start by pushing all incoming elements onto the first stack. When you need to dequeue, check the second stack: if it's empty, pop all elements from the first stack onto the second stack, reversing the order in the process. Then, pop from the second stack for your dequeue operation. This way, you maintain the FIFO order required by a queue while leveraging the LIFO properties of stacks. This method ensures that each element gets moved at most twice, leading to an average time complexity of O(1) for each enqueue or dequeue operation.

Amortized analysis is a method used to average the time complexity of an algorithm over a series of operations, even if some individual operations are costly. Instead of considering the worst-case time of each operation, we analyze the average time per operation in the worst-case scenario across a sequence of operations. This is especially useful in data structures where occasional expensive operations are balanced by many cheap ones.

For example, consider the dynamic array's growth operation: when the array gets full, reallocating and copying elements is costly, but this happens infrequently. By spreading this cost over multiple insertions, we can say that the average insertion operation is still efficient, typically O(1) in an amortized sense. This approach helps in designing and evaluating algorithms more realistically, offering a better perspective on their performance in practice.

Arrays and linked lists each have their own pros and cons, depending on what you need for your specific use case. Arrays offer constant-time access for retrieving or updating an element because you can directly jump to any index, thanks to contiguous memory allocation. However, inserting or deleting elements from an array can be costly since it may require shifting other elements around, especially for large arrays.

Linked lists, on the other hand, provide more flexibility with insertions and deletions. Since elements (nodes) are spread throughout memory and each node points to the next, you can easily add or remove a node without needing to move others. But this comes at a cost: accessing an element in a linked list takes linear time because you have to traverse from the head of the list to find the node you’re looking for. Also, linked lists use more memory due to the storage required for pointers.

I’d implement a min-heap with an array, because it gives you the complete binary tree structure for free.

The key rule is simple:

• Every parent value is less than or equal to its children
• The smallest element is always at the root, index 0

With an array, the index math is clean:

• Left child of i is 2*i + 1
• Right child of i is 2*i + 2
• Parent of i is (i - 1) // 2

The core operations are:

1. Insert
2. Add the new value to the end of the array
3. Then "bubble up" or "heapify up"
4. While the new value is smaller than its parent, swap them

5. Stop when the heap property is restored

6. Remove min

7. The minimum is at the root
8. Replace the root with the last element
9. Remove the last element from the array
10. Then "bubble down" or "heapify down"
11. Compare the new root with its children, swap with the smaller child if needed

12. Keep going until the heap property is restored

13. Peek min

14. Just return the element at index 0
15. That is O(1)

Time complexity:

• Insert: O(log n)
• Remove min: O(log n)
• Peek min: O(1)

If I were implementing it in an interview, I’d usually mention the helper methods too:

• heapifyUp(index)
• heapifyDown(index)
• swap(i, j)

If they want to go one step further, I’d also mention building a heap from an unsorted array:

• Start from the last non-leaf node
• Run heapifyDown moving backward to the root
• That builds the heap in O(n), not O(n log n)

That shows you understand both the data structure and the performance tradeoffs.

Binary search trees (BSTs) are a type of data structure that facilitates efficient searching, insertion, and deletion operations. In a BST, each node has a maximum of two children: a left child and a right child. The key property of a BST is that for any given node, the left child's value is less than the node's value, and the right child's value is greater than the node's value. This property allows the tree to maintain a sorted structure, making search operations logarithmic in time complexity.

BSTs are particularly useful for implementing associative arrays and priority queues. Due to their structure, they make it easy to perform in-order traversals, which will return the stored keys in sorted order. However, in the worst case, such as when the tree becomes unbalanced and resembles a linked list, the operations can degrade to linear time. Hence, balanced versions of BSTs like AVL trees or Red-Black trees are often used to ensure that the tree remains approximately balanced and operations stay efficient.

A balanced tree is a type of binary tree where the height difference between the left and right subtrees of any node is no more than a specific threshold, usually one. This structure ensures that the tree remains approximately symmetrical, minimizing the worst-case time complexity for operations like insertion, deletion, and lookup.

The importance of a balanced tree comes down to efficiency. When a tree stays balanced, the height is kept logarithmic relative to the number of nodes, which means that operations can be performed in O(log n) time. This is crucial for maintaining performance, especially with large datasets. Without balancing, a tree can degrade into a linear structure, turning operations into O(n) time complexity, significantly slowing down the performance.

In a binary search tree (BST), the main operations are insertion, deletion, and search. For insertion, you start at the root and compare the value to be inserted. If it’s smaller, you move to the left subtree; if it’s larger, you move to the right. You continue this until you find an appropriate null spot and insert the new node there. For searching, you follow a similar path based on comparisons until you either find the node or hit a null, indicating the value is not present.

Deletion is a bit trickier because it involves three cases: deleting a leaf node, deleting a node with one child, and deleting a node with two children. For a leaf node, you simply remove it. For a node with one child, you replace the node with its child. For a node with two children, you find the in-order successor (the smallest value in the right subtree) or the in-order predecessor (the largest value in the left subtree) to replace the node, and then delete the successor or predecessor node, which will now have at most one child.

Additional operations include traversals like in-order, pre-order, and post-order, which visit the nodes in different sequences. In-order traversal yields nodes in ascending order for a BST, which is handy for certain operations like verifying the tree's integrity.

AVL trees are a type of self-balancing binary search tree that ensures the tree remains approximately balanced, which maintains O(log n) time complexity for search, insertion, and deletion operations. One of the main advantages is that because they stay balanced, the worst-case scenario for time complexity is significantly better than an unbalanced binary search tree. This makes AVL trees particularly useful when you have a lot of read operations because those reads will be faster on average.

On the downside, AVL trees can be more complex to implement than other binary search trees due to the need to keep the tree balanced after every insertion and deletion. This balancing requires additional rotation operations, which can add overhead and slightly increase the complexity of insertions and deletions. Although the overhead is logarithmic, it can be non-trivial for very large datasets or systems where insertions and deletions are more frequent than reads.

A Bloom filter is a probabilistic data structure that’s used to test whether an element is a member of a set. It works by using multiple hash functions. When you add an element to the Bloom filter, it’s passed through several hash functions, and each hash function maps the element to a position in a bit array and sets the bit at that position to 1.

When checking if an element is in the set, you pass the element through the same hash functions to get multiple positions in the bit array. If any of the bits at these positions is 0, the element is definitely not in the set. If all positions are set to 1, then the element might be in the set, but there is a chance of false positives. However, it will never return a false negative.

They’re really efficient in terms of space because you only need a small amount of memory to store a large set of data, which is great for applications like network data routing and cache filtering.

To detect a cycle in a linked list, the most commonly used technique is called Floyd’s Tortoise and Hare algorithm. You use two pointers, one moving slowly (the Tortoise) and the other moving quickly (the Hare). Initially, both pointers start at the head of the list. In each step, the Tortoise pointer moves one node at a time, while the Hare pointer moves two nodes at a time. If there’s a cycle, the two pointers will eventually meet within the cycle. If the Hare reaches the end of the list (i.e., a null reference), there’s no cycle.

This method is efficient with a time complexity of O(n) and a space complexity of O(1), which makes it optimal for this kind of problem.

A circular queue is a linear data structure that follows the FIFO principle but, unlike a regular queue, it connects the end of the queue back to the front, forming a circle. This means when the queue is full and an element is dequeued, a new element can take its place without shifting other elements. This is particularly efficient in situations where managing the end of the queue and the beginning as a circular entity saves space and processing time.

Circular queues are often used in scenarios where buffer management is critical, like in CPU scheduling, memory management, or handling streaming data. For example, in operating systems, circular queues are used for managing the process queue, and in network data buffers, they help in efficient data packet management.

A trie is a tree-like data structure built for storing strings by character.

The main idea: - Each level represents the next character in a word - Paths from the root form prefixes - A node is marked to show when a full word ends

So if you store cat, car, and care, they all share the ca path. That shared prefix is what makes tries efficient.

Why it’s useful: - Search, insert, and delete are typically O(m), where m is the length of the word - Prefix lookups are very fast - It avoids repeating the same prefix over and over

Common use cases: - Autocomplete, like search bars or mobile keyboards - Spell checkers and dictionaries - Prefix matching, like finding all words starting with pre - IP routing, using bitwise tries for longest prefix match - Word games and text search features

One tradeoff: - Tries can use more memory than hash maps or balanced trees, because each node may store multiple child pointers

If I were explaining it in an interview, I’d say: “A trie is a prefix tree used to store strings efficiently. Each node represents a character, and words with the same prefix share part of the path. It’s especially useful for prefix-based lookups like autocomplete, dictionaries, and routing tables.”

A B-tree and a B+ tree are both self-balancing tree data structures used in databases and file systems, but they differ in how they handle data storage and retrieval. In a B-tree, both keys and data are stored in its internal and leaf nodes, making searches potentially shorter since relevant data can be found higher up in the tree. However, in a B+ tree, only keys are stored in the internal nodes while all data is stored in the leaf nodes, which are linked together in a linked list for easy in-order traversal.

This design in B+ trees makes range queries more efficient, as you can easily scan through the leaf nodes in sequence. Additionally, because internal nodes in a B+ tree contain only keys, they can hold more keys per node, allowing the tree to be balanced with fewer levels compared to a B-tree, potentially improving performance for large datasets.

A skip list is a type of data structure that allows for fast search, insertion, and deletion operations within an ordered sequence of elements. It builds on a linked list by adding multiple layers of linked lists that skip over intermediate elements, which helps speed up these operations. You can think of it as a compromise between a linked list and a balanced binary search tree.

The main advantages of skip lists include their simplicity and efficiency. They are easier to implement than other balanced data structures like AVL or Red-Black trees. Skip lists also have good average-case performance with a time complexity of O(log n) for search, insert, and delete operations, while still being relatively easy to manage and update without the need for complex re-balancing operations.

To implement a Least Recently Used (LRU) cache, you'd typically use a combination of a doubly linked list and a hash map. The doubly linked list helps to keep track of the usage order, making it easy to move items when they're accessed. The hash map stores the keys and their associated nodes in the linked list, allowing for O(1) access times.

Here's a basic way to do it: The hash map maps keys to their corresponding nodes in the doubly linked list. Whenever you access an item, you move it to the front (or back, depending on your implementation) of the linked list. If you add a new item and the cache is full, you remove the item at the back (the least recently used one) to make space. When both adding and accessing items, you should update the linked list accordingly to reflect the latest access order.

Using these data structures together balances the need for quick lookups with the need to maintain the access order efficiently. This way, you achieve a time complexity of O(1) for both insertions and lookups.

A Red-Black Tree is a self-balancing Binary Search Tree.

The idea is simple: - it follows normal BST ordering, left < node < right - each node also has a color, red or black - those color rules keep the tree from getting too skewed

Because of that, search, insert, and delete stay at O(log n).

The core properties are:

1. Every node is either red or black.
2. The root is black.
3. Every NIL leaf, the null child pointers, is black.
4. A red node cannot have a red child.
5. so you never get two reds in a row
6. Every path from a node to its descendant NIL leaves has the same number of black nodes.
7. this is called the black height property

Why this matters: - the tree stays roughly balanced - no path can become dramatically longer than the others - that prevents the tree from collapsing into something close to a linked list

How balancing happens: - after insertions or deletions, the tree may temporarily break one of the color rules - it fixes that with: - recoloring - left rotations - right rotations

A practical way to think about it: - AVL trees try to stay more strictly balanced - Red-Black Trees allow a little more flexibility - that usually means fewer rebalances on updates, which makes them a popular choice in real systems

So in one line: Red-Black Trees use color rules plus rotations to keep a BST balanced enough to guarantee O(log n) operations.

A clean way to answer this is:

1. Start with the ideal case, what performance looks like when the tree is balanced.
2. Then explain what sorted input does to a plain BST.
3. Finish with how balanced tree variants avoid the problem.

Example answer:

Sorting matters a lot for a regular binary search tree because insertion order shapes the tree.

• In a balanced BST, search, insert, and delete are typically O(log n).
• If you insert already sorted data into a plain BST, like 1, 2, 3, 4, 5, each new value goes to the right side.
• That makes the tree lopsided, basically like a linked list.

Once that happens:

• Search becomes O(n)
• Insert becomes O(n)
• Delete can also degrade to O(n)

So the issue is not sorting by itself, it is sorted insertion into an unbalanced BST.

If you use a self-balancing tree, like an AVL tree or Red-Black tree, the tree rebalances as you insert or delete nodes. That keeps the height close to log n, so performance stays efficient even when the input is sorted.

Lazy deletion is an approach where, instead of immediately removing an element from a data structure like a tree or heap, you mark it as deleted. This marker indicates that the element is logically deleted but still physically present in the structure. The main advantage of lazy deletion is that it avoids the complexity and potential performance hit of restructuring the tree or heap immediately.

For example, in a binary search tree, removing a node can require rebalancing the tree, which might be costly. By using lazy deletion, we can delay this restructuring until a later time when it's more convenient or perform a batch of updates all at once. However, one downside is that the tree or heap might become cluttered with these "marked-for-deletion" nodes, which can lead to inefficiencies if not managed properly.

I’d approach it by working backward from the problem.

First, I ask a few simple questions:

1. What operations matter most?
2. Fast lookup?
3. Frequent inserts and deletes?
4. Ordered traversal?
5. Min or max retrieval?

6. Relationship modeling?

7. What are the constraints?

8. Input size
9. Time limits
10. Memory limits

11. Whether the data is static or changing often

12. What tradeoffs am I okay with?

13. Faster reads but slower writes
14. Lower memory usage but more complex logic
15. Simpler implementation versus optimal performance

Then I map that to the structure that fits best.

A few common examples:

• Array or dynamic array
• Best when I need fast indexed access
• Good for mostly read-heavy data

• Not ideal for frequent inserts or deletes in the middle

• Linked list

• Useful when I need frequent insertions or removals and I already have the node reference

• Usually weaker for random access, since traversal is linear

• Hash map or hash set

• My go-to for fast lookup, membership checks, and counting

• Great when ordering does not matter

• Stack or queue

• I use these when the processing order matters
• Stack for LIFO cases like recursion simulation or expression evaluation

• Queue for FIFO cases like BFS or scheduling

• Heap

• Best when I repeatedly need the smallest or largest element

• Useful for priority queues, top K problems, and scheduling

• Tree

• Good when I need sorted data, range queries, or hierarchical structure

• A balanced BST helps when I need ordered operations efficiently

• Graph

• The right choice when the problem is really about relationships, connections, paths, or dependencies

For example, if I need to build a word frequency counter, I’d pick a hash map because the key operation is fast insert and lookup by word.

If I’m building something like an undo feature, I’d use a stack because I want the most recent action handled first.

If I’m solving shortest path between connected locations, I’d model it as a graph because the relationships are the core of the problem.

So overall, my process is, identify the critical operations, check the constraints, compare time and space tradeoffs, then choose the simplest data structure that handles the bottleneck efficiently.

A data structure is just a way to organize data so operations on it are efficient.

Think of it like choosing the right container for the job:

• If you want fast lookup by position, an array works well
• If you need easy insertions and deletions, a linked list can help
• If you want last-in, first-out behavior, use a stack
• If you want first-in, first-out behavior, use a queue

The main idea is simple:

• How is the data stored?
• How do you access it?
• How fast are common operations like search, insert, delete, or update?

The reason data structures matter is that the choice affects performance a lot. The same algorithm can feel fast or slow depending on how the data is organized.

So in plain terms, a data structure is a format for storing and managing data in a way that fits the problem you're trying to solve.

The main role of a heap is to help you quickly access the most important element.

Usually that means one of these:

• Max-heap, gives you the largest element first
• Min-heap, gives you the smallest element first

That is why heaps are most commonly used to build priority queues.

A good way to explain it in an interview is:

1. Start with what problem it solves

2. You need fast access to the highest or lowest priority item

3. Mention how it works at a high level

4. The root always stores the top-priority element

5. Call out the key time complexities

6. Peek top element: O(1)
7. Insert: O(log n)

8. Delete top element: O(log n)

9. Give a few practical use cases

10. Priority queues
11. Heapsort
12. Graph algorithms like Dijkstra’s and Prim’s
13. Scheduling and event simulation
14. Finding top k largest or smallest elements

A concise interview answer would be:

"A heap is a tree-based data structure mainly used when you need quick access to the maximum or minimum element. Its biggest role is in implementing priority queues, where the highest or lowest priority item should be removed first. In a heap, that top element is kept at the root, so access is efficient. Insertions and deletions are typically O(log n), and checking the top element is O(1). Heaps are also used in heapsort, graph algorithms, scheduling systems, and top k problems."

A stack and a queue mainly differ in the order items come back out.

• Stack: LIFO, last in, first out
• You add and remove from the same end
• The most recently added item is the first one you get back

• Common operations: push, pop, peek

• Queue: FIFO, first in, first out

• You add at the back and remove from the front
• The oldest item is the first one you get back
• Common operations: enqueue, dequeue, front

Easy way to picture it:

• Stack = a stack of plates

• Last plate placed on top is the first one taken off

• Queue = a line at a coffee shop

• First person in line gets served first

Typical use cases:

• Stack
• Function call tracking
• Undo/redo

• Expression evaluation

• Queue

• Task scheduling
• Print jobs
• Breadth-first search

So if order needs to be reversed, use a stack. If order needs to be preserved, use a queue.

A clean way to answer this is:

1. Start with the two big buckets.
2. Name a few examples in each.
3. Close with why the distinction matters.

Here’s a strong version:

The primary types of data structures are usually grouped into two categories:

• Linear data structures
• Data is arranged in a sequence.
• Each element typically has a clear predecessor and successor.

• Common examples:

  • Arrays
  • Linked lists
  • Stacks
  • Queues

• Non-linear data structures

• Data is organized in a hierarchical or connected way, not just one straight line.
• Common examples:
  • Trees
  • Graphs
  • Heaps
  • Binary search trees

What matters is when to use each one.

• Linear structures are great when you need simple ordering and sequential access.
• Non-linear structures are better when relationships are more complex, like parent-child hierarchies or network-style connections.

So in an interview, I’d say the main split is linear vs non-linear, then I’d mention that the right choice depends on access patterns, update cost, and the problem you’re solving.

Dynamic data structures are structures that can grow or shrink while the program is running.

Instead of reserving a fixed size upfront, they allocate memory as needed. That makes them useful when you do not know in advance how much data you will need to store.

Common examples are:

• Linked lists
• Trees
• Graphs
• Heaps
• Hash tables, in many implementations

Why they matter:

• Flexible size, you can add or remove elements at runtime
• Better memory usage, because you allocate based on need
• Good for frequent insertions and deletions

Trade-offs:

• More complex to implement and manage
• Extra memory overhead can exist, like pointers or resizing logic
• Access can be slower than static structures in some cases, for example compared to direct array indexing

In short, static structures like arrays usually have a fixed size, while dynamic data structures adapt as the data changes.

Arrays and linked lists both store collections of data, but they trade off speed, flexibility, and memory layout differently.

• Array:
• Stores elements in contiguous memory.
• Fixed size in many implementations, or resizing is expensive.
• Fast random access, O(1) by index.

• Insertions and deletions in the middle are costly, usually O(n) because elements have to shift.

• Linked list:

• Stores elements as separate nodes connected by pointers.
• Does not need contiguous memory.
• Can grow and shrink easily at runtime.
• Accessing an element is O(n) because you have to walk node by node.
• Insertions and deletions are efficient, often O(1) if you already have a reference to the right node.

The simplest way to explain it in an interview is:

1. Start with memory layout.
2. Arrays are contiguous.

3. Linked lists are scattered and connected by pointers.

4. Then talk about access time.

5. Arrays are great for indexing.

6. Linked lists are not.

7. Then cover updates.

8. Arrays are expensive to insert into or delete from.
9. Linked lists handle those updates more naturally.

A concise interview-style answer would be:

"An array stores elements in contiguous memory, so it's great when you need fast indexed access, O(1). The tradeoff is that insertions and deletions, especially in the middle, are expensive because you usually have to shift elements.

A linked list stores elements in nodes, where each node points to the next one. That makes it more flexible for growing or shrinking, and insertions or deletions can be very efficient if you already have the node reference. But access is slower because you have to traverse from the head, so lookup is O(n) instead of O(1)."

A Binary Search Tree, or BST, is a binary tree with one rule that makes it powerful:

• Everything in the left subtree is smaller than the node
• Everything in the right subtree is larger than the node

So if a node has value 10:

• left side might contain 4, 7, 9
• right side might contain 12, 15, 20

That ordering is what makes searching efficient.

Why it matters:

• To find a value, you compare and choose left or right
• To insert, you do the same until you find the right spot
• To delete, you preserve that left-smaller, right-larger rule

On average, these operations are fast:

• Search: O(log n)
• Insert: O(log n)
• Delete: O(log n)

But there is a catch:

• If the tree becomes unbalanced, like inserting sorted data 1, 2, 3, 4, 5, it can turn into something that looks like a linked list
• In that case, operations degrade to O(n)

That is why balanced versions exist, like:

• AVL trees
• Red-Black trees

They keep the tree height under control, so performance stays closer to O(log n).

A simple way to think about a BST is this: it is a structure that keeps data sorted while still allowing efficient search, insert, and delete operations.

A binary tree is the general version.

• Each node can have up to 2 children, left and right.
• There is no required ordering between node values.
• It is mainly about the shape, not the value rules.

A binary search tree, or BST, is a binary tree with an extra rule.

• Everything in the left subtree is smaller than the node.
• Everything in the right subtree is larger than the node.
• That ordering is what makes searching, inserting, and deleting more efficient, on average.

Simple way to think about it:

• Binary Tree = "at most two children"
• BST = "at most two children, plus sorted structure"

Example:

• This is a binary tree: root 10, left child 50, right child 3
• This is not a BST, because 50 is on the left of 10

Why it matters:

• In a regular binary tree, you may have to scan a lot of nodes to find a value.
• In a BST, you can decide to go left or right at each step based on the value you are looking for.

One clean line to use in an interview:

• Every BST is a binary tree, but not every binary tree is a BST. The difference is the ordering property.

In a singly linked list, insertion is really just about updating pointers in the right order.

There are 3 common cases:

1. Insert at the head
2. Create the new node.
3. Set newNode.next = head.
4. Move head to newNode.

This is the simplest case, and it takes O(1) time.

1. Insert in the middle, or at a specific position
2. First, walk to the node just before the insertion point.
3. Let that node be prev.
4. Set newNode.next = prev.next.
5. Then set prev.next = newNode.

That order matters. You connect the new node first, then hook the previous node to it, so you do not lose the rest of the list.

1. Insert at the tail
2. If you only have a head pointer, traverse until you reach the last node.
3. Set the last node’s next to newNode.
4. Make sure newNode.next = null.

If you also keep a tail pointer, this becomes O(1). Otherwise, it is O(n) because you have to traverse.

A couple edge cases to mention in an interview: - Empty list, inserting the first node means both head, and sometimes tail, point to the new node. - Inserting at position 0 is just head insertion. - Invalid positions should usually be checked and handled explicitly.

So the main idea is simple: find the right spot, update next pointers carefully, and avoid breaking the chain.

I’d explain it as a two-pointer merge, same idea as the merge step in merge sort.

How to structure the answer: 1. Say what pointers you use. 2. Walk through the comparison logic. 3. Mention the edge case at the end. 4. Call out time and space complexity.

Example answer: - Keep one pointer on each sorted list, l1 and l2. - Create a dummy node and a tail pointer for the merged list. - Compare l1.val and l2.val. - Attach the smaller node to tail.next - Move that list’s pointer forward - Move tail forward - Keep doing that until one list runs out. - When one list is empty, attach the rest of the other list directly, since it’s already sorted.

Why the dummy node helps: - It makes the code cleaner. - You do not need special handling for the head of the merged list. - It also handles empty-list cases nicely.

Complexity: - Time: O(m + n), because you visit each node once - Space: O(1) extra space, if you reuse the existing nodes

If they want a concise interview version: “You use two pointers, one for each list, and a dummy head for the result. Repeatedly compare the current nodes, link the smaller one to the merged list, and advance that pointer. Once one list is exhausted, link the remainder of the other list. That gives you a sorted merged list in linear time.”

I’d answer this by naming the main collision strategies, then comparing the tradeoffs. That shows you understand both the implementation and when to use each one.

A clean way to structure it:

1. Define what a collision is
2. Mention the common ways to handle it
3. Call out the tradeoffs, especially around performance and deletion
4. Mention load factor and resizing, because that affects all approaches

Example answer:

A collision happens when two different keys map to the same index in the hash table.

The two main ways to handle that are:

• Separate chaining
• Each bucket stores a small collection of entries, often a linked list, sometimes a dynamic array.
• If two keys land in the same bucket, you just store both there.
• This is simple to implement and makes deletion easy.

• Performance is usually O(1) on average, but if too many keys pile into one bucket, it can degrade toward O(n).

• Open addressing

• All entries stay inside the array itself.
• When a collision happens, you probe for another open slot.
• Common probing strategies are:
  • Linear probing, check the next slot
  • Quadratic probing, jump by increasing square offsets
  • Double hashing, use a second hash function to decide the jump
• This can be cache-friendly, but deletion is trickier, and clustering can hurt performance.

I’d also mention resizing, because collision handling is heavily affected by load factor.

• If the table gets too full, collisions become much more frequent.
• So once the load factor crosses a threshold, you grow the table and rehash the entries.
• That keeps average lookup, insert, and delete close to O(1).

If I had to pick one in practice:

• I’d use chaining when I want simpler deletion and easier implementation.
• I’d use open addressing when memory layout and cache performance matter, and I can manage probing carefully.

So the short version is: handle collisions with chaining or open addressing, and control collision frequency by keeping the load factor low through resizing.

I’d answer it by first defining what “depth” means, then giving the cleanest way to compute it.

A simple way is recursion:

1. If the node is null, its depth is 0.
2. Recursively get the depth of the left subtree.
3. Recursively get the depth of the right subtree.
4. Return max(left, right) + 1.

In plain terms, you keep going down both sides of the tree, and at each node you take the deeper side and add one for the current node.

The logic looks like this in Python:

max_depth(node)
- if node is None, return 0
- compute left = max_depth(node.left)
- compute right = max_depth(node.right)
- return max(left, right) + 1

A couple of interview points I’d mention:

• Time complexity is O(n) because you visit each node once.
• Space complexity is O(h) for the recursion stack, where h is the height of the tree.
• If they want an iterative version, you can also do it with BFS level-order traversal and count levels.

A Fibonacci heap is a priority queue data structure designed to make some operations extremely cheap, at least in an amortized sense.

The quick way to think about it:

• It stores elements in a bunch of heap-ordered trees
• The minimum element is easy to track
• It delays structural cleanup until it actually needs to do it

That "lazy" approach is the whole trick. Instead of aggressively reorganizing the heap after every update, it does the minimum work up front and cleans things up later.

Key performance highlights:

• insert is amortized O(1)
• merge or union is amortized O(1)
• decrease-key is amortized O(1)
• extract-min is amortized O(log n)

Why people care about it:

• It is especially strong when you do lots of decrease-key operations
• That makes it attractive for graph algorithms that keep improving tentative distances or edge weights

Common use cases:

• Dijkstra’s shortest path algorithm
• Prim’s minimum spanning tree algorithm
• Other network optimization problems

One practical note:

• Fibonacci heaps are famous more in theory than in production code
• In real systems, people often use binary heaps or pairing heaps instead, because they are simpler and usually faster in practice despite weaker theoretical bounds

So, if I were explaining it in an interview, I’d say: a Fibonacci heap is a lazily maintained heap that gives excellent amortized performance, especially for decrease-key, which is why it shows up in advanced graph algorithm analysis.

I’d usually reverse a linked list iteratively, because it’s simple, efficient, and uses constant extra space.

The idea is to walk through the list once and flip each pointer as you go.

A clean way to explain it:

1. Keep three pointers:
2. prev, starts as null
3. curr, starts at head

4. next, used to save curr.next

5. For each node:

6. Save the next node in next
7. Point curr.next back to prev
8. Move prev forward to curr

9. Move curr forward to next

10. When curr becomes null, prev is the new head of the reversed list.

Why this works: - You reverse one link at a time. - next prevents you from losing the rest of the list. - prev always holds the already reversed portion.

Complexity: - Time: O(n) - Space: O(1)

If I were saying it in an interview, I’d keep it short:

“I’d use three pointers, prev, curr, and next. Traverse the list, save the next node, reverse the current node’s pointer, then advance all pointers. At the end, prev points to the new head. That gives O(n) time and O(1) extra space.”