Scenario-Based C Programming with DSA Interview Questions

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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

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

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.