List Processing and In-Place Mutation Notes for GATE DA
List Processing and In-Place Mutation notes for GATE DA: 7 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.
list processing and in place mutation notes
Chapter Roadmap: List Processing and In-Place Mutation
Chapter Roadmap
Chapter journey
Recursive List Processing and In-Place Mutation Current topic. High-importance tracing.
Single-index recursive scans
Adjacent-swap counting
Two-pointer reversal
Chapter mastery
Track exact list state after every swap
Decide if call is scan or reversal
Predict final return value and list
Weight hint: Core tracing topic. Small code pieces can carry good marks through careful step-by-step execution.
Topic Hero: Recursion Meets Mutable Lists
Topic Hero: Recursion Meets Mutable Lists
A Python list is mutable. If a recursive function changes the list, the changed list is visible to all deeper recursive calls.
Two core shapes appear repeatedly:
Shape
Indices used
Typical operation
Single-index scan
i
Compare and possibly swap L[i] and L[i+1]
Two-pointer reversal
s1, s2
Swap D[s1] and D[s2], then move inward
Key idea: The list is shared, but the index variables are local to each recursive call.
The List Is Shared, Indices Are Local
The List Is Shared, Indices Are Local
In-place mutation
def swap_positions(L, i, j):
L[i], L[j] = L[j], L[i]
This changes the actual list object. There is no new list being created.
What this means for recursion
If call 1 swaps elements, call 2 sees the swapped list.
If call 2 swaps elements, call 3 sees the newer list.
Changing i, j, s1, or s2 inside one call does not change those variables in earlier calls.
Python swap detail
L[i], L[j] = L[j], L[i]
The right-hand side is evaluated first using the old list values. Then both assignments happen together. This avoids the classic mistake of overwriting one value before saving the other.
4 more cards in this chapter
Try a question
Answer it here to see how it works. Nothing is recorded until you sign in.
Question 1
Level 1: Warm-up
For a list of length N, the single-index scan uses the base condition i >= len(L) - 1. What is the minimum value of N for which the function will execute at least one comparison (i.e., not immediately hit the base case at i=0)?
Question 2
Level 1: Warm-up
For a list of length 5, what is the minimum number of recursive calls (including the initial call and the base case call) made by the scan function before it terminates, regardless of the list's initial order?
Question 3
Level 1: Warm-up
For a list of length N, the single-index scan pattern compares adjacent elements. What is the exact number of comparisons performed during a single pass, regardless of the initial order of the list?
Question 4
Level 1: Warm-up
If the single-index recursive scan is called on a list of length 1, what is the minimum number of swaps it can perform before hitting the base case?
Question 5
Level 1: Warm-up
The single-index scan uses the base condition i >= len(L) - 1. A student argues that for an empty list, the expression len(L) - 1 must evaluate to a minimum of 0 because list indices cannot be negative. What is the actual value of len(L) - 1 for an empty list, which contradicts this assumption?
Question 6
Level 1: Warm-up
Consider the adjacent-swap recursive scan on a list. Which of the following statements is true regarding the movement of elements during a single pass?
Question 7
Level 1: Warm-up
Assertion (A): In a recursive scan that counts swaps, the base case returns 0, and each swap adds 1 to the result of the next recursive call.
Reason (R): This aggregation correctly counts the total number of swaps because the function creates a new list at each step to keep track of the count.
Question 8
Level 1: Warm-up
Which of the following statements is true regarding the base condition of the adjacent-swap recursive scan for a list of length N?
Question 9
Level 1: Warm-up
Assertion (A): In the return aggregation pattern, a swap adds 1 to the result of the next recursive call.
Reason (R): This correctly computes the total number of elements in the list.
Question 10
Level 1: Warm-up
Assertion (A): The return value of the recursive scan is built by adding 1 for each swap and passing the result forward when no swap occurs.
Reason (R): This aggregation mechanism correctly computes the total number of inversions in the original unsorted list.
Free preview ends here
Login to view the complete notes
Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.
Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.
Built around you, not around a syllabus PDF
Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.
Revision that hits your weak spots
We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.
Questions calibrated to the real exam
Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.
Notes written for recall, not for volume
Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.
One place for everything
Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.
Honest progress
No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.
Unlock the whole course
Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.
List Processing and In-Place Mutation Notes for GATE DA
List Processing and In-Place Mutation notes for GATE DA: 7 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.
Chapter Roadmap: List Processing and In-Place Mutation
Chapter Roadmap
Chapter journey
Recursive List Processing and In-Place Mutation Current topic. High-importance tracing.
Single-index recursive scans
Adjacent-swap counting
Two-pointer reversal
Chapter mastery
Track exact list state after every swap
Decide if call is scan or reversal
Predict final return value and list
Weight hint: Core tracing topic. Small code pieces can carry good marks through careful step-by-step execution.
Topic Hero: Recursion Meets Mutable Lists
Topic Hero: Recursion Meets Mutable Lists
A Python list is mutable. If a recursive function changes the list, the changed list is visible to all deeper recursive calls.
Two core shapes appear repeatedly:
Shape
Indices used
Typical operation
Single-index scan
i
Compare and possibly swap L[i] and L[i+1]
Two-pointer reversal
s1, s2
Swap D[s1] and D[s2], then move inward
Key idea: The list is shared, but the index variables are local to each recursive call.
The List Is Shared, Indices Are Local
The List Is Shared, Indices Are Local
In-place mutation
def swap_positions(L, i, j):
L[i], L[j] = L[j], L[i]
This changes the actual list object. There is no new list being created.
What this means for recursion
If call 1 swaps elements, call 2 sees the swapped list.
If call 2 swaps elements, call 3 sees the newer list.
Changing i, j, s1, or s2 inside one call does not change those variables in earlier calls.
Python swap detail
L[i], L[j] = L[j], L[i]
The right-hand side is evaluated first using the old list values. Then both assignments happen together. This avoids the classic mistake of overwriting one value before saving the other.
Single-Index Recursive Scan Pattern
Single-Index Recursive Scan Pattern
Basic shape
def scan(L, i=0):
if i >= len(L) - 1:
return 0
if L[i] > L[i + 1]:
L[i], L[i + 1] = L[i + 1], L[i]
return 1 + scan(L, i + 1)
return scan(L, i + 1)
Why the base condition is i >= len(L) - 1
The function compares L[i] with L[i + 1].
If len(L) = n, the last valid comparison is between indices n - 2 and n - 1. Therefore recursion should stop when i reaches n - 1.
Empty and single-element lists
If len(L) = 0, then len(L) - 1 = -1, and 0 >= -1 is true.
If len(L) = 1, then len(L) - 1 = 0, and 0 >= 0 is true.
Both cases safely return the base value.
List Processing and In-Place Mutation: Solved Questions with Step-by-Step Explanations (10 Problems)
Question 1 · Programming, Data Structures and AlgorithmsMCQ
For a list of length N, the single-index scan uses the base condition i >= len(L) - 1. What is the minimum value of N for which the function will execute at least one comparison (i.e., not immediately hit the base case at i=0)?
A.
0
B.
1
C.
2
D.
3
Correct Answer:
C
Step-by-Step Solution
Key idea: The base condition prevents accessing out-of-bounds indices.
Step 1: The condition is i >= len(L) - 1. For N=1, len(L) - 1 = 0. At i=0, 0 >= 0 is true, so it hits the base case immediately without comparing.
Step 2: For N=2, len(L) - 1 = 1. At i=0, 0 >= 1 is false, so it proceeds to compare L[0] and L[1].
Answer: C
Question 2 · Programming, Data Structures and AlgorithmsMCQ
For a list of length 5, what is the minimum number of recursive calls (including the initial call and the base case call) made by the scan function before it terminates, regardless of the list's initial order?
A.
4
B.
5
C.
6
D.
7
Correct Answer:
B
Step-by-Step Solution
Key idea: The single-index scan always increments the index by 1 until it hits the base case.
Step 1: For a list of length N=5, the valid indices for comparison are 0, 1, 2, 3.
Step 2: The base case triggers when i≥N−1, which means i≥4.
Step 3: The function is called with i=0,1,2,3, and finally i=4 (which hits the base case).
Step 4: This results in exactly 5 calls.
Answer: B
Question 3 · Programming, Data Structures and AlgorithmsMCQ
For a list of length N, the single-index scan pattern compares adjacent elements. What is the exact number of comparisons performed during a single pass, regardless of the initial order of the list?
A.
N
B.
N−1
C.
N−2
D.
0
Correct Answer:
B
Step-by-Step Solution
Key idea: The scan compares L[i] and L[i+1] for each valid index i.
Step 1: The valid indices for comparison are 0,1,…,N−2.
Step 2: The number of such indices is (N−2)−0+1=N−1.
Step 3: Therefore, exactly N−1 comparisons are performed in every pass.
Answer: B
Question 4 · Programming, Data Structures and AlgorithmsMCQ
If the single-index recursive scan is called on a list of length 1, what is the minimum number of swaps it can perform before hitting the base case?
A.
1
B.
2
C.
3
D.
0
Correct Answer:
D
Step-by-Step Solution
Key idea: The base condition prevents any comparisons or swaps on lists that are too short.
Step 1: For a list of length N=1, the base condition is i >= len(L) - 1.
Step 2: At the initial call, i=0. The condition becomes 0 >= 1 - 1, which is 0 >= 0.
Step 3: This condition is True, so the function immediately hits the base case and returns 0 without performing any comparisons or swaps.
Answer: D
Question 5 · Programming, Data Structures and AlgorithmsMCQ
The single-index scan uses the base condition i >= len(L) - 1. A student argues that for an empty list, the expression len(L) - 1 must evaluate to a minimum of 0 because list indices cannot be negative. What is the actual value of len(L) - 1 for an empty list, which contradicts this assumption?
A.
-2
B.
-1
C.
0
D.
1
Correct Answer:
B
Step-by-Step Solution
Key idea: The length of an empty list is 0, and the base condition expression evaluates mathematically regardless of index validity.
Step 1: For an empty list, len(L) = 0.
Step 2: Substitute this into the expression len(L) - 1.
Step 3: The calculation is 0 - 1 = -1.
Step 4: The value is -1, which contradicts the student's assumption that it must be at least 0.
Answer: B
Question 6 · Programming, Data Structures and AlgorithmsMCQ
Consider the adjacent-swap recursive scan on a list. Which of the following statements is true regarding the movement of elements during a single pass?
A.
Every element moves to its correct sorted position.
B.
A large element can move right multiple positions, but a small element moves left by at most one position.
C.
The list is guaranteed to be fully sorted after one pass.
D.
Elements only move left, never right.
Correct Answer:
B
Step-by-Step Solution
Key idea: A single pass of adjacent swaps only moves elements one step in the "hard" direction.
Step 1: During a left-to-right pass, a large element can be swapped multiple times, moving right by many positions.
Step 2: However, a small element can only be swapped once when the large element passes it, moving left by at most one position.
Answer: B
Question 7 · Programming, Data Structures and AlgorithmsMCQ
Assertion (A): In a recursive scan that counts swaps, the base case returns 0, and each swap adds 1 to the result of the next recursive call.
Reason (R): This aggregation correctly counts the total number of swaps because the function creates a new list at each step to keep track of the count.
A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.
Correct Answer:
C
Step-by-Step Solution
Key idea: Recursive counting aggregates the number of swaps without creating new data structures.
Step 1: The assertion correctly describes the aggregation pattern: base case 0, add 1 for each swap.
Step 2: The reason claims a new list is created at each step. This is false; the list is mutated in-place, and the count is returned via the call stack.
Answer: C
Question 8 · Programming, Data Structures and AlgorithmsMCQ
Which of the following statements is true regarding the base condition of the adjacent-swap recursive scan for a list of length N?
A.
It triggers when the index reaches N.
B.
It triggers when the index reaches N−1.
C.
It triggers when the index reaches N−2.
D.
It triggers when the list is fully sorted.
Correct Answer:
B
Step-by-Step Solution
Key idea: The base condition prevents out-of-bounds access when comparing adjacent elements.
Step 1: The scan compares L[i] and L[i+1].
Step 2: For a list of length N, the highest valid index is N−1.
Step 3: To safely access L[i+1], i must be at most N−2.
Step 4: Therefore, the recursion must stop (base condition triggers) when i reaches N−1.
Answer: B
Question 9 · Programming, Data Structures and AlgorithmsMCQ
Assertion (A): In the return aggregation pattern, a swap adds 1 to the result of the next recursive call.
Reason (R): This correctly computes the total number of elements in the list.
A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.
Correct Answer:
C
Step-by-Step Solution
Key idea: The return aggregation pattern counts specific events, not list properties.
Step 1: Evaluate Assertion (A). The pattern 1+C(i+1) correctly adds 1 for each swap. This is true.
Step 2: Evaluate Reason (R). The aggregation counts the number of swaps, not the total number of elements in the list. This is false.
Answer: C
Question 10 · Programming, Data Structures and AlgorithmsMCQ
Assertion (A): The return value of the recursive scan is built by adding 1 for each swap and passing the result forward when no swap occurs.
Reason (R): This aggregation mechanism correctly computes the total number of inversions in the original unsorted list.
A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.
Correct Answer:
C
Step-by-Step Solution
Key idea: The return aggregation counts specific events during the traversal.
Step 1: Evaluate Assertion (A). The pattern 1+C(i+1) correctly adds 1 for each swap. This is true.
Step 2: Evaluate Reason (R). The aggregation counts the number of swaps performed in one pass, not the total number of inversions in the original list. This is false.