Systems Programmer Interview Questions &amp; Answers

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.

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

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.

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

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.

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.

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

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

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

Sorting, Searching and Dynamic ProgrammingMedium

Show answer

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

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

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.

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.

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

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.

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.

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.

What is memory alignment and why does it matter?

Pointers and Memory ManagementHard

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.

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.

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.

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 simple fixed-size memory pool allocator in C.

Pointers and Memory ManagementHard

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

Compare quicksort, merge sort and heap sort.

Sorting, Searching and Dynamic ProgrammingMedium

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.

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.

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.

How are graphs represented in C?

Trees and GraphsMedium

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.

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

Sorting, Searching and Dynamic ProgrammingEasy

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.

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.

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.

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

Sorting, Searching and Dynamic ProgrammingMedium

Show answer

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

What is the strict aliasing rule?

Pointers and Memory ManagementHard

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.

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

Trees and GraphsHard

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.

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.

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

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.

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.

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 that writes logs with fprintf loses the last lines when it crashes. Why, and how do you fix it?