Hard C Programming with DSA Interview Questions

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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