C Programming with DSA Interview Questions &amp; Answers

Show answer

Preprocessing expands #include files and macros and removes comments. Compilation turns the preprocessed code into assembly. Assembly converts it into an object file of machine code. Linking combines object files with libraries such as libc to produce the executable. With gcc you can stop at each stage using -E, -S and -c, which helps when debugging macro or linker errors.

What are the basic data types in C and their typical sizes?

Show answer

C has char (1 byte), short (usually 2), int (usually 4), long (4 on Windows, 8 on 64-bit Linux), long long (at least 8), float (4) and double (8). The standard only fixes minimum ranges, so sizes depend on the platform. Use sizeof to check and the fixed-width types from stdint.h such as int32_t and uint8_t when exact sizes matter.

What is the difference between a declaration and a definition in C?

Show answer

A declaration tells the compiler a name and its type, such as extern int count; or a function prototype, without allocating storage. A definition actually creates the object or provides the function body, such as int count = 0;. A variable can be declared many times but defined only once across the program, otherwise the linker reports a multiple definition error.

What does the static keyword do in different contexts?

Show answer

Inside a function, a static local variable keeps its value between calls and is initialised only once. At file level, a static global variable or function has internal linkage, so it is visible only in that source file, which helps hide implementation details. Static variables are stored in the data or BSS segment, not the stack, and default to zero.

What is the difference between ++i and i++?

Show answer

++i increments i and then yields the new value, while i++ yields the old value and then increments. As a standalone statement both have the same effect, and modern compilers generate the same code. The difference matters inside expressions: if i is 5, a = i++ sets a to 5, while a = ++i sets a to 6. Never use both on the same variable in one expression.

A program prints garbage values for a local variable. What is the likely cause?

Show answer

Local automatic variables are not initialised in C, so they hold whatever bytes were on the stack. Reading them is undefined behaviour and gives random results. Initialise every variable at declaration, such as int sum = 0;. Compiling with -Wall -Wuninitialized and running under Valgrind or with -fsanitize=memory helps detect such reads early.

Write a C program to swap two numbers without using a third variable.

Show answer

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.

Write a C function to check whether a number is an Armstrong number.

Show answer

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.

Write a header guard and explain why it is needed.

Show answer

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.

Why do you want to work in C and systems programming?

Show answer

Situation: during college I built a small shell in C for an operating systems lab. Task: make it handle pipes and background jobs. Action: I learned fork, exec and file descriptors and debugged crashes with gdb. Result: I enjoyed understanding how software talks to hardware and the OS, and I want roles in embedded, systems or performance critical software where C skills matter.

What is the difference between break and continue in C?

Show answer

break immediately exits the nearest enclosing loop or switch statement, and execution continues after it. continue skips the rest of the current loop iteration and moves to the next one; in a for loop the update expression still runs. In nested loops both affect only the innermost loop, so a flag or goto is needed to exit outer loops early.

Explain storage classes in C.

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.

What is undefined behaviour in C? Give examples.

C Basics, Data Types and OperatorsHard

Show answer

Undefined behaviour means the C standard places no requirement on what happens, so the program may crash, give wrong results or appear to work. Examples are signed integer overflow, dereferencing a null or freed pointer, reading an uninitialised variable, accessing an array out of bounds and modifying a variable twice without a sequence point, such as i = i++. Compilers optimise assuming it never happens.

What is integer promotion and why does it matter?

C Basics, Data Types and OperatorsHard

Show answer

In expressions, types smaller than int, like char and short, are promoted to int before arithmetic. In mixed signed and unsigned comparisons, the signed value may convert to unsigned. So if (-1 < sizeof(int)) is false, because -1 becomes a huge unsigned number. These rules cause subtle bugs in embedded and systems code, so compile with -Wall -Wextra and use explicit casts carefully.

Code works with -O0 but fails with -O2. How do you approach this?

C Basics, Data Types and OperatorsHard

Show answer

This usually means the code relies on undefined behaviour that the optimiser exploits, such as uninitialised variables, out-of-bounds access, strict aliasing violations or missing volatile on shared hardware variables. Build with -Wall -Wextra and -fsanitize=address,undefined, then fix each report. If a variable is changed by an interrupt or another thread, add volatile or proper atomics.

What is a pointer in C?

Show answer

A pointer is a variable that stores the memory address of another variable. int *p = &x; makes p hold the address of x, and *p reads or writes the value at that address. Pointers allow passing large data efficiently, modifying caller variables, working with arrays and strings, building dynamic data structures like linked lists and allocating memory at runtime.

What are null, dangling, wild and void pointers?

Show answer

A null pointer holds NULL and points to nothing; dereferencing it crashes. A dangling pointer points to memory that has been freed or a local that went out of scope. A wild pointer is uninitialised and holds a random address. A void pointer is a generic pointer that can hold any object address but must be cast before dereferencing, as malloc returns void *.

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

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.

What is the difference between stack and heap allocation?

Show answer

Stack memory holds local variables, is allocated and freed automatically when functions enter and return, and is very fast but limited in size, often 1 to 8 MB. Heap memory is allocated with malloc and freed manually, can be large and outlive the function, but is slower and can fragment or leak. Large or variable sized data and data that must outlive a function belong on the heap.

Write a function that dynamically allocates an array of n integers and fills it with squares.

Show answer

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

Write a function that swaps two integers using pointers.

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 does sizeof return for a pointer and for an array?

Show answer

sizeof on a pointer returns the size of the pointer itself, typically 8 bytes on a 64-bit system, regardless of what it points to. sizeof on an array declared in the same scope returns the total bytes of all elements, so sizeof arr / sizeof arr[0] gives the element count. Inside a function receiving an array parameter, sizeof returns pointer size, so pass the length separately.

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 strict aliasing rule?

Show answer

Strict aliasing says an object may be accessed only through an lvalue of its own type, a compatible type or a character type. Reading a float through an int pointer breaks the rule and is undefined behaviour, and optimisers at -O2 may reorder or drop such accesses. To reinterpret bytes safely, use memcpy into a variable of the other type, or a union, which GCC supports for type punning.

What is memory alignment and why does it matter?

Show answer

Alignment means placing data at addresses that are multiples of its size or required boundary, such as 4 for int. CPUs read aligned data faster, and some architectures fault on misaligned access. Compilers add padding in structs to align members. You can check alignment with _Alignof and request it with _Alignas or aligned_alloc in C11.

Memory use of a long running C service grows every hour. How do you investigate?

Show answer

Run it under Valgrind or with AddressSanitizer and LeakSanitizer in a test environment and reproduce typical traffic, then read the leak report with allocation stack traces. In production, compare heap usage over time with tools like heaptrack. Check error paths that return early without free, lost pointers after realloc, and caches without size limits. Fix ownership and add a leak check to CI.

Valgrind reports invalid read of size 4 after free. How do you fix it?

Show answer

This is a use-after-free: code reads memory that was already released. Valgrind shows where it was freed and where it was read. Fix the ownership logic so nothing uses the object after free, and set pointers to NULL right after freeing so accidental use fails fast. If multiple parts share the object, use reference counting or free only at one clear owner.

Implement your own version of memcpy.

Show answer

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.

Write a simple fixed-size memory pool allocator in C.

Show answer

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

How are strings represented in C?

Show answer

C has no string type. A string is a char array ending with the null character '\0', which marks its end. char s[] = "hi" creates an array of 3 bytes: 'h', 'i' and '\0'. Library functions like strlen and printf scan until the null terminator, so forgetting it, or writing past the array, causes reading of random memory and crashes.

What is the difference between char s[] = "hello" and char *s = "hello"?

Show answer

char s[] = "hello" creates a modifiable array of 6 bytes, usually on the stack, initialised with a copy of the literal. char *s = "hello" makes a pointer to a string literal stored in read-only memory; modifying it is undefined behaviour and often crashes. Declare such pointers as const char * so the compiler catches accidental writes.

Why is gets() dangerous and what should you use instead?

Show answer

gets() reads a line into a buffer without knowing its size, so long input overflows the buffer and can be used for code execution attacks. It was removed in C11. Use fgets(buf, sizeof buf, stdin), which stops at the buffer size and keeps the newline, then strip the newline if needed. For formatted input, give scanf field widths like %19s.

What is the two-pointer technique and when is it used?

Show answer

Two pointers keep two indexes that move through an array according to a rule, often from both ends of a sorted array or at different speeds. It solves pair sum on sorted arrays, removing duplicates in place, reversing, merging sorted arrays and partitioning. It usually gives O(n) time and O(1) extra space instead of nested loops.

An interview asks you to find the missing number from 1 to n in an array of n-1 numbers. What approaches work?

Show answer

Sum approach: expected sum n(n+1)/2 minus the actual sum gives the missing number, using a long type to avoid overflow. XOR approach: XOR all numbers from 1 to n and all array elements; pairs cancel and the missing number remains, with no overflow risk. Both are O(n) time and O(1) space, and XOR is the safer choice for very large n.

Reverse a string in place in C.

Show answer

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.

Merge two sorted arrays into a third sorted array.

Show answer

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.

Implement your own strcmp function.

Show answer

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.

Write a C function to count words in a sentence.

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.

How did you improve your problem solving skills?

Show answer

Situation: in my second year I could not solve even easy array problems in time. Task: become placement ready in six months. Action: I followed a topic-wise sheet, solved two problems daily in C, wrote down the pattern behind each one and revised mistakes every Sunday. Result: I solved over 300 problems, cleared three online coding tests and now explain complexity confidently.

What does it mean that arrays decay to pointers when passed to functions?

Show answer

When you pass an array to a function, C passes only a pointer to its first element, not a copy of the array. So void f(int a[]) is the same as void f(int *a), sizeof a inside gives the pointer size and changes to elements affect the caller's array. Always pass the length as a separate parameter, such as f(arr, n).

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 a buffer overflow and how can it be prevented in C?

Arrays and StringsHard

Show answer

A buffer overflow writes beyond the end of an array, corrupting nearby data, return addresses or heap metadata, and it is a classic security hole. Prevent it with bounds checked functions like fgets and snprintf, always passing buffer sizes, validating input lengths and using sizeof correctly. Compiler protections such as stack canaries, FORTIFY_SOURCE and sanitizers help catch and limit damage.

A matrix multiplication in C is very slow for 2000 by 2000 matrices. How would you speed it up?

Arrays and StringsHard

Show answer

The naive i, j, k loop accesses one matrix column by column, causing many cache misses. Swap the loop order to i, k, j so inner loops walk rows contiguously, use blocking or tiling to keep chunks in cache, compile with -O3 -march=native to enable vectorisation and consider OpenMP for multiple cores. For production, an optimised BLAS library is fastest.

Find the majority element that appears more than n/2 times in O(n) time and O(1) space.

Arrays and StringsHard

Show answer

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.

What is a structure in C and why is it used?

Show answer

A structure groups related variables of different types under one name, such as struct Student { int roll; char name[50]; float marks; };. It models real records, lets functions take or return one object instead of many parameters and is the base for data structures like linked lists and trees. Members are accessed with the dot operator or with -> through a pointer.

What is the difference between a structure and a union?

Show answer

In a structure each member has its own memory, so the size is at least the sum of members plus padding, and all members hold values at once. In a union all members share the same memory, so its size equals the largest member and only one member is meaningful at a time. Unions save memory and are used for variant types and in embedded protocol parsing.

What is typedef and how is it used with structures?

Show answer

typedef creates an alias for a type. typedef struct Node { int data; struct Node *next; } Node; lets you write Node *head instead of struct Node *head. It is also useful for function pointer types and platform specific types. Some style guides avoid hiding pointers behind typedefs because it makes ownership and const usage less clear.

What is an enum in C and what are its advantages?

Show answer

An enum defines a set of named integer constants, such as enum Color { RED, GREEN, BLUE };, where values start at 0 unless set. It makes code readable and lets compilers warn about missing cases in a switch with -Wswitch. Enum values are int sized in practice, and C23 allows specifying the underlying type. Use them for states, commands and error codes.

A file opened with fopen is NULL in production but fine on your machine. How do you debug?

Show answer

Always check the return value and print the reason with perror or strerror(errno), which shows errors like No such file or directory or Permission denied. Common causes are a relative path resolved from a different working directory, missing permissions for the service user, a full disk or too many open files. Use absolute or configured paths and close every file you open.

Define a struct for a student and print all students with marks above 75.

Show answer

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.

How do you pass a structure to a function efficiently?

Show answer

Passing a struct by value copies every member, which is costly for large structs. Pass a pointer instead, and add const when the function should only read it, such as void print(const Student *s). Access members with s->name. Small structs of a few bytes can be passed by value safely, and returning small structs by value is also fine.

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.

Why is it risky to write structs directly to a file with fwrite?

Show answer

A raw struct includes padding bytes, platform specific sizes and byte order, so a file written on one compiler or CPU may not read correctly on another. Pointers inside the struct are meaningless after reload. For portable formats, serialise each field explicitly with fixed-width types and a defined byte order, or use a format like JSON or Protocol Buffers.

What is a flexible array member?

Show answer

A flexible array member is a last struct member declared with empty brackets, such as struct Packet { size_t len; char data[]; };. You allocate the struct and its data in one malloc call: malloc(sizeof(struct Packet) + n). It keeps the header and payload together, improving cache use and needing only one free. It was standardised in C99.

Your embedded device must store 10,000 sensor records in limited RAM. How would you design the struct?

Show answer

Use fixed-width types sized to the real range, such as uint16_t for readings and uint32_t for timestamps, order members from largest to smallest to cut padding and pack boolean flags into bit fields or a single bitmask byte. Consider storing time as an offset from a base to save bytes. Check sizeof in a static assertion so the size stays as designed.

Two programs on different machines exchange a binary struct and values come out wrong. What is happening?

Show answer

Likely causes are different endianness, so multi-byte integers are reversed, different padding or type sizes, such as long being 4 bytes on one platform and 8 on another. Define a wire format with fixed-width types, convert integers with htonl and ntohl or explicit byte shifts and serialise field by field. Add a version field so the format can evolve.

100

Write a static assertion that checks a struct size at compile time.

Show answer

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.

101

What is a linked list and how is it different from an array?

Show answer

A linked list is a chain of nodes where each node holds data and a pointer to the next node, allocated separately on the heap. Unlike an array, it grows easily and inserts or deletes in O(1) once you have the position, but it has O(n) access by index, extra memory per node for pointers and poor cache locality. Arrays win for random access and iteration speed.

102

What are the types of linked lists?

Show answer

A singly linked list has a next pointer only and can be traversed one way. A doubly linked list adds a prev pointer, allowing backward traversal and O(1) deletion of a known node, at the cost of more memory. A circular linked list links the last node back to the first, useful for round-robin scheduling. Variants include lists with sentinel or dummy head nodes.

103

What is the time complexity of common linked list operations?

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.

104

How do you find the middle of a linked list in one pass?

Show answer

Use slow and fast pointers starting at the head. Move slow by one node and fast by two nodes each step. When fast reaches the end or NULL, slow is at the middle. For an even number of nodes this gives the second middle; start fast at head->next to get the first middle instead. It takes O(n) time and O(1) space.

105

A function to insert at the head does not change the list in main. Why?

Show answer

C passes arguments by value, so the function receives a copy of the head pointer; changing that copy does not affect main. Pass a pointer to the head, as in void push(Node **head, int x), and assign *head = newNode, or return the new head and assign it in the caller with head = push(head, x). This is a very common fresher interview mistake.

106

Describe a time you failed in an interview or test and what you learned.

Show answer

Situation: in my first product company interview I froze on a linked list reversal. Task: improve before the next opportunity. Action: I practised pointer problems daily, always drawing boxes and arrows before coding, and did mock interviews with friends where I spoke my thinking aloud. Result: two months later I solved a harder linked list problem calmly and got the offer.

107

What is a circular linked list and where is it used?

Show answer

In a circular linked list the last node points back to the first, so there is no NULL end. You can start at any node and visit all nodes, and keeping only a tail pointer gives O(1) access to both ends. It is used in round-robin CPU scheduling, multiplayer turn order and circular buffers. Traversal loops must stop when they return to the starting node.

108

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.

109

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.

110

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.

111

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.

112

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.

113

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.

114

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.

115

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.

116

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.

117

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.

118

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.

119

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.

120

Why do linked lists perform poorly compared to arrays on modern CPUs?

Show answer

Each node is allocated separately and may sit anywhere in memory, so traversing a list causes frequent cache misses and the CPU cannot prefetch well. Arrays store elements contiguously, so a cache line brings several elements at once. Even with O(1) insertion, linked lists are often slower in practice. Use them when frequent insertions in the middle with stable node addresses really matter.

121

What is an XOR linked list?

Show answer

An XOR linked list is a memory efficient doubly linked list where each node stores prev XOR next in one field instead of two pointers. Knowing the previous node lets you compute the next one. It saves memory but makes code harder to read, debug and use with garbage collectors or sanitizers, and it needs pointer to integer casts with uintptr_t. It is mostly an interview curiosity.

122

You must design an LRU cache in C with O(1) get and put. How would you build it?

Show answer

Combine a hash table that maps keys to nodes with a doubly linked list ordered by recent use. On get, find the node through the hash table and move it to the front. On put, update or insert at the front, and if capacity is exceeded remove the tail node and delete its key from the hash table. Both operations are O(1) on average.

123

A linked list used in a multithreaded C server sometimes corrupts. How would you fix it?

Show answer

Concurrent inserts and deletes race on next pointers. The simplest fix is a pthread mutex around every list operation, keeping critical sections short. For read-heavy workloads, a read-write lock lets readers run in parallel. Lock-free lists with atomic compare-and-swap are possible but very hard to get right because of the ABA problem and safe memory reclamation, so use them only with proven libraries.

124

Detect a cycle in a linked list and return the node where it starts.

Show answer

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

125

Remove the nth node from the end of a linked list in one pass.

Show answer

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.

126

What is a stack and where is it used?

Show answer

A stack is a last in, first out structure with push, pop and peek operations, all O(1). It is used for function call frames, undo features, expression evaluation, balanced bracket checking, backtracking and depth first search. In C you implement it with an array and a top index, or with a linked list when the size is not known in advance.

127

What is a queue and what are its variants?

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.

128

Implement a stack using an array in C.

Show answer

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.

129

Check whether brackets in an expression are balanced using a stack.

Show answer

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

130

How do you handle working with a teammate who writes buggy code?

Show answer

Situation: a teammate's stack and queue module in our project kept failing tests. Task: fix the quality issue without blaming. Action: I offered to pair on one bug, showed how drawing the array and indexes revealed the off-by-one error and suggested we both add edge case tests before pushing. Result: his code quality improved quickly and our module passed all tests at the review.

131

What is a deque and how can it be implemented in C?

Show answer

A deque, or double ended queue, supports insertion and removal at both the front and the rear in O(1). In C it is commonly implemented as a circular array with front and rear indexes that wrap using modulo, or as a doubly linked list. It is the core of the sliding window maximum algorithm and can act as both a stack and a queue.

132

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.

133

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.

134

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.

135

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

136

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.

137

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.

138

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

139

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.

140

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

141

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.

142

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.

143

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.

144

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

145

What makes a good hash function?

Show answer

A good hash function is fast, deterministic and spreads keys evenly across buckets so collisions are rare, even for similar keys like user1 and user2. For strings, functions like FNV-1a or djb2 are simple choices. Using a table size that is a power of two needs good mixing of low bits, while prime sizes help weaker hashes. For untrusted input, use a seeded hash like SipHash to resist collision attacks.

146

What is a ring buffer and why is it common in embedded systems?

Show answer

A ring buffer is a fixed-size circular queue in a static array. It needs no dynamic allocation, has O(1) operations and predictable memory, which suits microcontrollers. A single producer, such as a UART interrupt, writes at head while a single consumer, such as the main loop, reads at tail. With power of two sizes, index masking is cheap, and with one writer and one reader it can be lock free.

147

A UART receive buffer in firmware sometimes loses or duplicates bytes. How would you fix it?

Show answer

The interrupt writes and the main loop reads the same ring buffer, so check for race conditions. Use a single-producer, single-consumer design where only the ISR updates head and only the main loop updates tail, declare the indexes volatile or use C11 atomics, and update the index after writing data. Detect overflow when the buffer is full and size the buffer for the maximum burst rate.

148

You need the maximum of every sliding window of size k in an array. How would you solve it efficiently?

Show answer

Use a deque storing indexes in decreasing order of value. For each element, remove indexes outside the window from the front, pop smaller values from the back, then push the current index. The front is always the maximum of the current window. Each index enters and leaves once, so the total time is O(n) instead of O(nk).

149

Implement a simple hash table with separate chaining for string keys.

Show answer

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

150

What is the difference between open addressing and separate chaining in terms of performance?

Show answer

Separate chaining stores colliding keys in linked lists, so it handles high load factors gracefully and deletes easily, but each node is a separate allocation with poor cache locality. Open addressing keeps all entries in one array, giving excellent cache performance and no per-entry allocation, but it degrades sharply above about 70 percent load and needs tombstones for deletion. High performance tables usually use open addressing.

151

What is a binary search tree and what are its operation costs?

Show answer

A binary search tree keeps every node's left subtree smaller and right subtree larger than the node. Search, insert and delete follow one path from the root, so they cost O(h), where h is the height. A balanced tree has h of about log n, but inserting sorted data creates a skewed tree with h equal to n. In-order traversal of a BST gives keys in sorted order.

152

Explain the tree traversal orders.

Show answer

In-order visits left, node, right and gives sorted output for a BST. Pre-order visits node, left, right and is used to copy or serialise a tree. Post-order visits left, right, node and is used to delete a tree or evaluate expression trees. Level-order visits nodes level by level using a queue. The first three are depth first and use recursion or an explicit stack.

153

What is the difference between a complete, full and perfect binary tree?

Show answer

A full binary tree has every node with zero or two children. A complete binary tree has all levels filled except possibly the last, which is filled from left to right; heaps use this shape so they fit an array. A perfect binary tree has all internal nodes with two children and all leaves at the same level, so it has 2 to the power h+1 minus 1 nodes.

154

Insert a value into a binary search tree recursively in C.

Show answer

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.

155

Find the height of a binary tree in C.

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

156

How do you explain the time complexity of your solution to an interviewer?

Show answer

Situation: in a technical round I solved a tree problem but the interviewer questioned its efficiency. Task: justify the complexity clearly. Action: I explained that each node is visited once and does constant work, so time is O(n), and that recursion depth equals tree height, giving O(h) space, worst case O(n) for a skewed tree. Result: the interviewer agreed and moved to a harder follow-up.

157

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.

158

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.

159

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.

160

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.

161

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.

162

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.

163

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

164

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

165

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

166

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.

167

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.

168

How does Dijkstra's algorithm work?

Show answer

Dijkstra finds shortest paths from a source in a graph with non-negative edge weights. It keeps tentative distances, repeatedly takes the unvisited vertex with the smallest distance from a min heap and relaxes its edges, updating neighbours if a shorter path is found. With a binary heap it runs in O((V + E) log V). It fails with negative weights, where Bellman-Ford is used instead.

169

What is topological sorting and where is it used?

Show answer

A topological sort orders the vertices of a directed acyclic graph so every edge goes from earlier to later. Kahn's algorithm repeatedly removes vertices with zero in-degree using a queue; DFS adds vertices to the order after finishing their descendants. If not all vertices are processed, the graph has a cycle. It is used for build systems, course prerequisites and task scheduling.

170

What is the union-find data structure?

Show answer

Union-find, or disjoint set union, tracks which elements are in the same group. find returns a group's representative and union merges two groups. With path compression and union by rank, both run in nearly constant amortised time. It is used for Kruskal's minimum spanning tree, detecting cycles in undirected graphs and counting connected components in dynamic connectivity problems.

171

A build tool must compile modules in the correct dependency order and report circular dependencies. How would you design it?

Show answer

Model modules as vertices and dependencies as directed edges, then run Kahn's topological sort. Start with modules that have zero in-degree, process them in a queue and reduce in-degrees of dependants. Modules left unprocessed form a cycle, which you report by tracing them with DFS. Independent modules at the same stage can be compiled in parallel.

172

A social network feature must suggest friends of friends. How would you find them efficiently?

Show answer

Represent users and friendships as an undirected graph with adjacency lists. Run BFS from the user to depth two, collect nodes at distance exactly two and rank them by the number of mutual friends counted during traversal. Exclude existing friends. For huge graphs, precompute suggestions offline in batches and cap the number of neighbours explored per user.

173

Implement union-find with path compression and union by rank.

Show answer

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

174

Describe a time you had to make a trade-off between memory and speed.

Show answer

Situation: a C routing service on a small server ran out of memory with an adjacency matrix for 50,000 nodes. Task: fit within 512 MB without slowing queries much. Action: I switched to compact adjacency lists stored in flat arrays, known as CSR format, and kept a small cache for frequent routes. Result: memory fell from 10 GB worth of matrix to 60 MB and queries stayed under 20 ms.

175

A Dijkstra implementation gives wrong distances on a graph with a few negative edges. Why?

Show answer

Dijkstra assumes that once a vertex is taken from the heap its distance is final, which holds only when all weights are non-negative. A negative edge found later can make a shorter path, so results are wrong. Use Bellman-Ford, which relaxes all edges V-1 times in O(VE) and can also detect negative cycles, or reweight the graph with Johnson's algorithm.

176

What is Big O notation?

Show answer

Big O describes how an algorithm's time or memory grows as input size grows, ignoring constants and lower terms. Common classes are O(1), O(log n), O(n), O(n log n), O(n squared) and O(2 to the n). It usually describes the worst case. For example, binary search is O(log n), so a million elements need about 20 steps. Big Omega and Big Theta describe lower and tight bounds.

177

How does binary search work and what are common bugs?

Show answer

Binary search works on sorted data by comparing the middle element with the target and discarding half the range each step, giving O(log n). Common bugs are computing mid as (low + high) / 2, which can overflow, so use low + (high - low) / 2; wrong loop conditions causing infinite loops; and off-by-one errors when finding first or last occurrences. Test with zero, one and two elements.

178

What is recursion and what are its risks?

Show answer

Recursion is when a function calls itself on a smaller subproblem until reaching a base case. It expresses tree traversal, divide and conquer and backtracking naturally. Risks are stack overflow when depth is large, repeated work when subproblems overlap, like naive Fibonacci, and function call overhead. Use memoisation for overlapping subproblems and iterative versions when depth may be huge.

179

A recursive Fibonacci solution times out for n = 50. How do you fix it?

Show answer

Naive recursion recomputes the same subproblems repeatedly, giving about O(1.6 to the n) calls. Memoise results in an array so each value is computed once, giving O(n), or iterate bottom-up keeping only the last two values for O(1) space. Use unsigned long long, since fib(50) exceeds the int range. Matrix exponentiation gives O(log n) for very large n.

180

A search on a sorted array of 10 lakh elements is done with a linear loop. How would you justify changing it?

Show answer

Linear search takes up to 10 lakh comparisons, while binary search needs about 20, because log base 2 of 10 lakh is roughly 20. If searches are frequent, this is a huge saving at zero memory cost. If data changes often, keeping it sorted costs inserts, so consider a balanced tree or hash table. Measure with realistic workloads before and after.

181

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.

182

How do you keep improving your DSA skills while working full time?

Show answer

Situation: after joining a services company I had little time for practice. Task: stay ready for product company interviews. Action: I set a goal of five problems a week on weekday mornings, joined weekend contests and kept a notebook of patterns and mistakes, revising it monthly. Result: within a year I reached a solid contest rating and cleared interviews for a backend role.

183

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.

184

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.

185

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.

186

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.

187

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.

188

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.

189

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

190

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

191

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.

192

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.

193

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.

194

What is the master theorem used for?

Show answer

The master theorem gives the time complexity of divide and conquer recurrences of the form T(n) = aT(n/b) + f(n). Compare f(n) with n to the power log base b of a. For merge sort, a = 2, b = 2 and f(n) = n, which match, giving O(n log n). For binary search, a = 1 and b = 2 with constant work, giving O(log n). It does not cover every recurrence.

195

What is amortised analysis? Give an example.

Show answer

Amortised analysis averages the cost of operations over a sequence, so occasional expensive steps are spread over many cheap ones. A dynamic array that doubles when full copies all elements on resize, which is O(n), but because doubling happens rarely, n appends cost O(n) in total, so each append is O(1) amortised. Union-find with path compression is another classic example.

196

Quicksort in your code becomes very slow on already sorted input. Why and how do you fix it?

Show answer

Picking the first or last element as pivot on sorted input makes every partition split into sizes n-1 and 0, so quicksort degrades to O(n squared) and recursion depth reaches n. Choose a random pivot or median of three, switch to insertion sort for small parts and recurse on the smaller side first to bound stack depth. Introsort switches to heap sort if recursion gets too deep.

197

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.

198

How would you find the kth smallest element in an unsorted array efficiently?

Show answer

Sorting takes O(n log n). A max heap of size k gives O(n log k), good when k is small or data streams in. Quickselect partitions like quicksort but recurses into one side only, giving O(n) average and O(n squared) worst case, which random pivots make unlikely. Median of medians guarantees O(n) worst case but is slower in practice.

199

Solve the 0/1 knapsack problem in C with a 1D DP array.

Show answer

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

200

Find the length of the longest common subsequence of two strings.