Medium C Programming with DSA Interview Questions

Show answer

auto is the default for local variables, stored on the stack with block lifetime. register hints the variable should live in a CPU register, and its address cannot be taken. static gives a local variable lifetime for the whole program, or limits a global to its file. extern declares a variable defined in another file. Storage class decides scope, lifetime and linkage.

What is the difference between a macro and an inline function?

Show answer

A macro is plain text substitution by the preprocessor, with no type checking, and arguments may be evaluated more than once, so SQUARE(i++) misbehaves. An inline function is a real function with type checks and single evaluation of arguments, which the compiler may expand in place for speed. Prefer static inline functions and use macros only for things like conditional compilation.

What is the volatile qualifier used for in C?

Show answer

volatile tells the compiler that a variable can change outside normal program flow, for example a hardware register, a variable changed in an interrupt handler or memory shared with another device. The compiler must read it from memory every time and cannot cache it in a register or remove repeated reads. It does not provide atomicity or thread safety on its own.

What is the difference between const int p, int const p and const int *const p?

Show answer

const int *p is a pointer to a constant int: you cannot change the value through p, but p can point elsewhere. int *const p is a constant pointer: p always points to the same address, but the value can change. const int *const p fixes both. Read declarations from right to left to understand them. const pointers to data are common in function parameters.

Explain the memory layout of a C program.

Show answer

From low to high address, a typical process has the text segment holding code, the initialised data segment for globals and statics with values, BSS for uninitialised or zero globals, the heap growing upward for malloc memory, and the stack growing downward for function frames and local variables. Knowing this helps explain stack overflow, memory leaks and where variables live.

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

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.

Two source files both define a global variable named count and the build fails. How do you fix it?

Show answer

Each global may be defined only once. Define it in one .c file, such as int count = 0;, and declare it in a shared header as extern int count;, which other files include. If the variable should be private to each file, mark it static in both files instead. Since GCC 10, -fno-common is default, so duplicate tentative definitions also fail to link.

Write C code to count the number of set bits in an integer.

Show answer

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.

How do you set, clear and toggle a particular bit in C?

Show answer

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.

Which gcc flags would you use to build and debug a C program safely?

Show answer

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.

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

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.

Explain pointer arithmetic in C.

Show answer

Adding an integer to a pointer moves it by that many elements, not bytes, so p + 1 on an int pointer advances by sizeof(int). Subtracting two pointers into the same array gives the number of elements between them as ptrdiff_t. Arithmetic is valid only within an array or one past its end; going further is undefined behaviour. Void pointer arithmetic is not allowed in standard C.

What is the difference between an array and a pointer?

Show answer

An array is a block of contiguous elements whose size is fixed and known to the compiler; sizeof gives the full array size. A pointer is a variable holding an address; sizeof gives the pointer size. An array name decays to a pointer to its first element in most expressions, but it cannot be reassigned. When passed to a function, an array always becomes a pointer, losing its length.

What is a memory leak and how do you detect it?

Show answer

A memory leak happens when dynamically allocated memory is never freed and the last pointer to it is lost, so the program keeps growing in memory use. Long running services and embedded systems eventually fail. Detect leaks with Valgrind memcheck, AddressSanitizer with LeakSanitizer or allocation tracking wrappers. Prevent them with clear ownership rules and a single cleanup path per function.

What is a function pointer and where is it used?

Show answer

A function pointer stores the address of a function, declared like int (*op)(int, int) = add;, and called with op(2, 3). It enables callbacks such as the comparator in qsort, dispatch tables replacing long switch statements, plugin interfaces and state machines in embedded code. Using typedef makes function pointer types much more readable.

What is a double pointer and when do you need it?

Show answer

A double pointer, such as int **pp, stores the address of a pointer. It is needed when a function must change the caller's pointer itself, for example inserting at the head of a linked list or allocating memory inside a function and returning it through a parameter. It is also used for dynamic 2D arrays and arrays of strings, like char **argv.

A program crashes with a segmentation fault. How do you find the cause?

Show answer

Compile with -g and run under gdb; when it crashes, use bt to see the call stack and print variables in the failing frame. Common causes are dereferencing NULL, using freed memory, out-of-bounds array access and stack overflow from deep recursion. Building with -fsanitize=address gives a precise report of the bad access and where the memory was allocated or freed.

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

Show answer

Local arrays live on the stack and are destroyed when the function returns, so the returned pointer is dangling and later calls overwrite that memory. Fix it by having the caller pass a buffer and its size, allocating with malloc and documenting that the caller must free it, or using a static buffer, which is not thread safe. Compilers warn about this with -Wreturn-local-addr.

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.

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.

Use qsort with a function pointer to sort an array of integers in descending order.

Show answer

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.

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.

How do you write C code that other developers can maintain?

Show answer

Situation: I inherited a 3000 line C file with global variables everywhere. Task: make it safe to extend. Action: I split it into modules with clear headers, made helpers static, documented ownership of every allocated pointer, added unit tests with a small framework and followed a consistent style enforced by clang-format. Result: new features took half the time and code reviews became much faster.

What is the difference between strcpy, strncpy and snprintf for copying strings?

Show answer

strcpy copies until the null terminator with no bounds check, so it can overflow. strncpy limits the count but does not add a terminator if the source is too long and pads with zeros otherwise, which surprises many developers. snprintf(dst, size, "%s", src) always terminates and returns the length it wanted, so you can detect truncation. Prefer snprintf or a checked helper.

How is a 2D array stored in memory in C?

Show answer

C stores multidimensional arrays in row-major order: all elements of row 0, then row 1 and so on, in one contiguous block. Element a[i][j] of an array with C columns is at offset i * C + j. Traversing row by row is cache friendly and much faster than column by column for large matrices. When passing a 2D array to a function, every dimension except the first must be specified.

What is the sliding window technique?

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

What is a prefix sum array and why is it useful?

Show answer

A prefix sum array stores pre[i] = sum of elements from index 0 to i-1. Then the sum of any range from l to r is pre[r + 1] - pre[l] in O(1) after O(n) preprocessing. It is used for range sum queries, counting subarrays with a given sum together with a hash map, and 2D versions for matrix region sums.

Explain Kadane's algorithm.

Show answer

Kadane's algorithm finds the maximum sum contiguous subarray in O(n). It keeps the best sum ending at the current index: cur = max(a[i], cur + a[i]), and updates the global best with best = max(best, cur). If the running sum becomes worse than starting fresh, it starts a new subarray. Initialise with the first element to handle arrays where all numbers are negative.

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

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.

You need to find whether any two numbers in an unsorted array sum to a target. Compare approaches.

Show answer

Brute force checks all pairs in O(n squared). Sorting first with qsort and then using two pointers takes O(n log n) time and O(1) extra space but loses original indexes. A hash set gives O(n) time with O(n) memory; in C you would implement a simple open addressing table. Choose based on size, memory limits and whether indexes must be returned.

Write Kadane's algorithm in C.

Show answer

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.

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

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.

Find the length of the longest substring without repeating characters in C.

Show answer

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.

Describe how you approach a coding problem you have never seen before.

Show answer

Situation: in a coding round I got an unfamiliar matrix problem. Task: solve it within 30 minutes. Action: I restated the problem, worked through a small example by hand, explained a brute force first, then spotted that a prefix sum would remove repeated work and coded it in C while talking through edge cases like empty rows. Result: I finished in 25 minutes and the interviewer praised my clear reasoning.

What is structure padding and how can you reduce it?

Show answer

The compiler inserts padding bytes between members so each one is aligned, which can make a struct larger than the sum of its members. struct { char a; int b; char c; } is usually 12 bytes instead of 6. Reduce padding by ordering members from largest to smallest alignment. Packing with __attribute__((packed)) removes padding but can slow access or fault on some CPUs.

What are bit fields in C?

Show answer

Bit fields let struct members use a specified number of bits, such as unsigned int ready : 1; unsigned int mode : 3;, which saves memory for flags. They are common in embedded code and protocol headers. However, bit ordering, padding and whether plain int bit fields are signed are implementation defined, so for portable hardware register or wire format access, explicit masks and shifts are safer.

What is the difference between text and binary file modes?

Show answer

In text mode, the C library may translate line endings, for example \r\n on Windows to \n, and a Ctrl+Z byte can mean end of file. Binary mode reads and writes bytes exactly as stored. Use text mode with fprintf and fgets for human readable files and binary mode with fread and fwrite for images, structs and any exact byte format. On Linux both behave the same.

What is the difference between fseek, ftell and rewind?

Show answer

fseek(fp, offset, origin) moves the file position relative to SEEK_SET, SEEK_CUR or SEEK_END. ftell(fp) returns the current position as a long. rewind(fp) moves to the start and clears error flags. Together they let you find file size, jump to a record in a fixed-size record file or re-read data. For very large files, use fseeko and ftello with off_t.

A program reads a file with while (!feof(fp)) and processes the last line twice. Why?

Show answer

feof() becomes true only after a read has already failed at end of file. The loop checks feof before reading, so the final failed read leaves the old buffer content, which is processed again. Loop on the read function's return value instead, such as while (fgets(line, sizeof line, fp) != NULL), and check ferror after the loop.

You need to update one record in the middle of a large binary file without rewriting it all. How?

Show answer

Use fixed-size records so each one starts at index times record size. Open the file in r+b mode, fseek to that offset, fwrite the new record and fflush. Read it back to verify if needed. For crash safety, write to a temporary file and rename, or keep a simple journal. Databases like SQLite solve this robustly if requirements grow.

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

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.

Copy a file in C using fread and fwrite.

Show answer

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

Write code to check whether the machine is little endian or big endian.

Show answer

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.

Use a tagged union to store either an int, a float or a string value.

Show answer

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

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

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.

How do you handle a situation where requirements change late in a project?

Show answer

Situation: two weeks before release, the client asked to add a new field to our device's binary log format. Task: add it without breaking older files. Action: I explained the risk, added a version byte to the header, wrote a reader that handled both versions and tested with old and new samples. Result: we shipped on time and older devices kept working without a firmware update.

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

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.

How does Floyd's cycle detection algorithm work?

Linked ListsMedium

Show answer

Use a slow pointer moving one step and a fast pointer moving two steps. If the list has a cycle, the fast pointer eventually meets the slow one inside the loop; if fast reaches NULL, there is no cycle. To find the cycle start, reset one pointer to head and move both one step at a time; they meet at the start. It uses O(n) time and O(1) space.

Why is a dummy or sentinel node useful in linked list code?

Linked ListsMedium

Show answer

A dummy node placed before the real head removes special cases for an empty list or for inserting and deleting at the head, because every real node then has a previous node. Code for merging lists, removing elements and partitioning becomes shorter and less error prone. At the end, return dummy.next as the new head. It costs one extra node.

How would you detect if two linked lists intersect and find the intersection node?

Linked ListsMedium

Show answer

Two lists intersect if they share a node by address, not just value. Compute both lengths, advance the longer list by the difference, then move both together until the pointers are equal. A neat trick is to walk pointer a through list A then B, and pointer b through B then A; they meet at the intersection or both reach NULL. Both are O(m + n) time and O(1) space.

Your linked list program crashes when deleting the last node. What do you check?

Linked ListsMedium

Show answer

Check that the previous node's next pointer is set to NULL after freeing the last node, that the tail pointer is updated if you keep one and that you do not access the node after free. Also handle the case of a one-node list where head itself must become NULL, which requires passing a pointer to the head pointer. Run the code under AddressSanitizer to find invalid accesses.

Freeing a linked list causes a crash. What is the common mistake?

Linked ListsMedium

Show answer

A common bug is freeing the current node and then reading current->next, which is a use-after-free. Save the next pointer first, then free the node, then move on. Also make sure no node is freed twice and that the caller's head pointer is set to NULL afterwards so it is not used again. Valgrind or AddressSanitizer points to the exact line.

Reverse a singly linked list iteratively in C.

Linked ListsMedium

Show answer

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.

Insert a node at the end of a singly linked list using a double pointer.

Linked ListsMedium

Show answer

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.

Merge two sorted linked lists into one sorted list.

Linked ListsMedium

Show answer

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.

Tell me about a time you explained a complex data structure to your team.

Linked ListsMedium

Show answer

Situation: our team needed an LRU cache in a C service and several members had not built one. Task: align everyone before coding. Action: I drew the hash table and doubly linked list on a whiteboard, walked through get and put with a small example and shared a short test suite covering edge cases. Result: the team implemented it in two days with no major review issues.

How do you prioritise between writing fast code and readable code?

Linked ListsMedium

Show answer

Situation: a teammate replaced a clear linked list loop with a complex XOR trick to save memory. Task: decide what to keep. Action: I measured memory and speed, found the saving was under one percent and proposed keeping the readable version with a comment, while optimising a real hotspot the profiler showed. Result: we kept clear code and got a measurable 20 percent speedup elsewhere.

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

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

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.

What is a hash table and how are collisions handled?

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.

What is a monotonic stack?

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.

What is a heap and how does it implement a priority queue?

Show answer

A binary heap is a complete binary tree stored in an array where every parent is smaller than its children for a min heap, or larger for a max heap. For index i, children are at 2i + 1 and 2i + 2. Insert adds at the end and sifts up, and extracting the top swaps it with the last element and sifts down, both O(log n). Building a heap from an array takes O(n).

How do you convert an infix expression to postfix?

Show answer

Use the shunting yard algorithm with an operator stack. Output operands directly. For an operator, pop operators of higher precedence, or equal precedence if left associative, to the output, then push it. Push '(' and on ')' pop until the matching '('. At the end, pop all remaining operators. For example a + b * c becomes a b c * +. Postfix is easy to evaluate with a stack.

Your stack implementation crashes with deep recursion converted to an explicit stack. What would you check?

Show answer

Check for stack overflow of your own array: push must verify top < capacity and either fail or grow the array with realloc. Check pop on an empty stack returns an error instead of reading index -1. If using realloc, make sure no pointers into the old buffer are kept. Add asserts in debug builds and test with the largest expected input.

You need to look up 10 lakh user ids quickly in a C program. What structure do you choose?

Show answer

A hash table gives O(1) average lookup. Size it so the load factor stays under about 0.7, choose a good hash for the key type and use open addressing for better cache behaviour. If ids are dense integers in a known range, a plain array or bitmap is even faster. If the data is static, a sorted array with binary search is simple and memory efficient at O(log n).

A hash table becomes slow as more data is inserted. What is wrong?

Show answer

The load factor has grown, so chains get long or open addressing probes become long, turning O(1) into nearly O(n). Another cause is a poor hash function clustering keys into few buckets. Fix it by resizing to roughly double capacity and rehashing when the load factor crosses a threshold, and by using a better hash function. Measure the longest chain to confirm.

Implement a circular queue with enqueue and dequeue in C.

Show answer

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

Find the next greater element for every array element using a monotonic stack.

Show answer

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.

Evaluate a postfix expression of single digit numbers using a stack.

Show answer

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.

Tell me about a time you chose the right data structure under pressure.

Show answer

Situation: during a hackathon our C route planner was too slow to answer queries live. Task: fix it within a few hours. Action: I profiled it, found repeated linear searches of a list of stops and replaced them with a hash table keyed by stop id, plus a queue for BFS. Result: queries went from 4 seconds to 30 ms and we won second place.

You need to implement a queue using two stacks. How does it work and what is its cost?

Show answer

Use an in-stack for enqueue and an out-stack for dequeue. Enqueue always pushes to the in-stack. Dequeue pops from the out-stack, and only when it is empty moves all elements from the in-stack to it, which reverses their order so the oldest comes out first. Each element moves at most twice, so operations are O(1) amortised even though a single dequeue can be O(n).

Why are self-balancing trees like AVL and red-black trees needed?

Show answer

A plain BST can degrade to a linked list with O(n) operations when data arrives in sorted order. AVL trees keep the height difference of subtrees at most one using rotations, giving faster lookups. Red-black trees use colour rules with looser balance, so inserts and deletes need fewer rotations. Both guarantee O(log n). Red-black trees are used in the Linux kernel, C++ std::map and Java TreeMap.

How are graphs represented in C?

Show answer

An adjacency matrix is a V by V array where cell [u][v] marks an edge; it gives O(1) edge checks but uses O(V squared) memory, suiting dense graphs. An adjacency list stores for each vertex a list or dynamic array of neighbours, using O(V + E) memory, which suits sparse real world graphs like road or social networks. Weighted graphs store the weight with each edge.

Compare BFS and DFS.

Show answer

BFS explores level by level using a queue and finds the shortest path in unweighted graphs. DFS goes deep along one path using recursion or a stack, and suits cycle detection, topological sort, connected components and backtracking. Both run in O(V + E). BFS may use more memory on wide graphs, while recursive DFS can overflow the call stack on very deep graphs.

A recursive tree traversal crashes on a very large, skewed tree. How do you fix it?

Show answer

A skewed tree has height close to n, so recursion depth becomes huge and overflows the call stack. Convert the traversal to an iterative version using an explicit stack allocated on the heap, or use Morris traversal for in-order with O(1) extra space. Long term, use a self-balancing tree so height stays around log n.

You need to find the shortest route between two cities on a map with distances. Which algorithm do you use and why?

Show answer

Road distances are non-negative, so Dijkstra's algorithm with a min heap is the right choice, giving O((V + E) log V). If you only need one target, stop when it is popped from the heap. For very large maps, A star with a straight-line distance heuristic explores fewer nodes. If some edges had negative costs, Bellman-Ford would be needed.

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 would you check whether a binary tree is a valid BST?

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

Write BFS on a graph stored as an adjacency matrix.

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

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

Tell me about a project where you applied graph algorithms.

Show answer

Situation: our college fest needed a campus navigation kiosk. Task: give the shortest walking route between buildings. Action: I modelled buildings and paths as a weighted graph in C, implemented Dijkstra with a binary heap and added a simple text interface showing turn by turn directions. Result: the kiosk answered routes instantly for 40 locations and over 2000 visitors used it.

What is a trie and when is it better than a hash table?

Show answer

A trie is a tree where each edge represents a character, so words sharing a prefix share a path. Lookup and insert take O(L) for a word of length L, independent of how many words are stored. It beats a hash table for prefix queries such as autocomplete, spell checking and longest prefix matching in IP routing. The trade-off is higher memory use from many child pointers.

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.

What is dynamic programming?

Show answer

Dynamic programming solves problems that have overlapping subproblems and optimal substructure by storing results of subproblems instead of recomputing them. Top-down memoisation caches recursive calls, while bottom-up tabulation fills a table iteratively. Classic examples are Fibonacci, 0/1 knapsack, longest common subsequence, coin change and edit distance. Defining the state and transition clearly is the hardest part.

What is the difference between greedy algorithms and dynamic programming?

Show answer

A greedy algorithm makes the best local choice at each step and never revisits it, which works only when the greedy choice property holds, as in activity selection, Huffman coding and Dijkstra. Dynamic programming considers all relevant subproblem choices and combines them, so it works where greedy fails, such as 0/1 knapsack or coin change with arbitrary denominations. Greedy is faster when provably correct.

Your program sorts 1 crore integers in the range 0 to 999 and qsort is too slow. What would you do?

Show answer

With a small known range, use counting sort: count occurrences in an array of 1000 counters, then rewrite the array in order. It runs in O(n + k) time with only 1000 extra integers, far faster than O(n log n) comparison sorts. For larger ranges, radix sort on bytes works well. qsort also pays a function call per comparison through its comparator pointer.

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

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.

You must schedule the maximum number of non-overlapping meetings in one room. What algorithm do you use?

Show answer

This is activity selection, solved greedily. Sort meetings by end time, then pick each meeting whose start is not earlier than the end of the last picked one. Choosing the earliest finishing meeting always leaves the most room for the rest, which can be proven by an exchange argument. Sorting dominates, giving O(n log n) time.

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

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

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.

How do you handle a coding interview problem when you are stuck?

Show answer

Situation: in an onsite round I could not see how to solve an interval problem. Task: still show strong problem solving. Action: I stated a brute force solution with its complexity, tried small examples aloud, noticed that sorting by start time helped and asked a clarifying question about overlaps. Result: I reached an O(n log n) solution with a small hint, and the feedback praised my communication.

What is backtracking? Give an example.