C Programming with DSA Technical Round Questions &amp; Answers

Show answer

Use bit masks with shift operators. x |= (1u << n); // set bit n x &= ~(1u << n); // clear bit n x ^= (1u << n); // toggle bit n int bit = (x >> n) & 1u; // read bit n Use unsigned types so shifts are well defined. These operations are common in embedded code for configuring hardware registers.

What is a trie and when is it better than a hash table?

Show answer

A trie is a tree where each edge represents a character, so words sharing a prefix share a path. Lookup and insert take O(L) for a word of length L, independent of how many words are stored. It beats a hash table for prefix queries such as autocomplete, spell checking and longest prefix matching in IP routing. The trade-off is higher memory use from many child pointers.

Find the length of the longest substring without repeating characters in C.

Show answer

Sliding window with last seen positions. int longestUnique(const char *s) { int last[256]; for (int i = 0; i < 256; i++) last[i] = -1; int best = 0, start = 0; for (int i = 0; s[i]; i++) { unsigned char c = s[i]; if (last[c] >= start) start = last[c] + 1; last[c] = i; if (i - start + 1 > best) best = i - start + 1; } return best; } For abcabcbb it returns 3.

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.

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 hash table becomes slow as more data is inserted. What is wrong?

Stacks, Queues and HashingMedium

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.

A UART receive buffer in firmware sometimes loses or duplicates bytes. How would you fix it?

Stacks, Queues and HashingHard

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.

A program crashes with a segmentation fault. How do you find the cause?

Pointers and Memory ManagementMedium

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.

Valgrind reports invalid read of size 4 after free. How do you fix it?

Pointers and Memory ManagementHard

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 is the sliding window technique?

Show answer

Sliding window solves problems on contiguous subarrays or substrings by keeping a window with two indexes and moving them forward instead of rechecking every subarray. A fixed window finds things like the maximum sum of k elements, while a variable window expands and shrinks, as in the longest substring without repeating characters. It turns O(n squared) brute force into O(n).

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.

What is the difference between stack and heap allocation?

Pointers and Memory ManagementEasy

Show answer

Stack memory holds local variables, is allocated and freed automatically when functions enter and return, and is very fast but limited in size, often 1 to 8 MB. Heap memory is allocated with malloc and freed manually, can be large and outlive the function, but is slower and can fragment or leak. Large or variable sized data and data that must outlive a function belong on the heap.

Write Kadane's algorithm in C.

Show answer

Track the best sum ending here and the overall best. long maxSubarray(const int *a, int n) { long cur = a[0], best = a[0]; for (int i = 1; i < n; i++) { cur = (cur + a[i] > a[i]) ? cur + a[i] : a[i]; if (cur > best) best = cur; } return best; } Input {-2, 1, -3, 4, -1, 2, 1, -5, 4} returns 6 for subarray 4, -1, 2, 1.

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

Stacks, Queues and HashingMedium

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.

Write C code to count the number of set bits in an integer.

Show answer

Brian Kernighan's trick clears the lowest set bit each step. int countBits(unsigned int n) { int count = 0; while (n) { n &= n - 1; count++; } return count; } It runs once per set bit. GCC and Clang also offer __builtin_popcount(n), which uses a CPU instruction when available.

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.

How do you find the middle of a linked list in one pass?

Linked ListsEasy

Show answer

Use slow and fast pointers starting at the head. Move slow by one node and fast by two nodes each step. When fast reaches the end or NULL, slow is at the middle. For an even number of nodes this gives the second middle; start fast at head->next to get the first middle instead. It takes O(n) time and O(1) space.

You need to look up 10 lakh user ids quickly in a C program. What structure do you choose?

Stacks, Queues and HashingMedium

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 prefix sum array and why is it useful?

Show answer

A prefix sum array stores pre[i] = sum of elements from index 0 to i-1. Then the sum of any range from l to r is pre[r + 1] - pre[l] in O(1) after O(n) preprocessing. It is used for range sum queries, counting subarrays with a given sum together with a hash map, and 2D versions for matrix region sums.

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

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.

What is the union-find data structure?

Trees and GraphsHard

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.

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.

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.

Remove the nth node from the end of a linked list in one pass.

Linked ListsHard

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 is the difference between a macro and an inline function?

Show answer

A macro is plain text substitution by the preprocessor, with no type checking, and arguments may be evaluated more than once, so SQUARE(i++) misbehaves. An inline function is a real function with type checks and single evaluation of arguments, which the compiler may expand in place for speed. Prefer static inline functions and use macros only for things like conditional compilation.

Rotate an array to the right by k positions in O(n) time and O(1) space.

Sorting, Searching and Dynamic ProgrammingHard

Show answer

Use three reversals. void rev(int *a, int l, int r) { while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; } } void rotate(int *a, int n, int k) { k %= n; if (k == 0) return; rev(a, 0, n - 1); rev(a, 0, k - 1); rev(a, k, n - 1); } For 1 2 3 4 5 with k = 2 the result is 4 5 1 2 3.

Write a header guard and explain why it is needed.

C Basics, Data Types and OperatorsEasy

Show answer

A header guard stops a header from being included twice in one translation unit, which would cause redefinition errors. #ifndef MATH_UTILS_H #define MATH_UTILS_H int add(int a, int b); #endif Most compilers also support #pragma once, which is shorter but not part of the C standard.

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 the difference between const int p, int const p and const int *const p?

Show answer

const int *p is a pointer to a constant int: you cannot change the value through p, but p can point elsewhere. int *const p is a constant pointer: p always points to the same address, but the value can change. const int *const p fixes both. Read declarations from right to left to understand them. const pointers to data are common in function parameters.

What does the static keyword do in different contexts?

C Basics, Data Types and OperatorsEasy

Show answer

Inside a function, a static local variable keeps its value between calls and is initialised only once. At file level, a static global variable or function has internal linkage, so it is visible only in that source file, which helps hide implementation details. Static variables are stored in the data or BSS segment, not the stack, and default to zero.

How would you detect if two linked lists intersect and find the intersection node?

Linked ListsMedium

Show answer

Two lists intersect if they share a node by address, not just value. Compute both lengths, advance the longer list by the difference, then move both together until the pointers are equal. A neat trick is to walk pointer a through list A then B, and pointer b through B then A; they meet at the intersection or both reach NULL. Both are O(m + n) time and O(1) space.

Which gcc flags would you use to build and debug a C program safely?

Show answer

A good development build is: gcc -std=c17 -Wall -Wextra -Wpedantic -g -O1 \ -fsanitize=address,undefined \ -o app main.c utils.c -Wall and -Wextra turn on useful warnings, -g adds debug symbols for gdb, and sanitizers catch memory errors and undefined behaviour at runtime. For release, drop sanitizers and use -O2.

A strlen call crashes on a buffer received from a network packet. What is wrong?

Show answer

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.

How would you check whether a binary tree is a valid BST?

Show answer

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

Your program sorts 1 crore integers in the range 0 to 999 and qsort is too slow. What would you do?

Sorting, Searching and Dynamic ProgrammingMedium

Show answer

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.

A build tool must compile modules in the correct dependency order and report circular dependencies. How would you design it?

Trees and GraphsHard

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.

You need to find whether any two numbers in an unsorted array sum to a target. Compare approaches.

Show answer

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.

What is the difference between strcpy, strncpy and snprintf for copying strings?

Show answer

strcpy copies until the null terminator with no bounds check, so it can overflow. strncpy limits the count but does not add a terminator if the source is too long and pads with zeros otherwise, which surprises many developers. snprintf(dst, size, "%s", src) always terminates and returns the length it wanted, so you can detect truncation. Prefer snprintf or a checked helper.

A program that writes logs with fprintf loses the last lines when it crashes. Why, and how do you fix it?