Practice
1. You are given a singly linked list where each node contains a binary digit (0 or 1). The linked list represents a binary number with the head as the most significant bit. Which approach guarantees an optimal solution to convert this linked list to its decimal integer value?
easy
Solution
Step 1: Understand the problem constraints
The linked list represents a binary number with the head as the most significant bit, so the decimal value can be built by processing bits from left to right.Step 2: Identify the optimal approach
Iteratively shifting the accumulated value left by 1 and OR-ing with the current bit correctly builds the decimal value in O(n) time and O(1) space, without extra string conversions or complex DP.Final Answer:
Option A -> Option AQuick Check:
Bitwise accumulation matches binary to decimal conversion [OK]
Hint: Bitwise accumulation is optimal for binary to decimal conversion [OK]
Common Mistakes:
- Using string concatenation then parsing wastes time and space
- Greedy approaches don't apply to binary number conversion
- Dynamic programming is unnecessary overhead here
2. Given the following code snippet for splitting a linked list into
k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?easy
Solution
Step 1: Calculate total nodes and part sizes
Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.Step 2: Assign nodes to parts
Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].Final Answer:
Option B -> Option BQuick Check:
Sum of parts equals original list length and sizes differ by at most one [OK]
Hint: Remainder nodes assigned to first parts -> first part larger [OK]
Common Mistakes:
- Assigning remainder nodes to last parts
- Off-by-one in part sizes
- Returning fewer than k parts
3. What is the time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list with total n nodes, considering the worst-case scenario where each node has a child list?
medium
Solution
Step 1: Analyze tail-finding loop
Although tail is found by traversing child lists, each node is visited at most once as tail or curr.Step 2: Amortized analysis
All next pointers are traversed linearly; tail searches do not overlap nodes multiple times, so total work is linear.Final Answer:
Option A -> Option AQuick Check:
Each node processed once, tail searches amortize to O(n) [OK]
Hint: Tail searches look nested but total visits are linear [OK]
Common Mistakes:
- Assuming tail search is repeated fully for each child causing O(n^2)
- Confusing amortized with worst-case per iteration
- Ignoring that nodes are not revisited multiple times
4. Suppose the linked list can be extremely long (millions of nodes), causing recursion stack overflow in the recursive solution. Which modification is the best to handle this scenario efficiently?
hard
Solution
Step 1: Identify the problem with recursion
Deep recursion causes stack overflow for very long linked lists.Step 2: Evaluate alternatives
Increasing recursion limit is risky and platform-dependent; divide-and-conquer adds complexity without reducing total depth; string conversion is inefficient.Step 3: Choose iterative approach
Iterative bitwise accumulation uses constant stack space and linear time, handling large inputs safely.Final Answer:
Option B -> Option BQuick Check:
Iterative approach avoids recursion stack overflow [OK]
Hint: Iterative avoids recursion stack overflow on large inputs [OK]
Common Mistakes:
- Relying on recursion limit increase which is unsafe
- Assuming divide-and-conquer reduces recursion depth effectively
- Using string conversion which is inefficient for large inputs
5. Suppose the partition problem is modified so that nodes can be reused multiple times (e.g., the list represents a multiset with unlimited copies). Which modification to the optimal in-place partition algorithm correctly handles this scenario without breaking the algorithm?
hard
Solution
Step 1: Understand the reuse constraint
Nodes can be reused multiple times, so in-place rearrangement that moves nodes breaks because nodes are unique objects.Step 2: Evaluate modifications
In-place rearrangement cannot handle duplicates without cloning. Cloning in-place is complex and error-prone. Using arrays to store values and rebuild the list handles duplicates safely and cleanly.Step 3: Compare cloning approaches
Cloning nodes in-place or in two lists adds complexity and risks pointer errors. Arrays simplify the problem.Final Answer:
Option A -> Option AQuick Check:
Rebuilding from arrays safely handles duplicates and reuse [OK]
Hint: Rebuild list from arrays to handle node reuse safely [OK]
Common Mistakes:
- Trying to rearrange nodes in-place with reuse
- Cloning nodes without updating pointers correctly
- Assuming pointer moves work with reused nodes
