I can provide C code examples for each of the questions you've listed.

Please note that for some

problems, there might be multiple approaches, and I'll aim to provide a common or efficient
solution. Also, error handling and complete edge case considerations might be simplified for brevity.

Here are the C codes for each question:

Arrays & Strings:

1. Reverse a string without using built-in functions.

#include <stdio.h>

#include <string.h>

void reverseString(char* str) {

int length = 0;

while (str[length] != '\0') {

length++;

int i = 0;

int j = length - 1;

while (i < j) {

char temp = str[i];

str[i] = str[j];

str[j] = temp;

i++;

j--;

int main() {

char str[] = "hello";

printf("Original string: %s\n", str);

reverseString(str);

printf("Reversed string: %s\n", str);

 return 0;

2. Find the first non-repeating character in a string.

#include <stdio.h>

#include <string.h>

#include <limits.h> // For CHAR_MAX

char firstNonRepeatingChar(char* str) {

int freq[256] = {0}; // Assuming ASCII characters

int i;

// Populate frequency array

for (i = 0; str[i] != '\0'; i++) {

freq[(unsigned char)str[i]]++;

// Find the first character with frequency 1

for (i = 0; str[i] != '\0'; i++) {

if (freq[(unsigned char)str[i]] == 1) {

return str[i];

return '\0'; // No non-repeating character found

int main() {

char str1[] = "leetcode";

printf("First non-repeating character in \"%s\": %c\n", str1, firstNonRepeatingChar(str1));

char str2[] = "aabbcc";

 printf("First non-repeating character in \"%s\": %c\n", str2, firstNonRepeatingChar(str2));

return 0;

3. Check if two strings are anagrams.

#include <stdio.h>

#include <string.h>

#include <stdbool.h>

bool areAnagrams(char* str1, char* str2) {

int count1[256] = {0};

int count2[256] = {0};

int i;

if (strlen(str1) != strlen(str2)) {

return false;

for (i = 0; str1[i] != '\0'; i++) {

count1[(unsigned char)str1[i]]++;

for (i = 0; str2[i] != '\0'; i++) {

count2[(unsigned char)str2[i]]++;

for (i = 0; i < 256; i++) {

if (count1[i] != count2[i]) {

return false;

}
 return true;

int main() {

char str1[] = "listen";

char str2[] = "silent";

printf("\"%s\" and \"%s\" are anagrams: %s\n", str1, str2, areAnagrams(str1, str2) ? "true" :
"false");

char str3[] = "hello";

char str4[] = "world";

printf("\"%s\" and \"%s\" are anagrams: %s\n", str3, str4, areAnagrams(str3, str4) ? "true" :
"false");

return 0;

4. Rotate an array by k steps.

#include <stdio.h>

#include <stdlib.h> // For malloc, free

void reverse(int* nums, int start, int end) {

while (start < end) {

int temp = nums[start];

nums[start] = nums[end];

nums[end] = temp;

start++;

end--;

void rotate(int* nums, int numsSize, int k) {

k %= numsSize; // Handle k larger than numsSize

 if (k == 0) return;

reverse(nums, 0, numsSize - 1);

reverse(nums, 0, k - 1);

reverse(nums, k, numsSize - 1);

void printArray(int* nums, int numsSize) {

for (int i = 0; i < numsSize; i++) {

printf("%d ", nums[i]);

printf("\n");

int main() {

int nums[] = {1, 2, 3, 4, 5, 6, 7};

int n = sizeof(nums) / sizeof(nums[0]);

int k = 3;

printf("Original array: ");

printArray(nums, n);

rotate(nums, n, k);

printf("Rotated array by %d steps: ", k);

printArray(nums, n);

return 0;

5. Find the maximum subarray sum (Kadane's Algorithm).

#include <stdio.h>

#include <limits.h> // For INT_MIN

int maxSubArraySum(int* nums, int numsSize) {

int max_so_far = INT_MIN;

int current_max = 0;

for (int i = 0; i < numsSize; i++) {

current_max += nums[i];

if (current_max > max_so_far) {

max_so_far = current_max;

if (current_max < 0) {

current_max = 0;

return max_so_far;

int main() {

int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

int n = sizeof(nums) / sizeof(nums[0]);

printf("Maximum subarray sum: %d\n", maxSubArraySum(nums, n));

int nums2[] = {1};

printf("Maximum subarray sum: %d\n", maxSubArraySum(nums2, 1));

int nums3[] = {5, 4, -1, 7, 8};

printf("Maximum subarray sum: %d\n", maxSubArraySum(nums3, 5));

return 0;

6. Merge two sorted arrays in-place.

This problem typically implies merging nums2 into nums1, where nums1 has enough space.
C

#include <stdio.h>

#include <stdlib.h> // For memcpy

void merge(int* nums1, int m, int* nums2, int n) {

int i = m - 1; // Pointer for nums1's actual elements

int j = n - 1; // Pointer for nums2

int k = m + n - 1; // Pointer for the end of nums1 (merged array)

while (i >= 0 && j >= 0) {

if (nums1[i] > nums2[j]) {

nums1[k--] = nums1[i--];

} else {

nums1[k--] = nums2[j--];

// If there are remaining elements in nums2, copy them

while (j >= 0) {

nums1[k--] = nums2[j--];

void printArray(int* nums, int numsSize) {

for (int i = 0; i < numsSize; i++) {

printf("%d ", nums[i]);

printf("\n");

int main() {
 int nums1[10] = {1, 2, 3, 0, 0, 0}; // nums1 has space for m+n elements

int m = 3;

int nums2[] = {2, 5, 6};

int n = 3;

printf("nums1 before merge: ");

printArray(nums1, m);

printf("nums2: ");

printArray(nums2, n);

merge(nums1, m, nums2, n);

printf("nums1 after merge: ");

printArray(nums1, m + n);

return 0;

7. Remove duplicates from a sorted array.

#include <stdio.h>

int removeDuplicates(int* nums, int numsSize) {

if (numsSize == 0) {

return 0;

int i = 0; // Pointer for unique elements

for (int j = 1; j < numsSize; j++) {

if (nums[j] != nums[i]) {

i++;

nums[i] = nums[j];

}
 return i + 1; // New length of the array

void printArray(int* nums, int numsSize) {

for (int i = 0; i < numsSize; i++) {

printf("%d ", nums[i]);

printf("\n");

int main() {

int nums[] = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};

int n = sizeof(nums) / sizeof(nums[0]);

printf("Original array: ");

printArray(nums, n);

int newLength = removeDuplicates(nums, n);

printf("Array after removing duplicates (new length %d): ", newLength);

printArray(nums, newLength);

return 0;

8. Implement a function to perform string compression (e.g., aabcccccaaa -> a2b1c5a3).

#include <stdio.h>

#include <string.h>

#include <stdlib.h> // For malloc, free, sprintf

char* compressString(char* str) {

if (str == NULL || *str == '\0') {

return strdup(""); // Return an empty string or original if empty/null

 }

int len = strlen(str);

char* compressed = (char*)malloc(len * 2 + 1); // Max possible size (e.g., "abc" -> "a1b1c1") + null
terminator

if (compressed == NULL) {

return NULL; // Handle memory allocation failure

int compressedIndex = 0;

for (int i = 0; i < len; ) {

char currentChar = str[i];

int count = 0;

while (i < len && str[i] == currentChar) {

count++;

i++;

compressedIndex += sprintf(compressed + compressedIndex, "%c%d", currentChar, count);

compressed[compressedIndex] = '\0';

// Check if compressed string is actually shorter

if (compressedIndex < len) {

return compressed;

} else {

free(compressed); // Free allocated memory if no compression achieved

return strdup(str); // Return a copy of the original string

int main() {
 char str1[] = "aabcccccaaa";

char* compressed1 = compressString(str1);

printf("Original: %s, Compressed: %s\n", str1, compressed1);

free(compressed1);

char str2[] = "abc";

char* compressed2 = compressString(str2);

printf("Original: %s, Compressed: %s\n", str2, compressed2);

free(compressed2);

char str3[] = "aaabbbccc";

char* compressed3 = compressString(str3);

printf("Original: %s, Compressed: %s\n", str3, compressed3);

free(compressed3);

return 0;

Linked Lists:

For Linked List problems, we'll define a basic ListNode structure.

#include <stdio.h>

#include <stdlib.h> // For malloc, free

// Definition for singly-linked list.

struct ListNode {

int val;

struct ListNode *next;

};

// Helper function to create a new node

struct ListNode* createNode(int val) {

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

 if (newNode) {

newNode->val = val;

newNode->next = NULL;

return newNode;

// Helper function to print a linked list

void printList(struct ListNode* head) {

struct ListNode* current = head;

while (current != NULL) {

printf("%d -> ", current->val);

current = current->next;

printf("NULL\n");

1. Reverse a linked list.

// Function to reverse a linked list

struct ListNode* reverseList(struct ListNode* head) {

struct ListNode* prev = NULL;

struct ListNode* current = head;

struct ListNode* next = NULL;

while (current != NULL) {

next = current->next; // Store next node

current->next = prev; // Reverse current node's pointer

prev = current; // Move prev to current

current = next; // Move current to next

return prev; // prev will be the new head

}

int main() {

struct ListNode* head = createNode(1);

head->next = createNode(2);

head->next->next = createNode(3);

head->next->next->next = createNode(4);

printf("Original list: ");

printList(head);

struct ListNode* reversedHead = reverseList(head);

printf("Reversed list: ");

printList(reversedHead);

// Free memory

struct ListNode* temp;

while (reversedHead != NULL) {

temp = reversedHead;

reversedHead = reversedHead->next;

free(temp);

return 0;

2. Detect a cycle in a linked list.

#include <stdbool.h>

// Function to detect a cycle in a linked list using Floyd's Cycle-Finding Algorithm

bool hasCycle(struct ListNode* head) {

if (head == NULL || head->next == NULL) {

 return false;

struct ListNode* slow = head;

struct ListNode* fast = head;

while (fast != NULL && fast->next != NULL) {

slow = slow->next;

fast = fast->next->next;

if (slow == fast) {

return true; // Cycle detected

return false; // No cycle

int main() {

// Create a list with a cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to 2)

struct ListNode* head1 = createNode(1);

struct ListNode* node2 = createNode(2);

struct ListNode* node3 = createNode(3);

struct ListNode* node4 = createNode(4);

head1->next = node2;

node2->next = node3;

node3->next = node4;

node4->next = node2; // Creates a cycle

printf("List with cycle: %s\n", hasCycle(head1) ? "true" : "false");

 // Create a list without a cycle: 1 -> 2 -> 3 -> NULL

struct ListNode* head2 = createNode(1);

head2->next = createNode(2);

head2->next->next = createNode(3);

printf("List without cycle: %s\n", hasCycle(head2) ? "true" : "false");

// Free memory for the list without a cycle

struct ListNode* temp;

while (head2 != NULL) {

temp = head2;

head2 = head2->next;

free(temp);

// For the cyclic list, be careful with freeing to avoid infinite loop

// If a cycle is detected, you would typically break the cycle before freeing

// For demonstration, we won't free the cyclic list in main to keep it simple.

return 0;

3. Merge two sorted linked lists.

// Function to merge two sorted linked lists

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {

if (list1 == NULL) return list2;

if (list2 == NULL) return list1;

struct ListNode* head;

if (list1->val <= list2->val) {

head = list1;

list1 = list1->next;

} else {
 head = list2;

list2 = list2->next;

struct ListNode* current = head;

while (list1 != NULL && list2 != NULL) {

if (list1->val <= list2->val) {

current->next = list1;

list1 = list1->next;

} else {

current->next = list2;

list2 = list2->next;

current = current->next;

if (list1 != NULL) {

current->next = list1;

} else if (list2 != NULL) {

current->next = list2;

return head;

int main() {

struct ListNode* l1 = createNode(1);

l1->next = createNode(2);

l1->next->next = createNode(4);

struct ListNode* l2 = createNode(1);

l2->next = createNode(3);
 l2->next->next = createNode(4);

printf("List 1: ");

printList(l1);

printf("List 2: ");

printList(l2);

struct ListNode* mergedList = mergeTwoLists(l1, l2);

printf("Merged list: ");

printList(mergedList);

// Free memory

struct ListNode* temp;

while (mergedList != NULL) {

temp = mergedList;

mergedList = mergedList->next;

free(temp);

return 0;

4. Find the middle node of a linked list.

// Function to find the middle node of a linked list using slow and fast pointers

struct ListNode* middleNode(struct ListNode* head) {

if (head == NULL) {

return NULL;

struct ListNode* slow = head;

struct ListNode* fast = head;

while (fast != NULL && fast->next != NULL) {

 slow = slow->next;

fast = fast->next->next;

return slow; // Slow pointer will be at the middle

int main() {

struct ListNode* head1 = createNode(1);

head1->next = createNode(2);

head1->next->next = createNode(3);

head1->next->next->next = createNode(4);

head1->next->next->next->next = createNode(5);

printf("List 1: ");

printList(head1);

struct ListNode* middle1 = middleNode(head1);

if (middle1) {

printf("Middle node value: %d\n", middle1->val);

struct ListNode* head2 = createNode(1);

head2->next = createNode(2);

head2->next->next = createNode(3);

head2->next->next->next = createNode(4);

printf("List 2: ");

printList(head2);

struct ListNode* middle2 = middleNode(head2);

if (middle2) {

printf("Middle node value: %d\n", middle2->val);

}
 // Free memory

struct ListNode* temp;

while (head1 != NULL) { temp = head1; head1 = head1->next; free(temp); }

while (head2 != NULL) { temp = head2; head2 = head2->next; free(temp); }

return 0;

5. Remove the Nth node from the end of a linked list.

// Function to remove the Nth node from the end of a linked list

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {

struct ListNode* dummy = createNode(0); // Dummy node to handle edge case of removing head

dummy->next = head;

struct ListNode* first = dummy;

struct ListNode* second = dummy;

// Move first pointer N+1 steps ahead

for (int i = 0; i <= n; i++) {

first = first->next;

// Move both pointers until first reaches the end

while (first != NULL) {

first = first->next;

second = second->next;

// Second pointer is now at the node before the one to be removed

struct ListNode* nodeToDelete = second->next;

second->next = second->next->next;
 free(nodeToDelete);

head = dummy->next;

free(dummy); // Free the dummy node

return head;

int main() {

struct ListNode* head1 = createNode(1);

head1->next = createNode(2);

head1->next->next = createNode(3);

head1->next->next->next = createNode(4);

head1->next->next->next->next = createNode(5);

printf("Original list: ");

printList(head1);

head1 = removeNthFromEnd(head1, 2); // Remove 2nd from end (node with value 4)

printf("List after removing 2nd from end: ");

printList(head1);

// Free memory

struct ListNode* temp;

while (head1 != NULL) {

temp = head1;

head1 = head1->next;

free(temp);

struct ListNode* head2 = createNode(1);

head2->next = createNode(2);
 printf("Original list: ");

printList(head2);

head2 = removeNthFromEnd(head2, 2); // Remove 2nd from end (node with value 1)

printf("List after removing 2nd from end: ");

printList(head2);

while (head2 != NULL) {

temp = head2;

head2 = head2->next;

free(temp);

return 0;

Trees & Graphs:

For Tree problems, we'll define a basic TreeNode structure.

#include <stdio.h>

#include <stdlib.h> // For malloc, free

#include <stdbool.h> // For boolean types

// Definition for a binary tree node.

struct TreeNode {

int val;

struct TreeNode *left;

struct TreeNode *right;

};

// Helper function to create a new tree node

struct TreeNode* createTreeNode(int val) {

struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

if (newNode) {
 newNode->val = val;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

1. Implement Binary Tree traversal (Inorder, Preorder, Postorder).

// Inorder Traversal (Left, Root, Right)

void inorderTraversal(struct TreeNode* root) {

if (root == NULL) {

return;

inorderTraversal(root->left);

printf("%d ", root->val);

inorderTraversal(root->right);

// Preorder Traversal (Root, Left, Right)

void preorderTraversal(struct TreeNode* root) {

if (root == NULL) {

return;

printf("%d ", root->val);

preorderTraversal(root->left);

preorderTraversal(root->right);

// Postorder Traversal (Left, Right, Root)

void postorderTraversal(struct TreeNode* root) {

if (root == NULL) {
 return;

postorderTraversal(root->left);

postorderTraversal(root->right);

printf("%d ", root->val);

int main() {

// Example Tree:

// 1

// /\

// 2 3

// / \

// 4 5

struct TreeNode* root = createTreeNode(1);

root->left = createTreeNode(2);

root->right = createTreeNode(3);

root->left->left = createTreeNode(4);

root->left->right = createTreeNode(5);

printf("Inorder Traversal: ");

inorderTraversal(root);

printf("\n");

printf("Preorder Traversal: ");

preorderTraversal(root);

printf("\n");

printf("Postorder Traversal: ");

postorderTraversal(root);

printf("\n");
 // Free memory (simple post-order like freeing)

free(root->left->left);

free(root->left->right);

free(root->left);

free(root->right);

free(root);

return 0;

2. Check if a binary tree is balanced.

A balanced binary tree is one where the depth of the two subtrees of every node never differs by
more than one.

// Helper function to calculate height and check balance

int isBalancedHelper(struct TreeNode* root) {

if (root == NULL) {

return 0; // Height of an empty tree is 0

int leftHeight = isBalancedHelper(root->left);

if (leftHeight == -1) {

return -1; // Left subtree is unbalanced

int rightHeight = isBalancedHelper(root->right);

if (rightHeight == -1) {

return -1; // Right subtree is unbalanced

if (abs(leftHeight - rightHeight) > 1) {

return -1; // Current node's subtrees are unbalanced

 }

// Return the height of the current subtree

return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

bool isBalanced(struct TreeNode* root) {

return isBalancedHelper(root) != -1;

int main() {

// Balanced tree

struct TreeNode* root1 = createTreeNode(3);

root1->left = createTreeNode(9);

root1->right = createTreeNode(20);

root1->right->left = createTreeNode(15);

root1->right->right = createTreeNode(7);

printf("Tree 1 is balanced: %s\n", isBalanced(root1) ? "true" : "false");

// Free memory for root1 (simple post-order like freeing)

free(root1->right->left);

free(root1->right->right);

free(root1->left);

free(root1->right);

free(root1);

// Unbalanced tree

struct TreeNode* root2 = createTreeNode(1);

root2->left = createTreeNode(2);

root2->left->left = createTreeNode(3);

root2->left->left->left = createTreeNode(4);

printf("Tree 2 is balanced: %s\n", isBalanced(root2) ? "true" : "false");

 // Free memory for root2

free(root2->left->left->left);

free(root2->left->left);

free(root2->left);

free(root2);

return 0;

3. Find the Lowest Common Ancestor (LCA) in a BST.

// Function to find the Lowest Common Ancestor in a Binary Search Tree (BST)

struct TreeNode* lowestCommonAncestorBST(struct TreeNode* root, struct TreeNode* p, struct

TreeNode* q) {

if (root == NULL) {

return NULL;

// If both p and q are smaller than root, LCA is in the left subtree

if (p->val < root->val && q->val < root->val) {

return lowestCommonAncestorBST(root->left, p, q);

// If both p and q are greater than root, LCA is in the right subtree

else if (p->val > root->val && q->val > root->val) {

return lowestCommonAncestorBST(root->right, p, q);

// Otherwise, root is the LCA (one is on left, one is on right, or one is root itself)

else {

return root;

int main() {
// Example BST:

// 6

// /\

// 2 8

// / \ / \

// 0 4 7 9

// /\

// 3 5

struct TreeNode* root = createTreeNode(6);

root->left = createTreeNode(2);

root->right = createTreeNode(8);

root->left->left = createTreeNode(0);

root->left->right = createTreeNode(4);

root->right->left = createTreeNode(7);

root->right->right = createTreeNode(9);

root->left->right->left = createTreeNode(3);

root->left->right->right = createTreeNode(5);

struct TreeNode* p1 = root->left; // Node 2

struct TreeNode* q1 = root->right; // Node 8

struct TreeNode* lca1 = lowestCommonAncestorBST(root, p1, q1);

printf("LCA of %d and %d: %d\n", p1->val, q1->val, lca1->val); // Expected: 6

struct TreeNode* p2 = root->left; // Node 2

struct TreeNode* q2 = root->left->right->right; // Node 5

struct TreeNode* lca2 = lowestCommonAncestorBST(root, p2, q2);

printf("LCA of %d and %d: %d\n", p2->val, q2->val, lca2->val); // Expected: 2

// Free memory (simplified, as actual tree memory management can be complex)

// You'd typically have a function to free the entire tree

// For demonstration, not explicitly freeing all nodes here.

 return 0;

4. Serialize and deserialize a binary tree.

Serialization means converting a tree into a string (or array) representation. Deserialization means
rebuilding the tree from that representation. We'll use a simple pre-order traversal with a special
marker for null nodes.

#define MAX_SERIALIZED_SIZE 1000 // Max size for the serialized string

#define NULL_MARKER '#'

// Function to serialize a binary tree into a string

void serializeHelper(struct TreeNode* root, char* buffer, int* offset) {

if (root == NULL) {

*offset += sprintf(buffer + *offset, "%c,", NULL_MARKER);

return;

*offset += sprintf(buffer + *offset, "%d,", root->val);

serializeHelper(root->left, buffer, offset);

serializeHelper(root->right, buffer, offset);

char* serialize(struct TreeNode* root) {

char* buffer = (char*)malloc(sizeof(char) * MAX_SERIALIZED_SIZE);

if (buffer == NULL) return NULL;

int offset = 0;

serializeHelper(root, buffer, &offset);

return buffer;

// Function to deserialize a string into a binary tree

struct TreeNode* deserializeHelper(char** data) {

if (**data == NULL_MARKER) {
 // Move past the marker and comma

(*data)++; // Move past '#'

if (**data == ',') (*data)++; // Move past ','

return NULL;

// Read the number

int val = 0;

bool negative = false;

if (**data == '-') {

negative = true;

(*data)++;

while (**data != ',' && **data != '\0') {

val = val * 10 + (**data - '0');

(*data)++;

if (negative) {

val = -val;

if (**data == ',') {

(*data)++; // Move past ','

struct TreeNode* root = createTreeNode(val);

root->left = deserializeHelper(data);

root->right = deserializeHelper(data);

return root;
}

struct TreeNode* deserialize(char* data) {

return deserializeHelper(&data);

int main() {

// Example Tree:

// 1

// /\

// 2 3

// / \

// 4 5

struct TreeNode* root = createTreeNode(1);

root->left = createTreeNode(2);

root->right = createTreeNode(3);

root->left->left = createTreeNode(4);

root->left->right = createTreeNode(5);

printf("Original tree (Inorder): ");

inorderTraversal(root);

printf("\n");

char* serialized_string = serialize(root);

printf("Serialized string: %s\n", serialized_string);

struct TreeNode* deserialized_root = deserialize(serialized_string);

printf("Deserialized tree (Inorder): ");

inorderTraversal(deserialized_root);

printf("\n");
 // Free memory

free(serialized_string);

// Free the deserialized tree (similar to freeing original tree)

// (A more robust free function would be needed for a real application)

return 0;

5. Implement BFS and DFS for a graph.

For graph representation, we'll use an adjacency list.

#include <stdbool.h>

#define MAX_NODES 100

// Adjacency list representation for a graph

struct AdjListNode {

int dest;

struct AdjListNode* next;

};

struct Graph {

int numVertices;

struct AdjListNode** adjLists;

bool* visited;

};

// Queue for BFS

struct QueueNode {

int data;

struct QueueNode* next;

};
struct Queue {

struct QueueNode *front, *rear;

};

struct AdjListNode* createAdjListNode(int dest) {

struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));

newNode->dest = dest;

newNode->next = NULL;

return newNode;

struct Graph* createGraph(int vertices) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->numVertices = vertices;

graph->adjLists = (struct AdjListNode**)malloc(vertices * sizeof(struct AdjListNode*));

graph->visited = (bool*)malloc(vertices * sizeof(bool));

for (int i = 0; i < vertices; i++) {

graph->adjLists[i] = NULL;

graph->visited[i] = false;

return graph;

void addEdge(struct Graph* graph, int src, int dest) {

// Add edge from src to dest

struct AdjListNode* newNode = createAdjListNode(dest);

newNode->next = graph->adjLists[src];

graph->adjLists[src] = newNode;

// For undirected graph, add edge from dest to src as well

 newNode = createAdjListNode(src);

newNode->next = graph->adjLists[dest];

graph->adjLists[dest] = newNode;

// DFS (Depth First Search)

void DFS(struct Graph* graph, int vertex) {

graph->visited[vertex] = true;

printf("%d ", vertex);

struct AdjListNode* adjList = graph->adjLists[vertex];

while (adjList != NULL) {

int connectedVertex = adjList->dest;

if (!graph->visited[connectedVertex]) {

DFS(graph, connectedVertex);

adjList = adjList->next;

// Queue operations for BFS

struct Queue* createQueue() {

struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));

q->front = q->rear = NULL;

return q;

void enqueue(struct Queue* q, int value) {

struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));

newNode->data = value;

newNode->next = NULL;
 if (q->rear == NULL) {

q->front = q->rear = newNode;

return;

q->rear->next = newNode;

q->rear = newNode;

int dequeue(struct Queue* q) {

if (q->front == NULL) return -1; // Or handle error

struct QueueNode* temp = q->front;

int data = temp->data;

q->front = q->front->next;

if (q->front == NULL) q->rear = NULL;

free(temp);

return data;

bool isEmpty(struct Queue* q) {

return q->front == NULL;

// BFS (Breadth First Search)

void BFS(struct Graph* graph, int startVertex) {

struct Queue* q = createQueue();

for (int i = 0; i < graph->numVertices; i++) {

graph->visited[i] = false; // Reset visited for BFS

graph->visited[startVertex] = true;
 enqueue(q, startVertex);

while (!isEmpty(q)) {

int currentVertex = dequeue(q);

printf("%d ", currentVertex);

struct AdjListNode* adjList = graph->adjLists[currentVertex];

while (adjList != NULL) {

int connectedVertex = adjList->dest;

if (!graph->visited[connectedVertex]) {

graph->visited[connectedVertex] = true;

enqueue(q, connectedVertex);

adjList = adjList->next;

free(q); // Free the queue structure

int main() {

struct Graph* graph = createGraph(5);

addEdge(graph, 0, 1);

addEdge(graph, 0, 2);

addEdge(graph, 1, 3);

addEdge(graph, 2, 4);

addEdge(graph, 3, 4);

printf("DFS starting from vertex 0: ");

// Reset visited for DFS

for (int i = 0; i < graph->numVertices; i++) {

graph->visited[i] = false;
 }

DFS(graph, 0);

printf("\n");

printf("BFS starting from vertex 0: ");

BFS(graph, 0);

printf("\n");

// Free graph memory

for (int i = 0; i < graph->numVertices; i++) {

struct AdjListNode* current = graph->adjLists[i];

while (current != NULL) {

struct AdjListNode* temp = current;

current = current->next;

free(temp);

free(graph->adjLists);

free(graph->visited);

free(graph);

return 0;

Dynamic Programming:

1. Fibonacci number (recursive + DP).

#include <stdio.h>

#include <stdlib.h> // For malloc, free

// Recursive Fibonacci (without DP - for comparison, can be slow)

int fibonacciRecursive(int n) {

if (n <= 1) {
 return n;

return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);

// Fibonacci using Dynamic Programming (Memoization - Top-Down)

int memo[100]; // Assuming n won't exceed 100

int fibonacciMemoization(int n) {

if (n <= 1) {

return n;

if (memo[n] != -1) {

return memo[n];

memo[n] = fibonacciMemoization(n - 1) + fibonacciMemoization(n - 2);

return memo[n];

// Fibonacci using Dynamic Programming (Tabulation - Bottom-Up)

int fibonacciTabulation(int n) {

if (n <= 1) {

return n;

int dp[n + 1];

dp[0] = 0;

dp[1] = 1;

for (int i = 2; i <= n; i++) {

dp[i] = dp[i - 1] + dp[i - 2];

return dp[n];
}

int main() {

int n = 10;

printf("Fibonacci (Recursive): F(%d) = %d\n", n, fibonacciRecursive(n));

// Initialize memoization array

for (int i = 0; i < 100; i++) {

memo[i] = -1;

printf("Fibonacci (Memoization): F(%d) = %d\n", n, fibonacciMemoization(n));

printf("Fibonacci (Tabulation): F(%d) = %d\n", n, fibonacciTabulation(n));

return 0;

2. Climbing stairs problem.

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2
steps. In how many distinct ways can you climb to the top?

#include <stdio.h>

// Climbing Stairs using Dynamic Programming (similar to Fibonacci)

int climbStairs(int n) {

if (n <= 0) return 0;

if (n == 1) return 1;

if (n == 2) return 2;

int dp[n + 1];

dp[1] = 1;

dp[2] = 2;
 for (int i = 3; i <= n; i++) {

dp[i] = dp[i - 1] + dp[i - 2];

return dp[n];

int main() {

int n1 = 2;

printf("Ways to climb %d stairs: %d\n", n1, climbStairs(n1)); // Expected: 2 (1+1, 2)

int n2 = 3;

printf("Ways to climb %d stairs: %d\n", n2, climbStairs(n2)); // Expected: 3 (1+1+1, 1+2, 2+1)

int n3 = 5;

printf("Ways to climb %d stairs: %d\n", n3, climbStairs(n3)); // Expected: 8

return 0;

3. Longest Increasing Subsequence (LIS).

#include <stdio.h>

#include <stdlib.h> // For max

// Helper for max

int max(int a, int b) {

return (a > b) ? a : b;

int lengthOfLIS(int* nums, int numsSize) {

if (numsSize == 0) {

return 0;
 }

int dp[numsSize]; // dp[i] stores the length of LIS ending at index i

int maxLength = 1;

for (int i = 0; i < numsSize; i++) {

dp[i] = 1; // Minimum LIS ending at i is 1 (the element itself)

for (int j = 0; j < i; j++) {

if (nums[i] > nums[j]) {

dp[i] = max(dp[i], dp[j] + 1);

maxLength = max(maxLength, dp[i]);

return maxLength;

int main() {

int nums1[] = {10, 9, 2, 5, 3, 7, 101, 18};

int n1 = sizeof(nums1) / sizeof(nums1[0]);

printf("Length of LIS in [10, 9, 2, 5, 3, 7, 101, 18]: %d\n", lengthOfLIS(nums1, n1)); // Expected: 4

(2, 3, 7, 18 or 2, 3, 7, 101)

int nums2[] = {0, 1, 0, 3, 2, 3};

int n2 = sizeof(nums2) / sizeof(nums2[0]);

printf("Length of LIS in [0, 1, 0, 3, 2, 3]: %d\n", lengthOfLIS(nums2, n2)); // Expected: 4 (0, 1, 2, 3)

int nums3[] = {7, 7, 7, 7, 7, 7, 7};

int n3 = sizeof(nums3) / sizeof(nums3[0]);

printf("Length of LIS in [7, 7, 7, 7, 7, 7, 7]: %d\n", lengthOfLIS(nums3, n3)); // Expected: 1

return 0;
}

4. 0/1 Knapsack problem.

Given weights and values of N items, put these items in a knapsack of capacity W to get the
maximum total value in the knapsack.

#include <stdio.h>

#include <stdlib.h> // For max

// Function to solve 0/1 Knapsack problem

int knapSack(int W, int* wt, int* val, int n) {

int dp[n + 1][W + 1];

// Build dp table in bottom-up manner

for (int i = 0; i <= n; i++) {

for (int w = 0; w <= W; w++) {

if (i == 0 || w == 0) {

dp[i][w] = 0;

} else if (wt[i - 1] <= w) {

dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);

} else {

dp[i][w] = dp[i - 1][w];

return dp[n][W];

int main() {

int val[] = {60, 100, 120};

int wt[] = {10, 20, 30};

int W = 50;
 int n = sizeof(val) / sizeof(val[0]);

printf("Maximum value in Knapsack: %d\n", knapSack(W, wt, val, n)); // Expected: 220

return 0;

5. Coin change problem (minimum coins needed).

Given a set of coin denominations and a target amount, find the minimum number of coins needed
to make that amount. If it's not possible, return -1.

#include <stdio.h>

#include <limits.h> // For INT_MAX

// Function to find the minimum number of coins for a given amount

int coinChange(int* coins, int coinsSize, int amount) {

int dp[amount + 1];

dp[0] = 0; // 0 coins needed for amount 0

for (int i = 1; i <= amount; i++) {

dp[i] = INT_MAX; // Initialize with a very large value

for (int j = 0; j < coinsSize; j++) {

if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {

if (dp[i - coins[j]] + 1 < dp[i]) {

dp[i] = dp[i - coins[j]] + 1;

return (dp[amount] == INT_MAX) ? -1 : dp[amount];

int main() {
 int coins1[] = {1, 2, 5};

int amount1 = 11;

printf("Min coins for amount %d with coins {1,2,5}: %d\n", amount1, coinChange(coins1, 3,
amount1)); // Expected: 3 (5+5+1)

int coins2[] = {2};

int amount2 = 3;

printf("Min coins for amount %d with coins {2}: %d\n", amount2, coinChange(coins2, 1,
amount2)); // Expected: -1

int coins3[] = {1};

int amount3 = 0;

printf("Min coins for amount %d with coins {1}: %d\n", amount3, coinChange(coins3, 1,
amount3)); // Expected: 0

return 0;

Sorting & Searching:

1. Implement QuickSort / MergeSort.

QuickSort

#include <stdio.h>

// Function to swap two elements

void swap(int* a, int* b) {

int temp = *a;

*a = *b;

*b = temp;

// Partition function for QuickSort

int partition(int* arr, int low, int high) {

int pivot = arr[high]; // Choose the last element as pivot

 int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {

// If current element is smaller than or equal to pivot

if (arr[j] <= pivot) {

i++; // Increment index of smaller element

swap(&arr[i], &arr[j]);

swap(&arr[i + 1], &arr[high]);

return (i + 1);

// QuickSort function

void quickSort(int* arr, int low, int high) {

if (low < high) {

// pi is partitioning index, arr[pi] is now at right place

int pi = partition(arr, low, high);

// Separately sort elements before partition and after partition

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

void printArray(int* arr, int size) {

for (int i = 0; i < size; i++) {

printf("%d ", arr[i]);

printf("\n");

}
int main() {

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted array (QuickSort): ");

printArray(arr, n);

return 0;

MergeSort

#include <stdio.h>

#include <stdlib.h> // For malloc, free

// Merge function

void merge(int* arr, int left, int mid, int right) {

int i, j, k;

int n1 = mid - left + 1;

int n2 = right - mid;

// Create temp arrays

int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]

for (i = 0; i < n1; i++)

L[i] = arr[left + i];

for (j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

 // Merge the temp arrays back into arr[left..right]

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray

k = left; // Initial index of merged subarray

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

k++;

// Copy the remaining elements of L[], if there are any

while (i < n1) {

arr[k] = L[i];

i++;

k++;

// Copy the remaining elements of R[], if there are any

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}
// MergeSort function

void mergeSort(int* arr, int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

// Sort first and second halves

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

void printArray(int* arr, int size) {

for (int i = 0; i < size; i++) {

printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

mergeSort(arr, 0, n - 1);

printf("Sorted array (MergeSort): ");

printArray(arr, n);

return 0;

}
 2. Binary Search variations (find first/last occurrence).

#include <stdio.h>

// Standard Binary Search

int binarySearch(int* arr, int size, int target) {

int low = 0;

int high = size - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {

return mid; // Target found

} else if (arr[mid] < target) {

low = mid + 1;

} else {

high = mid - 1;

return -1; // Target not found

// Find First Occurrence of an element

int findFirstOccurrence(int* arr, int size, int target) {

int low = 0;

int high = size - 1;

int result = -1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {
 result = mid; // Potential first occurrence

high = mid - 1; // Look in the left half for an earlier occurrence

} else if (arr[mid] < target) {

low = mid + 1;

} else {

high = mid - 1;

return result;

// Find Last Occurrence of an element

int findLastOccurrence(int* arr, int size, int target) {

int low = 0;

int high = size - 1;

int result = -1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {

result = mid; // Potential last occurrence

low = mid + 1; // Look in the right half for a later occurrence

} else if (arr[mid] < target) {

low = mid + 1;

} else {

high = mid - 1;

return result;

}
int main() {

int arr[] = {1, 2, 3, 3, 3, 4, 5, 5};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Array: ");

printArray(arr, n);

int target1 = 3;

printf("Standard Binary Search for %d: %d\n", target1, binarySearch(arr, n, target1));

printf("First occurrence of %d: %d\n", target1, findFirstOccurrence(arr, n, target1));

printf("Last occurrence of %d: %d\n", target1, findLastOccurrence(arr, n, target1));

int target2 = 5;

printf("First occurrence of %d: %d\n", target2, findFirstOccurrence(arr, n, target2));

printf("Last occurrence of %d: %d\n", target2, findLastOccurrence(arr, n, target2));

int target3 = 6;

printf("First occurrence of %d: %d\n", target3, findFirstOccurrence(arr, n, target3));

return 0;

3. Search in a rotated sorted array.

#include <stdio.h>

int searchRotatedSortedArray(int* nums, int numsSize, int target) {

int low = 0;

int high = numsSize - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

 if (nums[mid] == target) {

return mid;

// Check if left half is sorted

if (nums[low] <= nums[mid]) {

if (target >= nums[low] && target < nums[mid]) {

high = mid - 1; // Target is in the sorted left half

} else {

low = mid + 1; // Target is in the unsorted right half

// Right half must be sorted

else {

if (target > nums[mid] && target <= nums[high]) {

low = mid + 1; // Target is in the sorted right half

} else {

high = mid - 1; // Target is in the unsorted left half

return -1; // Target not found

int main() {

int nums1[] = {4, 5, 6, 7, 0, 1, 2};

int n1 = sizeof(nums1) / sizeof(nums1[0]);

int target1 = 0;

printf("Index of %d in [4,5,6,7,0,1,2]: %d\n", target1, searchRotatedSortedArray(nums1, n1,

target1)); // Expected: 4
 int target2 = 3;

printf("Index of %d in [4,5,6,7,0,1,2]: %d\n", target2, searchRotatedSortedArray(nums1, n1,

target2)); // Expected: -1

int nums2[] = {1};

int n2 = sizeof(nums2) / sizeof(nums2[0]);

int target3 = 1;

printf("Index of %d in [1]: %d\n", target3, searchRotatedSortedArray(nums2, n2, target3)); //

Expected: 0

return 0;

4. Find the Kth smallest/largest element.

This can be done using QuickSelect (an algorithm similar to QuickSort's partition) or by sorting the
array. QuickSelect is typically more efficient for finding just the Kth element.

Using QuickSelect (for Kth smallest)

#include <stdio.h>

#include <stdlib.h> // For rand(), srand()

#include <time.h> // For time()

// Function to swap two elements

void swap(int* a, int* b) {

int temp = *a;

*a = *b;

*b = temp;

// Partition function for QuickSelect (random pivot for better average performance)

int partitionRandom(int* arr, int low, int high) {

srand(time(NULL)); // Seed the random number generator

int random = low + rand() % (high - low + 1);

swap(&arr[random], &arr[high]); // Move random element to end as pivot

 int pivot = arr[high];

int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (arr[j] <= pivot) {

i++;

swap(&arr[i], &arr[j]);

swap(&arr[i + 1], &arr[high]);

return (i + 1);

// QuickSelect algorithm to find Kth smallest element

int quickSelect(int* nums, int low, int high, int k) {

if (low <= high) {

int pivotIndex = partitionRandom(nums, low, high);

if (pivotIndex == k - 1) { // Found the Kth smallest element (0-indexed)

return nums[pivotIndex];

} else if (pivotIndex < k - 1) { // Kth smallest is in the right partition

return quickSelect(nums, pivotIndex + 1, high, k);

} else { // Kth smallest is in the left partition

return quickSelect(nums, low, pivotIndex - 1, k);

return -1; // Should not happen for valid k

// Function to find Kth smallest element

int findKthSmallest(int* nums, int numsSize, int k) {

if (k < 1 || k > numsSize) {

return -1; // Invalid k

return quickSelect(nums, 0, numsSize - 1, k);

// Function to find Kth largest element (by finding (n-k+1)th smallest)

int findKthLargest(int* nums, int numsSize, int k) {

if (k < 1 || k > numsSize) {

return -1; // Invalid k

return quickSelect(nums, 0, numsSize - 1, numsSize - k + 1);

int main() {

int nums[] = {3, 2, 1, 5, 6, 4};

int n = sizeof(nums) / sizeof(nums[0]);

// Note: QuickSelect modifies the array. If original array order is needed, pass a copy.

// For Kth smallest

int nums_copy1[] = {3, 2, 1, 5, 6, 4};

printf("Kth smallest element:\n");

printf("1st smallest: %d\n", findKthSmallest(nums_copy1, n, 1)); // Expected: 1

int nums_copy2[] = {3, 2, 1, 5, 6, 4};

printf("3rd smallest: %d\n", findKthSmallest(nums_copy2, n, 3)); // Expected: 3

int nums_copy3[] = {3, 2, 1, 5, 6, 4};

printf("6th smallest: %d\n", findKthSmallest(nums_copy3, n, 6)); // Expected: 6

printf("\nKth largest element:\n");

 // For Kth largest

int nums_copy4[] = {3, 2, 1, 5, 6, 4};

printf("1st largest: %d\n", findKthLargest(nums_copy4, n, 1)); // Expected: 6

int nums_copy5[] = {3, 2, 1, 5, 6, 4};

printf("2nd largest: %d\n", findKthLargest(nums_copy5, n, 2)); // Expected: 5

int nums_copy6[] = {3, 2, 1, 5, 6, 4};

printf("4th largest: %d\n", findKthLargest(nums_copy6, n, 4)); // Expected: 3

return 0;

Miscellaneous:

1. Implement a stack using queues.

We'll use two queues for this implementation.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// Basic Queue implementation (linked list based)

struct QNode {

int data;

struct QNode* next;

};

struct Queue {

struct QNode *front, *rear;

int size;

};

struct Queue* createQueue() {

struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));

q->front = q->rear = NULL;

 q->size = 0;

return q;

void enqueue(struct Queue* q, int value) {

struct QNode* newNode = (struct QNode*)malloc(sizeof(struct QNode));

newNode->data = value;

newNode->next = NULL;

if (q->rear == NULL) {

q->front = q->rear = newNode;

} else {

q->rear->next = newNode;

q->rear = newNode;

q->size++;

int dequeue(struct Queue* q) {

if (q->front == NULL) {

// Queue is empty, handle error or return a sentinel value

return -1;

struct QNode* temp = q->front;

int data = temp->data;

q->front = q->front->next;

if (q->front == NULL) {

q->rear = NULL;

free(temp);

q->size--;

return data;
}

int queueSize(struct Queue* q) {

return q->size;

bool isQueueEmpty(struct Queue* q) {

return q->front == NULL;

// Stack implementation using two queues

struct MyStack {

struct Queue* q1;

struct Queue* q2;

};

struct MyStack* myStackCreate() {

struct MyStack* obj = (struct MyStack*)malloc(sizeof(struct MyStack));

obj->q1 = createQueue();

obj->q2 = createQueue();

return obj;

void myStackPush(struct MyStack* obj, int x) {

// Always push to q1

enqueue(obj->q1, x);

int myStackPop(struct MyStack* obj) {

// Move all but the last element from q1 to q2

while (queueSize(obj->q1) > 1) {

 enqueue(obj->q2, dequeue(obj->q1));

// Pop the last element from q1 (which is the top of the stack)

int popped_val = dequeue(obj->q1);

// Swap q1 and q2 so q1 is always the main queue

struct Queue* temp = obj->q1;

obj->q1 = obj->q2;

obj->q2 = temp;

return popped_val;

int myStackTop(struct MyStack* obj) {

// Move all but the last element from q1 to q2

while (queueSize(obj->q1) > 1) {

enqueue(obj->q2, dequeue(obj->q1));

// Get the top element from q1

int top_val = obj->q1->front->data;

// Move the top element back to q2

enqueue(obj->q2, dequeue(obj->q1));

// Swap q1 and q2 so q1 is always the main queue

struct Queue* temp = obj->q1;

obj->q1 = obj->q2;

obj->q2 = temp;

return top_val;

}
bool myStackEmpty(struct MyStack* obj) {

return isQueueEmpty(obj->q1);

void myStackFree(struct MyStack* obj) {

while (!isQueueEmpty(obj->q1)) dequeue(obj->q1);

while (!isQueueEmpty(obj->q2)) dequeue(obj->q2);

free(obj->q1);

free(obj->q2);

free(obj);

int main() {

struct MyStack* obj = myStackCreate();

myStackPush(obj, 1);

myStackPush(obj, 2);

printf("Top: %d\n", myStackTop(obj)); // Expected: 2

printf("Pop: %d\n", myStackPop(obj)); // Expected: 2

printf("Empty: %s\n", myStackEmpty(obj) ? "true" : "false"); // Expected: false

printf("Pop: %d\n", myStackPop(obj)); // Expected: 1

printf("Empty: %s\n", myStackEmpty(obj) ? "true" : "false"); // Expected: true

myStackFree(obj);

return 0;

2. Design LRU Cache.

An LRU (Least Recently Used) Cache can be implemented using a Doubly Linked List and a Hash Map.
The doubly linked list maintains the order of usage (most recently used at the head, least recently
used at the tail), and the hash map provides O(1) average time complexity for get and put operations
by storing key-node mappings.

#include <stdio.h>
#include <stdlib.h>

// Node for Doubly Linked List

struct Node {

int key;

int value;

struct Node *prev;

struct Node *next;

};

// Hash Map (simple array of pointers for demonstration, a real hash table would be more complex)

// For simplicity, assuming keys are small integers for direct array indexing

#define MAX_CACHE_KEY 1000

struct LRUCache {

struct Node* head; // Most recently used

struct Node* tail; // Least recently used

struct Node* map[MAX_CACHE_KEY + 1]; // Maps key to Node

int capacity;

int size;

};

// Helper: Create a new node

struct Node* createNode(int key, int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->key = key;

newNode->value = value;

newNode->prev = NULL;

newNode->next = NULL;

return newNode;

}
// Helper: Add node to the head (make it MRU)

void addNode(struct LRUCache* cache, struct Node* node) {

node->next = cache->head;

node->prev = NULL;

if (cache->head != NULL) {

cache->head->prev = node;

cache->head = node;

if (cache->tail == NULL) { // If it was empty

cache->tail = node;

cache->map[node->key] = node;

cache->size++;

// Helper: Remove a node

void removeNode(struct LRUCache* cache, struct Node* node) {

if (node->prev != NULL) {

node->prev->next = node->next;

} else {

cache->head = node->next; // Node was head

if (node->next != NULL) {

node->next->prev = node->prev;

} else {

cache->tail = node->prev; // Node was tail

cache->map[node->key] = NULL; // Remove from map

cache->size--;
 free(node);

// Helper: Move an existing node to the head (make it MRU)

void moveToHead(struct LRUCache* cache, struct Node* node) {

removeNode(cache, node); // Temporarily remove (frees memory in this simple implementation,

need to re-create)

// A better implementation would just unlink and relink without freeing

struct Node* newNode = createNode(node->key, node->value); // Recreate for simplicity of

removeNode

addNode(cache, newNode);

struct LRUCache* lRUCacheCreate(int capacity) {

struct LRUCache* cache = (struct LRUCache*)malloc(sizeof(struct LRUCache));

cache->head = NULL;

cache->tail = NULL;

for (int i = 0; i <= MAX_CACHE_KEY; i++) {

cache->map[i] = NULL;

cache->capacity = capacity;

cache->size = 0;

return cache;

int lRUCacheGet(struct LRUCache* obj, int key) {

if (obj->map[key] != NULL) {

struct Node* node = obj->map[key];

// Move to head as it's recently used

if (node != obj->head) { // Only move if it's not already the head

// This simpler 'moveToHead' re-creates and adds, which is inefficient.

 // For a true O(1) move, it should just relink pointers.

removeNode(obj, node); // Remove old node (frees it)

struct Node* newNode = createNode(key, node->value);

addNode(obj, newNode);

obj->map[key] = newNode; // Update map with new node's address

return node->value;

return -1; // Not found

void lRUCachePut(struct LRUCache* obj, int key, int value) {

if (obj->map[key] != NULL) {

// Key already exists, update value and move to head

struct Node* node = obj->map[key];

node->value = value;

if (node != obj->head) {

removeNode(obj, node);

struct Node* newNode = createNode(key, value);

addNode(obj, newNode);

obj->map[key] = newNode;

} else {

// New key

if (obj->size >= obj->capacity) {

// Cache is full, remove LRU item (tail)

removeNode(obj, obj->tail);

// Add new node to head

struct Node* newNode = createNode(key, value);

addNode(obj, newNode);
 }

void lRUCacheFree(struct LRUCache* obj) {

struct Node* current = obj->head;

while (current != NULL) {

struct Node* temp = current;

current = current->next;

free(temp);

free(obj);

int main() {

struct LRUCache* lRUCache = lRUCacheCreate(2);

lRUCachePut(lRUCache, 1, 1); // cache is {1=1}

lRUCachePut(lRUCache, 2, 2); // cache is {1=1, 2=2}

printf("Get 1: %d\n", lRUCacheGet(lRUCache, 1)); // returns 1 (cache is {2=2, 1=1})

lRUCachePut(lRUCache, 3, 3); // LRU key 2 is evicted, cache is {1=1, 3=3}

printf("Get 2: %d\n", lRUCacheGet(lRUCache, 2)); // returns -1 (not found)

lRUCachePut(lRUCache, 4, 4); // LRU key 1 is