C Programming with DSA Interview Questions in Noida

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.

How is a 2D array stored in memory in C?

Arrays and StringsMedium

Show answer

C stores multidimensional arrays in row-major order: all elements of row 0, then row 1 and so on, in one contiguous block. Element a[i][j] of an array with C columns is at offset i * C + j. Traversing row by row is cache friendly and much faster than column by column for large matrices. When passing a 2D array to a function, every dimension except the first must be specified.

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.

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.

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.

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

Trees and GraphsHard

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.

Use qsort with a function pointer to sort an array of integers in descending order.

Sorting, Searching and Dynamic ProgrammingEasy

Show answer

Write a comparator that returns negative, zero or positive. int cmpDesc(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (y > x) - (y < x); } int arr[] = {4, 1, 9, 3}; qsort(arr, 4, sizeof arr[0], cmpDesc); Returning y - x can overflow, so the comparison form is safer.

Write binary search in C that returns the index of the target or -1.

Show answer

Use an overflow safe midpoint. int binarySearch(const int *a, int n, int target) { int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == target) return mid; if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } Time O(log n). The array must be sorted in ascending order.

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.

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.

Why is gets() dangerous and what should you use instead?

Arrays and StringsEasy

Show answer

gets() reads a line into a buffer without knowing its size, so long input overflows the buffer and can be used for code execution attacks. It was removed in C11. Use fgets(buf, sizeof buf, stdin), which stops at the buffer size and keeps the newline, then strip the newline if needed. For formatted input, give scanf field widths like %19s.

Compare BFS and DFS.

Show answer

BFS explores level by level using a queue and finds the shortest path in unweighted graphs. DFS goes deep along one path using recursion or a stack, and suits cycle detection, topological sort, connected components and backtracking. Both run in O(V + E). BFS may use more memory on wide graphs, while recursive DFS can overflow the call stack on very deep graphs.

Two source files both define a global variable named count and the build fails. How do you fix it?

Show answer

Each global may be defined only once. Define it in one .c file, such as int count = 0;, and declare it in a shared header as extern int count;, which other files include. If the variable should be private to each file, mark it static in both files instead. Since GCC 10, -fno-common is default, so duplicate tentative definitions also fail to link.

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

You need to update one record in the middle of a large binary file without rewriting it all. How?

Structures, Unions and File HandlingMedium

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.

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

Why is a dummy or sentinel node useful in linked list code?

Linked ListsMedium

Show answer

A dummy node placed before the real head removes special cases for an empty list or for inserting and deleting at the head, because every real node then has a previous node. Code for merging lists, removing elements and partitioning becomes shorter and less error prone. At the end, return dummy.next as the new head. It costs one extra node.

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

Explain pointer arithmetic in C.

Show answer

Adding an integer to a pointer moves it by that many elements, not bytes, so p + 1 on an int pointer advances by sizeof(int). Subtracting two pointers into the same array gives the number of elements between them as ptrdiff_t. Arithmetic is valid only within an array or one past its end; going further is undefined behaviour. Void pointer arithmetic is not allowed in standard C.

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.

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.

Write code to check whether the machine is little endian or big endian.

Structures, Unions and File HandlingMedium

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.

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.

How do you handle a situation where requirements change late in a project?

Structures, Unions and File HandlingMedium

Show answer

Situation: two weeks before release, the client asked to add a new field to our device's binary log format. Task: add it without breaking older files. Action: I explained the risk, added a version byte to the header, wrote a reader that handled both versions and tested with old and new samples. Result: we shipped on time and older devices kept working without a firmware update.

What is a pointer in C?

Pointers and Memory ManagementEasy

Show answer

A pointer is a variable that stores the memory address of another variable. int *p = &x; makes p hold the address of x, and *p reads or writes the value at that address. Pointers allow passing large data efficiently, modifying caller variables, working with arrays and strings, building dynamic data structures like linked lists and allocating memory at runtime.

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

A program prints garbage values for a local variable. What is the likely cause?

C Basics, Data Types and OperatorsEasy

Show answer

Local automatic variables are not initialised in C, so they hold whatever bytes were on the stack. Reading them is undefined behaviour and gives random results. Initialise every variable at declaration, such as int sum = 0;. Compiling with -Wall -Wuninitialized and running under Valgrind or with -fsanitize=memory helps detect such reads early.

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.

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.

Implement quicksort in C using Lomuto partition.

Sorting, Searching and Dynamic ProgrammingMedium

Show answer

Partition around the last element, then sort both sides. void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } int partition(int *a, int lo, int hi) { int pivot = a[hi], i = lo; for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(&a[i++], &a[j]); swap(&a[i], &a[hi]); return i; } void quickSort(int *a, int lo, int hi) { if (lo < hi) { int p = partition(a, lo, hi); quickSort(a, lo, p - 1); quickSort(a, p + 1, hi); } }

What is a stack and where is it used?

Stacks, Queues and HashingEasy

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

Explain Kadane's algorithm.

Arrays and StringsMedium

Show answer

Kadane's algorithm finds the maximum sum contiguous subarray in O(n). It keeps the best sum ending at the current index: cur = max(a[i], cur + a[i]), and updates the global best with best = max(best, cur). If the running sum becomes worse than starting fresh, it starts a new subarray. Initialise with the first element to handle arrays where all numbers are negative.

Tell me about a time you debugged a hard crash in C code.