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 40 of the top data structure questions you should practice before your next interview.
Here’s what we’ll cover today:
- Complexity Measures Questions
- C# Arrays
- C# Linked Lists
- C# Stacks and Queues
- C# Trees and Tries
- C# Heaps and Hashing
- 18 more questions for C# coding interview
- What to learn next
Ace your C# interview the first time
Practice hundreds of common interview questions with hands-on code environments and instant feedback.
Data Structures for Coding Interviews in C#
Complexity Measures Questions
1. Big O complexity: Nested Addition
Find the Big O complexity of the following code snippet.
using System;
namespace Chapter_1
{
class Challenge_1
{
static void Main(string[] args)
{
int n = 10;
int sum = 0;
float pie = 3.14F;
for (int i = 0; i < n; i += 3)
{
Console.WriteLine(pie);
for (int j = 0; j < n; j += 2)
{
sum += 1;
Console.WriteLine(sum);
}
}
}
}
}
Solution and Explanation
O(n^2)
On line 11 in the outer loop, int i=0; runs once.
i<n; gets executed (n/3)+1 times, and i+=3 executed n/3
times.
In the inner loop, int j=0; gets executed (n/3) times in total. j<n; executes (n/3) * ((n/2) +1) times, and j+=2 gets executed (n/3) * (n/2) times.
2. Big O complexity: Nested Multiplication
Find the Big O complexity of the following code snippet.
using System;
namespace Chapter_1
{
class Challenge_6
{
static void Main(string[] args)
{
int n = 10;
int sum = 0;
float pie = 3.14f;
for (int i = 0; i < n; i++)
{
int j = 1;
Console.WriteLine(pie);
while (j < i)
{
sum += 1;
j *= 2;
}
}
Console.WriteLine(sum);
return;
}
}
}
O(n)
A loop statement that multiplies/divides the loop variable by a constant takes logk n time because the loop runs that many times. In the outer loop, the loop variable is multiplied by 2 in each iteration. Therefore, the outer loop runs O(log2 n) times.
The inner loop runs counter times and not n times. The value of counter is 1 in the first iteration, then 2, then 4, then 8, and so on, until 2^k such that (2^k) < n. When you sum the counter values for all the iterations of the outer loop, the inner loop runs:
1+2+4+8+ ...+(2^k) times.
You will use a geometric series to figure out this value. To make this calculation simpler, you must assume that 2^k = n.
(2^0)+(2^1)+(2^2)...+(2^k) = 2^(k+1)-1
(2^k)(2^1) - 1
Substituting n for 2^k you get:
= 2n-1
It appears that the inner loop runs a total of 2n-1 times (considering all the iterations of the outer loop), but remember that you assumed n = 2^k when n>(2^k). In actuality, the inner loop runs less than 2n-1 times, but you can consider this to be the upper bound.
3. Big O with nested multiplication (advanced)
Find the Big O complexity of the following code snippet:
using System;
namespace Chapter_1
{
class Challenge_7
{
static void Main(string[] args)
{
int n = 10; // you can change the value of n
int sum = 0;
int j = 1;
float pie = 3.14f;
for (int i = 0; i < n; i++)
{
Console.WriteLine(pie);
while (j < i)
{
sum += 1;
j *= 2;
}
}
Console.WriteLine(sum );
}
}
}
O(n)
The outer loop in the main function has n iterations as it iterates on i from 0 to n-1. If the condition j < i is true, the inner loop is entered. However, j is doubled immediately. Note that j is not reset to 1 in the code, since the j is immediately doubled.
Therefore, the inner while loop will run O(log2 n) times for all the iterations of the outer loop.
C# Arrays
4. Remove even integers from an array
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
using System;
namespace chapter_2
{
class Solution
{
static int [] removeEven(int[]Arr, int size)
{
int m = 0;
for (int i = 0; i < size; i++)
{
if (Arr[i] % 2 != 0) // if odd number found
{
Arr[m] = Arr[i]; //inserting odd values in the array
++m;
}
}
int[] temp = new int[m];
for (int i = 0; i < m; i++)
temp[i] = Arr[i];
Arr = temp;
return Arr; // returning the array after removing the odd numbers
}
//Remove Event Integers from an Array:
static void Main(string[] args)
{
int[] arr = null; // declaring array
arr = new int[10]; // memory allocation
Console.Write("Before remove even: ");
for (int i = 0; i < 10; i++)
{
arr[i] = i; // assigning values
Console.Write(arr[i] + " ");
}
Console.WriteLine("");
arr = removeEven(arr, 10); // calling removeEven
Console.Write("After remove even: ");
for (int i = 0; i < 5; i++)
{
Console.Write( arr[i] + " "); // prinitng array
}
Console.WriteLine("");
return ;
}
}
}
Time Complexity: O(n)
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.
5. Find the minimum value in an array
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
using System;
namespace chapter_2
{
class Solution
{
// Find Minimum Value in an Array
static int findMinimum(int []arr, int size)
{
int minimum = arr[0];
//At every index compare its value with the minimum and if it is less
//then make that index value the new minimum value”
for (int i = 0; i < size; i++)
{
if (arr[i] < minimum)
{
minimum = arr[i];
}
}
return minimum;
}
static void Main(string[] args)
{
int size = 4;
int []arr = { 9, 2, 3, 6 };
Console.Write("Array : ");
for (int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.WriteLine("");
int min = findMinimum(arr, size);
Console.WriteLine("Minimum in the Array: " + min );
return ;
}
}
}
Time Complexity: O(n)
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 minimumto that number.
By the end of the array, the number stored in minimum will be the smallest integer in the whole array.
6. Maximum subarray sum
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
using System;
namespace chapter_2
{
class Solution
{
//Maximum Sum Subarray
static int maxSumArr(int []arr, int arrSize)
{
if (arrSize < 1)
{
return 0;
}
int currMax = arr[0];
int globalMax = arr[0];
for (int i = 1; i < arrSize; i++)
{
if (currMax < 0)
{
currMax = arr[i];
}
else
{
currMax += arr[i];
}
if (globalMax < currMax)
{
globalMax = currMax;
}
}
return globalMax;
}
static void Main(string[] args)
{
int []arr = { -4, 2, -5, 1, 2, 3, 6, -5, 1 };
int arrSize = arr.Length;
int maxSum = maxSumArr(arr, arrSize);
Console.WriteLine("Maximum contiguous sum is " + maxSum);
return;
}
}
}
Time Complexity: O(n)
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.
C# Linked Lists
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;
}
}
7. Insertion at Tail
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
//main.cs
using System;
namespace chapter_3
{
class Solution
{
static void Main(string[] args)
{
LinkedList list = new LinkedList();
var rand = new Random();
//srand(time(NULL)); // seed to produce random numbers everytime
int num = 0;
for (int i = 1; i < 6; i++)
{
num = rand.Next(10); //generating random numbers in range 1 to 10
list.InsertAtTail(num); // inserting value at the tail of the list
list.PrintList();
}
}
}
}
//LinkedList.cs
using System;
namespace chapter_3
{
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 Node GetHead()
{
return head;
}
bool IsEmpty()
{
if (head == null) //Check whether the head points to null
return true;
else
return false;
}
public bool PrintList()
{
if (IsEmpty())
{
Console.Write("List is Empty!");
return false;
}
Node temp = head;
Console.Write("List : ");
while (temp != null)
{
Console.Write(temp.data + "->");
temp = temp.nextElement;
}
Console.WriteLine("null ");
return true;
}
public void InsertAtHead(int value)
{
Node newNode = new Node();
newNode.data = value;
newNode.nextElement = head; //Linking newNode to head's nextNode
head = newNode;
}
public string Elements()
{
string elementsList = "";
Node start = head;
while (start != null)
{
elementsList += start.data.ToString();
elementsList += "->";
start = start.nextElement;
}
elementsList += "null";
return elementsList;
}
public void InsertAtTail(int value)
{
if (IsEmpty())
{ // inserting first element in list
InsertAtHead(value); // head will point to first element of the list
}
else
{
Node newNode = new Node(); // creating new node
Node last = head; // last pointing at the head of the list
while (last.nextElement != null)
{ // traversing through the list
last = last.nextElement;
}
newNode.data = value;
Console.Write(value + " Inserted! ");
newNode.nextElement = null; // point last's nextElement to nullptr
last.nextElement = newNode; // adding the newNode at the end of the list
}
}
}
}
Time Complexity: O(n)
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.
8. Remove Duplicates from a Linked List
Implement the removeDuplicates() function, which takes a linked list and returns the linked list with no duplicate nodes.
Solution and Explanation
//main.cs
using System;
namespace chapter_3
{
class Challenge_8
{
static void Main(string[] args)
{
LinkedList list = new LinkedList();
for (int i = 1; i < 4; i++)
{
list.InsertAtHead(i); // inserting value in the list
list.PrintList();
}
list.InsertAtHead(2);
list.PrintList(); //after adding more elements
list.InsertAtHead(4);
list.PrintList(); //after adding more elements
list.InsertAtHead(1);
list.PrintList(); //after adding more elements
string removeDuplicate = list.RemoveDuplicates(); // calling removeDuplicates function
Console.WriteLine("List after deleting duplicates from list :" + removeDuplicate);
return;
}
}
}
// LinkedList.cs
using System;
namespace chapter_3
{
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 Node GetHead()
{
return head;
}
bool IsEmpty()
{
if (head == null) //Check whether the head points to null
return true;
else
return false;
}
public bool PrintList()
{
if (IsEmpty())
{
Console.Write("List is Empty!");
return false;
}
Node temp = head;
Console.Write("List : ");
while (temp != null)
{
Console.Write(temp.data + "->");
temp = temp.nextElement;
}
Console.WriteLine("null ");
return true;
}
public void InsertAtHead(int value)
{
Node newNode = new Node();
newNode.data = value;
newNode.nextElement = head; //Linking newNode to head's nextNode
head = newNode;
Console.Write(value + " Inserted!");
}
public string Elements()
{ // this function will return all values of linked List
string elementsList = "";
Node start = head;
Node check = head;
elementsList += start.data.ToString();
elementsList += "->";
start = start.nextElement;
while (start != null && start.data != check.data)
{
elementsList += start.data.ToString();
elementsList += "->";
start = start.nextElement;
}
if (start == null)
return elementsList + "null";
elementsList += check.data.ToString();
return elementsList;
}
public string RemoveDuplicates()
{
Node start, startNext = null;
start = head;
/* Pick elements one by one */
while ((start != null) && (start.nextElement != null))
{
startNext = start;
/* Compare the picked element with rest
of the elements */
while (startNext.nextElement != null)
{
/* If duplicate then delete it */
if (start.data == startNext.nextElement.data)
{
// skipping elements from the list to be deleted
startNext.nextElement = startNext.nextElement.nextElement;
}
else
startNext = startNext.nextElement; // pointing to next of startNext
}
start = start.nextElement;
}
return Elements();
}
}
}
Time Complexity: O(n^2)
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.
9. Join two linked lists
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
// main.cs
using System;
namespace chapter_3
{
class Challenge_9
{
static void Main(string[] args)
{
LinkedList list1 = new LinkedList(); // creating lists
LinkedList list = new LinkedList();
var rand = new Random();
int rand_num = rand.Next(5);
Console.WriteLine("List 1 ");
for (int i = 1; i < 5; i++)
{
rand_num = rand.Next(5);
list.InsertAtHead(rand_num); // inserting value in the list
}
list.PrintList();
Console.WriteLine("List 2 ");
for (int i = 4; i < 8; i++)
{
rand_num = rand.Next(5);
list1.InsertAtHead(rand_num); // inserting value in the list
}
list1.PrintList();
string check = list.Union(list, list1); // calling union function
Console.WriteLine("Union List : " + check);
return;
}
}
}
// LinkedList.cs
using System;
namespace chapter_3
{
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 Node GetHead()
{
return head;
}
bool IsEmpty()
{
if (head == null) //Check whether the head points to null
return true;
else
return false;
}
public bool PrintList()
{
if (IsEmpty())
{
Console.Write("List is Empty!");
return false;
}
Node temp = head;
Console.Write("List : ");
while (temp != null)
{
Console.Write(temp.data + "->");
temp = temp.nextElement;
}
Console.WriteLine("null ");
return true;
}
public void InsertAtHead(int value)
{
Node newNode = new Node();
newNode.data = value;
newNode.nextElement = head; //Linking newNode to head's nextNode
head = newNode;
}
public string Elements()
{ // this function will return all values of linked List
string elementsList = "";
Node start = head;
Node check = head;
elementsList += start.data.ToString();
elementsList += "->";
start = start.nextElement;
while (start != null && start.data != check.data)
{
elementsList += start.data.ToString();
elementsList += "->";
start = start.nextElement;
}
if (start == null)
return elementsList + "null";
elementsList += check.data.ToString();
return elementsList;
}
public string RemoveDuplicates()
{
Node start, startNext = null;
start = head;
/* Pick elements one by one */
while ((start != null) && (start.nextElement != null))
{
startNext = start;
/* Compare the picked element with rest
of the elements */
while (startNext.nextElement != null)
{
/* If duplicate then delete it */
if (start.data == startNext.nextElement.data)
{
// skipping elements from the list to be deleted
startNext.nextElement = startNext.nextElement.nextElement;
}
else
startNext = startNext.nextElement; // pointing to next of startNext
}
start = start.nextElement;
}
return Elements();
}
public string Union(LinkedList list1, LinkedList list2)
{
//Return other List if one of them is empty
if (list1.IsEmpty())
return list2.Elements();
else if (list2.IsEmpty())
return list1.Elements();
Node start = list1.head; // starting from head of list 1
//Traverse first list till the last element
while (start.nextElement != null)
{
start = start.nextElement;
}
//Link last element of first list to the first element of second list
start.nextElement = list2.head; // appendinf list2 with list 1
return list1.RemoveDuplicates(); // removing duplicates from list and return list
}
}
}
Time Complexity: O(m + n)^2 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.
C# Stacks and Queues
Below are the implementations of Stacks and Queues available for you to use throughout this section:
using System;
using System.Diagnostics;
class myStack
{
int[] stackArr;
int capacity;
int numElements;
public myStack(int size)
{
capacity = size;
stackArr = new int[size];
Debug.Assert(stackArr != null);
numElements = 0;
}
public bool isEmpty()
{
return (numElements == 0);
}
public int getTop()
{
return (numElements == 0 ? -1 : stackArr[numElements - 1]);
}
public bool push(int value)
{
if (numElements < capacity)
{
stackArr[numElements] = value;
numElements++;
return true;
}
else
{
Console.WriteLine("Stack Full.");
return false;
}
}
public int pop()
{
if (numElements == 0)
{
Console.WriteLine("Stack Empty");
return -1;
}
else
{
numElements--;
return stackArr[numElements];
}
}
public int getSize()
{
return numElements;
}
public void showStack()
{
int i = 0;
while (i < numElements)
{
Console.Write("\t" + stackArr[numElements - 1 - i]);
i++;
}
Console.WriteLine("");
}
}
using System;
using System.Diagnostics;
namespace chapter_4
{
class myQueue
{
int[] queueArr;
int capacity;
int numElements;
int front;
int back;
public myQueue(int size)
{
capacity = size;
queueArr = new int[size];
Debug.Assert(queueArr != null);
numElements = 0;
front = 0;
back = -1;
}
public bool isEmpty()
{
return (numElements == 0);
}
public int getFront()
{
if (isEmpty())
{
Console.WriteLine("Queue Empty");
return -1;
}
else
return queueArr[front];
}
public void enqueue(int value)
{
if (numElements == capacity)
{
Console.WriteLine("Queue Full");
return;
}
if (back == capacity - 1)
back = -1;
queueArr[++back] = value;
numElements++;
}
public int dequeue()
{
if (isEmpty())
{
Console.WriteLine("Queue Empty");
return -1;
}
int tmp = queueArr[front++];
if (front == capacity)
front = 0;
numElements--;
return tmp;
}
public int getSize()
{
return numElements;
}
public void showqueue()
{
int i = front;
int count = 0;
while (count != numElements)
{
Console.Write("\t" + queueArr[i % capacity]);
i++;
count++;
}
Console.WriteLine("");
}
}
}
10. Generate binary numbers from 1 to N
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
using System;
using System.Collections;
namespace chapter_4
{
class Challenge_1
{
//Start with Enqueuing 1.
//Dequeue a number from queue and append 0 to it and enqueue it back to queue.
//Perform step 2 but with appending 1 to the original number and enqueue back to queue.
//Queue takes integer values so before enqueueing it make sure to convert string to integer.
//Size of Queue should be 1 more than number because for a single number we're enqueuing two
//variations of it , one with appended 0 while other with 1 being appended.
static string [] findBin(int n)
{
string [] result = new string[n];
Queue queue = new Queue();
queue.Enqueue(1);
string s1, s2;
for (int i = 0; i < n; i++)
{
result[i] = queue.Dequeue().ToString();
s1 = result[i] + "0";
s2 = result[i] + "1";
queue.Enqueue(Convert.ToInt32(s1));
queue.Enqueue(Convert.ToInt32(s2));
}
return result;
}
static void Main(string[] args)
{
var output = findBin(4);
for (int i = 0; i < 4; i++)
Console.Write(output[i] + " ");
return;
}
}
}
Time Complexity: O(n)
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.
11. Implement a queue using stacks
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
using System;
using System.Collections.Generic;
namespace chapter_4
{
//Create Stack => myStack stack = new myStack(5);
//where 5 is size of stack
//Push Function => stack.push(int);
//Pop Function => stack.pop();
//TopFunction => stack.getTop();
//Helper Functions => stack.isEmpty();
class newQueue
{
Stack <int> mainStack;
Stack <int> tempStack;
public newQueue()
{
//Can use size from argument to create stack
mainStack = new Stack<int> ();
tempStack = new Stack<int> ();
}
void EnQueue(int value)
{
//Traverse elements from mainStack to tempStack
//Push given value to mainStack
//Traverse back the elements from tempStack to mainStack
while (mainStack.Count != 0)
{
tempStack.Push(mainStack.Pop());
}
mainStack.Push(value);
while (tempStack.Count != 0)
{
mainStack.Push(tempStack.Pop());
}
}
int DeQueue()
{
//If mainStack is empty then we have no elements.
//else return top element of mainStack as we always put oldest entered
//element at the top of mainStack
if (mainStack.Count == 0)
return -1;
else
return mainStack.Pop();
}
static void Main(string[] args)
{
newQueue queue = new newQueue();
queue.EnQueue(1);
queue.EnQueue(2);
queue.EnQueue(3);
queue.EnQueue(4);
queue.EnQueue(5);
Console.WriteLine( queue.DeQueue());
Console.WriteLine( queue.DeQueue());
Console.WriteLine( queue.DeQueue());
Console.WriteLine(queue.DeQueue());
Console.WriteLine( queue.DeQueue());
Console.WriteLine(queue.DeQueue());
return ;
}
};
}
Time Complexity: O(n)
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.
12. Find the lowest value in a stack
Implement the minStack class with the function min(), which returns the lowest value in the stack. min() must have a complexity of $O(1)$.
Hint: The element is returned, not popped.
Solution and Explanation
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace chapter_4
{
class newStack
{
//We will use two stacks mainStack to hold origional values
//and minStack to hold minimum values. Top of minStack will always
//be the minimum value from mainStack
Stack <int> mainStack;
Stack<int> minStack;
public newStack(int size)
{
mainStack = new Stack<int>(size);
minStack = new Stack<int>(size);
}
//Removes and returns value from newStack
//1. Pop element from minStack to make it sync with mainStack.
//2. Pop element from mainStack and return that value.
int pop()
{
minStack.Pop();
return mainStack.Pop();
}
//Pushes values into newStack
//1. Push value in mainStack and check value with the top value of minStack
//2. If value is greater than top, then push top in minStack
//else push value in minStack.
void push(int value)
{
mainStack.Push(value);
if ( (minStack.Count != 0) && (value > minStack.Peek()) )
{
minStack.Push(minStack.Peek());
}
else
minStack.Push(value);
}
//Returns minimum value from newStack in O(1) Time
int min()
{
return minStack.Peek();
}
static void Main(string[] args)
{
newStack stack = new newStack(6);
stack.push(5);
stack.push(2);
stack.push(4);
stack.push(1);
stack.push(3);
stack.push(9);
Console.WriteLine(stack.min());
stack.pop();
stack.pop();
stack.pop();
Console.WriteLine(stack.min());
return ;
}
}
}
Time Complexity: O(1)
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.
Keep practicing C#.
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.
Data Structures for Coding Interviews in C#
C# Trees and Tries
Below is an implementation of Binary Search Trees available for your use in this section.
// main.cs
using System;
namespace chapter_6
{
class Solution
{
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree(13);
Console.WriteLine("The root value of the Binary Search Tree is " + BST.getRoot().value);
return;
}
}
}
namespace chapter_6
{
// Node class with a value, left child node, and the rithe child node
class Node
{
public int value;
public Node leftChild;
public Node rightChild;
public Node()
{
value = 0;
leftChild = null;
rightChild = null;
}
public Node(int val)
{
value = val;
leftChild = null;
rightChild = null;
}
};
//BinarySearchTree class that contains the root node.
class BinarySearchTree
{
Node root;
public BinarySearchTree(int rootValue)
{
root = new Node(rootValue);
}
public BinarySearchTree()
{
root = null;
}
public Node getRoot()
{
return root;
}
};
}
13. Find the lowest value in a Binary Search Tree
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
// main.cs
using System;
namespace chapter_6
{
class Solution
{
static public int findMin(Node rootNode)
{
// Traverse (in order) towards left till you reach leaf node,
//and then return leaf node's value
if (rootNode == null)
return -1;
else if (rootNode.leftChild == null)
return rootNode.value;
else
return findMin(rootNode.leftChild);
}
static void Main(string[] args)
{
BinarySearchTree bsT = new BinarySearchTree(6);
bsT.insertBST(3);
bsT.insertBST(8);
bsT.insertBST(12);
bsT.insertBST(10);
bsT.insertBST(14);
Console.WriteLine(findMin(bsT.getRoot()));
return;
}
}
}
// BTS.cs
using System;
namespace chapter_6
{
class Node
{
public int value;
public Node leftChild;
public Node rightChild;
public Node()
{
value = 0;
leftChild = null;
rightChild = null;
}
public Node(int val)
{
value = val;
leftChild = null;
rightChild = null;
}
}
class BinarySearchTree
{
Node root;
public BinarySearchTree(int rootValue)
{
root = new Node(rootValue);
}
public BinarySearchTree()
{
root = null;
}
public Node getRoot()
{
return root;
}
public Node insert(Node currentNode, int val)
{
if (currentNode == null)
{
return new Node(val);
}
else if (currentNode.value > val)
{
currentNode.leftChild = insert(currentNode.leftChild, val);
}
else
{
currentNode.rightChild = insert(currentNode.rightChild, val);
}
return currentNode;
}
public void insertBST(int value)
{
if (getRoot() == null)
{
root = new Node(value);
return;
}
insert(this.getRoot(), value);
}
public void inOrderPrint(Node currentNode)
{
if (currentNode != null)
{
inOrderPrint(currentNode.leftChild);
Console.WriteLine(currentNode.value);
inOrderPrint(currentNode.rightChild);
}
}
Node searchBST(int value)
{
//let's start with the root
Node currentNode = root;
while ((currentNode != null) && (currentNode.value != value))
{
//the loop will run until the currentNode IS NOT null
//and until we get to our value
if (value < currentNode.value)
{
//traverse to the left subtree
currentNode = currentNode.leftChild;
}
else
{ //traverse to the right subtree
currentNode = currentNode.rightChild;
}
}
//after the loop, we'll have either the searched value
//or null in case the value was not found
return currentNode;
}
public Node search(Node currentNode, int value)
{
if (currentNode == null)
return null;
else if (currentNode.value == value)
return currentNode;
else if (currentNode.value > value)
return search(currentNode.leftChild, value);
else
return search(currentNode.rightChild, value);
}
public bool deleteBST(int value)
{
return Delete(root, value);
}
public bool Delete(Node currentNode, int value)
{
if (root == null)
{
return false;
}
Node parent = root; //To Store parent of currentNode
while ((currentNode != null) && (currentNode.value != value))
{
parent = currentNode;
if (currentNode.value > value)
currentNode = currentNode.leftChild;
else
currentNode = currentNode.rightChild;
}
if (currentNode == null)
return false;
else if ((currentNode.leftChild == null) && (currentNode.rightChild == null))
{
//1. Node is Leaf Node
//if that leaf node is the root (a tree with just root)
if (root.value == currentNode.value)
{
root = null;
return true;
}
else if (currentNode.value < parent.value)
{
parent.leftChild = null;
return true;
}
else
{
parent.rightChild = null;
return true;
}
}
else if (currentNode.rightChild == null)
{
if (root.value == currentNode.value)
{
root = currentNode.leftChild;
return true;
}
else if (currentNode.value < parent.value)
{
parent.leftChild = currentNode.leftChild;
return true;
}
else
{
parent.rightChild = currentNode.leftChild;
return true;
}
}
else if (currentNode.leftChild == null)
{
if (root.value == currentNode.value)
{
root = currentNode.rightChild;
return true;
}
else if (currentNode.value < parent.value)
{
parent.leftChild = currentNode.rightChild;
return true;
}
else
{
parent.rightChild = currentNode.rightChild;
return true;
}
}
else
{
//Find Least Value Node in right-subtree of current Node
Node leastNode = findLeastNode(currentNode.rightChild);
//Set CurrentNode's Data to the least value in its right-subtree
int tmp = leastNode.value;
Delete(root, tmp);
currentNode.value = leastNode.value;
//Delete the leafNode which had the least value
return true;
}
}
//Helper function to find least value node in right-subtree of currentNode
public Node findLeastNode(Node currentNode)
{
Node temp = currentNode;
while (temp.leftChild != null)
{
temp = temp.leftChild;
}
return temp;
}
public void preOrderPrint(Node currentNode)
{
if (currentNode != null)
{
Console.WriteLine(currentNode.value);
preOrderPrint(currentNode.leftChild);
preOrderPrint(currentNode.rightChild);
}
}
}
}
Time Complexity: O(h)
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).
14. Find the height of a BST
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
using System;
namespace chapter_6
{
class Solution
{
static int findHeight(Node rootNode)
{
if (rootNode == null)
return -1;
else
{
// Find Height of left subtree and then right subtree
// Return greater height value of left or right subtree (plus 1)
int leftHeight = findHeight(rootNode.leftChild);
int rightHeight = findHeight(rootNode.rightChild);
if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
}
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree(6);
BST.insertBST(4);
BST.insertBST(9);
BST.insertBST(5);
BST.insertBST(2);
BST.insertBST(8);
BST.insertBST(12);
Console.WriteLine(findHeight(BST.getRoot()));
}
}
}
// BTS.cs
using System;
namespace chapter_6
{
class Node
{
public int value;
public Node leftChild;
public Node rightChild;
public Node()
{
value = 0;
leftChild = null;
rightChild = null;
}
public Node(int val)
{
value = val;
leftChild = null;
rightChild = null;
}
}
class BinarySearchTree
{
Node root;
public BinarySearchTree(int rootValue)
{
root = new Node(rootValue);
}
public BinarySearchTree()
{
root = null;
}
public Node getRoot()
{
return root;
}
public Node insert(Node currentNode, int val)
{
if (currentNode == null)
{
return new Node(val);
}
else if (currentNode.value > val)
{
currentNode.leftChild = insert(currentNode.leftChild, val);
}
else
{
currentNode.rightChild = insert(currentNode.rightChild, val);
}
return currentNode;
}
public void insertBST(int value)
{
if (getRoot() == null)
{
root = new Node(value);
return;
}
insert(this.getRoot(), value);
}
public void inOrderPrint(Node currentNode)
{
if (currentNode != null)
{
inOrderPrint(currentNode.leftChild);
Console.WriteLine(currentNode.value);
inOrderPrint(currentNode.rightChild);
}
}
Node searchBST(int value)
{
//let's start with the root
Node currentNode = root;
while ((currentNode != null) && (currentNode.value != value))
{
//the loop will run until the currentNode IS NOT null
//and until we get to our value
if (value < currentNode.value)
{
//traverse to the left subtree
currentNode = currentNode.leftChild;
}
else
{ //traverse to the right subtree
currentNode = currentNode.rightChild;
}
}
//after the loop, we'll have either the searched value
//or null in case the value was not found
return currentNode;
}
public Node search(Node currentNode, int value)
{
if (currentNode == null)
return null;
else if (currentNode.value == value)
return currentNode;
else if (currentNode.value > value)
return search(currentNode.leftChild, value);
else
return search(currentNode.rightChild, value);
}
public bool deleteBST(int value)
{
return Delete(root, value);
}
public bool Delete(Node currentNode, int value)
{
if (root == null)
{
return false;
}
Node parent = root; //To Store parent of currentNode
while ((currentNode != null) && (currentNode.value != value))
{
parent = currentNode;
if (currentNode.value > value)
currentNode = currentNode.leftChild;
else
currentNode = currentNode.rightChild;
}
if (currentNode == null)
return false;
else if ((currentNode.leftChild == null) && (currentNode.rightChild == null))
{
//1. Node is Leaf Node
//if that leaf node is the root (a tree with just root)
if (root.value == currentNode.value)
{
root = null;
return true;
}
else if (currentNode.value < parent.value)
{
parent.leftChild = null;
return true;
}
else
{
parent.rightChild = null;
return true;
}
}
else if (currentNode.rightChild == null)
{
if (root.value == currentNode.value)
{
root = currentNode.leftChild;
return true;
}
else if (currentNode.value < parent.value)
{
parent.leftChild = currentNode.leftChild;
return true;
}
else
{
parent.rightChild = currentNode.leftChild;
return true;
}
}
else if (currentNode.leftChild == null)
{
if (root.value == currentNode.value)
{
root = currentNode.rightChild;
return true;
}
else if (currentNode.value < parent.value)
{
parent.leftChild = currentNode.rightChild;
return true;
}
else
{
parent.rightChild = currentNode.rightChild;
return true;
}
}
else
{
//Find Least Value Node in right-subtree of current Node
Node leastNode = findLeastNode(currentNode.rightChild);
//Set CurrentNode's Data to the least value in its right-subtree
int tmp = leastNode.value;
Delete(root, tmp);
currentNode.value = leastNode.value;
//Delete the leafNode which had the least value
return true;
}
}
//Helper function to find least value node in right-subtree of currentNode
public Node findLeastNode(Node currentNode)
{
Node temp = currentNode;
while (temp.leftChild != null)
{
temp = temp.leftChild;
}
return temp;
}
public void preOrderPrint(Node currentNode)
{
if (currentNode != null)
{
Console.WriteLine(currentNode.value);
preOrderPrint(currentNode.leftChild);
preOrderPrint(currentNode.rightChild);
}
}
int findMin(Node rootNode)
{
// So keep traversing (in order) towards left till you reach leaf node,
//and then return leaf node's value
if (rootNode == null)
return -1;
else if (rootNode.leftChild == null)
return rootNode.value;
else
return findMin(rootNode.leftChild);
}
}
}
Time Complexity: O(n)
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.
15. 2-3 Trees vs. BST
What is the difference between 2-3 Trees and Binary Search Trees?
2-3 tree is a balanced and ordered search tree, which provides a very efficient storage mechanism to guarantee fast operations.
In a 2-tree, each node only has 2 children maximum. With a 3-tree, each node can have a maximum of 3 children. Children are ordered with the lowest value to the left and the highest value to the right.
Unlike BST, it always remains balanced regardless of insertions or deletions. This is to make sure the height doesn’t increase up to a certain level as the time complexity of all the operations is mainly dependent upon it.
Ideally, you want the height to be in logarithmic terms because as the tree grows larger, it will require more time to perform operations.
16. Insertion in a Trie
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
// main.cs
using System;
namespace chapter_7
{
class Program
{
static void Main(string[] args)
{
string [] keys = { "the", "a", "there", "answer", "any", "by", "bye", "their", "abc" };
Trie t = new Trie();
Console.WriteLine("Keys to insert:");
for (int i = 0; i < 9; i++)
{
Console.Write(keys[i] + ", ");
}
Console.WriteLine("");
// Construct trie
for (int i = 0; i < 9; i++)
{
t.insertNode(keys[i]);
Console.WriteLine("\"" + keys[i] + "\"" + "Inserted.");
}
return;
}
}
}
// Trie.cs
using System;
namespace chapter_7
{
class TrieNode
{
const int ALPHABET_SIZE = 26;
public TrieNode[] children = new TrieNode[ALPHABET_SIZE];
public bool isEndWord;
public TrieNode()
{
this.isEndWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
{
this.children[i] = null; ;
}
}
//Function to unMark the currentNode as Leaf
public void markAsLeaf()
{
this.isEndWord = true;
}
//Function to unMark the currentNode as Leaf
public void unMarkAsLeaf()
{
this.isEndWord = false;
}
}
class Trie
{
TrieNode root;
public Trie()
{
root = new TrieNode();
}
//Function to get the index of a character 't'
public int getIndex(char t)
{
return t - 'a';
}
//Function to insert a key,value pair in the Trie
public void insertNode(string key)
{
//Empty string is not allowed
if (key == string.Empty)
return;
//using transform() function and ::tolower in STL to convert 'key' to lowercase
//transform(key.begin(), key.end(), key.begin(), ::tolower);
key = key.ToLower();
TrieNode currentNode = root;
int index = 0;
//Iterate the trie with the given character index,
//If the index points to NULL
//simply create a TrieNode and go down a level
for (int level = 0; level < key.Length; level++)
{
index = getIndex(key[level]);
if (currentNode.children[index] == null)
{
currentNode.children[index] = new TrieNode();
Console.WriteLine( key[level] + " inserted" );
}
currentNode = currentNode.children[index];
}
//Mark the end character as leaf node
currentNode.markAsLeaf();
Console.WriteLine( "'" + key + "' inserted" );
}
//Function to search given key in Trie
public bool searchNode(string key)
{
return false;
}
//Function to delete given key from Trie
public bool deleteNode(string key)
{
return false;
}
}
}
Time Complexity: O(n)
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.
17. Total words in a Trie
Implement the totalWords() function, which will take a trie and return the total number of words in the trie.
Solution and Explanation
// main.cs
using System;
namespace chapter_7
{
class Program
{
static int totalWords(TrieNode root)
{
int result = 0;
// Leaf denotes end of a word
if (root.isEndWord)
result++;
for (int i = 0; i < 26; i++)
if (root.children[i] != null)
result += totalWords(root.children[i]);
return result;
}
static void Main(string[] args)
{
string [] keys = { "the", "a", "there", "answer", "any", "by", "bye", "their", "abc" };
Trie t = new Trie();
// Construct trie
for (int i = 0; i < 9; i++)
{
t.insertNode(keys[i]);
}
Console.WriteLine( totalWords(t.getRoot()));
return;
}
}
}
// Trie.cs
using System;
namespace chapter_7
{
class TrieNode
{
const int ALPHABET_SIZE = 26;
public TrieNode[] children = new TrieNode[ALPHABET_SIZE];
public bool isEndWord;
public TrieNode()
{
this.isEndWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
{
this.children[i] = null; ;
}
}
//Function to unMark the currentNode as Leaf
public void markAsLeaf()
{
this.isEndWord = true;
}
//Function to unMark the currentNode as Leaf
public void unMarkAsLeaf()
{
this.isEndWord = false;
}
}
class Trie
{
const int ALPHABET_SIZE = 26;
TrieNode root;
public Trie()
{
root = new TrieNode();
}
public TrieNode getRoot()
{
return root;
}
//Function to get the index of a character 't'
public int getIndex(char t)
{
return t - 'a';
}
//Function to insert a key,value pair in the Trie
public void insertNode(string key)
{
//Empty string is not allowed
if (key == string.Empty)
return;
//using transform() function and ::tolower in STL to convert 'key' to lowercase
//transform(key.begin(), key.end(), key.begin(), ::tolower);
key = key.ToLower();
TrieNode currentNode = root;
int index = 0;
//Iterate the trie with the given character index,
//If the index points to NULL
//simply create a TrieNode and go down a level
for (int level = 0; level < key.Length; level++)
{
index = getIndex(key[level]);
if (currentNode.children[index] == null)
{
currentNode.children[index] = new TrieNode();
Console.WriteLine( key[level] + " inserted" );
}
currentNode = currentNode.children[index];
}
//Mark the end character as leaf node
currentNode.markAsLeaf();
Console.WriteLine( "'" + key + "' inserted" );
}
//Function to search given key in Trie
public bool searchNode(string key)
{
if (key == string.Empty)
return false;
key = key.ToLower();
TrieNode currentNode = root;
int index = 0;
//Iterate the Trie with given character index,
//If it is NULL at any point then we stop and return false
//We will return true only if we reach leafNode and have traversed the
//Trie based on the length of the key
for (int level = 0; level < key.Length; level++)
{
index = getIndex(key[level]);
if (currentNode.children[index] == null)
return false;
currentNode = currentNode.children[index];
}
if ((currentNode != null) & (currentNode.isEndWord))
{
return true;
}
return false;
}
//Helper Function to return true if currentNode does not have any children
public bool hasNoChildren(TrieNode currentNode)
{
for (int i = 0; i < ALPHABET_SIZE; i++)
{
if ((currentNode.children[i]) != null)
return false;
}
return true;
}
//Recursive function to delete given key
public bool deleteHelper(string key, TrieNode currentNode, int length, int level)
{
bool deletedSelf = false;
if (currentNode == null)
{
Console.WriteLine("Key does not exist");
return deletedSelf;
}
//Base Case: If we have reached at the node which points to the alphabet at the end of the key.
if (level == length)
{
//If there are no nodes ahead of this node in this path
//Then we can delete this node
if (hasNoChildren(currentNode))
{
currentNode = null; //clear the pointer by pointing it to NULL
deletedSelf = true;
}
//If there are nodes ahead of currentNode in this path
//Then we cannot delete currentNode. We simply unmark this as leaf
else
{
currentNode.unMarkAsLeaf();
deletedSelf = false;
}
}
else
{
TrieNode childNode = currentNode.children[getIndex(key[level])];
bool childDeleted = deleteHelper(key, childNode, length, level + 1);
if (childDeleted)
{
//Making children pointer also null: since child is deleted
currentNode.children[getIndex(key[level])] = null;
//If currentNode is leaf node that means currntNode is part of another key
//and hence we can not delete this node and it's parent path nodes
if (currentNode.isEndWord)
{
deletedSelf = false;
}
//If childNode is deleted but if currentNode has more children then currentNode must be part of another key.
//So, we cannot delete currenNode
else if (!hasNoChildren(currentNode))
{
deletedSelf = false;
}
//Else we can delete currentNode
else
{
currentNode = null;
deletedSelf = true;
}
}
else
{
deletedSelf = false;
}
}
return deletedSelf;
}
//Function to delete given key from Trie
public void deleteNode(string key)
{
if ((root == null) || (key == string.Empty))
{
Console.WriteLine("Null key or Empty trie error");
return;
}
deleteHelper(key, root, key.Length, 0);
}
}
}
Time Complexity: $O(n)$
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.
C# Heaps and Hashing
18. Implement a Max-Heap
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
//main.cs
using System;
namespace chapter_8
{
class Program
{
static void Main(string[] args)
{
MaxHeap<int> heap = new MaxHeap<int>();
int size = 6;
int [] arr = { 1, 2, 3, 4, 5, 6 };
heap.buildHeap(arr, size);
heap.printHeap();
Console.WriteLine(heap.getMax());
heap.removeMax();
Console.WriteLine(heap.getMax());
heap.removeMax();
Console.WriteLine(heap.getMax());
heap.insert(1000);
Console.WriteLine(heap.getMax());
}
}
}
// MaxHeap.cs
using System;
using System.Collections.Generic;
namespace chapter_8
{
class MaxHeap<T> where T: IComparable<T>
{
void percolateUp(int i)
{
if (i <= 0)
return;
else if (h[parent(i)].CompareTo ( h[i]) < 0)
{
// Swaps the value of two variables
T temp = h[i];
h[i] = h[parent(i)];
h[parent(i)] = temp;
percolateUp(parent(i));
}
}
public void maxHeapify(int i)
{
int lc = lchild(i);
int rc = rchild(i);
int imax = i;
if (lc < size() && (h[lc].CompareTo(h[imax]) > 0))
imax = lc;
if (rc < size() && (h[rc].CompareTo(h[imax]) > 0))
imax = rc;
if (i != imax)
{
T temp = h[i];
h[i] = h[imax];
h[imax] = temp;
maxHeapify(imax);
}
}
List<T> h = null;
public MaxHeap() {
h = new List<T>();
}
public int size() {
return h.Count;
}
public T getMax()
{
if (size() <= 0)
{
return (T)Convert.ChangeType(-1, typeof(T));
}
else
return h[0];
}
public void insert(T key)
{
// Push elements into vector from the back
h.Add(key);
// Store index of last value of vector in variable i
int i = size() - 1;
// Restore heap property
percolateUp(i);
}
public void printHeap()
{
for (int i = 0; i <= size() - 1; i++)
{
Console.Write( h[i] + " ") ;
}
Console.WriteLine("");
}
public void buildHeap(T [] arr, int size)
{
// Copy elements of array into the List h
h.AddRange(arr);
for (int i = (size - 1) / 2; i >= 0; i--)
{
maxHeapify(i);
}
}
public int parent(int i)
{
return (i - 1) / 2;
}
public int lchild(int i)
{
return i * 2 + 1;
}
public int rchild(int i)
{
return i * 2 + 2;
}
public void removeMax()
{
if (size() == 1)
{
// Remove the last item from the list
h.RemoveAt(h.Count - 1);
}
else if (size() > 1)
{
// Swaps the value of two variables
T temp = h[0];
h[0] = h[size() - 1];
h[size() - 1] = temp;
// Deletes the last element
h.RemoveAt(h.Count - 1);
// Restore heap property
maxHeapify(0);
}
}
}
}
Time Complexity: O(n)
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.
19. Find k smallest elements in an array
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:
using System;
using System.Collections.Generic;
namespace chapter_8
{
class MinHeap<T> where T : IComparable<T>
{
List<T> h = null;
public int parent(int i)
{
return (i - 1) / 2;
}
public int lchild(int i)
{
return i * 2 + 1;
}
public int rchild(int i)
{
return i * 2 + 2;
}
void minHeapify(int i)
{
int lc = lchild(i);
int rc = rchild(i);
int imin = i;
if (lc < size() && (h[lc].CompareTo(h[imin]) < 0))
imin = lc;
if (rc < size() && (h[rc].CompareTo(h[imin]) < 0))
imin = rc;
if (i != imin)
{
T temp = h[i];
h[i] = h[imin];
h[imin] = temp;
minHeapify(imin);
}
}
//percolateUp(): It is meant to restore the
//heap property going up from a node to the root.
void percolateUp(int i)
{
if (i <= 0)
return;
else if (h[parent(i)].CompareTo(h[i]) > 0)
{
// Swaps the value of two variables
T temp = h[i];
h[i] = h[parent(i)];
h[parent(i)] = temp;
percolateUp(parent(i));
}
}
public MinHeap()
{
h = new List<T>();
}
public int size()
{
return h.Count;
}
public T getMin()
{
if (size() <= 0)
{
return (T)Convert.ChangeType(-1, typeof(T));
}
else
{
return h[0];
}
}
public void insert(T key)
{
// Push elements into vector from the back
h.Add(key);
// Store index of last value of vector in variable i
int i = size() - 1;
// Restore heap property
percolateUp(i);
}
public void removeMin()
{
if (size() == 1)
{
// Remove the last item from the list
h.RemoveAt(h.Count - 1);
}
else if (size() > 1)
{
// Swaps the value of two variables
T temp = h[0];
h[0] = h[size() - 1];
h[size() - 1] = temp;
// Deletes the last element
h.RemoveAt(h.Count - 1);
// Restore heap property
minHeapify(0);
}
}
public void buildHeap(T[] arr, int size)
{
// Copy elements of array into the List h
h.AddRange(arr);
for (int i = (size - 1) / 2; i >= 0; i--)
{
minHeapify(i);
}
}
//Bonus function: printHeap()
public void printHeap()
{
for (int i = 0; i <= size() - 1; i++)
{
Console.Write( h[i] + " ");
}
Console.WriteLine("");
}
}
}
Solution and Explanation
using System;
using System.Collections.Generic;
namespace chapter_8
{
class excercise_2
{
static List<int> findKSmallest(int[] arr, int size, int k)
{
MinHeap<int> heap = new MinHeap<int>();
heap.buildHeap(arr, size);
List<int> output = new List<int>();
for (int i = 0; (i < k) && (i < size); i++)
{
output.Add(heap.getMin());
heap.removeMin();
}
return output;
}
static void Main(string[] args)
{
int size = 7;
int[] input = { 9, 4, 7, 1, -2, 6, 5 };
int [] output = findKSmallest(input, size, 3).ToArray();
for (int i = 0; i < output.Length; i++)
{
Console.Write(output[i] + " ");
}
return;
}
}
}
// MinHeap.cs
using System;
using System.Collections.Generic;
namespace chapter_8
{
class MinHeap<T> where T : IComparable<T>
{
List<T> h = null;
public int parent(int i)
{
return (i - 1) / 2;
}
public int lchild(int i)
{
return i * 2 + 1;
}
public int rchild(int i)
{
return i * 2 + 2;
}
void minHeapify(int i)
{
int lc = lchild(i);
int rc = rchild(i);
int imin = i;
if (lc < size() && (h[lc].CompareTo(h[imin]) < 0))
imin = lc;
if (rc < size() && (h[rc].CompareTo(h[imin]) < 0))
imin = rc;
if (i != imin)
{
T temp = h[i];
h[i] = h[imin];
h[imin] = temp;
minHeapify(imin);
}
}
//percolateUp(): It is meant to restore the
//heap property going up from a node to the root.
void percolateUp(int i)
{
if (i <= 0)
return;
else if (h[parent(i)].CompareTo(h[i]) > 0)
{
// Swaps the value of two variables
T temp = h[i];
h[i] = h[parent(i)];
h[parent(i)] = temp;
percolateUp(parent(i));
}
}
public MinHeap()
{
h = new List<T>();
}
public int size()
{
return h.Count;
}
public T getMin()
{
if (size() <= 0)
{
return (T)Convert.ChangeType(-1, typeof(T));
}
else
{
return h[0];
}
}
public void insert(T key)
{
// Push elements into vector from the back
h.Add(key);
// Store index of last value of vector in variable i
int i = size() - 1;
// Restore heap property
percolateUp(i);
}
public void removeMin()
{
if (size() == 1)
{
// Remove the last item from the list
h.RemoveAt(h.Count - 1);
}
else if (size() > 1)
{
// Swaps the value of two variables
T temp = h[0];
h[0] = h[size() - 1];
h[size() - 1] = temp;
// Deletes the last element
h.RemoveAt(h.Count - 1);
// Restore heap property
minHeapify(0);
}
}
public void buildHeap(T[] arr, int size)
{
// Copy elements of array into the List h
h.AddRange(arr);
for (int i = (size - 1) / 2; i >= 0; i--)
{
minHeapify(i);
}
}
//Bonus function: printHeap()
public void printHeap()
{
for (int i = 0; i <= size() - 1; i++)
{
Console.Write( h[i] + " ");
}
Console.WriteLine("");
}
}
}
Time Complexity: O(n + klog n)
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).
20. Trie vs. Hash Table
Compare the use and performance of Tries and Hash Tables.
Both of these data structures can be used for the same job, but their performance would vary based on the nature of your program.
On average, hash tables can perform search, insertion, and deletion in constant time. Whereas trie usually works in $O(n)$.
An efficient hash table requires a smart hash function that would distribute the keys over all the space that is available to you. A trie is simpler to implement because it only accesses additional space when it is needed.
Finally, a trie will prove more useful for ordered data because its tree structure helps maintain the data's order.
21. Subset Array Checker
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
using System;
using System.Collections.Generic;
namespace chapter_9
{
class Program
{
static bool isSubset(int [] arr1, int [] arr2, int size1, int size2)
{
if (size2 > size1)
{
return false;
}
HashSet<int> ht = new HashSet<int>();
// ht stores all the values of arr1
for (int i = 0; i < size1; i++)
{
// following the last element of the container
// If key is not present in the unordered_set then insert it
if (!ht.Contains(arr1[i]))
ht.Add(arr1[i]);
}
// loop to check if all elements of arr2 are also in arr1
for (int i = 0; i < size2; i++)
{
// If key is not found condition will return false
// If found it will return iterator to that key
if (!ht.Contains(arr2[i]))
return false;
}
return true;
}
static void Main(string[] args)
{
int []arr1 = { 9, 4, 7, 1, -2, 6, 5 };
int []arr2 = { 7, 1, -2 };
Console.WriteLine(isSubset(arr1, arr2, 7, 3));
return;
}
}
}
Time Complexity: O(m+n) 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.
22. Find two pairs with an equal sum
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:
a+b = c+d
Remember: You only have to find any two pairs in the array, not all pairs.
Solution and Explanation
using System;
using System.Collections.Generic;
namespace chapter_9
{
class challenge_5
{
static string findPair(int[] arr, int size)
{
string result = "";
// Create HashMap with Key being sum and value being a pair i.e key = 3 , value = {1,2}
// Traverse all possible pairs in given arr and store sums in map
// If sum already exist then print out the two pairs.
Dictionary<int, int[]> hMap = new Dictionary<int, int[]>();
int sum;
int[] prev_pair = null;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
sum = arr[i] + arr[j]; //calculate sum
if (!hMap.ContainsKey(sum))
{
// If the sum is not present in Map then insert it along with pair
int[] temp_Arr = new int[2];
temp_Arr[0] = arr[i];
temp_Arr[1] = arr[j];
hMap[sum] = temp_Arr;
}
else
{
//Sum already present in Map
prev_pair = hMap[sum];
// Since array elements are distinct, we don't
// need to check if any element is common among pairs
result += "{" + prev_pair[0].ToString() + "," + prev_pair[1].ToString() + "}{" + arr[i].ToString() + "," + arr[j].ToString() + "}";
return result;
}
}
}//end of for
return result;
}
static void Main(string[] args)
{
int[] arr = { 3, 4, 7, 1, 12, 9 };
Console.WriteLine(findPair(arr, 6));
}
}
}
Time Complexity: O(n^2)
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.
18 more questions for a C# coding interview
- Reverse a string in C#
- Check if a given string is a palindrome
- Rotate an array
- Find the second largest integer within an array using one loop
- Convert a 2D Array to a 1D Array
- Explain and implement the MergeSort algorithm
- Find out if a linked list is circular
- Balance a binary search tree
- Search a sorted array with lowest time complexity possible
- 0-1 Knapsack problem
- Reverse a linked list
- Match beginning and ending parenthesis in a string
- Shuffle an array of integers in place
- Find the ancestors of a given node in a BST
- Find the shortest path between two vertices in a graph
- Count the number of edges in an undirected graph
- Check balanced parenthesis using a stack
- Sort values in a stack
What to learn next
Great 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!
Top comments (0)