TRENDING TOPICS
LEGAL
Cookie Settings
Data structure questions are some of the most commonly asked in coding interviews. These questions test your ability to implement, optimize, and adapt data structures to solve a unique situation. It’s essential to review common questions before your coding interview to ensure you’re not caught off guard with an unfamiliar question.
Today, we’ll help you brush up on your data structure skills by reviewing 45 of the top data structure questions you should practice before your next interview.
Here’s what we’ll cover today:
Practice hundreds of common interview questions with hands-on code environments and instant feedback.
Data Structures for Coding Interviews in C#
Find the Big O complexity of the following code snippet.
Find the Big O complexity of the following code snippet:
Implement a function removeEven( int[]Arr, int size ), which takes an array arr and its size and removes all the even elements from the given array.
For example:
// Input: Arr = [1,2,4,5,10,6,3]
// Output: Arr = [1,5,3]Solution and Explanation
Time Complexity:
This solution first checks if the first element of Arr is odd. Then it appends this element to the start of the array Arr; otherwise, it jumps to the next element. This repeats until the end of the array Arr is reached while keeping the count of total odd numbers m in Arr. Next, we make a temporary array, temp, to store all odd numbers.
From there, we delete the memory allocated to Arr, and point it to the temp array. Lastly, we return the array Arr that is, which now contains only odd elements.
Implement a function findMinimum(int arr[], int size), which takes an array arr and its size and returns the smallest number in the given array.
For example:
// Input: arr = [9,2,3,6]
// Output: 2
Solution and Explanation
Time Complexity:
Start with the first element (which is 9 in this example), and save it as the smallest value. Then, iterate over the rest of the array. Whenever an element that is smaller than minimum is found, set minimum to that number.
By the end of the array, the number stored in minimum will be the smallest integer in the whole array.
Given an unsorted array Arr, find the collection of contiguous elements that sums to the greatest value.
Hint: Remember that the array could contain negative numbers.
Solution and Explanation
Time Complexity:
This solution uses Kadane’s algorithm to scan the entire array.
Take a look at Kadane’s algorithm in pseudocode:
currMax = A[0]
globalMax = A[0]
for i = 1 -> size of A
if currMax is less than 0
then currMax = A[i]
otherwise
currMax = currMax + A[i]
if globalMax is less than currMax
then globalMax = currMax
At each position in the array, we find the maximum sum of the subarray ending there. This is achieved by keeping a currMax for the current array index and a globalMax. By the end, we know that the value of globalMax will be the highest subarray, regardless of the value of currMax.
Below are the Node and LinkedList classes available for you to use throughout this section:
using System;
public class LinkedList
{
public class Node
{
internal int data; //Data to store (could be int,string,object etc)
internal Node nextElement; //Pointer to next element
public Node()
{
//Constructor to initialize nextElement of newlyCreated Node
nextElement = null;
}
};
Node head;
public LinkedList()
{
head = null;
}
public bool IsEmpty()
{
if (head == null) //Check whether the head points to null
return true;
else
return false;
}
//Function inserts a value/new Node as the first Element of list
public void InsertAtHead(int value)
{
Node newNode = new Node(); //creating a new node
newNode.data = value;
newNode.nextElement = head; //Linking newNode to head's pointer
head = newNode; //head pointing to the start of the list
Console.Write(value + " Inserted ! ");
}
public bool PrintList()
{ // Printing the list
if (IsEmpty())
{
Console.Write("List is Empty!");
return false;
}
Node temp = head; // starting from head node
Console.Write("List : ");
while (temp != null)
{ // traveresing through the List
Console.Write(temp.data + "->");
temp = temp.nextElement; // moving on to the temp's nextElement
}
Console.WriteLine("null "); // printing null at the end
return true;
}
}
Create a function insertAtTail() that takes an integer, adds the integer to the end of a linked list, and returns the updated linked list. The new node will point to null.
Solution and Explanation
Time Complexity:
If the list is empty, the situation is exactly like insertion at the head.
Otherwise, you can simply use a loop to reach the tail of the list, and set your new node as the nextElement of the last node.
Implement the removeDuplicates() function, which takes a linked list and returns the linked list with no duplicate nodes.
Solution and Explanation
Time Complexity:
In this implementation, we check each node against the remaining list to see if a node contains an identical value.
start iterates through the outer loop, while startNext checks for duplicates on line 90 in LinkedList.cs.
Whenever a duplicate is found, it is removed from the list using line 103.
Implement the Union() function that takes two linked lists and returns a single linked list that contains all unique elements from both linked lists.
Solution and Explanation
Time Complexity: where m is the size of the first list, and n is the size of the second list.
Traverse to the tail of the first list, and link it to the first node of the second list on line 125 - 131 in LinkedList.cs. Now, remove duplicates from the combined list.
Below are the implementations of Stacks and Queues available for you to use throughout this section:
Implement a function string [] findBin(int n), which generates binary numbers from 1 to n stored in a String array using a queue.
Solution and Explanation
Time Complexity:
On line 17, 1 is enqueued as a starting point. Then, a number is dequeued from the queue and stored in the result array to generate a binary number sequence.
On lines 22-23, 0 and 1 are appended to it to produce the next numbers, which are then also enqueued to the queue on lines 24-25. The queue takes integer values. Before enqueueing, the solution makes sure to convert the string to an integer.
The size of the queue should be one more than n because you are enqueuing two variations of each number; one is appended with 0, and one with 1.
Use the myStack class to implement the enqueue() function in the NewQueue class. enqueue() takes an integer and returns true after inserting the value into the queue.
Solution and Explanation
Time Complexity:
This approach, uses two stacks. The mainStack stores the queue elements and the tempStack acts as a temporary buffer to provide queue functionality.
Make sure that after every enqueue operation, the newly inserted value is at the bottom of the main stack.
Before insertion, all the other elements are transferred to tempStack and naturally, their order is reversed. The new element is added into the empty mainStack. Finally, all the elements are pushed back into mainStack and tempStack becomes empty.
Implement the minStack class with the function min(), which returns the lowest value in the stack. min() must have a complexity of .
Hint: The element is returned, not popped.
Solution and Explanation
Time Complexity:
The whole implementation relies on the existence of two stacks: minStack and mainStack.
mainStack holds the actual stack with all the elements, whereas minStack is a stack whose top always contains the current minimum value in the stack.
Whenever push is called, mainStack simply inserts the new value at the top.
However, minStack checks the value being pushed. If minStack is empty, this value is pushed into it and becomes the current minimum. If minStack already has elements in it, the value is compared with the top element.
If the value is lower than the top of minStack, it is pushed in and becomes the new minimum. Otherwise, the top remains the same.
Due to all these safeguards put in place, the min function only needs to return the value at the top of minStack.
Below is an implementation of a Graph available for your use throughout this section. The Graph Class consists of two data members:
Implement a Depth First Search algorithm that can find a passed integer within a graph.
Depth First Search: Starts at the graph’s root node and explores as far as possible along each branch before backtracking.
Solution and Explanation
Time Complexity:
The approach is very similar to that of the BFS solution. However, instead of a queue, use a stack since it follows the Last In First Out (LIFO) approach. You will see how that is useful in this situation.
dfsTraversal calls the helper function dfs_helper on every vertex, which is not visited. dfs_helper starts from source and each node is pushed into the stack. Whenever a node is popped, it is marked “visited” in the visited array, and its adjacent nodes are pushed into the stack.
The stack is helpful because it pops out the new adjacent nodes instead of returning the previous nodes that you pushed in.
Implement the int findMotherVertex(Graph g) function, which will take a graph as input and find out a mother vertex in the graph. By definition, the mother vertex is one from which all other vertices are reachable.
Solution and Explanation
Time Complexity:
This solution is based in Kosaraju’s Strongly Connected Component Algorithm.
Initially, we run the Depth First Search on the whole graph in a loop on line 17. The DFS ensures that all the nodes in the graph are visited. If the graph is disconnected, the visited array will still have some vertices, which haven’t been set to true.
The theory is that the last vertex visited in the recursive DFS will be the mother vertex because at the last vertex, all slots in visited would be true (DFS only stops when all nodes are visited); hence, keeping track of this last vertex using lastV.
Then reset the visited array, and run the DFS only on lastV. If it visits all nodes, it is a mother vertex. If not, a mother vertex does not exist.
The only limitation in this algorithm is that it can only detect one mother vertex even if others exist.
Implement the remove_Edge() function that takes a source and destination node and deletes any edge between the two.
Reminder: An edge is the connection between two nodes in a graph.
Solution and Explanation
Time Complexity:
Edge connections are handled by our source linked list. We’ll access this source linked list and call our delete() function from line 127 on the node connections between 2 and3.
delete() essentially searches for a passed value then removes the node by redirecting the pointer.
Practice hundreds of hands-on C# questions, each with in-depth explanations. Educative’s text-based courses are easy to skim and feature live practice environments so you can prepare for your interview in half the time.
Below is an implementation of Binary Search Trees available for your use in this section.
Implement int findMin(Node* rootNode), which takes a Binary Search Tree and returns the lowest value within the tree.
Remember: Nodes in the left subtree of a current node will always be lower, while the right subtree will always be greater.
Solution and Explanation
Time Complexity:
This solution is recursive to increase efficiency. The sorted structure of a BST makes this solution easier because we just have to find the left-most node.
First, we check if the root is null. If it is, we return -1(lines 10-11). Otherwise, we check to see if the left child of the current node is null. If it is, then this root is the leftmost node, and you return the value there (lines 12-13).
If a left node exists, call the findMin() function on it (lines 14-15).
Implement int findHeight(Node* rootNode), which takes a binary search tree and returns its height.
The height of a tree is equal to the number of edges between the root node and the lowest node.
Solution and Explanation
Time Complexity:
The height of your tree equals the greatest height from either the left or right subtree.
Therefore, we must recursively find the heights of the left and right-subtrees. First, we check if the tree is empty, returning -1 if the given node is null. If not, we call the findHeight() function on the left and right-subtrees and return the one that has a greater value plus 1.
Implement the insertNode(string key) function, which takes a word and inserts it into an existing trie.
Remember: Consider the three cases for insertion: no common prefix, common prefix, and existing word.
Solution and Explanation
Time Complexity:
The function takes a string key, indicating a word. NULL keys are not allowed, and all keys are stored in lowercase.
First, we iterate over the characters in the key. For each character, we generate an index using getIndex().
The next step is to check the child of currentNode at that particular index. If it is NULL, then we create a new TrieNode at that index.
In the end, we mark the last node as a leaf since the word has ended.
Implement the totalWords() function, which will take a trie and return the total number of words in the trie.
Solution and Explanation
Time Complexity:
Starting from the root, we visit each branch recursively. Whenever a node is found with isEndWord set to true, the result variable is incremented by 1.
At the end, we return result to state the total number of words.
A max-heap is a complete binary tree in which the value of each internal node is greater than or equal to the values in the children of that node.
Your max-heap must include insert() and delete() functions but can also contain any additional functionalities.
Solution and Explanation
Time Complexity:
Notice that you start from the bottom of the heap, i.e., i = size-1 (line 78). If the height of the heap is h, then the levels go from “0” (at the root node) to “h” at the deepest leaf nodes. By calling maxHeapify() at the leaf nodes, you will have a constant time operation.
At level h - 1h−1, for every node, maxHeapify() makes one comparison and swap operation at most. At level h−2, , it makes two at most comparisons and swaps for every node. This continues until the root node, where it makes h comparisons at most, swaps operations.
Implement a function findKSmallest(int[] arr, int size, int k) that takes an unsorted integer array as input and returns the “k” smallest elements in the array by using a heap.
You can use the following minHeap implementation as a starting point:
Solution and Explanation
Time Complexity:
Here create a heap and then call the buildHeap (line 12) function to create a minimum heap from the given array. To find the k smallest elements in an array:
You get the minimum value from the heap.
Save the result to the vector output.
Remove the minimum value from the heap.
Repeat the same steps k times (provided k < size).
Implement the isSubset(int[] arr1, int[] arr2, int size1, int size2) function, which will take two arrays and their sizes as input and check if one array is the subset of the other.
The arrays will not contain duplicate values.
Solution and Explanation
Time Complexity: where m is the number of elements in arr1 and n is the number of elements in arr2.
C# built-in HashSet makes this solution much simpler. First, we iterate over arr1 on line 16. If the value at the current index is not present in the HashSet, we insert that value in the HashSet on lines 20-21. Then, we iterate through arr2 to see whether their elements are present in HashSet.
If all the elements of arr2 are present in HashSet, then your function will return true lines 25-32.
Implement the string findPair(int[] arr, int size) function, which will take an array and find two pairs, [a, b] and [c, d], in an array such that:
Remember: You only have to find any two pairs in the array, not all pairs.
Solution and Explanation
Time Complexity:
This solution uses C#'s built-in Dictionary class for simplicity.
On lines 23-33, each element in arr is summed with all other elements. The sum becomes the key in the hMap. At every key, store the integer pair whose sum generated that key.
Whenever a sum is found such that its key in the hMap already has an integer pair stored in it, you can conclude that this sum can be made by two different pairs in the array. These two pairs are then returned in the result array on lines 36-46.
k elements in a queueGreat work on those questions! The best way to prepare for your next interview is to keep getting hands-on practice with common data structure questions like these.
To help your prepare for your interview right, Educative has created the course Data Structures for Coding Interviews in C#. This course lets you hone your data structure skills with hundreds of practice questions, each with live coding environments and in-depth explanations.
By the end of the course, you’ll be an expert on identifying and solving all the most-asked interview question patterns.
Happy learning!
