Senior C Engineer Interview Questions &amp; Answers

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.

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

Show answer

Keep indexes of elements still waiting for a greater value. void nextGreater(const int *a, int n, int *res) { int st[n], top = -1; for (int i = 0; i < n; i++) { res[i] = -1; while (top >= 0 && a[st[top]] < a[i]) { res[st[top--]] = a[i]; } st[++top] = i; } } For 4 5 2 25 the result is 5 25 25 -1, in O(n) time.

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

Show answer

Push digits and apply operators to the top two values. int evalPostfix(const char *s) { int st[100], top = -1; for (; *s; s++) { if (isdigit((unsigned char)*s)) st[++top] = *s - '0'; else if (strchr("+-*/", *s)) { int b = st[top--], a = st[top--]; switch (*s) { case '+': st[++top] = a + b; break; case '-': st[++top] = a - b; break; case '*': st[++top] = a * b; break; case '/': st[++top] = a / b; break; } } } return st[top]; } 23*5+ evaluates to 11.

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

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.

What makes a good hash function?

Stacks, Queues and HashingHard

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.

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.

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.

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.

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.

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

Sorting, Searching and Dynamic ProgrammingMedium

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.

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.

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.

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

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.

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

Linked ListsHard

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.

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.

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.

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.

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.

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 the difference between open addressing and separate chaining in terms of performance?

Stacks, Queues and HashingHard

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.

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

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.

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.

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

Stacks, Queues and HashingHard

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

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.

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.

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

Pointers and Memory ManagementMedium

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.

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

Structures, Unions and File HandlingMedium

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.

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.

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.

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

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

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

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.

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

Structures, Unions and File HandlingHard

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

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.

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