Data structures are a fundamental topic in computer science and are frequently asked about in interviews and exams. Here are some of the most commonly discussed data structures, along with practice questions for each:
1. Arrays
Practice Question: Given an array of integers, find the maximum product of two integers in the array.
Solution: Iterate through the array and keep track of the maximum and second maximum numbers, as well as the minimum and second minimum numbers (to handle negative numbers). The maximum product is either the product of the maximum and second maximum numbers or the product of the minimum and second minimum numbers.
#include <stdio.h>
#include <limits.h>
int maxProduct(int arr[], int n) {
if (n < 2) {
printf("No pairs exist");
return;
}
int max1 = INT_MIN, max2 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (int i = 0; i < n; i++) {
if (arr[i] > max1) {
max2 = max1;
max1 = arr[i];
} else if (arr[i] > max2) {
max2 = arr[i];
}
if (arr[i] < min1) {
min2 = min1;
min1 = arr[i];
} else if (arr[i] < min2) {
min2 = arr[i];
}
}
return max1 * max2 > min1 * min2 ? max1 * max2 : min1 * min2;
}
int main() {
int arr[] = {1, 4, 3, -6, -7, 0};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Max Product is %d", maxProduct(arr, n));
return 0;
}
2. Linked Lists
Practice Question: Determine if a given linked list has a cycle.
Solution: Use the Floyd’s cycle-finding algorithm, also known as the “tortoise and the hare” approach. Move two pointers, one with a speed of 1 and the other with a speed of 2. If there is a loop, they will meet at some point.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int hasCycle(struct Node* head) {
struct Node *slow_p = head, *fast_p = head;
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p) {
return 1;
}
}
return 0;
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->next = head; // Creating a cycle for testing
if (hasCycle(head))
printf("Cycle found");
else
printf("No cycle found");
return 0;
}
Note: Remember to free the allocated memory in real applications.
2. Stacks
Practice Question: Implement a function to sort a stack.
Solution: Use an auxiliary stack. While the original stack is not empty, pop the top item from the original stack and compare it with the top item of the auxiliary stack. If the auxiliary stack is empty or the popped item is smaller than the top item of the auxiliary stack, push it onto the auxiliary stack. Otherwise, pop items from the auxiliary stack and push them onto the original stack until the condition is met.
#include <stdio.h>
#include <stdlib.h>
struct Stack {
int data;
struct Stack* next;
};
void push(struct Stack** top, int new_data) {
struct Stack* new_node = (struct Stack*) malloc(sizeof(struct Stack));
new_node->data = new_data;
new_node->next = *top;
*top = new_node;
}
int pop(struct Stack** top) {
if (*top == NULL) return -1;
struct Stack* temp = *top;
*top = (*top)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct Stack* top) {
if (!top) return -1;
return top->data;
}
int isEmpty(struct Stack* top) {
return !top;
}
void sortedInsert(struct Stack** s, int x) {
if (isEmpty(*s) || x > peek(*s)) {
push(s, x);
return;
}
int temp = pop(s);
sortedInsert(s, x);
push(s, temp);
}
void sortStack(struct Stack** s) {
if (!isEmpty(*s)) {
int x = pop(s);
sortStack(s);
sortedInsert(s, x);
}
}
int main() {
struct Stack* top = NULL;
push(&top, 30);
push(&top, -5);
push(&top, 18);
push(&top, 14);
push(&top, -3);
sortStack(&top);
while (!isEmpty(top)) {
printf("%d ", pop(&top));
}
return 0;
}
3. Queues
Practice Question: Implement a function to reverse the first K elements of a queue.
Solution: Use an auxiliary stack. Dequeue the first K elements from the queue and push them onto the stack. Then, pop the elements from the stack and enqueue them back to the queue. Finally, dequeue the remaining elements from the queue and enqueue them back to ensure the order.
#include <stdio.h>
#include <stdlib.h>
struct Queue {
int front, rear, size;
unsigned capacity;
int* array;
};
struct Queue* createQueue(unsigned capacity) {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->array = (int*)malloc(queue->capacity * sizeof(int));
return queue;
}
int isFull(struct Queue* queue) {
return (queue->size == queue->capacity);
}
int isEmpty(struct Queue* queue) {
return (queue->size == 0);
}
void enqueue(struct Queue* queue, int item) {
if (isFull(queue)) return;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
}
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size = queue->size - 1;
return item;
}
void reverseQueueFirstK(struct Queue* queue, int k) {
if (!queue || k > queue->size) return;
struct Stack* stack = NULL;
for (int i = 0; i < k; i++) {
push(&stack, dequeue(queue));
}
while (!isEmpty(stack)) {
enqueue(queue, pop(&stack));
}
for (int i = 0; i < queue->size - k; i++) {
enqueue(queue, dequeue(queue));
}
}
int main() {
struct Queue* q = createQueue(10);
enqueue(q, 1);
enqueue(q, 2);
enqueue(q, 3);
enqueue(q, 4);
enqueue(q, 5);
enqueue(q, 6);
enqueue(q, 7);
enqueue(q, 8);
enqueue(q, 9);
enqueue(q, 10);
int k = 5;
reverseQueueFirstK(q, k);
while (!isEmpty(q)) {
printf("%d ", dequeue(q));
}
return 0;
}
4. Trees (Binary Trees, Binary Search Trees)
Practice Question: Check if a binary tree is balanced.
Solution: A balanced binary tree is one in which the depth of the two subtrees of every node never differ by more than Recursively check the height of left and right subtrees of a node and return whether they are balanced.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
int max(int a, int b) {
return (a > b) ? a : b;
}
int height(Node* node) {
if (node == NULL) return 0;
return 1 + max(height(node->left), height(node->right));
}
int isBalanced(Node* root) {
if (root == NULL) return 1;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right))
return 1;
return 0;
}
Node* newNode(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(8);
if (isBalanced(root))
printf("Tree is balanced");
else
printf("Tree is not balanced");
return 0;
}
5. Hash Tables
Practice Question: Find the first non-repeated character in a string.
Solution: Traverse the string and store the frequency of each character in a hash table. Then, traverse the string again and check the frequency of each character. The first character with a frequency of 1 is the answer.
#include <stdio.h>
#include <string.h>
#define NO_OF_CHARS 256
char firstNonRepeating(char* str) {
int count[NO_OF_CHARS] = {0};
int len = strlen(str);
for (int i = 0; i < len; i++)
count[str[i]]++;
for (int i = 0; i < len; i++)
if (count[str[i]] == 1)
return str[i];
return '\0';
}
int main() {
char str[] = "geeksforgeeks";
char result = firstNonRepeating(str);
if (result != '\0')
printf("The first non-repeating character is %c", result);
else
printf("All characters are repeating");
return 0;
}
6. Graphs
Practice Question: Determine if a directed graph has a cycle.
Solution: Use depth-first search (DFS) and maintain a set of visited nodes. If a node is revisited before the DFS for that node finishes, then a cycle exists.
Determine if a directed graph has a cycle:
This is a bit more complicated and involves using Depth First Search (DFS) to detect cycles. Due to space constraints, I’ll provide a high-level algorithm for this:
- For each unvisited node, start the DFS.
- Maintain a “visited” and “recursion stack” list.
- If a node is not visited, mark it and put it in the recursion stack.
- Visit its adjacent nodes. If any of the adjacent nodes are in the recursion stack, a cycle exists.
- When exiting the recursive call for a node, remove it from the recursion stack.