Programming & Data Structures

Sheet 1

Arrays, Linked Lists, Stacks & Queues

1 formula

Core concepts

• Array access O(1); array insert/delete in the middle O(n)
• Singly linked list: insert/delete at head O(1); search O(n); tail ops O(1) only with a tail pointer
• Stack push/pop/peek: O(1)
• Queue enqueue/dequeue: O(1) with proper head/tail tracking

Key formulas

Circular Queue Full Check ☆

\[ (rear+1)\bmod \text{size} = front \]

Test your recall

Can you recall the circular queue full check formula?

Reveal formula

\[ (rear+1)\bmod \text{size} = front \]

GATE traps 4 traps

Stack-as-list needs head-only ops

A stack backed by a singly linked list must insert/delete only at the HEAD for O(1) -- doing it at the tail without a tail pointer is O(n), a common bad-implementation trap option.

The rear+1 trick disambiguates full/empty

Circular queue 'full' and 'empty' both look like front==rear if you're not careful -- the (rear+1)%size==front trick (sacrificing one slot) is the standard way GATE expects you to disambiguate them.

Reversing a list is O(n) time, O(1) space

Reversing a singly linked list in place is O(n) time, O(1) space -- a classic hand-trace question; track prev/curr/next carefully since one wrong pointer swap changes the whole answer.

Doubly linked = O(1) deletion

Doubly linked lists trade one extra pointer per node for O(1) deletion given only a node pointer (no need to search for the predecessor) -- a common 'why use this' conceptual question.

Sheet 2

Trees & Heaps

4 formulas

Core concepts

• Full binary tree: leaf nodes = internal nodes + 1
• BST search/insert/delete: O(h); O(log n) average, O(n) worst case (skewed)
• AVL tree: height always O(log n), balance factor in {-1, 0, 1}
• Build-heap O(n); heapify O(log n); extract-min/max O(log n)

Key formulas

Max Nodes at Height h ☆

\[ 2^{h+1}-1 \]

Min Height for n Nodes ☆

\[ \lceil \log_2(n{+}1) \rceil - 1 \]

0-Indexed Heap Indices ☆

\[ \text{parent}=\lfloor (i{-}1)/2 \rfloor,\ \text{left}=2i{+}1,\ \text{right}=2i{+}2 \]

for node i

Distinct Binary Trees ☆

\[ C_n = \frac{(2n)!}{(n{+}1)!\,n!} \]

Catalan number

Test your recall

Can you recall the max nodes at height h formula?

Reveal formula

\[ 2^{h+1}-1 \]

GATE traps 4 traps

Full vs. complete are different

'Full' (every node has 0 or 2 children) and 'complete' (all levels filled except possibly the last, left to right) are DIFFERENT tree properties -- GATE routinely tests this exact distinction with tree diagrams.

A plain BST can degrade to O(n)

A plain BST's worst-case height is O(n), not O(log n) -- only balanced trees (AVL, Red-Black) guarantee O(log n); a BST built from already-sorted input degrades to a linked list.

Build-heap is O(n), not O(n log n)

Build-heap is O(n), NOT O(n log n) -- one of the most commonly misremembered results (the loose per-element bound gives O(n log n), but the tight sum-of-heights analysis gives O(n)).

In-order BST traversal is sorted

In-order traversal of a BST always yields sorted order -- a fast sanity check for any tree-reconstruction question.

Sheet 3

Hashing & Complexity

5 formulas

Key formulas

Load Factor ☆

\[ \alpha = n/m \]

n keys, m slots

Expected Search (Chaining) ☆

\[ O(1+\alpha) \]

Linear Probing ☆

\[ h(k,i) = (h(k)+i) \bmod m \]

Quadratic Probing ☆

\[ h(k,i) = (h(k)+c_1 i+c_2 i^2) \bmod m \]

Double Hashing ☆

\[ h(k,i) = (h_1(k)+i\,h_2(k)) \bmod m \]

Test your recall

Can you recall the load factor formula?

Reveal formula

\[ \alpha = n/m \]

GATE traps 4 traps

Double hashing avoids clustering

Linear probing suffers from primary clustering (occupied runs grow and degrade performance) -- double hashing avoids this, a favorite conceptual comparison question.

Deletion needs a tombstone

Deleting a key in open addressing needs a 'deleted' marker (tombstone), NOT simply clearing the slot -- clearing it outright breaks the probe sequence for other keys, a genuine correctness bug, not just a style choice.

Open addressing caps at α ≤ 1

A load factor greater than 1 is only possible with chaining -- open addressing requires alpha <= 1 since every key needs its own slot, a quick elimination trick on MCQs.

Collisions are inevitable near α=1

Even a perfectly uniform hash function can't avoid collisions as load factor approaches 1 -- that's a pigeonhole consequence, not a hash-quality problem.