Data Structure Interview Question

Here you get a free Data Structure Interview Question which helps you to Give Correct Answer of the Question in the Interview. It also helps you for you college exams Preparation.

Basic of DSA

1. Explain the Running Sum of 1D Array in DSA.
2. How Shuffle the Array in DSA ???
3. Explain the Fibonacci Numbers in DSA.
4. Explain the Reversing a String in DSA.
5. Explain the Search Insert Position in DSA.
6. Explain Jewels and Stones in DSA.

Arrays and Matrices

1. Find the maximum Sum Subarray using Divide and Conquer.
2. Implement an algorithm to find the submatrix with the maximum sum.
3. Rotate a square matrix by 90 degrees in-place.
4. Find the median of two sorted arrays of different sizes.
5. Find all subarrays with a given XOR value.
6. Implement the Kadane’s algorithm for a 2D matrix.
7. Find the smallest range that includes elements from K sorted arrays.
8. Find the majority element in an array using the Boyer-Moore algorithm.
9. Determine if a Sudoku puzzle is valid.
10. Implement the Strassen’s Matrix Multiplication algorithm.

Strings

1. Find the longest palindromic substring using Manacher’s algorithm.
2. Implement KMP (Knuth-Morris-Pratt) pattern matching algorithm.
3. Find the shortest superstring containing all given strings.
4. Solve the “Edit Distance” problem using Dynamic Programming.
5. Count distinct substrings of a string using a Trie.
6. Implement Rabin-Karp for pattern searching with rolling hash.
7. Find the lexicographically smallest rotation of a string.
8. Check if a string can be rearranged into a palindrome.
9. Find the minimum number of characters to insert to make a string palindrome.
10. Perform a Z-algorithm for pattern matching.

Linked Lists

1. Reverse a linked list in groups of K.
2. Detect and remove a loop in a linked list.
3. Merge K sorted linked lists into one sorted list.
4. Flatten a multilevel doubly linked list.
5. Clone a linked list with random pointers.
6. Find the intersection point of two linked lists.
7. Add two numbers represented by linked lists.
8. Rotate a linked list by K nodes.
9. Find the starting node of the cycle in a linked list.
10. Merge two sorted linked lists without recursion.

Stacks and Queues

1. Implement a stack that supports getMin() in O(1).
2. Sort a stack using recursion.
3. Implement a queue using two stacks.
4. Find the maximum element in each sliding window of size K.
5. Evaluate a postfix expression using a stack.
6. Implement an LRU Cache using a Doubly Linked List.
7. Check for balanced parentheses using a stack.
8. Find the largest rectangle in a histogram.
9. Implement a monotonic stack for finding the next greater element.
10. Design a circular queue with dynamic resizing.

Trees

1. Serialize and Deserialize a binary tree.
2. Find the Lowest Common Ancestor in a binary tree.
3. Implement a Segment Tree for range sum queries.
4. Check if a binary tree is height-balanced.
5. Construct a binary tree from its preorder and inorder traversals.
6. Convert a binary tree to its mirror image.
7. Find the diameter of a binary tree.
8. Implement the Morris Traversal for in-order traversal.
9. Find the maximum path sum in a binary tree.
10. Design an AVL tree with insertion and deletion.

Binary Search Trees (BST)

1. Find the Kth smallest/largest element in a BST.
2. Implement a BST iterator with O(1) average time per operation.
3. Validate if a given tree is a BST.
4. Convert a BST to a balanced BST.
5. Construct a BST from a sorted array.
6. Find pairs with a given sum in a BST.
7. Merge two BSTs into a balanced BST.
8. Delete a node in a BST.
9. Invert a BST.
10. Find the inorder successor/predecessor in a BST.

Heaps and Priority Queues

1. Implement a max heap and min heap.
2. Find the Kth largest element in a stream.
3. Merge K sorted arrays using a heap.
4. Implement a median-finding data structure.
5. Check if a binary tree is a heap.
6. Find the smallest range that includes elements from K lists.
7. Solve the “Task Scheduler” problem.
8. Reorganize a string such that no two adjacent characters are the same.
9. Find the top K frequent elements in an array.
10. Implement a heap sort algorithm.

Graphs

1. Implement Dijkstra’s algorithm for the shortest path.
2. Find the bridges in a graph using Tarjan’s algorithm.
3. Solve the “Travelling Salesman Problem” using dynamic programming.
4. Implement Kruskal’s algorithm for Minimum Spanning Tree.
5. Check if a graph is bipartite.
6. Find all strongly connected components using Kosaraju’s algorithm.
7. Solve the “Word Ladder” problem using BFS.
8. Implement Prim’s algorithm for Minimum Spanning Tree.
9. Perform a topological sort using Kahn’s algorithm.
10. Find the shortest path in a weighted DAG.

Dynamic Programming

1. Solve the “Longest Increasing Subsequence” problem.
2. Solve the “0/1 Knapsack” problem.
3. Find the number of ways to decode a message.
4. Implement the “Egg Dropping Problem”.
5. Solve the “Longest Palindromic Subsequence” problem.
6. Count the number of ways to partition a set into subsets.
7. Solve the “Matrix Chain Multiplication” problem.
8. Find the minimum cost to paint houses with a color constraint.
9. Solve the “Wildcard Matching” problem.
10. Solve the “Subset Sum” problem.

Greedy Algorithms

1. Solve the “Activity Selection” problem.
2. Implement Huffman Encoding for data compression.
3. Find the minimum number of platforms required for a railway station.
4. Solve the “Fractional Knapsack” problem.
5. Find the minimum spanning tree using Kruskal’s algorithm.
6. Solve the “Job Sequencing Problem”.
7. Determine the optimal strategy for the “Gas Station” problem.
8. Implement the “Interval Partitioning” problem.
9. Solve the “Optimal File Merge Pattern”.
10. Find the minimum cost to connect ropes.

Backtracking

1. Solve the N-Queens problem.
2. Find all subsets of a set.
3. Solve the “Sudoku Solver” problem.
4. Solve the “Rat in a Maze” problem.
5. Find all permutations of a string or array.
6. Solve the “Word Break” problem using backtracking.
7. Implement a Knight’s Tour problem.
8. Solve the “Partition Equal Subset Sum” problem.
9. Find all combinations that sum to a given value.
10. Solve the “Hamiltonian Path” problem.