Programming and Data Structures
What this domain tests
Expect C programming fundamentals, pointer and array behaviour, linear and non-linear data structures, traversals, and time-complexity comparisons of searching and sorting algorithms.
C fundamentals
Arrays are zero-indexed and stored in contiguous memory; the array name decays to a pointer to its first element. C uses pass by value, so a function receives copies unless addresses are passed. Pointer arithmetic is scaled by the size of the pointed-to type, so p + 1 advances by sizeof(type) bytes, not one byte.
Data structures at a glance
A stack is LIFO with push and pop; a queue is FIFO with enqueue at the rear and dequeue at the front; a circular queue reuses freed slots. A binary search tree keeps smaller keys left and larger keys right, so its inorder traversal is sorted. Binary search needs a sorted array and runs in O(log n); quicksort averages O(n log n) but degrades to O(n^2); merge sort is O(n log n) and stable; hashing gives average O(1) lookup but needs collision handling.
Worked example
Convert A + B * (C - D) to postfix. Scan left to right: A goes to output; + is pushed; B goes to output; * has higher precedence than + and is pushed; ( is pushed; C goes to output; - is pushed; D goes to output; the closing bracket pops - to output; at the end * then + are popped. Result: A B C D - * +.
Traps that cost marks
- Accessing index n in an array of n elements.
- Assuming an array argument is passed by value in full; only its address is copied.
- Believing quicksort is always O(n log n).
- Forgetting that binary search requires sorted data, and that inorder of a BST is ascending.