C Programming with DSA Interview Questions in Pune

Show answer

Comparing each node only with its children is wrong, because a deeper node can break the rule. Pass a valid range down: the left child must be in (min, node value) and the right child in (node value, max), starting with the full range of long long. Alternatively, do an in-order traversal and check values are strictly increasing. Both are O(n).

A strlen call crashes on a buffer received from a network packet. What is wrong?

Arrays and StringsMedium

Show answer

Network data is not guaranteed to be null terminated, so strlen keeps reading past the buffer until it hits a zero byte or invalid memory. Always track the received byte count and use length-aware functions such as memchr, strnlen or memcpy with explicit sizes. If you need a C string, allocate one extra byte and add the terminator yourself after checking the length.

Rotate an array to the right by k positions in O(n) time and O(1) space.

Arrays and StringsMedium

Show answer

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.

Tell me about a time you fixed a memory leak.

Show answer

Situation: a C based telemetry agent grew by 200 MB a day on customer servers. Task: find and fix the leak quickly. Action: I reproduced it with recorded traffic under Valgrind and found that an error path returned early without freeing a parsed message buffer. I restructured the function with a single cleanup label and added a leak check job to CI. Result: memory stayed flat for weeks after the patch.

Find the lowest common ancestor of two nodes in a binary search tree.

Show answer

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).

Why is a circular queue better than a simple array queue?

Stacks, Queues and HashingMedium

Show answer

In a simple array queue, the front moves forward as elements are removed, so the space before it is wasted and the queue appears full even when there is room. A circular queue wraps indexes using modulo, so rear = (rear + 1) % size reuses freed slots. You track fullness with a count or by keeping one slot empty to distinguish full from empty.

Write a function that swaps two integers using pointers.

Pointers and Memory ManagementEasy

Show answer

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.

What is a monotonic stack?

Stacks, Queues and HashingMedium

Show answer

A monotonic stack keeps elements in increasing or decreasing order by popping elements that break the order before pushing a new one. Each element is pushed and popped at most once, so problems run in O(n). It solves next greater element, daily temperatures, stock span and largest rectangle in a histogram, which would otherwise need nested loops.

Implement merge sort in C.

Show answer

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); }

Write a C program that counts lines, words and characters in a file.

Structures, Unions and File HandlingMedium

Show answer

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.

What is the time complexity of common linked list operations?

Linked ListsEasy

Show answer

Access or search by value is O(n). Insert or delete at the head is O(1). Insert at the tail is O(1) if you keep a tail pointer, otherwise O(n). Deleting a given node is O(1) in a doubly linked list but O(n) in a singly linked list, since you must find the previous node. Finding length is O(n) unless you store a count.

An interview asks for the minimum number of coins to make an amount. How do you approach it?

Sorting, Searching and Dynamic ProgrammingEasy

Show answer

Greedy fails for some coin sets, such as coins 1, 3, 4 with amount 6, where greedy gives three coins but two coins of 3 is optimal. Use DP: dp[0] = 0 and dp[x] = 1 + min over coins c of dp[x - c], filling from 1 to the amount. Time is O(amount times coins) and space O(amount). Report -1 if the amount cannot be formed.

A doubly linked list delete function leaves the list broken when deleting the head. What is missing?

Linked ListsMedium

Show answer

When deleting the head there is no previous node, so the head pointer itself must move to head->next, and the new head's prev must be set to NULL. Similarly, deleting the tail needs the new tail's next set to NULL. The fix is to check node->prev and node->next for NULL and update head or tail pointers accordingly, or use a sentinel node to avoid these cases.

What is a hash table and how are collisions handled?

Stacks, Queues and HashingMedium

Show answer

A hash table maps keys to array slots using a hash function, giving O(1) average insert, search and delete. Collisions happen when two keys map to the same slot. Separate chaining stores a linked list per slot. Open addressing probes for another free slot using linear probing, quadratic probing or double hashing. Keep the load factor low and resize when it grows to maintain speed.

Write binary search in C that returns the index of the target or -1.

Show answer

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.

Tell me about a time you debugged a hard crash in C code.

C Basics, Data Types and OperatorsMedium

Show answer

Situation: our data logger crashed randomly after hours of running. Task: find the cause before a client demo. Action: I rebuilt with AddressSanitizer, ran a long stress test and found a buffer overflow in a string copy that corrupted a nearby pointer. I replaced it with a bounded snprintf and added a length check. Result: the logger ran for a week without a crash and we added sanitizer builds to CI.

Tell me about a time you optimised an algorithm in a real project.

Show answer

Situation: a C tool comparing two inventory files of 5 lakh rows took 25 minutes. Task: make it run in a nightly window of 2 minutes. Action: I found nested loops doing O(n squared) matching, sorted both files with qsort and merged them with two pointers, which is O(n log n). Result: runtime fell to 40 seconds, and the approach became our standard for file reconciliation jobs.

What is a queue and what are its variants?

Stacks, Queues and HashingEasy

Show answer

A queue is first in, first out with enqueue at the rear and dequeue at the front, both O(1). Variants are the circular queue, which reuses array space; the deque, which allows insertion and removal at both ends; and the priority queue, which removes the highest priority element first. Queues are used in BFS, task scheduling, print spooling and buffering data between producers and consumers.

Write BFS on a graph stored as an adjacency matrix.

Sorting, Searching and Dynamic ProgrammingHard

Show answer

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; } } } }

Write a C function to count words in a sentence.

Arrays and StringsEasy

Show answer

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.

A program that writes logs with fprintf loses the last lines when it crashes. Why, and how do you fix it?

Structures, Unions and File HandlingMedium

Show answer

stdio streams are buffered, so fprintf stores data in memory and writes it to disk only when the buffer fills, the file closes or fflush is called. A crash loses whatever is still in the buffer. Call fflush after important log lines, set line buffering with setvbuf(fp, NULL, _IOLBF, 0) or write critical messages to unbuffered stderr. For durability on disk, add fsync on POSIX systems.

A DP solution for a large grid uses too much memory. How can you reduce it?

Show answer

Many grid DPs only need the previous row to compute the current one, so replace the 2D table with two 1D arrays or even one array updated in place, cutting memory from O(rows times cols) to O(cols). For knapsack, iterate capacity backwards in a single array. If you also need to reconstruct the path, store compact choice bits or use Hirschberg's divide and conquer technique.

What is the difference between malloc, calloc, realloc and free?

Pointers and Memory ManagementEasy

Show answer

malloc(size) allocates uninitialised memory. calloc(n, size) allocates memory for n elements and sets all bytes to zero, and it checks n times size for overflow. realloc(ptr, size) resizes a block, possibly moving it, and returns the new address. free(ptr) releases memory back to the allocator. All allocators return NULL on failure, so always check the result.

A loop that sums large numbers gives a negative result. What is happening?

C Basics, Data Types and OperatorsMedium

Show answer

The sum overflowed the range of int, and signed overflow in C is undefined behaviour, often wrapping to a negative value. Use a wider type like long long or int64_t for the accumulator, check before adding with a condition like if (sum > INT_MAX - x), or use compiler builtins such as __builtin_add_overflow. Compile with -fsanitize=undefined to catch it during testing.

Tell me about a project where you worked with files or binary data in C.

Structures, Unions and File HandlingMedium

Show answer

Situation: in my final year project we logged GPS data on a microcontroller SD card. Task: store records reliably with small memory. Action: I designed a packed 16 byte record with fixed-width types, wrote it with a checksum, flushed every ten records and wrote a PC tool to decode the file. Result: we logged a full day with no corruption and could replay any trip.

What is backtracking? Give an example.

Show answer

Backtracking builds a solution step by step and abandons a path as soon as it cannot lead to a valid answer, then tries the next option. It explores a search tree with pruning. Examples are N-Queens, Sudoku, generating permutations and subsets, and maze path finding. Time can be exponential, so good pruning and ordering choices matter a lot.

After calling realloc, the program sometimes crashes. What could be wrong?

Show answer

realloc may move the block and returns the new address, so old pointers to the block become invalid. Writing ptr = realloc(ptr, n) also leaks the original memory if realloc fails and returns NULL. Store the result in a temporary pointer, check for NULL, then assign. Make sure no other pointers still refer to the old location after a successful move.

What is the sliding window technique?

Arrays and StringsMedium

Show answer

Sliding window solves problems on contiguous subarrays or substrings by keeping a window with two indexes and moving them forward instead of rechecking every subarray. A fixed window finds things like the maximum sum of k elements, while a variable window expands and shrinks, as in the longest substring without repeating characters. It turns O(n squared) brute force into O(n).

Implement quicksort in C using Lomuto partition.

Show answer

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); } }

Find the height of a binary tree in C.

Trees and GraphsEasy

Show answer

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).

Allocate and free a dynamic 2D array of rows by cols in C.

Show answer

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.

Compare quicksort, merge sort and heap sort.

Show answer

Quicksort is O(n log n) on average and very fast in practice with in-place partitioning, but O(n squared) in the worst case with poor pivots and not stable. Merge sort is always O(n log n) and stable but needs O(n) extra memory. Heap sort is O(n log n) worst case and in place but not stable and slower due to poor cache use. C's qsort is usually a tuned hybrid.

Count the number of islands in a grid of land and water cells. What approach do you take?

Show answer

Treat each land cell as a graph node connected to its four neighbours. Scan the grid, and when you find unvisited land, increment the count and flood fill with DFS or BFS to mark the whole island visited. Time and space are O(rows times cols). For very large grids, use iterative BFS to avoid recursion depth issues, or union-find.

How do you check whether a linked list is a palindrome in O(1) extra space?

Linked ListsMedium

Show answer

Find the middle with slow and fast pointers, reverse the second half in place, then compare the first half and the reversed second half node by node. Finally reverse the second half again to restore the list, which interviewers appreciate. Time is O(n) and extra space is O(1). A simpler O(n) space approach copies values into an array or stack first.

A function returns the address of a local array and the caller gets wrong data. Why?