GATE DA & AI Engineering Programming, Data Structures and Algorithms Syllabus

What is a hash collision, and name two strategies to resolve it.

A collision occurs when two distinct keys hash to the same index. Resolution strategies: (1) separate chaining — each bucket holds a linked list of entries; (2) open addressing — probe for another open slot (linear probing, quadratic probing, or double hashing).

Define the load factor of a hash table and its effect on performance.

The load factor is $\alpha = \frac{n}{m}$, where $n$ is the number of stored entries and $m$ is the number of buckets. As $\alpha$ grows, collisions and average probe length increase, degrading performance; tables are typically resized (rehashed) when $\alpha$ exceeds a threshold.

What are the average and worst-case lookup complexities of a hash table?

Average case: $O(1)$. Worst case (all keys collide into one bucket): $O(n)$.

What property must a good hash function have?

It should distribute keys uniformly across buckets (minimizing collisions), be fast (ideally $O(1)$) to compute, and be deterministic — the same key always maps to the same index.

What is searching in the context of algorithms?

Searching is the process of locating a target element (or determining its absence) within a data collection, returning its position or a found/not-found result.

Describe the linear search algorithm.

Linear (sequential) search scans elements one by one from the start, comparing each to the target, until a match is found or the list ends. It works on unsorted data.

State the best-, average-, and worst-case time complexity of linear search.

Best case: $O(1)$ (target is first). Average case: $O(n)$. Worst case: $O(n)$ (target last or absent). Space complexity is $O(1)$.

What precondition must hold for binary search to be applied?

The data must be sorted (in a known order, e.g., ascending) and randomly accessible by index (as in an array).

Describe one iteration of the binary search algorithm.

Compute the middle index $mid = \lfloor \frac{low + high}{2} \rfloor$. If $A[mid]$ equals the target, return it. If the target is smaller, search the left half ($high = mid - 1$); if larger, search the right half ($low = mid + 1$). Repeat until the range is empty.

State the time complexity of binary search and the recurrence it satisfies.

Binary search runs in $O(\log n)$ time, satisfying the recurrence $T(n) = T\!\left(\frac{n}{2}\right) + O(1)$. Space is $O(1)$ iteratively or $O(\log n)$ recursively.

Why is binary search asymptotically faster than linear search?

Binary search halves the search space each step ($O(\log n)$), exploiting the sorted order, whereas linear search examines elements one at a time ($O(n)$). For large $n$, $\log n \ll n$.

What is a sorting algorithm, and what does 'in-place' mean?

A sorting algorithm rearranges elements of a collection into a defined order (e.g., ascending). An in-place algorithm sorts using only $O(1)$ (or $O(\log n)$) extra memory beyond the input array.

What does it mean for a sorting algorithm to be stable?

A stable sort preserves the relative order of elements that have equal keys. Insertion sort, bubble sort, and mergesort are stable; selection sort and standard quicksort are not.

Describe how selection sort works.

Selection sort repeatedly finds the minimum element from the unsorted portion and swaps it into the next position of the sorted portion, growing the sorted prefix one element per pass.

State the time and space complexity of selection sort.

Time complexity is $O(n^{2})$ in best, average, and worst cases (the comparisons are unavoidable). Space is $O(1)$. It performs at most $n-1$ swaps.

Describe how bubble sort works.

Bubble sort repeatedly steps through the list, comparing adjacent elements and swapping them if out of order, so the largest unsorted element 'bubbles' to its correct position each pass. It repeats until no swaps are needed.

State the best-, average-, and worst-case time complexity of bubble sort.

Best case $O(n)$ (already sorted, with an early-exit optimization), average and worst case $O(n^{2})$. Space is $O(1)$; it is stable.

Describe how insertion sort works.

Insertion sort builds the sorted array one element at a time: it takes the next element and inserts it into its correct position among the already-sorted prefix by shifting larger elements rightward.

State the best-, average-, and worst-case time complexity of insertion sort.

Best case $O(n)$ (nearly sorted input), average and worst case $O(n^{2})$. Space is $O(1)$; it is stable and efficient for small or nearly-sorted data.

Among selection, bubble, and insertion sort, which adapts best to nearly-sorted input and why?

Insertion sort — for nearly-sorted data it does few shifts per element, approaching its best case of $O(n)$. Selection sort is always $O(n^{2})$, and bubble sort only reaches $O(n)$ with an early-exit check.

What is the divide-and-conquer algorithmic paradigm?

Divide and conquer solves a problem by (1) dividing it into smaller subproblems of the same type, (2) conquering each subproblem recursively, and (3) combining their solutions into the solution of the original problem. Examples: mergesort, quicksort, binary search.

State the Master Theorem form for divide-and-conquer recurrences.

For $T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n)$ with $a \geq 1$, $b > 1$: compare $f(n)$ to $n^{\log_b a}$. If $f(n)$ is polynomially smaller, $T(n)=\Theta(n^{\log_b a})$; if equal (up to log factors), $T(n)=\Theta(n^{\log_b a}\log n)$; if larger (and regularity holds), $T(n)=\Theta(f(n))$.

Describe the mergesort algorithm.

Mergesort divides the array into two halves, recursively sorts each half, then merges the two sorted halves into a single sorted array. It is a divide-and-conquer, comparison-based sort.

State the time and space complexity of mergesort.

Time complexity is $O(n \log n)$ in best, average, and worst cases, from the recurrence $T(n) = 2T\!\left(\frac{n}{2}\right) + O(n)$. Space is $O(n)$ for the auxiliary merge array; it is stable.

Why is mergesort preferred for sorting linked lists or external (disk-based) data?

Mergesort accesses data sequentially and merges without random access, so it works efficiently on linked lists (no extra space needed for the merge) and on data too large to fit in memory (external sorting).

Describe the quicksort algorithm.

Quicksort picks a pivot element, partitions the array so that elements smaller than the pivot come before it and larger ones after it (placing the pivot in its final position), then recursively sorts the two partitions. It is in-place and comparison-based.

State the best/average and worst-case time complexity of quicksort, and when the worst case occurs.

Best and average case: $O(n \log n)$. Worst case: $O(n^{2})$, occurring with consistently unbalanced partitions (e.g., already-sorted input with a fixed first/last pivot). Space is $O(\log n)$ for the recursion stack.

Contrast mergesort and quicksort on worst-case time, space, and stability.

Mergesort: worst case $O(n \log n)$, needs $O(n)$ extra space, stable. Quicksort: worst case $O(n^{2})$ but $O(n \log n)$ average, in-place ($O(\log n)$ stack), not stable. Quicksort is usually faster in practice due to better cache locality and low constants.

What is a graph, and what are its two fundamental components?

A graph $G = (V, E)$ is a collection of vertices (nodes) $V$ and edges $E$ connecting pairs of vertices. It models pairwise relationships and may be directed or undirected, weighted or unweighted.

Distinguish a directed graph from an undirected graph, and define the degree of a vertex.

In an undirected graph edges have no direction (an edge $\{u,v\}$ is bidirectional); a vertex's degree is its number of incident edges. In a directed graph (digraph) edges are ordered pairs $(u,v)$; each vertex has an in-degree (incoming) and out-degree (outgoing).

Compare the space complexity of an adjacency matrix versus an adjacency list for a graph with $V$ vertices and $E$ edges.

Adjacency matrix: $O(V^{2})$ space, $O(1)$ edge lookup — good for dense graphs. Adjacency list: $O(V + E)$ space, $O(\deg(v))$ edge lookup — good for sparse graphs.

Compare BFS and DFS graph traversals: data structure used and complexity.

BFS (Breadth-First Search) explores level by level using a queue and finds shortest paths in unweighted graphs. DFS (Depth-First Search) explores as deep as possible using a stack (or recursion). Both run in $O(V + E)$ time with an adjacency list.