Top 100+ Data Structure Interview Questions and Answers

To find the sum of all elements in an array, iterate through each element, adding them to a cumulative sum variable initialized at zero.

To remove duplicates from an array without using any additional data structure, iterate through the array, comparing each element with the rest. Overwrite duplicates with the next unique element, adjusting the array's size accordingly.

Rotating an array to the left by 'n' positions involves shifting each element 'n' positions to the left, with the leftmost elements wrapping around to the right end of the array.

To find the maximum and minimum element in an array, iterate through the array, comparing each element to the current maximum and minimum, updating these variables as necessary.

Merging two sorted arrays into a single sorted array requires iterating through both arrays simultaneously, comparing elements, and adding the smaller element to a new array until all elements are merged.

Finding the intersection of two arrays involves iterating through one array and checking if its elements appear in the second array, storing the matches in a new array.

The algorithm to find the "Kth" largest element in an array typically involves sorting the array and accessing the element at the position length minus 'k'.

To move all zeros in an array to the end while maintaining the order of other elements, iterate through the array, shifting non-zero elements forward, and filling the end of the array with zeros.

An algorithm to check if an array contains a duplicate within 'k' distance from each other involves iterating through the array and checking the elements within 'k' positions ahead for duplicates.

Finding the majority element in an array, if it exists, requires iterating through the array to count the occurrences of each element and determining if any count exceeds half the size of the array.

Performing a binary search on a sorted array involves repeatedly dividing the search interval in half, comparing the target value to the middle element, and narrowing the search based on the comparison.

To find all pairs in an array that sum up to a specific number, iterate through the array, for each element, searching for a complementary element that equals the target sum minus the current element.

Cyclically rotating an array by one position involves moving the last element of the array to the front, and shifting all other elements one position to the right.

Implementing a two-dimensional array's diagonal traversal requires iterating over the array in a manner that increases the row index and decreases the column index simultaneously for one direction, or vice versa.

Shuffling an array randomly involves iterating through the array and swapping each element with another randomly selected element from the array.

Finding the common elements in three sorted arrays requires iterating through all three arrays simultaneously, advancing in each array based on the comparison of the current elements to find matches.

Flattening a multi-dimensional array involves recursively traversing each element, if the element is an array itself, further traversing its elements, and aggregating the leaf values into a new, single-dimensional array.

Implementing an algorithm to find the next greater element for every element in an array involves iterating through the array and for each element, searching the subsequent elements for a larger value.

Finding the longest consecutive sequence in an array requires sorting it and then iterating through it to find the longest sequence of consecutive numbers.

Computing the prefix sum array for a given array involves iterating through the original array and summing the elements from the start to the current index, storing each sum in a new array at the corresponding index.

A function splits a circular linked list into two equal parts by finding the middle of the list using a fast and slow pointer approach and then cutting the list into two halves. Adjust the next pointers of the two halves to make them separate circular linked lists.

Implementing a function to check if a linked list is a palindrome involves reversing the second half of the list and comparing it with the first half. If all elements match, the linked list is a palindrome.

An algorithm removes all elements from a linked list of integers that have a specific value by iterating through the list, maintaining a previous pointer, and unlinking the nodes that match the value.

An algorithm adds two numbers represented by two linked lists by traversing both lists simultaneously, summing the corresponding digits along with any carry, and forming a new linked list of the sum.

To rotate a linked list to the right by 'k' places, find the length, mod it with 'k' to get the effective rotations, and change the next pointers accordingly after locating the new head and tail.

A function swaps pairs of nodes in a linked list by iterating through the list and swapping the next pointers of adjacent nodes.

A function finds the entry node of a cycle in a linked list using Floyd's Tortoise and Hare algorithm to first detect the cycle and then find the cycle's entry point by moving two pointers at different speeds.

Flattening a multilevel doubly linked list involves recursively traversing the list and connecting child nodes in line with the main list, adjusting the previous and next pointers accordingly.

A method partitions a linked list around a value 'x' by creating two separate lists: one for nodes less than 'x' and another for nodes greater than or equal to 'x', and then concatenating these two lists.

A function copies a linked list with a next and random pointer by creating a mapping from the original nodes to their copies and then iterating through the list to assign the next and random pointers of the copies.

An algorithm finds the node at which the intersection of two singly linked lists begins by first calculating the length of both lists, aligning them at the same start point, and then iterating until the intersection node is found.

Finding the sum of two linked lists using Stack involves pushing all elements of both lists into separate stacks, popping them to sum the digits with carry, and forming a new linked list with the sum from the carried-over digits.

A method reverses nodes in a linked list in groups of size 'k' by iteratively picking 'k' nodes, reversing them, and then connecting the reversed group with the rest of the list.

Implementing a doubly linked list's insertion sort involves iterating through the list, comparing each node with its predecessors, and placing it in its correct position ensuring both next and previous pointers are correctly updated.

A function moves the last element to the front in a given singly linked list by traversing to the end of the list, disconnecting the last node, and setting it as the new head.

Removing the nth node from the end of a linked list requires traversing the list to find the length, calculating the position of the node from the beginning, and unlinking it from the list.

A function merges k sorted linked lists into one sorted linked list by using a min-heap to keep track of the smallest elements of each list and linking them together to form a single sorted list.

A program deletes a linked list by iterating through the list and deleting each node until the entire list is deleted, finally setting the head pointer to null.

An efficient algorithm checks if a linked list has a loop by using Floyd's cycle detection algorithm and removes the loop by finding the junction point and setting the next of the loop node to null.

Implementing a queue using two stacks with costly enqueues involves using one stack for enqueuing elements and another for dequeuing, moving elements from the enqueue stack to the dequeue stack when necessary to maintain the queue order.

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Stack finds usage in scenarios like function calls, undo mechanisms in software, and for solving algorithmic problems such as syntax parsing and expression evaluation.

To implement a stack using arrays, maintain a pointer to the top element of the stack. For push operations, increase the pointer and insert the element at the new top position. For pop operations, return the element at the top position and decrease the pointer.

A function to push an element onto a stack adds the element to the end of the stack and updates the top pointer to point to this new element.

To pop an element from a stack, remove the element at the top of the stack and decrement the top pointer.

A method to check if a stack is empty compares the top pointer with the initial state, indicating an empty stack if they match.

To implement a stack using a linked list, insert and remove elements from the same end, typically the head of the list, ensuring LIFO order is maintained.

The time complexity of push and pop operations in a stack is O(1), as these operations only involve working with the top element.

A function to return the top element of a stack retrieves the value at the top pointer without modifying the stack's structure.

To reverse a string using a stack, push each character of the string onto the stack and then pop them in sequence, which reverses the order of the characters.

A program to evaluate a postfix expression uses a stack to sequentially push operands and pop them for evaluation when an operator is encountered, pushing back the result until the expression is fully evaluated.

To implement two stacks in one array efficiently, divide the array from both ends, with one stack growing from the start and the other from the end, maximizing space utilization.

The balanced parentheses problem is solved using a stack by pushing open parentheses onto the stack and popping them when a matching closing parenthesis is encountered, checking for balance throughout.

Design a stack to support the getMin() operation in constant time by keeping an auxiliary stack that stores the minimum element at the top after each operation.

A function to sort a stack uses a temporary stack to hold elements while the original stack is manipulated with push and pop operations to arrange the elements in sorted order.

The Tower of Hanoi problem can be coded using stacks by representing each peg as a stack and moving disks according to the rules, utilizing recursive stack operations.

A queue can be implemented using two stacks by enqueuing in one stack and dequeuing by reversing the order into the second stack, ensuring FIFO order is maintained.

An algorithm to find the next greater element for every element in an array pushes array indices onto a stack and pops them when a greater element is found, associating the greater element with the popped indices.

Check for circular dependencies in a project using a stack by performing a depth-first search on the dependency graph, pushing nodes onto the stack as they are visited, and detecting cycles when a node is encountered that is already in the stack.

Design a stack with operations on the middle element by using a doubly linked list to enable efficient access and modification of the middle element, adjusting the middle pointer as elements are added or removed.

To find the largest rectangular area in a histogram using a stack, push the indices of the bars onto the stack when the current bar is higher than the bar at the top stack index and calculate areas by popping when the current bar is lower, updating the maximum area accordingly.

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where elements are added at one end, called the rear, and removed from the other end, called the front.

Implement a queue using arrays by maintaining two pointers for the front and rear positions. Increase the rear pointer when adding an element and increase the front pointer when removing an element.

Implement a circular queue in Java by using an array and two pointers, front and rear. Wrap around the rear to the beginning of the array when it reaches the end to utilize empty spaces.

The main difference between a stack and a queue is in their ordering principles: a stack operates on a Last-In-First-Out (LIFO) principle, while a queue uses a First-In-First-Out (FIFO) principle.

Reverse a queue using recursion by dequeuing an element, recursively reversing the remaining queue, and then adding the dequeued element at the rear of the queue.

Implement a priority queue by using a heap data structure where elements are inserted based on their priority and the element with the highest priority is always removed first.

A dequeue (double-ended queue) is a data structure that allows the insertion and removal of elements from both the front and rear ends. Implement it using a doubly linked list to efficiently manage elements from both ends.

Implement a queue using two stacks by using one stack for enqueuing elements and the other stack for dequeuing. When dequeuing, if the dequeue stack is empty, transfer all elements from the enqueue stack to the dequeue stack.

A blocking queue in multithreading is a queue that blocks the dequeue operation until an element becomes available and blocks the enqueue operation if the queue reaches its capacity, ensuring thread safety.

Generate binary numbers from 1 to N using a queue by enqueuing the initial binary number "1" and then repeatedly removing the front element, appending "0" and "1" to it, and enqueuing these new binary numbers until N numbers are generated.

Perform a level order traversal of a binary tree using a queue by enqueueing the root, then repeatedly dequeuing an element, printing it, and enqueuing its left and right children until the queue is empty.

Design a queue with a constant time complexity for getMinimum() by using two auxiliary data structures: a primary queue for enqueue and dequeue operations and an auxiliary deque to maintain the minimum element.

Check if a queue is palindrome by using a stack to reverse half of the queue's elements, then comparing these elements with the second half of the queue as they are dequeued.

Find the circular tour that visits all petrol pumps using a queue by enqueueing petrol pump positions and their petrol amounts, then check if a complete tour is possible by maintaining a running sum of petrol.

Sort a queue without using extra space by repeatedly finding the minimum element in the queue, dequeuing, and enqueuing elements as needed until the queue is sorted.

Implement a queue using a singly linked list by maintaining two pointers, one for the front of the queue and one for the rear, allowing for efficient enqueue and dequeue operations.

Solve the 'truck tour' problem using queues by enqueueing all petrol pumps with their petrol and distance to the next pump, then calculating if a truck can complete the circuit by starting at different pumps.

Merge k sorted queues into one sorted queue by using a min-heap to efficiently find and remove the smallest element among the front elements of all queues until all queues are empty.

Implement a sliding window maximum algorithm using a dequeue by maintaining a dequeue of indices for elements within the current window, ensuring the front of the dequeue always contains the index of the maximum element.

Design an LRU cache using a queue by pairing each element with its last access time, and when the cache reaches its capacity, dequeuing the least recently used element before enqueuing a new element.

A tree data structure is a hierarchical model that consists of nodes with a parent-child relationship, used in databases, and file systems, and for efficient data searching and sorting.

Traverse a binary tree using in-order traversal by visiting the left subtree first, then the current node, and finally the right subtree to achieve a sorted sequence of elements for binary search trees.

Find the height of a binary tree by recursively calculating the maximum depth of the left and right subtrees and adding one to account for the root node.

In the binary search trees, each node has a value greater than all values in its left subtree and less than all values in its right subtree, facilitating efficient search operations.

Implement a binary search tree insertion operation by comparing the new value with the current node's value and recursively inserting it into the left subtree if it's less, or the right subtree if it's greater, ensuring the binary search tree property is maintained.

Check if a binary tree is balanced by ensuring that the height difference between the left and right subtrees of every node is no more than one.

Convert a binary tree into a doubly linked list by performing an in-order traversal and adjusting pointers to link nodes in a way that they form a doubly linked list.

A binary heap is a complete binary tree that maintains the heap property; perform an insert operation by adding the element at the bottom and rightmost position, then heapify up to maintain the heap structure.

Delete a node from a binary search tree by locating the node, then replacing it with its in-order predecessor (the maximum-value node in its left subtree) or in-order successor (the minimum-value node in its right subtree) if the node has two children, and adjusting pointers to maintain the binary search tree properties.

Find the lowest common ancestor of two nodes in a binary search tree by traversing from the root and choosing the path based on the values of the nodes being compared until finding the node where one value is on one side and the other is on the opposite side.

Perform level-order traversal of a binary tree by using a queue to hold nodes and their children as you traverse the tree, ensuring that nodes are visited level by level.

Serialize a binary tree by converting it into a string of node values separated by commas, including null values for empty nodes, and deserialize by reconstructing the tree from this string using a queue to maintain the order of nodes.

AVL trees are self-balancing binary search trees that maintain a balance factor of -1, 0, or 1 for every node and perform rotations—single or double, left or right—to restore balance when inserting or deleting nodes.

Implement a trie (prefix tree) by using a tree-like data structure where each node represents a character of a string, and insert and search operations traverse the tree based on the characters of the string being inserted or searched.

Find the maximum path sum in a binary tree by calculating, for each node, the maximum path sum that includes the node and possibly one of its subtrees, and updating the global maximum based on these values.

Mirror a binary tree by swapping the left and right children of every node in the tree, either recursively or iteratively, to create a mirror image.

A segment tree is a binary tree used for storing intervals or segments, built by recursively dividing the segment into two halves until reaching individual elements, and storing information like sums or minimums at each node.

Check if a binary tree is a valid binary search tree by ensuring, through in-order traversal, that the values of nodes are in ascending order, indicating that each node adheres to the binary search tree property.

A Fenwick tree, or binary indexed tree, is a data structure that provides efficient methods for calculating prefix sums in a list of numbers, used in scenarios requiring frequent updates and queries for cumulative sums.

Find the kth smallest element in a binary search tree by performing an in-order traversal and maintaining a count of visited nodes, stopping when the count reaches k to return the current node's value.

A binary search tree (BST) is defined as a binary tree where each node has a value greater than all values in its left subtree and less than or equal to all values in its right subtree.

Insert a value into a BST by comparing it with the root, recursively inserting it into the left subtree if the value is less, or into the right subtree if it is greater, until finding a leaf position where the new value can be added as a child node.

To delete a node from a BST, find the node, then if it has two children, find its in-order successor (the smallest node in the right subtree), swap values, and delete the successor node; if the node has one or no child, adjust pointers to bypass the deleted node.

Search for a value in a BST by starting at the root and recursively searching the left or right subtree based on whether the value is less than or greater than the current node's value until finding the value or reaching a leaf node.

The inorder predecessor in a BST is the largest value node in the left subtree of the given node, and the inorder successor is the smallest value node in the right subtree of the given node.

Find the minimum value in a BST by traversing down the left subtree until reaching the last node. Similarly, find the maximum value by traversing down the right subtree until reaching the last node.

Check if a binary tree is a BST by verifying that for every node, all values in its left subtree are less, and in its right subtree are greater, using an in-order traversal to ensure the values are sorted.

Find the height of a BST by calculating the maximum depth from the root to the furthest leaf node, using a recursive function that returns the greater height of the left or right subtree plus one.

The advantages of using a BST include efficient search, insert, and delete operations due to the tree's structured organization, and facilitating binary search methods with an average time complexity of O(log n).

Find the kth smallest element in a BST by performing an in-order traversal and maintaining a count of visited nodes until reaching the kth element.

Convert a sorted array to a balanced BST by selecting the middle element as the root, recursively doing the same for the left half and right half of the array to construct the left and right subtrees.

Balance a BST by rotating nodes to ensure that the difference in heights between the left and right subtrees of any node does not exceed one, using rotations to restructure the tree.

Count the number of nodes in a BST that fall within a given range by traversing the tree and incrementing a counter for each node whose value lies within the range, using a recursive or iterative approach.

Check if two BSTs are identical by comparing their structures and node values recursively, ensuring that for every node in one tree, there is a corresponding node with the same value in the other tree.

Merge two BSTs into a single BST by performing an in-order traversal of both trees to create sorted arrays, merging these arrays into a single sorted array, and then constructing a balanced BST from the merged array.

The time complexity of inserting an element into a BST is O(log n) on average, assuming the tree is balanced, but can degrade to O(n) if the tree becomes skewed.

Perform a level-order traversal on a BST by using a queue to keep track of nodes at each level, enqueueing the root, and then continuously removing a node from the queue, visiting it, and enqueuing its left and right children until the queue is empty.

A self-balancing BST is a binary search tree that automatically maintains its balance to ensure operations remain efficient. Examples include AVL trees and Red-Black trees, which use rotations to maintain a balanced height.

Determine if a BST is balanced by ensuring that for every node, the height difference between the left and right subtrees is no more than one, using a recursive function that checks the balance of each subtree.

Find the lowest common ancestor of two nodes in a BST by starting from the root and moving toward the left or right child depending on the nodes’ values until finding a node where one node is on one side and the other node is on the opposite side, indicating the LCA.

A graph data structure consists of a set of vertices (nodes) connected by edges (links), and its types include undirected graphs, directed graphs, weighted graphs, and unweighted graphs.

Represent graphs in computer memory using adjacency lists, which list all nodes connected to each node, or adjacency matrices, a 2D array where matrix[i][j] indicates the presence or absence of an edge between i and j.

Implement graph traversal using BFS (Breadth-First Search) by starting at a chosen node, exploring all its neighbors at the current depth level before moving on to the nodes at the next depth level, using a queue to manage the order of exploration.

Implement DFS (Depth-First Search) for a graph using an adjacency list by starting at a selected node, recursively exploring each branch before backtracking, and using a stack (explicit or via recursion) to keep track of the vertices.

The difference between a tree and a graph is that a tree is a special form of a graph that is connected and acyclic, with a single path between any two vertices, whereas graphs can have cycles, and multiple paths between vertices, and may not be connected.

Detect a cycle in a directed graph using Depth-First Search (DFS) by keeping track of visited vertices and the recursion stack. A cycle exists if a vertex is reached that is already in the recursion stack.

Find the shortest path between two vertices in a graph using Dijkstra's algorithm, which progressively extends the shortest path from the starting vertex to all other vertices by exploring the nearest unvisited vertex.

A weighted graph is a graph where each edge has a numerical value (weight) associated with it, representing costs like distance or time. Represent it using adjacency lists with weights or adjacency matrices where the elements are weights instead of booleans.

The Dijkstra algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights by using a priority queue to select the closest unvisited vertex and updating the paths to its neighbors if shorter paths are found.

Implement a graph using adjacency matrices by creating a 2D array where the element at row i and column j indicates whether an edge exists between vertex i and vertex j, with the value representing the edge weight in weighted graphs.

Check if a graph is bipartite by attempting to color each vertex using two colors in such a way that no two adjacent vertices share the same color, using BFS or DFS to propagate the coloring.

A spanning tree is a subset of a graph that includes all the vertices connected by the minimum number of edges required to maintain connectivity. A minimum spanning tree is a spanning tree with the least total edge weight.

Implement Kruskal’s algorithm to find a minimum spanning tree by sorting all edges in non-decreasing order of their weight and adding them to the spanning tree one by one, ensuring that no cycles are formed, using a disjoint-set data structure to efficiently check for cycles.

Find strongly connected components in a graph using Kosaraju’s algorithm or Tarjan's algorithm, which involves DFS traversals to explore the connectivity and structure of the graph.

Perform topological sorting in a DAG by using DFS to recursively visit nodes, pushing a node onto a stack only after all its dependent nodes have been visited, thereby ensuring that nodes are processed in dependency order.

The Bellman-Ford Algorithm calculates the shortest paths from a single source vertex to all other vertices in a weighted graph, including those with negative weights, unlike Dijkstra's, which requires non-negative edge weights.

Find all pairs shortest path in a graph using the Floyd-Warshall algorithm, which iteratively updates distances between pairs of vertices through an intermediate vertex, considering all vertices as intermediate points.

Detect negative cycles in a graph using the Bellman-Ford algorithm by performing one extra iteration after finding the shortest paths. If any distance is updated in this extra iteration, a negative cycle exists.

The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of vertices in a graph, handling negative weights. It iteratively improves the path lengths between every pair using each vertex as an intermediate point.

Implement Prim's algorithm for finding a minimum spanning tree by starting from an arbitrary vertex and growing the spanning tree one edge at a time, choosing the smallest edge connecting the tree to a vertex not yet in the tree, and using a priority queue to select the smallest edge efficiently.

A Trie is a tree-like data structure that stores a dynamic set of strings, where the keys are usually characters. Its applications include autocomplete, spell-checking, IP routing, and pattern matching.

Insert a word into a Trie by creating nodes for each character of the word if they do not already exist, marking the last node as the end of the word.

Search for a word in a Trie by traversing the Trie from the root, following the nodes corresponding to each character of the word. The search is successful if it reaches a node that marks the end of the word.

To delete a word from a Trie, recursively remove nodes from the end if they do not lead to any other words, ensuring not to disrupt other words in the Trie.

Implement auto-suggestions by performing a prefix search to find the node corresponding to the last character of the prefix, then recursively find all words that branch from that node, collecting suggestions.

The time complexity of inserting and searching for a word in a Trie is O(m), where m is the length of the word. This efficiency is due to the direct path followed for each character in the word.

Count the number of words in a Trie by performing a depth-first search (DFS) and counting nodes that mark the end of a word, ensuring to traverse each possible path in the Trie.

Design a Trie to support wildcard searches by modifying the search function to allow a special wildcard character to match any character at a certain position, recursively searching all possible paths when a wildcard is encountered.

Store and retrieve a large dictionary efficiently using a Trie by utilizing the structure's ability to share prefixes, significantly reducing memory usage compared to storing each word independently, and allowing for quick lookups.

Find the longest common prefix among a set of strings by inserting all the strings into a Trie and then traversing the Trie from the root until reaching a node that has more than one child or is the end of a word, concatenating the characters traversed.