Stacks, Queues and Hashing Interview Questions for C Programming with DSA

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.

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.

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.

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

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.

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.

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.

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.

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.

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

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.

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.

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

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.

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

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.

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.

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

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?