Practical C Programming with DSA Interview Questions

Using arithmetic or XOR through pointers: void swap(int *a, int *b) { if (a == b) return; *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } The a == b check matters because XOR swapping a variable with itself sets it to zero. In real code a temporary variable is clearer and just as fast.

Sum of digits raised to the number of digits equals the number. int isArmstrong(int n) { int digits = 0, t = n, sum = 0; while (t) { digits++; t /= 10; } t = n; while (t) { int d = t % 10, p = 1; for (int i = 0; i < digits; i++) p *= d; sum += p; t /= 10; } return sum == n; } For example 153 = 1 + 125 + 27.

Brian Kernighan's trick clears the lowest set bit each step. int countBits(unsigned int n) { int count = 0; while (n) { n &= n - 1; count++; } return count; } It runs once per set bit. GCC and Clang also offer __builtin_popcount(n), which uses a CPU instruction when available.

Use bit masks with shift operators. x |= (1u << n); // set bit n x &= ~(1u << n); // clear bit n x ^= (1u << n); // toggle bit n int bit = (x >> n) & 1u; // read bit n Use unsigned types so shifts are well defined. These operations are common in embedded code for configuring hardware registers.

A header guard stops a header from being included twice in one translation unit, which would cause redefinition errors. #ifndef MATH_UTILS_H #define MATH_UTILS_H int add(int a, int b); #endif Most compilers also support #pragma once, which is shorter but not part of the C standard.

A good development build is: gcc -std=c17 -Wall -Wextra -Wpedantic -g -O1 \ -fsanitize=address,undefined \ -o app main.c utils.c -Wall and -Wextra turn on useful warnings, -g adds debug symbols for gdb, and sanitizers catch memory errors and undefined behaviour at runtime. For release, drop sanitizers and use -O2.

Check the allocation and let the caller free it. int *makeSquares(size_t n) { int *arr = malloc(n * sizeof *arr); if (arr == NULL) return NULL; for (size_t i = 0; i < n; i++) { arr[i] = (int)(i * i); } return arr; } // caller int *a = makeSquares(10); if (a) { /* use */ free(a); }

Pass addresses so the function can modify the caller's variables. void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int main(void) { int x = 3, y = 7; swap(&x, &y); printf("%d %d\n", x, y); // 7 3 return 0; } C passes everything by value, so pointers are needed to change caller data.

A single block is cache friendly and easy to free. int (*grid)[cols] = malloc(rows * sizeof *grid); if (!grid) return -1; grid[2][3] = 5; free(grid); // array of row pointers alternative int **m = malloc(rows * sizeof *m); for (int i = 0; i < rows; i++) m[i] = calloc(cols, sizeof **m); for (int i = 0; i < rows; i++) free(m[i]); free(m); The first form uses a variable length array type.

Write a comparator that returns negative, zero or positive. int cmpDesc(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (y > x) - (y < x); } int arr[] = {4, 1, 9, 3}; qsort(arr, 4, sizeof arr[0], cmpDesc); Returning y - x can overflow, so the comparison form is safer.

Copy byte by byte through unsigned char pointers. void *my_memcpy(void *dest, const void *src, size_t n) { unsigned char *d = dest; const unsigned char *s = src; while (n--) { *d++ = *s++; } return dest; } memcpy must not be used for overlapping regions; memmove handles overlap by copying backwards when needed. Real libraries copy whole words for speed.

A free list of equal blocks avoids malloc in hot or embedded paths. #define BLOCKS 64 typedef union Block { union Block *next; char data[32]; } Block; static Block pool[BLOCKS]; static Block *freeList; void poolInit(void) { for (int i = 0; i < BLOCKS - 1; i++) pool[i].next = &pool[i + 1]; pool[BLOCKS - 1].next = NULL; freeList = pool; } void *poolAlloc(void) { Block *b = freeList; if (b) freeList = b->next; return b; } void poolFree(void *p) { Block *b = p; b->next = freeList; freeList = b; }

Swap characters from both ends moving inward. void reverse(char *s) { size_t n = strlen(s); if (n < 2) return; for (size_t i = 0, j = n - 1; i < j; i++, j--) { char t = s[i]; s[i] = s[j]; s[j] = t; } } Time O(n) and O(1) extra space. The string must be a modifiable array, not a literal.

Track the best sum ending here and the overall best. long maxSubarray(const int *a, int n) { long cur = a[0], best = a[0]; for (int i = 1; i < n; i++) { cur = (cur + a[i] > a[i]) ? cur + a[i] : a[i]; if (cur > best) best = cur; } return best; } Input {-2, 1, -3, 4, -1, 2, 1, -5, 4} returns 6 for subarray 4, -1, 2, 1.

Use three reversals. void rev(int *a, int l, int r) { while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; } } void rotate(int *a, int n, int k) { k %= n; if (k == 0) return; rev(a, 0, n - 1); rev(a, 0, k - 1); rev(a, k, n - 1); } For 1 2 3 4 5 with k = 2 the result is 4 5 1 2 3.

Sliding window with last seen positions. int longestUnique(const char *s) { int last[256]; for (int i = 0; i < 256; i++) last[i] = -1; int best = 0, start = 0; for (int i = 0; s[i]; i++) { unsigned char c = s[i]; if (last[c] >= start) start = last[c] + 1; last[c] = i; if (i - start + 1 > best) best = i - start + 1; } return best; } For abcabcbb it returns 3.

Walk both arrays with two indexes. void merge(const int *a, int n, const int *b, int m, int *out) { int i = 0, j = 0, k = 0; while (i < n && j < m) out[k++] = (a[i] <= b[j]) ? a[i++] : b[j++]; while (i < n) out[k++] = a[i++]; while (j < m) out[k++] = b[j++]; } Time O(n + m). Using <= keeps the merge stable.

Compare character by character until a difference or the end. int my_strcmp(const char *a, const char *b) { while (*a && *a == *b) { a++; b++; } return (unsigned char)*a - (unsigned char)*b; } Casting to unsigned char matches the standard behaviour for characters above 127. It returns zero if equal, negative if a sorts first and positive otherwise.

Count transitions from space to non-space. #include <ctype.h> int countWords(const char *s) { int count = 0, inWord = 0; for (; *s; s++) { if (isspace((unsigned char)*s)) { inWord = 0; } else if (!inWord) { inWord = 1; count++; } } return count; } This handles multiple spaces, tabs and leading or trailing spaces correctly.

Boyer-Moore voting algorithm. int majority(const int *a, int n) { int cand = 0, count = 0; for (int i = 0; i < n; i++) { if (count == 0) cand = a[i]; count += (a[i] == cand) ? 1 : -1; } return cand; } If a majority is not guaranteed, make a second pass to count cand and confirm it exceeds n/2.

Use an array of structs and the dot operator. typedef struct { int roll; char name[50]; float marks; } Student; void printToppers(const Student *s, int n) { for (int i = 0; i < n; i++) { if (s[i].marks > 75.0f) printf("%d %s %.1f\n", s[i].roll, s[i].name, s[i].marks); } } Passing a const pointer avoids copying the whole array.

Read character by character with fgetc. FILE *fp = fopen(path, "r"); if (!fp) { perror("fopen"); return 1; } long lines = 0, words = 0, chars = 0; int c, inWord = 0; while ((c = fgetc(fp)) != EOF) { chars++; if (c == '\n') lines++; if (isspace(c)) inWord = 0; else if (!inWord) { inWord = 1; words++; } } fclose(fp); printf("%ld %ld %ld\n", lines, words, chars); c is int so EOF can be distinguished from valid bytes.

Use a buffer and binary mode. int copyFile(const char *src, const char *dst) { FILE *in = fopen(src, "rb"); if (!in) return -1; FILE *out = fopen(dst, "wb"); if (!out) { fclose(in); return -1; } char buf[8192]; size_t n; while ((n = fread(buf, 1, sizeof buf, in)) > 0) { if (fwrite(buf, 1, n, out) != n) break; } fclose(in); return fclose(out); }

Look at the first byte of a known integer. int isLittleEndian(void) { uint32_t x = 1; unsigned char *p = (unsigned char *)&x; return p[0] == 1; } // using a union union { uint32_t i; unsigned char c[4]; } u = { 1 }; int little = (u.c[0] == 1); x86 and most ARM systems are little endian; network byte order is big endian.

An enum tag tells which member is valid. typedef enum { T_INT, T_FLOAT, T_STR } Tag; typedef struct { Tag tag; union { int i; float f; const char *s; } v; } Value; void printValue(Value x) { switch (x.tag) { case T_INT: printf("%d\n", x.v.i); break; case T_FLOAT: printf("%f\n", x.v.f); break; case T_STR: printf("%s\n", x.v.s); break; } }

C11 provides _Static_assert, and C23 adds static_assert as a keyword. #include <stdint.h> typedef struct { uint32_t timestamp; uint16_t reading; uint8_t sensorId; uint8_t flags; } Record; _Static_assert(sizeof(Record) == 8, "Record must be 8 bytes"); The build fails if someone adds a field or padding changes, which protects file formats and protocols.

Flip each next pointer while walking the list. typedef struct Node { int data; struct Node *next; } Node; Node *reverse(Node *head) { Node *prev = NULL, *cur = head; while (cur) { Node *next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } Time O(n), space O(1). The returned prev is the new head.

A pointer to pointer handles the empty list without special cases. int append(Node **head, int value) { Node *n = malloc(sizeof *n); if (!n) return -1; n->data = value; n->next = NULL; while (*head) head = &(*head)->next; *head = n; return 0; } Call it as append(&head, 5). Keep a tail pointer if you append often.

A dummy node keeps the code simple. Node *mergeSorted(Node *a, Node *b) { Node dummy = {0, NULL}; Node *tail = &dummy; while (a && b) { if (a->data <= b->data) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return dummy.next; } It reuses existing nodes in O(n + m) time.

Floyd's algorithm in two phases. Node *cycleStart(Node *head) { Node *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } } return NULL; }

Move a lead pointer n steps ahead, then move both together. Node *removeNthFromEnd(Node *head, int n) { Node dummy = {0, head}; Node *fast = &dummy, *slow = &dummy; for (int i = 0; i <= n; i++) fast = fast->next; while (fast) { fast = fast->next; slow = slow->next; } Node *del = slow->next; slow->next = del->next; free(del); return dummy.next; } The dummy node handles removing the head.

Track the top index and check bounds. #define MAX 100 typedef struct { int data[MAX]; int top; } Stack; void init(Stack *s) { s->top = -1; } int push(Stack *s, int x) { if (s->top == MAX - 1) return -1; s->data[++s->top] = x; return 0; } int pop(Stack *s, int *out) { if (s->top < 0) return -1; *out = s->data[s->top--]; return 0; } Returning an error code avoids undefined reads on empty stacks.

Push opening brackets and match on closing ones. int isBalanced(const char *s) { char st[1000]; int top = -1; for (; *s; s++) { char c = *s; if (c == '(' || c == '[' || c == '{') { if (top == 999) return 0; st[++top] = c; } else if (c == ')' || c == ']' || c == '}') { if (top < 0) return 0; char o = st[top--]; if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return 0; } } return top == -1; }

Use modulo arithmetic and a count. #define CAP 8 typedef struct { int a[CAP]; int front, rear, count; } Queue; int enqueue(Queue *q, int x) { if (q->count == CAP) return -1; q->a[q->rear] = x; q->rear = (q->rear + 1) % CAP; q->count++; return 0; } int dequeue(Queue *q, int *x) { if (q->count == 0) return -1; *x = q->a[q->front]; q->front = (q->front + 1) % CAP; q->count--; return 0; }

Keep indexes of elements still waiting for a greater value. void nextGreater(const int *a, int n, int *res) { int st[n], top = -1; for (int i = 0; i < n; i++) { res[i] = -1; while (top >= 0 && a[st[top]] < a[i]) { res[st[top--]] = a[i]; } st[++top] = i; } } For 4 5 2 25 the result is 5 25 25 -1, in O(n) time.

An array of linked list heads with djb2 hashing. #define SIZE 1024 typedef struct Entry { char *key; int val; struct Entry *next; } Entry; Entry *table[SIZE]; unsigned long hash(const char *s) { unsigned long h = 5381; int c; while ((c = (unsigned char)*s++)) h = h * 33 + c; return h % SIZE; } void put(const char *k, int v) { unsigned long i = hash(k); for (Entry *e = table[i]; e; e = e->next) if (strcmp(e->key, k) == 0) { e->val = v; return; } Entry *e = malloc(sizeof *e); e->key = strdup(k); e->val = v; e->next = table[i]; table[i] = e; }

Push digits and apply operators to the top two values. int evalPostfix(const char *s) { int st[100], top = -1; for (; *s; s++) { if (isdigit((unsigned char)*s)) st[++top] = *s - '0'; else if (strchr("+-*/", *s)) { int b = st[top--], a = st[top--]; switch (*s) { case '+': st[++top] = a + b; break; case '-': st[++top] = a - b; break; case '*': st[++top] = a * b; break; case '/': st[++top] = a / b; break; } } } return st[top]; } 23*5+ evaluates to 11.

Go left or right until an empty spot is found. typedef struct TNode { int key; struct TNode *left, *right; } TNode; TNode *insert(TNode *root, int key) { if (root == NULL) { TNode *n = malloc(sizeof *n); n->key = key; n->left = n->right = NULL; return n; } if (key < root->key) root->left = insert(root->left, key); else if (key > root->key) root->right = insert(root->right, key); return root; } Duplicates are ignored here.

Height is one plus the larger subtree height. int height(const TNode *root) { if (root == NULL) return 0; int lh = height(root->left); int rh = height(root->right); return 1 + (lh > rh ? lh : rh); } This counts nodes on the longest root to leaf path; return -1 for empty trees if height is defined in edges. Time O(n).

Use a queue and a visited array. void bfs(int n, int adj[n][n], int start) { int visited[n], queue[n], front = 0, rear = 0; for (int i = 0; i < n; i++) visited[i] = 0; visited[start] = 1; queue[rear++] = start; while (front < rear) { int u = queue[front++]; printf("%d ", u); for (int v = 0; v < n; v++) { if (adj[u][v] && !visited[v]) { visited[v] = 1; queue[rear++] = v; } } } }

Use the BST order to walk down from the root. TNode *lcaBST(TNode *root, int a, int b) { while (root) { if (a < root->key && b < root->key) root = root->left; else if (a > root->key && b > root->key) root = root->right; else return root; } return NULL; } The first node where a and b split is the LCA. Time O(h) and space O(1).

Two small functions cover most uses. int parent[MAXN], rnk[MAXN]; void makeSet(int n) { for (int i = 0; i < n; i++) { parent[i] = i; rnk[i] = 0; } } int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } int unite(int a, int b) { a = find(a); b = find(b); if (a == b) return 0; if (rnk[a] < rnk[b]) { int t = a; a = b; b = t; } parent[b] = a; if (rnk[a] == rnk[b]) rnk[a]++; return 1; }

Use an overflow safe midpoint. int binarySearch(const int *a, int n, int target) { int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == target) return mid; if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } Time O(log n). The array must be sorted in ascending order.

Partition around the last element, then sort both sides. void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } int partition(int *a, int lo, int hi) { int pivot = a[hi], i = lo; for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(&a[i++], &a[j]); swap(&a[i], &a[hi]); return i; } void quickSort(int *a, int lo, int hi) { if (lo < hi) { int p = partition(a, lo, hi); quickSort(a, lo, p - 1); quickSort(a, p + 1, hi); } }

Split, sort halves, merge with a temp buffer. void merge(int *a, int l, int m, int r, int *tmp) { int i = l, j = m + 1, k = l; while (i <= m && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; while (i <= m) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (k = l; k <= r; k++) a[k] = tmp[k]; } void mergeSort(int *a, int l, int r, int *tmp) { if (l >= r) return; int m = l + (r - l) / 2; mergeSort(a, l, m, tmp); mergeSort(a, m + 1, r, tmp); merge(a, l, m, r, tmp); }

Iterate capacity backwards so each item is used once. int knapsack(const int *wt, const int *val, int n, int W) { int dp[W + 1]; for (int c = 0; c <= W; c++) dp[c] = 0; for (int i = 0; i < n; i++) { for (int c = W; c >= wt[i]; c--) { int take = dp[c - wt[i]] + val[i]; if (take > dp[c]) dp[c] = take; } } return dp[W]; } Time O(nW), space O(W).

Classic 2D DP. int lcs(const char *a, const char *b) { int n = strlen(a), m = strlen(b); int dp[n + 1][m + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i == 0 || j == 0) dp[i][j] = 0; else if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]; } } return dp[n][m]; } For ABCBDAB and BDCABA it returns 4.