Revision approach
- Structure rules and representations
- Operation traces
- Seven blueprint items
- Common structures
- Searching and sorting implementations
- Practical structure selection
- Structure selection and operation traces
👁 Full explanation
Learn each structure through its rules, representation and operation traces. The seven blueprint items require understanding common structures, implementing searching and sorting, and selecting structures for practical problems. This chapter develops core data structures and algorithms through definitions, traces and cost comparisons. - Representation before tracing
- Label indices or pointers
- Empty and full conventions
👁 Full explanation
Draw the representation, label indices or pointers, and state the empty/full convention before tracing. - Comparable cost assumptions
- Fixed capacity versus resizing
- Balanced versus arbitrary trees
- Expected versus worst case
👁 Full explanation
Compare costs under the same assumptions: fixed capacity or resizing, balanced or arbitrary tree, expected or worst case. - Independent practice
- Invariant-based justification
- Short calculations
👁 Full explanation
Practise without answer keys, then justify every choice using an invariant or a short calculation.
DSA01
Data types and representations
[Exam Focus]- ADT versus representation
- ADT values and operations
- Array-backed LIFO stack
- Linked-node LIFO stack
- Abstraction: relevant details
- Patient urgency and arrival order
- Hair colour irrelevant
👁 Full explanation
An abstract data type (ADT) defines values and operations; representation supplies implementation. Arrays or linked nodes can implement the same LIFO stack. Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not. - Structure classifications
- Linear: arrays, lists, stacks, queues
- Trees: hierarchies
- Graphs: general connections
- Heterogeneous records
- Integer, character, floating fields
- Ordinary array: one element type
👁 Full explanation
Arrays, linked lists, stacks and queues are linear. Trees model hierarchies; graphs model general connections. A record grouping integer, character and floating fields is heterogeneous; an ordinary array has one element type.
7 related practice questions
Blueprint: DSA1, DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- ADT versus representation
DSA02
Arrays: access, capacity, shifting
[Exam Focus]- Array address arithmetic
- Equal-size elements
- Zero-based indexing
- address(A[i])=base+i×element_size
- RAM positional access: O(1)
- Row-major rectangular matrix
- base+(row×columns+column)×element_size
👁 Full explanation
For equal-size elements, address(A[i]) = base + i × element_size under zero-based indexing. This arithmetic gives constant-time positional access in the usual RAM cost model. A row-major rectangular matrix uses base + (row × columns + column) × element_size. - Array capacity and growth
- Fixed capacity chosen beforehand
- Capacity choice: beyond compile time
- Resizing: larger block and copy
- Middle insertion: linear shifts
- Spare-capacity append: O(1)
- Resizing append: O(n)
- Geometric growth: amortized O(1) append
👁 Full explanation
A fixed array has a chosen capacity; the choice need not occur at compile time. A resizable array allocates a larger block and copies when needed. Inserting in the middle shifts later elements, so it costs linear time. Appending into spare capacity is constant; a resizing append can be linear, though repeated geometric growth gives amortized constant append cost. - Worked example Insertion by rightward shifting
- Spare slot required
- Insert 9 at index 1
- Shift 6 before 4
- [2,4,6]→[2,9,4,6]
👁 Full explanation
Work it throughInsert 9 at index 1 of [2,4,6] with a spare slot: shift 6 then 4 right, giving [2,9,4,6].
8 related practice questions
Blueprint: DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Array address arithmetic
DSA03
Operations, records, memory ownership
- Structure operations
- Traversal: every item
- Searching: target location
- Insertion/deletion: membership changes
- Updating: stored value changes
- Sorting: item reordering
- Merging: sequence combination
- Sorted merge: smaller front first
- [1,4]+[2,3]→[1,2,3,4]
- Destruction: owned storage release
👁 Full explanation
Traversal processes every item; searching locates a target; insertion and deletion change membership; updating changes a stored value. Sorting reorders items, while merging combines sequences. To merge sorted [1,4] and [2,3], repeatedly emit the smaller front, producing [1,2,3,4]. Destroying a structure releases owned storage. - Records and memory ownership
- C struct: named fields
- Array and pointer fields
- Singly linked node: payload, same-type link
- C declaration: no field initializers
- Modern C++: default member initializers
- new↔delete
- new[]↔delete[]
- Repair links before freeing
- No dereferencing freed nodes
👁 Full explanation
A C struct groups named fields, including arrays and pointers. A singly linked node needs payload plus a same-type link. C fields cannot have initializers inside the type declaration; modern C++ permits default member initializers. In C++, match new with delete and new[] with delete[]. Repair links before freeing a node; never dereference it afterwards.
5 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Structure operations
DSA04
Algorithm properties
- Separate algorithm obligations
- Finiteness: every valid input terminates
- Definiteness: unambiguous instructions
- Effectiveness: executable steps
- Correctness: specified valid-input results
- Finite algorithms can be incorrect
👁 Full explanation
Finiteness means termination after finitely many steps for every valid input. Definiteness means each instruction has one interpretation; effectiveness means each step is executable. Correctness means meeting the stated result for every valid input. A finite program can still return the wrong answer. - Problem and algorithm specification
- Inputs, outputs, assumptions
- Procedure language independence
- Implementation language dependence
- Efficiency resource model
- Omitted characteristic ≠ false characteristic
👁 Full explanation
A problem specifies inputs, outputs and assumptions. Language independence concerns the procedure, not its implementation. Efficiency needs a resource model. An unfamiliar characteristic is not false merely because a teaching list omits it.
3 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Separate algorithm obligations
DSA05
Resource cost models
- Resource cost models
- Time: chosen operations
- Space: memory and live recursive frames
- Distributed communication volume
- Assignment unit ≠ one second
- Sequential costs add
- Independent nested iteration counts multiply
- Conditional worst case: test+costlier branch
👁 Full explanation
Time counts chosen operations; space counts memory, including live recursive frames. Distributed algorithms may also measure communication volume. A single assignment is one unit in the elementary model, not literally one second. Sequential blocks add costs; independent nested loops multiply their iteration counts. Conditional worst-case cost includes the test and the more expensive branch. - Input-case comparisons
- Equal input sizes
- Best, average, worst cases
- Average requires distribution
- Expected total=m f(n)
- Independence unnecessary
- Exact coefficients depend on operation counting
👁 Full explanation
Best, average and worst compare equal-size inputs; average needs a distribution. For m operations each with mean cost f(n), expected total is m f(n), without requiring independence. Exact coefficients depend on which elementary operations count.
8 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Resource cost models
DSA06
Asymptotic bounds
- Asymptotic bound meanings
- Eventually nonnegative functions
- O: f(n)≤c g(n), n≥k
- c>0
- Ω: reversed inequality
- Θ: upper and lower bounds
- o: f/g→0
- ω: f/g→∞
- Best/average/worst-case functions
- Space functions also bounded
👁 Full explanation
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both. Little-o means f/g tends to zero; little-omega means it grows without bound. These relations can describe best-case, average-case, worst-case or space functions. - Polynomial bounds and witnesses
- 3n²+4n+1≤8n², n≥1
- O(n²): c=8,k=1
- Ignore constants and lower-order terms
- Transitivity: f≤cg≤cdh
- Both thresholds required
👁 Full explanation
For n≥1, 3n²+4n+1≤8n²: c=8,k=1 witness O(n²). Constants and lower-order terms disappear from tight polynomial growth. Transitivity multiplies witnesses: f≤c g≤cd h beyond both thresholds. - Worked example Increasing growth rates
- 1<log n<n<n log n
- n log n<n²<n³
- n³<2^n<3^n
- 3^n<n!<n^n
- Log bases: constant-factor difference
👁 Full explanation
Work it throughIncreasing representative rates: 1, log n, n, n log n, n², n³, 2^n, 3^n, n!, n^n. Logarithm bases differ only by a constant factor. - Exam trap Tightness versus valid upper bounds
- Linear functions also O(n²)
- Tightest listed order usually intended
- Mixed O/Θ options may overlap
👁 Full explanation
A linear function is also O(n²). MCQs usually intend the tightest listed order; mixed O and Theta options may overlap.
8 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Asymptotic bound meanings
DSA07
Loops and hidden access costs
- Loop and stack counting
- i*=2: about log₂n iterations
- Independent nested n-loops: Θ(n²)
- Constant work per iteration
- n recursive levels: Θ(n) stack
- Constant live storage per level
👁 Full explanation
A loop i=1; i<n; i*=2 takes about log₂n iterations. Two independent n-iteration loops nested around constant work take Theta(n²). An n-level ordinary recursion with constant live storage per level needs Theta(n) stack space. - Hidden indexed-access costs
- List implementation matters
- Java LinkedList.get(i): nearer-end traversal
- get(0),get(2),…: Θ(N²) total
- Many middle indices: linear traversal each
- Iterator scan: Θ(N)
- Damaged return: runtime uncertainty
- Missing cost convention: no exact runtime
👁 Full explanation
Indexed access is not constant for every List implementation. Java LinkedList.get(i) walks from the nearer endpoint. Summing get(0), get(2), get(4), … over a length-N list still gives Theta(N²), because a linear number of middle indices each require linear traversal. An iterator scans once in linear time. An exact executable runtime requires valid code and an explicit cost convention.
2 related practice questions
Note references: DSA_NEW, DSA_JAVA
- Loop and stack counting
DSA08
Singly linked chains
[Exam Focus]- Singly linked chain representation
- Node: data and next
- Head: first node
- Noncircular terminator: null
- Empty: head==null
- Dynamic node allocation
- Pointer storage overhead
- No direct index arithmetic
👁 Full explanation
A singly linked node contains data and next. Head points to the first node; null ends a noncircular chain. Empty means head==null. Nodes allocated as needed grow dynamically, with pointer overhead and no direct index arithmetic. - Linked-chain traversal
- Follow next from head
- Stop at null
- Display/count: process every node
- Counting: Θ(n)
- Maintained size avoids recounting
- Array-linked lists still follow links
- Separate positional index exception
👁 Full explanation
To display or count nodes, follow next from head until null, processing each node. Counting is Theta(n) unless size is maintained. An array-linked list still follows links unless separately position-indexed.
16 related practice questions
Blueprint: DSA1 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Singly linked chain representation
DSA09
Safe linked-list updates
[Exam Focus]- Safe insertion and head deletion
- Prepend: new.next=head; head=new
- Insert-after: new.next=p.next before p.next=new
- Head-only append: tail traversal
- Maintained tail avoids append traversal
- Delete-head: save old=head
- Advance head=head.next
- Release old in C++
👁 Full explanation
Prepend with new.next=head; head=new. To insert after a known predecessor p, set new.next=p.next before p.next=new. Appending with only head requires a tail traversal; maintaining tail avoids it. Delete the head by saving old=head, advancing head=head.next and releasing old in C++. - Deletion boundary cases
- Singly linked tail needs predecessor
- Known tail insufficient
- Empty and single-node cases
- Only-node removal: head=tail=null
- Successor deletion: bypass before deallocation
- Clear owned chain: visit/release every node
👁 Full explanation
Deleting the tail of a singly linked list requires its predecessor, even when tail itself is known. Handle empty and single-node lists separately; after removing the only node, set both head and tail to null. To remove a known successor, bypass it before deallocation. Clearing an owned n-node chain visits and releases every node. - Three-pointer chain reversal
- Initially prev=null, cur=head
- Save next=cur.next
- Redirect cur.next=prev
- Advance prev=cur; cur=next
- Finish head=prev
- Linear time
- Constant extra pointers
👁 Full explanation
Reverse a chain with prev=null, cur=head: save next=cur.next; set cur.next=prev; advance prev=cur and cur=next; finish with head=prev. This is linear time and constant extra pointers. - Worked example Insertion link-order trace
- 3→7→9; insert 5 after 3
- First 5→7, then 3→5
- Reversed assignments lose 7→9
👁 Full explanation
Work it throughFor 3→7→9, insert 5 after 3: first point 5 at 7, then 3 at 5. Reversing those assignments can lose access to 7→9.
10 related practice questions
Blueprint: DSA1, DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Safe insertion and head deletion
DSA10
List variants and practical choices
[Exam Focus]- Doubly linked and circular lists
- Doubly linked nodes: prev
- Head/tail: constant-time end operations
- Singly linked tail deletion: predecessor needed
- Circular tail.next=head
- Traversal stops on return to start
- Handle empty circular list separately
👁 Full explanation
Doubly linked nodes add prev; head and tail enable constant-time operations at both ends. Singly linked tail deletion still needs its predecessor. A circular tail links back to head; stop traversal on returning to the start, handling empty separately. - Practical linked-list selection
- Changing sequences with known insertion positions
- Position search: linear
- Polynomial terms: coefficient, exponent
- Directory and block links
- Nonbinary-tree child lists
- Hash chains
- Browser history: doubly linked cursor
- Playlist: circular option
- Airline seats: specify record model
👁 Full explanation
Lists suit changing sequences when references to insertion positions are already available. Finding a position is still linear. Lists can hold polynomial terms (coefficient, exponent), directory or block links, child lists in nonbinary trees, and hash chains. Browser history can use a doubly linked cursor. A playlist may be circular; airline seat lookup requires a specified seat-record model, not an automatic linked-list answer. - Index access comparison
- Array: O(1)
- Singly linked list: O(n) worst
👁 Full explanation
Operation Array Singly linked list Access index i O(1) O(n) worst - Front insertion comparison
- Array: O(n) shifts
- Singly linked list: O(1)
👁 Full explanation
Operation Array Singly linked list Insert at front O(n) shifts O(1) - Append comparison
- Array spare capacity: O(1)
- Linked list with tail: O(1)
- Linked list head only: O(n)
👁 Full explanation
Operation Array Singly linked list Append O(1) with spare capacity O(1) with tail; O(n) head only - Tail deletion comparison
- Array: O(1)
- Singly linked list: O(n)
- Predecessor required
👁 Full explanation
Operation Array Singly linked list Delete tail O(1) O(n), predecessor needed
10 related practice questions
Blueprint: DSA1, DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Doubly linked and circular lists
DSA11
Stack implementation conventions
[Exam Focus]- Stack convention and operations
- LIFO=FILO
- Push: insert
- Pop: remove/return top
- Peek: observe top
- Zero-based occupied-slot top
- Empty: top=-1
- Full: top=C-1
- Check before A[++top]=x
- Check before returning A[top--]
👁 Full explanation
Stack policy is LIFO, equivalently FILO. Push inserts, pop removes/returns top, and peek only observes. With zero-based occupied slots, top=-1 is empty and top=C-1 is full. Check before A[++top]=x or returning A[top--]. - Alternative stack implementations
- Count-based empty: size=0
- Count-based push: A[size++]=x
- Keep empty/full conventions consistent
- Fixed-array push/pop: O(1)
- Linked stack: head insertion/deletion O(1)
- Singly linked tail pop: predecessor traversal
👁 Full explanation
A count-based alternative uses size=0 and A[size++]=x. Do not combine its empty/full tests with the top-index convention. Fixed-array push/pop are constant time. Linked stacks achieve constant time by inserting and deleting at the head; using a singly linked tail for pop would require a predecessor traversal. - Exam trap Stack failure conditions
- Overflow: insertion into full storage
- Underflow: removal from empty storage
- isEmpty check ≠ underflow
👁 Full explanation
Overflow is an attempted insertion into full storage; underflow is an attempted removal from empty storage. Merely checking isEmpty does not underflow.
25 related practice questions
Blueprint: DSA1 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Stack convention and operations
DSA12
Stack traces and applications
[Exam Focus]- Stack operation tracing
- Record bottom-to-top after each instruction
- Record popped values separately
- Push 1,2; pop→2; remaining [1]
- Complete output: 2,2,1,1,2
👁 Full explanation
Write the stack bottom-to-top after every instruction and record popped values separately. Push 1, push 2, pop emits 2 and leaves [1]. Push 1, push 2, pop, pop, pop then emits 2,1,1; push 2, pop emits 2. The complete output is 2,2,1,1,2. - Stack applications
- Nested calls: latest returns first
- Bracket matching: openings pushed
- Closing bracket matches top
- Reversal: push input then pop
- Undo: latest action→redo
- Redo: action→undo
- New edit after undo: clear redo
- DFS/backtracking: latest pending choice
👁 Full explanation
Calls nest on a runtime stack; the latest call returns first. Bracket matching pushes opening brackets and matches each closing bracket against top. Reversal pushes input then pops it. Undo moves the latest action from undo to redo; redo moves it back. A new edit after undo normally clears redo. DFS and backtracking use the same latest-pending-choice discipline.
14 related practice questions
Blueprint: DSA1, DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Stack operation tracing
DSA13
Expression notation and evaluation
- Expression notation and conversion
- Infix: operator between operands
- Precedence and parentheses
- Prefix: operator first
- Postfix: operator last
- Fixed arity determines grouping
- Infix→postfix: output operands immediately
- Stack pending operators
- Pop higher precedence before pushing
- Left-associative: pop equal precedence
- Parentheses override operator order
👁 Full explanation
Infix places an operator between operands and uses precedence and parentheses. Prefix places it first; postfix places it last. Their fixed operator arity determines grouping. To convert infix to postfix, output operands immediately and hold operators on a stack. Pop higher-precedence operators before pushing a new operator; also pop equal precedence for left-associative operators. Parentheses temporarily override this order. - Postfix evaluation and expression trees
- Push operands
- Binary operator: pop right then left
- Push left op right
- Prefix tree traversal: preorder
- Postfix tree traversal: postorder
- Stack useful, other representations possible
👁 Full explanation
To evaluate postfix, push operands. At a binary operator, pop right operand first, then left, and push left op right. Build an expression tree for either prefix (preorder) or postfix (postorder); a stack is useful but is not the only possible conversion representation. - Worked example Expression conversion traces
- A+B*C-D/E→ABC*+DE/-
- 8 3 -: pop 3 then 8
- 8−3=5
- (A+B)*C→AB+C*
- Prefix: *+ABC
👁 Full explanation
Work it throughA+B*C-D/E becomes ABC*+DE/-. For 8 3 -, pop 3 then 8, producing 5. (A+B)*C becomes AB+C* and prefix *+ABC.
5 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT, DSA_PREFIX
- Expression notation and conversion
DSA14
FIFO queue operations
[Exam Focus]- Ordinary queue policy
- FIFO=first-come, first-served
- Enqueue at rear
- Dequeue/peek at front
- Linked head/tail operations: O(1)
- Append tail, remove head
- First insertion: set both pointers
- Last removal: clear both pointers
- Head-only insertion: tail traversal
👁 Full explanation
An ordinary queue enqueues at rear, dequeues at front, and peeks at front. This is FIFO or first-come, first-served. A linked implementation with head and tail supports both operations in constant time: append at tail, remove at head. The first insertion sets both pointers; removing the last item clears both. With head alone, insertion must traverse to the tail. - Queue applications and modeling
- Equal-priority printer jobs
- Shared-resource waiting
- Asynchronous buffers
- Level-order exploration
- Play sequence
- Airline seats versus waiting requests
- Application name insufficient for representation
👁 Full explanation
FIFO suits equal-priority printer jobs, shared-resource waiting, asynchronous buffers and level-order exploration. A play sequence can also use a queue. Distinguish airline seat records from waiting requests; an application name alone does not force one representation. - Worked example Conditional queue trace
- Enqueue 4,8; peek=4
- peek>5 false: no removal
- Enqueue 1,6; dequeue
- Result: [8,1,6]
👁 Full explanation
Work it throughEnqueue 4,8; peek is 4, so a conditional removal only if peek>5 does nothing. Enqueue 1,6 then dequeue: [8,1,6].
30 related practice questions
Blueprint: DSA1, DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Ordinary queue policy
DSA15
Circular buffer conventions
[Exam Focus]- Circular buffer count convention
- Noncircular rear exhaustion: false overflow
- Released front slots reusable
- Modulo wraparound
- Front: next removal
- Size: item count
- Insertion slot=(front+size)%C
- Empty: size==0
- Full: size==C
👁 Full explanation
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front. A circular queue reuses slots with modulo arithmetic. Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C. - Circular dequeue and alternate convention
- Read A[front]
- front=(front+1)%C
- Decrease size
- Alternative: reserve one unused slot
- Full: next(rear)==front
- Different empty test and capacity
- State convention before tracing
👁 Full explanation
Dequeue reads A[front], sets front=(front+1)%C and decreases size. An alternative reserves one unused slot and uses next(rear)==front for full; its empty test and capacity differ. State the convention before tracing. - Worked example Physical versus logical queue order
- Capacity six, initially full
- Remove 11; enqueue 9 at slot 0
- Physical: [9,13,15,17,19,21]
- Logical: [13,15,17,19,21,9]
- Noncircular version may overflow
👁 Full explanation
Work it throughFull capacity-six [11,13,15,17,19,21], front=0: remove 11, then enqueue 9 into slot 0. Physical array: [9,13,15,17,19,21]; logical front-to-rear queue: [13,15,17,19,21,9]. A noncircular version can instead overflow.
8 related practice questions
Blueprint: DSA1, DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Circular buffer count convention
DSA16
Deques and queue policies
[Exam Focus]- Deque versus dequeue
- Deque: insertion/removal at both ends
- No guaranteed middle access
- Linked endpoints: O(1)
- Linked middle indexing: O(n)
- Circular-array deque: possible indexed access
- Dequeue: removal operation
👁 Full explanation
A deque permits both-end insertion/removal without guaranteeing middle access. Endpoint-linked operations are constant but middle indexing is linear. A circular-array deque may support indexed access. Dequeue names removal; deque names the structure. - Queue combination and capacity policies
- Merge: concatenate or alternate fronts
- Predicate split: matching output queue
- Append preserves subgroup order
- Full buffer: reject, block, overwrite
- Capacity alone specifies no policy
👁 Full explanation
Merging FIFO queues needs an explicit policy: append one sequence after another or alternate their fronts. Splitting by a predicate preserves each subgroup’s original order if each removed item is appended to its matching output queue. A fixed-capacity buffer also needs a full-policy choice: reject, block or overwrite. Capacity alone does not choose a policy.
10 related practice questions
Blueprint: DSA1 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Deque versus dequeue
DSA17
Priority queues and tie rules
[Exam Focus]- Priority queue service
- Minimum or maximum priority convention
- Urgency before arrival
- Interleaved insertions and extractions
- Binary heap peek: O(1)
- Binary heap insert/extract: O(log n)
👁 Full explanation
A priority queue returns the smallest or largest priority key under its convention. Urgent patients may precede earlier arrivals. Insertions and extractions can interleave. Binary heaps support constant peek and logarithmic insert/extract. - Priority queue implementations and ties
- Unordered sequence: cheap insertion
- Unordered sequence: linear extremum removal
- Ordered sequence: reversed tradeoff
- Equal priority ≠ inherent FIFO
- Stable service: (priority,arrival_counter)
- Specify priority direction and tie rule
👁 Full explanation
Arrays and lists can also implement priority queues: an unordered sequence gives cheap insertion but linear extremum removal; an ordered sequence reverses that tradeoff. Equal priorities have no inherent FIFO guarantee. If stable service is required, compare (priority, arrival_counter). Choose the priority direction and tie rule before tracing. - Exam trap FIFO tie-policy trap
- Guide assumes undefined stability
- FIFO ties: additional policy
- No universal priority-queue stability
👁 Full explanation
FIFO ordering among equal priorities requires an explicit stability policy. That is an additional policy, not a universal priority-queue rule.
6 related practice questions
Blueprint: DSA1, DSA3 · Note references: DSA_SHORT, DSA_PQ
- Priority queue service
DSA18
Tree vocabulary and binary shapes
- Rooted-tree vocabulary
- Root: no parent
- Other nodes: one parent
- Connected and acyclic
- n nodes: n−1 edges
- Unique path between each pair
- Depth: root-to-node edges
- Height: maximum depth
- Single-node height: zero
- Leaves: no children
👁 Full explanation
A rooted tree has one parentless root and one parent per other node. It is connected and acyclic, has n-1 edges, and one path between any pair. Depth counts root-to-node edges; height is maximum depth. A single-node tree therefore has height zero. Leaves have no children. - Binary-tree shape distinctions
- Binary: at most two children
- Full: zero or two children
- Complete: earlier levels filled
- Complete: last level fills leftward
- Perfect: leaves at same level
- Perfect: two children per internal node
- Balanced: logarithmic height under stated rule
- Balanced ≠ necessarily perfect
👁 Full explanation
Binary means at most two children. Full means each node has zero or two children. Complete means all earlier levels are filled and the last fills from left. Perfect means all leaves share a level and every internal node has two children. Balanced means height stays logarithmic under a stated rule; it does not require a perfect shape.
9 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Rooted-tree vocabulary
DSA19
BST ordering and search
[Exam Focus]- Global BST ordering invariant
- Distinct keys assumption
- Entire left subtree smaller
- Entire right subtree larger
- Immediate-child checks insufficient
- 10→left 5→right 12: invalid
- Duplicates: count or placement policy
👁 Full explanation
With distinct keys, every key in a node’s left subtree is smaller and every key in its right subtree is larger. Immediate-child comparisons alone are insufficient: root 10, left child 5, and 5’s right child 12 violate the root’s restriction. Duplicates require a separate count or placement policy. - BST operations and search costs
- Compare; follow one child
- Search ends at equality or null
- Insertion: same path, new leaf
- Operation cost: O(height)
- Balanced: logarithmic; chain: linear
- Root hit: Θ(1) best case
- Optimal BST: access probabilities
- Minimize expected search cost
- Construction distinct from searching
👁 Full explanation
Search compares at each node and follows one child until equality or null. Insertion uses that same path to attach a new leaf. Operations cost O(height): logarithmic for balanced trees, linear for a chain. Best-case successful search is Theta(1), a root hit. An optimal BST minimizes expected search cost using access probabilities; constructing it is a different problem from searching it. - Optimal-BST dynamic programming
- Every key interval
- Try each possible root
- O(n²) intervals × O(n) roots
- Construction: O(n³)
- Probability-weighted search depth
- Objective ≠ minimum worst-case height
👁 Full explanation
Standard optimal-BST dynamic programming tries each possible root for each key interval: O(n²) intervals times O(n) roots gives O(n³) construction. It minimizes probability-weighted search depth, not necessarily worst-case height. - Worked example BST insertion shape trace
- Insert 40,20,50,10,30,60
- 40 children: 20,50
- 20 children: 10,30
- 50 right child: 60
- Height: two edges
- Sorted 1,2,3,4,5: right chain
👁 Full explanation
Work it throughInsert 40,20,50,10,30,60: root children are 20 and 50; 20 has 10,30; 50 has right child 60. Height is two edges. Sorted insertions 1,2,3,4,5 instead form a right chain.
13 related practice questions
Blueprint: DSA3 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT, DSA_OBST
- Global BST ordering invariant
DSA20
Tree traversal rules
- Tree traversal rules
- Preorder: node,left,right
- Inorder: left,node,right
- Postorder: left,right,node
- Recursive application; null does nothing
- Sorted inorder requires BST
- Preorder: copying
- Postorder: children-before-parent deletion
- Level order: FIFO queue
👁 Full explanation
Preorder visits node,left,right; inorder left,node,right; postorder left,right,node. Apply recursively; null children do nothing. Inorder returns sorted keys only for a BST. Preorder supports copying, postorder supports deleting children before parents, and level order uses a FIFO queue. - Traversal worked tree
- Root 4; children 2,6
- Leaves 1,3,5,7
- Preorder: 4,2,1,3,6,5,7
- Inorder: 1,2,3,4,5,6,7
- Postorder: 1,3,2,5,7,6,4
- Level order: 4,2,6,1,3,5,7
- Randomized visitation possible
- Randomized ≠ standard named DFS order
👁 Full explanation
For root 4, children 2 and 6, and leaves 1,3,5,7: preorder is 4,2,1,3,6,5,7; inorder is 1,2,3,4,5,6,7; postorder is 1,3,2,5,7,6,4. Level order is 4,2,6,1,3,5,7. Randomized visitation is possible; it is simply not one of these standard named depth-first orders.
4 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Tree traversal rules
DSA21
BST deletion methods
- BST deletion cases
- Leaf: clear parent link
- One child: parent bypass
- Two children: copy inorder replacement
- Predecessor: left-subtree maximum
- Successor: right-subtree minimum
- Delete replacement at original position
- Replacement deletion: at most one child
👁 Full explanation
A leaf can be detached by clearing its parent link. For one child, make the parent bypass the node and point to the child. For two children, copy the inorder predecessor (left-subtree maximum) or successor (right-subtree minimum), then delete that replacement from its original location. That second deletion has at most one child. - BST deletion by merging
- Promote right subtree
- Attach old left at right minimum
- Symmetric left promotion
- Root deletion: update root
- Copying versus reconnecting: different valid shapes
- Name deletion method before tracing
👁 Full explanation
Deletion by merging is another approach. Promote the right subtree and attach the entire old left subtree to the minimum node in the promoted right subtree; or use the symmetric left promotion. Update root itself when deleting root. Copying values and reconnecting subtrees can yield different valid shapes, so a trace must name its deletion method.
2 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- BST deletion cases
DSA22
Balanced search trees
- AVL balancing and rotations
- Balance factor=height(left)−height(right)
- Allowed factors: −1,0,1
- Insertion/deletion: update heights upward
- LL: right rotation
- RR: left rotation
- LR: left-child left, node right
- RL: symmetric double rotation
- Rotations preserve inorder keys
👁 Full explanation
AVL balance factor is height(left)-height(right); every node must have factor -1,0 or 1. After insertion or deletion, update heights upward and rotate where necessary. LL imbalance needs a right rotation; RR needs left; LR rotates the left child left then the node right; RL is symmetric. Rotations preserve inorder key order. - Balanced search-tree guarantees
- 30,20,10: LL imbalance
- Repair root 20; children 10,30
- Red-black colouring discipline
- Logarithmic height
- Avoid linear worst-case search
- Ordered ranges versus ordinary hashing
👁 Full explanation
Inserting 30,20,10 triggers LL repair: 20 becomes root with children 10,30. Red-black colouring rules provide another logarithmic-height discipline. Both prevent linear worst-case search; balanced trees also support ordered ranges unlike ordinary hashing.
5 related practice questions
Note references: DSA_SHORT, DSA_BAL
- AVL balancing and rotations
DSA23
Heap order and indexing
- Heap shape and order
- Binary heap: complete tree
- Max-heap: parent≥children
- Min-heap: reversed order
- No BST-style subtree ordering
- Max-heap root: maximum
- Distinct keys: second largest root child
- Duplicate maxima: distinct runner-up may deepen
- [9,9,9,8,7,6,5]: runner-up 8, index 3
- Minimum may occupy any leaf
- Minimum search: linear worst case
👁 Full explanation
A binary max-heap is complete with each parent at least its children; a min-heap reverses this order. Unlike BSTs, heaps do not order entire subtrees. The root is maximum. If all keys are distinct, the second largest is a root child. With duplicate maxima, the second largest distinct value may be deeper: [9,9,9,8,7,6,5] is a valid max-heap and that value is 8 at index 3. The minimum may be any leaf, requiring linear worst-case scanning. - Heap array indexing
- Zero-based root: 0
- Zero-based children: 2i+1,2i+2
- Zero-based parent: floor((i−1)/2), i>0
- One-based children: 2i,2i+1
- One-based parent: floor(i/2)
- Child index < current heap size
👁 Full explanation
Zero-based array representation: root index 0, left=2i+1, right=2i+2, parent=floor((i-1)/2) for i>0. One-based representation uses children 2i,2i+1 and parent floor(i/2). A child exists only if its index is inside the current heap size. - Exam trap Heap indexing convention trap
- Right child 2i+1: one-based
- Zero-based heap indexing
- Explicit convention change required
👁 Full explanation
The right-child formula 2i+1 assumes one-based indexing. For zero-based indexing with the root at index 0, the right-child formula is 2i+2.
6 related practice questions
Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Heap shape and order
DSA24
Heap restoration and construction
[Exam Focus]- Heap restoration and construction
- Insert at next complete-tree position
- Swim while parent order violated
- Root removal: final element→root
- Reduce heap size
- Sink with more dominant child
- Stop when heap order restored
- Swim/sink: logarithmic paths
- Bottom-up internal-node sinking: O(n)
- Repeated insertion construction: O(n log n)
👁 Full explanation
Insert at the next complete-tree position and swap upward while parent order is violated. To remove the root, move the final element to root, reduce heap size, then swap downward with the more dominant child until order holds. Each path has logarithmic length. Building bottom-up by sinking internal nodes takes linear total time; repeated independent insertions give an O(n log n) construction bound. - Worked example Max-heap removal trace
- Start [10,8,6,2,1,4,5]
- Remove 10; move 5; sink
- Result [8,5,6,2,1,4]
- Remove 8; move 4; exchange 6
- Result [6,5,4,2,1]
👁 Full explanation
Work it throughMax-heap [10,8,6,2,1,4,5]: remove 10, move 5 to root and sink, giving [8,5,6,2,1,4]. Remove 8, move 4 up then exchange with 6: [6,5,4,2,1].
1 related practice question
Blueprint: DSA2, DSA3 · Note references: DSA_MOD, DSA_PQ
- Heap restoration and construction
DSA25
Addressing and hash functions
- Direct addressing versus hashing
- Direct addressing: every possible key
- Finite universe U: Θ(|U|) slots
- Hash address h(key)∈0..m−1
- Actual entries plus bucket capacity
- h(k)=k mod 6
- 36 home address: 0
- Collision may change final storage slot
👁 Full explanation
Direct addressing reserves a position for every possible key in a finite universe U, costing Theta(|U|) slots. A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity. With h(k)=k mod 6, key 36 has home address 0; collisions may move its final storage position. - Hash-function properties
- Determinism: equal keys, same chosen-function address
- Uniformity: evenly spread expected keys
- Universal hashing: random suitable-family function
- One function chosen per table
- Choice independent of fixed key set
- No unrelated fresh function per lookup
- Collision probability controlled
- Zero collisions not guaranteed
👁 Full explanation
Determinism means repeated equal keys get the same address for the chosen function. Uniformity means expected keys spread evenly. Universal hashing chooses one function randomly from a suitable family for the table, independently of a fixed key set; it does not choose a fresh unrelated function for each lookup. Random choice controls collision probability, not a promise of zero collisions.
9 related practice questions
Note references: DSA_SHORT, DSA_UNIV
- Direct addressing versus hashing
DSA26
Collisions, probing, load factor
[Exam Focus]- Collision handling and load
- Separate chaining: bucket lists
- Load α=n/m
- α: average chain length
- Expected O(1+α): suitable distribution
- Worst case: O(n)
- Open addressing: entries inside array
- Probe until key or available slot
👁 Full explanation
Separate chaining stores colliding entries in a bucket list. Load alpha=n/m is average chain length; expected operations are O(1+alpha) under suitable distribution assumptions, with O(n) worst cases. Open addressing keeps entries inside the array and probes until a key or an available slot is found. - Probing schemes and deletion
- Linear probing: (h(k)+j)%m
- m=7; keys 10,17,24
- Home 3; final positions 3,4,5
- Quadratic probing: changing step
- Double hashing: (h1(k)+j h2(k)) mod m
- Step relatively prime to m
- Relatively prime step: all-slot coverage
- Collisions remain possible
- Deletion: tombstones or reinsertion
- Avoid premature search termination
👁 Full explanation
Linear probing tries (h(k)+j)%m. For size 7 and keys 10,17,24, all home addresses are 3 and occupied positions become 3,4,5. Quadratic probing changes the step; double hashing uses h1(k)+j h2(k), modulo m, with a step relatively prime to m to cover all slots. Neither method guarantees no collisions. Deletion needs tombstones or reinsertion so searches do not stop prematurely. - Linear-probing wraparound
- Seven slots; home address 3
- Probe order: 3,4,5,6,0,1,2
- Home slot ≠ guaranteed final slot
👁 Full explanation
At h(k)=3 in a seven-slot linear-probing table, addresses wrap 3,4,5,6,0,1,2. A home address is not guaranteed to remain the final slot.
7 related practice questions
Blueprint: DSA3 · Note references: DSA_SHORT, DSA_HASH
- Collision handling and load
DSA27
Maps, sets, dictionaries, caches
[Exam Focus]- Maps, sets, lists: contracts
- Map: unique keys→values
- Different keys may share values
- Map entries traversable
- Set: no duplicate elements
- Null policy: implementation-dependent
- Iteration order: implementation-dependent
- Lists preserve positions
- Lists generally allow duplicates
- Java LinkedList permits null
👁 Full explanation
A map associates unique keys with values; different keys may share values, and entries can be traversed. A set forbids duplicate elements. Null and iteration-order policies depend on implementation. Lists preserve positions and generally allow duplicates; Java LinkedList also permits null. - Dictionaries, symbol tables, caches
- Hashing: expected O(1) lookup
- Balanced tree: ordered O(log n) lookup
- Bounded cache: eviction policy required
- FIFO eviction: queue
- LRU: hash+doubly linked recency list
- Hit: move to recent end
- Full: evict least-recent end
- Best structure depends on operations/policies
👁 Full explanation
A dictionary or compiler symbol table can use hashing for expected constant lookup, or a balanced tree for logarithmic lookup with ordering. A bounded cache also needs eviction rules: FIFO uses a queue; LRU can combine hash lookup with a doubly linked recency list. Move a hit to the recent end and evict the least-recent end when full. No storage structure is universally best without operation and policy requirements.
8 related practice questions
Blueprint: DSA3 · Note references: DSA_MAP, DSA_SET, DSA_JAVA, DSA_SHORT, DSA_CACHE
- Maps, sets, lists: contracts
DSA28
Linear search
[Exam Focus]- Linear search cost cases
- Successive target comparisons
- Stop at equality or exhaustion
- Sorted or unsorted data
- First match: Θ(1)
- Absent/last match: n comparisons
- Worst time: Θ(n)
- Uniform successful positions: (n+1)/2 average
- Average remains linear
👁 Full explanation
Compare the target with successive elements until equal or exhausted. Unsorted data is allowed; sorted data is allowed too. A first-element match costs Theta(1). An absent target or last-position match needs n comparisons, giving Theta(n) worst time. Uniformly likely successful positions average (n+1)/2 comparisons, still linear. - When scanning suffices
- Single unsorted query: sorting rarely justified
- Small lists: setup costs matter
- Mean: examine all values
- Variance: examine all values
- Arbitrary parity counts: examine all values
- Sorting avoids none of these scans
👁 Full explanation
For a single unsorted query, sorting first is rarely justified. Small lists may favour scanning because setup matters. Sorting does not avoid examining all values for mean, variance or arbitrary parity counts.
11 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Linear search cost cases
DSA29
Binary search
[Exam Focus]- Binary search interval invariant
- Ascending random-access sequence
- lo=0; hi=n−1
- mid=lo+(hi−lo)//2
- Equality: finish
- target<A[mid]: hi=mid−1
- Otherwise lo=mid+1
- Failure: lo>hi
- Descending order: reverse comparisons
- Comparable keys; finite valid bounds
- Fixed preallocation unnecessary
👁 Full explanation
On an ascending random-access sequence, set lo=0, hi=n-1. Compute mid=lo+(hi-lo)//2. Equality finishes; if target<A[mid], set hi=mid-1; otherwise set lo=mid+1. Stop unsuccessfully when lo>hi. Reverse comparisons for descending order. Comparable keys and valid finite bounds matter; fixed allocation before population is not an extra algorithmic requirement. - Binary search costs and variants
- Worst probes=⌊log₂n⌋+1, n>0
- 100 keys: seven probes
- Million keys: about twenty probes
- Iteration: constant space
- Recursion: logarithmic stack
- Linked midpoint traversal loses logarithmic total
- Boundary variants: retain candidate at equality
👁 Full explanation
Worst probes are floor(log₂n)+1 for n>0: seven for 100 keys, about twenty for one million. Iteration uses constant space; recursion uses logarithmic stack depth. Linked midpoint traversal loses logarithmic total time. Boundary variants retain a candidate rather than stopping at equality. - Worked example Binary search worked interval
- Target 19 in [11,13,15,17,19,21]
- mid=2: 15
- Keep indices 3..5
- mid=4: 19
- Binary debugging: ordered good/bad boundary
- Arbitrary fault locations insufficient
👁 Full explanation
Work it throughFind 19 in [11,13,15,17,19,21]: mid=2 gives 15; search indices 3..5; mid=4 gives 19. Binary debugging needs an ordered good/bad boundary, not arbitrary fault locations.
22 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Binary search interval invariant
DSA30
Search variants and assumptions
[Exam Focus]- Interpolation search assumptions
- Numeric index estimation
- lo+(hi−lo)×(key−A[lo])/(A[hi]−A[lo])
- Round to valid index
- Guard equal endpoints
- Guard out-of-range targets
- Sorted, suitably uniform data
- Expected probes: O(log log n)
- Pathological distribution: linear
- Binary search: logarithmic worst case
- Binary search: no uniformity requirement
👁 Full explanation
Interpolation search estimates the index from numeric values: lo+(hi-lo)×(key-A[lo])/(A[hi]-A[lo]), rounded to a valid index. Guard equal endpoints and out-of-range targets. On sorted, suitably uniform data its expected probes can be O(log log n); pathological distributions can require linear time. Binary search gives a logarithmic worst bound without that distribution assumption. - Other sorted-search variants
- Ternary: compare two split points
- Retain relevant third
- Ternary search: logarithmic
- Jump search: block-boundary probes
- Then scan selected block
- Regular intervals: unit steps or jumps
- Interpolation also requires sortedness
- Prerequisite MCQ options may overlap
👁 Full explanation
Sorted-array ternary search compares two split points and keeps the relevant third, still logarithmic. Jump search probes block boundaries then scans within a block. Regular intervals could mean unit-step scanning or larger jumps. Interpolation also needs sortedness, so prerequisite questions can overlap binary search.
5 related practice questions
Blueprint: DSA2 · Note references: DSA_INTERP, DSA_SEARCH, DSA_JUMP
- Interpolation search assumptions
DSA31
Sorting properties and cost comparison
[Exam Focus]- Sorting properties and comparison assumptions
- Stability: preserve equal-key input order
- In-place: fixed extra element storage
- Total auxiliary space includes recursive stack
- Stable/in-place alone identify no unique algorithm
- Specify implementation, input case, resource
👁 Full explanation
Stable sorting preserves the input order of equal keys. An in-place element algorithm uses a fixed amount of extra element storage; a recursive call stack may still matter when total auxiliary space is requested. There is no single algorithm identified by stable or in-place alone. State the implementation, input case and resource being compared. - Bubble sort with early stopping
- Best: n
- Average/worst: n²
- Constant extra storage
- Stable
👁 Full explanation
Method Best / average / worst time Extra storage; usual stability Bubble with early stop n / n² / n² constant; stable - Selection sort profile
- Best/average/worst: n²
- Constant extra storage
- Unstable
👁 Full explanation
Method Best / average / worst time Extra storage; usual stability Selection n² / n² / n² constant; unstable - Insertion sort profile
- Best: n
- Average/worst: n²
- Constant extra storage
- Stable
👁 Full explanation
Method Best / average / worst time Extra storage; usual stability Insertion n / n² / n² constant; stable - Quicksort profile
- Best/average: n log n
- Worst: n²
- Average stack: log n
- Worst stack: n
- Unstable
👁 Full explanation
Method Best / average / worst time Extra storage; usual stability Quicksort n log n / n log n / n² stack usually log n average, n worst; unstable - Ordinary array mergesort profile
- All cases: n log n
- Linear extra storage
- Stable with left-first ties
👁 Full explanation
Method Best / average / worst time Extra storage; usual stability Ordinary array mergesort n log n in all cases linear; stable with left-first ties - Heapsort profile
- All cases: O(n log n) bound
- Iterative sink: constant storage
- Unstable
👁 Full explanation
Method Best / average / worst time Extra storage; usual stability Heapsort O(n log n) bound in all cases constant with iterative sink; unstable - Exam trap Overlapping bounds and logarithm placement
- n log(n²)=2n log n
- Same growth as n log n
- Different from n(log n)²
- Big-O options can overlap
👁 Full explanation
Big-O bounds can overlap. n log(n²)=2n log n, so it has the same growth as n log n, unlike n(log n)².
21 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Sorting properties and comparison assumptions
DSA32
Bubble sort
[Exam Focus]- Bubble-sort adjacent passes
- Ascending: swap only left>right
- Left-to-right pass: remaining maximum→end
- Shrink unsorted boundary each pass
- Up to n(n−1)/2 pair comparisons
- Average/worst: quadratic
👁 Full explanation
For ascending order, compare each adjacent pair and swap only when left>right. The largest remaining value moves to the final unsorted position after one left-to-right pass. Shrink the next pass by one position. Quadratic worst/average work comes from up to n(n-1)/2 pair comparisons. - Bubble optimizations and stability
- Early stop: no-swap pass finishes
- Sorted input with early stop: linear
- Fixed pass schedule: quadratic
- Strict swaps preserve ties
- Cocktail sort: bidirectional bubble passes
- Cocktail stability: strict swaps
👁 Full explanation
Early stopping makes a sorted input linear: one no-swap pass finishes. A fixed pass schedule stays quadratic. Strict swaps preserve equal-key order. Cocktail sort runs bubble passes in both directions and is stable with strict swaps. - Worked example Bubble first-pass trace
- [4,1,3,2]→[1,4,3,2]
- Then [1,3,4,2]
- Then [1,3,2,4]
- Maximum 4 reaches final position
👁 Full explanation
Work it through[4,1,3,2] → [1,4,3,2] → [1,3,4,2] → [1,3,2,4] after the first pass.
11 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Bubble-sort adjacent passes
DSA33
Selection sort
[Exam Focus]- Selection-sort comparison and exchange counts
- Scan suffix minimum
- Exchange minimum with A[i]
- n−1 meaningful placements
- n(n−1)/2 comparisons regardless of order
- At most n−1 distinct-position exchanges
- Final self-swap: n swap calls possible
👁 Full explanation
At position i, scan the remaining suffix for its minimum, then exchange it with A[i]. There are n-1 meaningful placements and n(n-1)/2 comparisons regardless of initial order. At most n-1 exchanges of distinct positions are needed. A loop that also swaps the last item with itself can count n swap calls. - Selection-sort suitability and instability
- Expensive record moves; cheap comparisons
- Large dataset alone insufficient
- [2a,2b,1]→[1,2b,2a]
- Equal-key order reversed
- Constant element storage: nonunique property
👁 Full explanation
Selection suits expensive record moves with cheap key comparisons, not every large dataset. It is unstable: exchanging first 2a with 1 in [2a,2b,1] gives [1,2b,2a]. Constant extra element storage is shared by several sorts.
6 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Selection-sort comparison and exchange counts
DSA34
Insertion sort
[Exam Focus]- Insertion-sort sorted-prefix invariant
- First element initially sorted
- Save next value
- Shift larger predecessors right
- Insert into gap
- n−1 insertion passes
- Sorted input: one check, no shifts
- Sorted time: linear
- Reverse shifts: 1+2+…+(n−1)
- Reverse time: quadratic
👁 Full explanation
Begin with the first element already sorted. For each remaining item, save its value, shift larger preceding values right, and insert it into the gap. That gives n-1 insertion passes. On sorted input each pass needs one ordering check and no shifts: linear time. Reverse order causes 1+2+…+(n-1) shifts: quadratic time. - Insertion-sort adaptiveness and stability
- Few inversions: few shifts
- Nearly sorted or small arrays
- Strictly larger shifts preserve ties
- Linked implementation avoids array shifts
- Linked insertion position still requires search
👁 Full explanation
Few inversions mean few shifts, favouring insertion for nearly sorted or small arrays. Shift only strictly larger keys for stability. A linked implementation saves array shifts but still must locate each insertion position. - Worked example Insertion into sorted prefix
- Insert 2 into [1,4,7]
- Save 2
- Shift 7 before 4
- Write after 1
- Result: [1,2,4,7]
👁 Full explanation
Work it throughInsert 2 into prefix [1,4,7]: save 2, move 7 then 4 right, and write 2 after 1. The sorted prefix becomes [1,2,4,7].
9 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Insertion-sort sorted-prefix invariant
DSA35
Shell sort
[Exam Focus]- Shell-sort gap passes
- Positive gaps ending at 1
- Gap h: insertion-sort h-spaced subsequences
- Earlier long moves reduce disorder
- Final h=1 finishes sorting
- h-sorted: A[j]≤A[j+h]
- Both indices must exist
👁 Full explanation
Choose a sequence of positive gaps ending at 1. For each gap h, insertion-sort each subsequence of positions h apart. The final h=1 pass finishes ordinary sorting after earlier long moves have reduced disorder. An h-sorted array satisfies A[j]≤A[j+h] wherever both indices exist. - Shell-sort complexity and stability
- Bounds depend on gap sequence
- Knuth increments: 1,4,13,…
- Knuth worst order: O(n^(3/2))
- Distant moves can reorder ties
- Generally unstable
- Constant extra element storage
👁 Full explanation
The O(n^(3/2)) bound depends on gaps; Knuth increments 1,4,13,… have that worst order. Shell sort is generally unstable because distant moves can reorder ties; extra element storage is constant. - Worked example Shell-sort gap trace
- Start [5,4,3,2,1]
- Gap 3: positions (0,3),(1,4)
- After gap 3: [2,1,3,5,4]
- After gap 1: [1,2,3,4,5]
👁 Full explanation
Work it throughFor [5,4,3,2,1], gap 3 sorts positions (0,3) and (1,4), giving [2,1,3,5,4]. Gap 1 then produces [1,2,3,4,5].
Blueprint: DSA2 · Note references: DSA_MOD, DSA_SHELL
- Shell-sort gap passes
DSA36
Quicksort partition rules
[Exam Focus]- Quicksort partition balance
- Choose pivot, partition, recurse
- Balanced partitions: n log n
- Repeated extremes: n+(n−1)+…
- Extreme-pivot time: quadratic
- Expected n log n: input/random-pivot model
- Random versus median-of-three tradeoffs
- No universally best pivot policy
👁 Full explanation
Choose a pivot, partition, then recursively sort the pieces. Balanced partitions give n log n work; repeated extreme pivots sum n+(n-1)+… to quadratic work. Expected n log n needs an input/random-pivot model. Random and median-of-three choices have different tradeoffs; neither is universally best. - Partition invariants versus exact arrays
- Ten distinct values; final pivot 5
- Five smaller before; four larger after
- Internal order depends on partition algorithm
- Multiple arrays may satisfy invariant
- Name algorithm for exact trace
- Same-array rearrangement
- Worst recursive storage: linear
👁 Full explanation
In the ten-distinct-value example, a final pivot 5 has five smaller values before it and four larger after it. Internal orders depend on the partition algorithm; several candidate arrays can satisfy the invariant. State the algorithm before predicting one exact array. Quicksort normally rearranges in the same array but recursive storage can be linear in the worst case.
13 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_NEW, DSA_SHORT
- Quicksort partition balance
DSA37
Mergesort and external sorting
[Exam Focus]- Merge-sort recurrence and stability
- Split halves, sort, merge
- Advance smaller current front
- Left-first ties preserve equal-key order
- Ordinary array buffer: linear
- Logarithmic levels × linear merge work
- Sorted input: n log n
- Merge-skipping optimization exception
👁 Full explanation
Split into halves, sort them, then merge by advancing the smaller current front. With left-first tie handling, equal keys retain order. Ordinary array merging needs a linear auxiliary buffer. There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges. - Merge variants and external sorting
- Top-down: recursive
- Bottom-up: iterative widths 1,2,4,…
- In-place merging variants: different tradeoffs
- Linear merge: operation, ambiguous sort label
- Internal sorting: dataset fits memory
- External sorting: sorted disk runs
- Buffered stream merges reduce I/O
- Reverse input ≠ maximum merge comparisons
👁 Full explanation
Top-down mergesort recurses; bottom-up merges runs of widths 1,2,4,… iteratively. In-place merging variants exist with different tradeoffs; linear merge names an operation, not a universally standardized sort variant. Internal sorting fits the working dataset in memory. External sorting builds sorted runs and merges buffered streams from disk, aiming to reduce I/O. Reverse order alone does not characterize maximum merge comparisons.
21 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD, DSA_EXTERNAL
- Merge-sort recurrence and stability
DSA38
Heapsort
[Exam Focus]- Ascending in-place heapsort trace
- Build max-heap
- Exchange root with final active element
- Shrink active heap
- Sink new root
- Removed maximum joins sorted suffix
- Repeat until one active item
👁 Full explanation
For ascending in-place heapsort, build a max-heap over the array. Exchange root with the final active element, shrink the active heap, and sink the new root. The removed maximum now belongs in the sorted suffix. Repeat until one active item remains. - Heapsort costs and distinguishing mechanism
- Bottom-up build: linear
- Repeated extraction: O(n log n) worst
- Iterative sink: constant auxiliary storage
- Long root-to-end exchanges reorder ties
- Generally unstable
- Any comparison sort can compare priorities
- Heap extraction: distinctive mechanism
👁 Full explanation
Building with bottom-up sinking is linear; repeated extraction gives O(n log n) worst time. Iterative sinking needs constant auxiliary storage. The method is generally unstable because long root-to-end exchanges can reorder equal keys. It is not uniquely the method for sorting by priorities: any comparison sort can compare a priority field. Heap extraction is its distinctive mechanism.
2 related practice questions
Blueprint: DSA2 · Note references: DSA_MOD
- Ascending in-place heapsort trace
DSA39
Radix sorting
[Exam Focus]- LSD radix sort
- Fixed-width digit keys
- Least-significant digit first
- Move left with stable digit passes
- Stability preserves earlier digit ordering
- d digits; radix r
- Counting passes: O(d(n+r))
- Auxiliary storage: O(n+r)
👁 Full explanation
LSD radix sorting handles fixed-width digit keys by stably sorting least-significant digit first, then moving left. Stable intermediate passes preserve the ordering already established by less-significant digits. With d digits and radix r, counting-based passes take O(d(n+r)) time and O(n+r) auxiliary storage. - MSD radix and key assumptions
- Leading digits first
- Subdivide equal-prefix groups
- Strings: lexicographic comparison
- Accessible digits required
- Specify length and signed-value conventions
- Arbitrary unstructured keys unsuitable
- Large radix/long keys/small n: comparison alternative
👁 Full explanation
MSD begins at leading digits and subdivides equal-prefix groups. Strings are lexicographically comparable. Radix methods require accessible digits and length/signed-value conventions, not arbitrary unstructured keys. Large radix, long keys or small n may favour comparison sorting.
4 related practice questions
Blueprint: DSA2 · Note references: DSA_RADIX
- LSD radix sort
DSA40
Graph models and representations
[Exam Focus]- Graph relationship models
- Vertices V; edges E
- Directed: u→v distinct from v→u
- Following accounts: directed
- Mutual friendship: undirected
- Weighted edges: costs
- Unweighted shortest paths: edge counts
- DAG: directed acyclic graph
- Trees: connected acyclic graphs
- Graph structures may contain cycles
👁 Full explanation
A graph has vertices V and edges E. Directed edges distinguish u→v from v→u; undirected edges represent two-way relationships. Following accounts is directed; a mutual friendship relation is undirected. Weighted edges carry costs; unweighted shortest-path questions count edges. DAG expands to directed acyclic graph. Trees are connected acyclic graphs, although graph data structures may also contain cycles. - Graph representation costs
- Matrix space: Θ(V²)
- Matrix edge lookup: O(1)
- Adjacency-list space: Θ(V+E)
- Lists enumerate neighbours
- Dense simple graphs: near-quadratic edges
- Every-edge work increases with density
- Vertex-only work needn't inspect every edge
👁 Full explanation
A matrix uses Theta(V²) space and constant edge lookup. Adjacency lists use Theta(V+E) space and enumerate neighbours. Dense simple graphs approach quadratic edge counts. Examining every edge costs more on denser graphs; vertex-only operations need not inspect every edge.
5 related practice questions
Blueprint: DSA3 · Note references: DSA_SHORT
- Graph relationship models
DSA41
Breadth-first search
[Exam Focus]- BFS discovery discipline
- Mark source on enqueue
- Dequeue; examine neighbours
- Unvisited neighbour: mark and enqueue
- Store predecessor[v] on discovery
- Predecessors reconstruct paths
- FIFO: distance d before later layers
👁 Full explanation
Mark the source when enqueuing it. Repeatedly dequeue a vertex, examine its neighbours, and enqueue each unvisited neighbour while marking it. Store predecessor[v] when discovering v if a path must be reconstructed. FIFO ensures vertices at distance d are explored before later distance layers. - BFS guarantees and costs
- Unweighted minimum-edge paths
- No arbitrary minimum-weight guarantee
- Adjacency lists: O(V+E)
- Matrix scan: O(V²)
- Disconnected graph: restart at unvisited vertices
- Neighbour order changes tied traversal
- Minimum distances unchanged
👁 Full explanation
BFS finds minimum-edge paths in unweighted graphs, not arbitrary minimum-weight paths. With adjacency lists it costs O(V+E); scanning a matrix costs O(V²). To traverse a disconnected graph, restart from each unvisited vertex. Neighbour order affects tied traversal order but not minimum distances. - Worked example BFS alphabetical-neighbour trace
- Edges A–B,A–C,B–D,C–D
- Queue [A]→[B,C]→[C,D]→[D]→[]
- Discovery: A,B,C,D
- D distance: two
👁 Full explanation
Work it throughEdges A–B, A–C, B–D, C–D; alphabetical neighbours: queue [A] → [B,C] → [C,D] → [D] → []. Discovery order A,B,C,D; D has distance two.
8 related practice questions
Blueprint: DSA3 · Note references: DSA_SHORT, DSA_GRAPH
- BFS discovery discipline
DSA42
Depth-first search
[Exam Focus]- DFS latest-pending-work discipline
- Mark vertex
- Recursively finish each unmarked neighbour
- Then continue later neighbours
- Explicit stack alternative
- Queue changes discipline
- Marking prevents cyclic infinite repetition
👁 Full explanation
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours. An explicit stack can store pending work instead. Both implement latest-pending-work first; a queue would change that discipline. Marking prevents infinite repetition around graph cycles. - DFS guarantees, applications, costs
- Alphabetical recursive discovery: A,B,D,C
- Reachability witness, not necessarily shortest
- Adjacency lists: O(V+E)
- Visited state: O(V)
- Possible stack depth: O(V)
- Cycle and connectivity analysis
- Directed cycle test: active versus completed
👁 Full explanation
Using the same graph and alphabetical neighbours, recursive DFS can discover A,B,D,C. Its path is a valid reachability witness but not necessarily shortest. Adjacency-list cost is O(V+E), with O(V) visited state and possible stack depth. DFS supports cycle and connectivity analysis; a directed cycle test distinguishes active recursion vertices from already completed ones.
11 related practice questions
Blueprint: DSA3 · Note references: DSA_SHORT
- DFS latest-pending-work discipline
DSA43
Shortest paths and spanning trees
[Exam Focus]- Dijkstra shortest-path conditions
- Nonnegative weights
- Source distance 0; others ∞
- Finalize smallest unsettled distance
- Relax outgoing edges
- dist[v]=min(dist[v],dist[u]+w(u,v))
- Min-priority queue: next vertex
- Equal edge costs: BFS sufficient
- Negative edges: justified alternative
- Bellman–Ford alternative
👁 Full explanation
For nonnegative weights, standard Dijkstra initializes source distance zero and others infinity, repeatedly finalizes the unsettled vertex with smallest distance, and relaxes each outgoing edge: dist[v]=min(dist[v],dist[u]+w(u,v)). A min-priority queue supports the next choice. BFS is enough when every edge has equal cost; negative edges require another justified method, such as Bellman–Ford. - Minimum spanning tree objective
- Connected undirected weighted graph
- Minimum total connection cost
- Prim: cheapest current-tree crossing edge
- Kruskal: increasing edge weights
- Reject already-connected endpoints
- MST ≠ shortest source routes
- Equal weights: multiple MSTs possible
👁 Full explanation
An MST minimizes the total cost of connecting all vertices of a connected undirected weighted graph. Prim adds the cheapest edge crossing from its current tree to an outside vertex. Kruskal processes edges by increasing weight and rejects those joining vertices already connected. An MST need not give shortest source-to-vertex routes, and equal weights can permit several MSTs. - Worked example Triangle MST and shortest paths
- AB=1; BC=2; AC=10
- Prim/Kruskal: AB,BC
- MST total: 3
- Dijkstra from A: B=1
- C: 10→3 through B
👁 Full explanation
Work it throughTriangle weights AB=1, BC=2, AC=10: Prim or Kruskal selects AB,BC, total 3. Dijkstra from A gets B=1 and improves C from 10 to 3 through B.
4 related practice questions
Blueprint: DSA3 · Note references: DSA_SHORT, DSA_SP, DSA_MST
- Dijkstra shortest-path conditions
DSA44
Kadane and KMP
- Kadane maximum contiguous subarray
- Required nonempty answer
- Initialize ending=best=A[0]
- ending=max(x,ending+x)
- best=max(best,ending)
- Linear time
- Constant working storage
- best=0 silently allows empty answer
- All-negative nonempty case fails
👁 Full explanation
Kadane’s algorithm finds a contiguous maximum-sum subarray. For a required nonempty answer, initialize ending=best=A[0]; update ending=max(x,ending+x), then best=max(best,ending). It is linear time with constant working storage. Initializing best=0 instead silently allows an empty answer and fails the nonempty all-negative case. - Knuth–Morris–Pratt pattern matching
- Pattern inside text
- Preprocess longest proper prefix/suffix lengths
- Mismatch: prefix-length fallback
- Avoid restarting comparisons from beginning
- Text pointer needn't move backward
- Preprocessing+scan: O(pattern length+text length)
👁 Full explanation
Knuth–Morris–Pratt (KMP) finds a pattern inside text. Preprocess the pattern’s longest proper prefix that is also a suffix. After mismatch, fall back using those prefix lengths rather than restarting comparisons from the beginning; the text pointer need not move backward. Pattern preprocessing plus scanning takes O(pattern length+text length). - Worked example Kadane and KMP worked values
- Input [-2,3,-1,4,-5]
- Ending values: −2,3,2,6,1
- Best=6 from [3,−1,4]
- ABAB prefix lengths: [0,0,1,2]
👁 Full explanation
Work it throughFor [-2,3,-1,4,-5], Kadane ending values are -2,3,2,6,1, so best is 6 from [3,-1,4]. Pattern ABAB has prefix lengths [0,0,1,2].
2 related practice questions
Note references: DSA_KADANE, DSA_KMP
- Kadane maximum contiguous subarray
DSA45
Missing data and misleading labels
- Trace completeness and answer-key limits
- Complete operation sequence
- Initial state
- Capacity
- Output orientation
- State assumptions before calculation
- Highlighted key cannot remove valid overlaps
👁 Full explanation
A trace needs the complete operation sequence, initial state, capacity and output orientation. State these assumptions before calculating. Evaluate all choices against the rules; a selected answer does not make other valid choices false. - Implementation versus best-choice questions
- Can implement versus best under costs
- ADT permits multiple representations
- Serial-access memory ≠ inherently LIFO
- Heap file: unordered database records
- Heap file unrelated to binary heap
- Insertion: available space
- Lookup: scanning possible
- Ordered output: sorting or index
- Beginning insertion unnecessary
👁 Full explanation
Specify whether a question asks which structure can implement something or which is best under stated costs. ADTs do not force one representation, and serial-access memory is not inherently LIFO. A heap file is an unordered database record file, unrelated to a binary heap: insertion uses available space, scanning can find records, and ordered output requires sorting or an index. It need not insert at the beginning.
5 related practice questions
Note references: DSA_MOD, DSA_DB
- Trace completeness and answer-key limits
No matching topics. Clear the search or change the filter.
Blueprint learning outcomes
- DSA1 · Understand the most common concepts of data structures like stack, queue and linked list
DSA01, DSA08, DSA09, DSA10, DSA11, DSA12, DSA14, DSA15, DSA16, DSA17 - DSA2 · Implement the Sorting and searching concepts
DSA24, DSA28, DSA29, DSA30, DSA31, DSA32, DSA33, DSA34, DSA35, DSA36, DSA37, DSA38, DSA39 - DSA3 · Use the concepts related to Data Structures and Algorithms to solve real world
DSA01, DSA02, DSA09, DSA10, DSA12, DSA14, DSA15, DSA17, DSA19, DSA24, DSA26, DSA27, DSA40, DSA41, DSA42, DSA43