TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
m x n
matrix and fill it with the values of a linked list in spiral order.None
.HAPPY CASE
Input:
- m = 3, n = 5
- new_reads = Node('Book 1', Node('Book 2', Node('Book 3', ... Node('Book 13'))))
Output:
- [
['Book 1', 'Book 2', 'Book 3', 'Book 4', 'Book 5'],
['Book 12', 'Book 13', None, None, 'Book 6'],
['Book 11', 'Book 10', 'Book 9', 'Book 8', 'Book 7']
]
EDGE CASE
Input:
- m = 1, n = 4
- new_reads = Node('Book 1', Node('Book 2', Node('Book 3')))
Output:
- [['Book 1', 'Book 2', 'Book 3', None]]
Explanation:
- The matrix is filled in spiral order until the list is exhausted, leaving one `None` in the last position.
Match what this problem looks like to known categories of problems, e.g. Spiral Matrix, Linked Lists, etc.
For Linked List problems involving Spiral Matrix, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will create an empty matrix of size m x n
and traverse it in spiral order while filling it with values from the linked list.
1) Create an empty matrix of size `m x n` filled with `None`.
2) Initialize boundaries: top, bottom, left, and right.
3) Use a while loop to fill the matrix in a spiral order:
- Fill the top row from left to right.
- Fill the right column from top to bottom.
- Fill the bottom row from right to left.
- Fill the left column from bottom to top.
4) After each step, update the boundaries to move inward.
5) Continue until the entire matrix is filled or the linked list is exhausted.
6) Return the filled matrix.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def spiralize_books(m, n, new_reads):
# Step 1: Create an empty matrix of size m x n filled with None
matrix = [[None for _ in range(n)] for _ in range(m)]
# Step 2: Initialize boundaries
top, bottom = 0, m - 1
left, right = 0, n - 1
current = new_reads
# Step 3: Fill the matrix in a spiral order
while current and top <= bottom and left <= right:
# Fill the top row
for i in range(left, right + 1):
if current:
matrix[top][i] = current.value
current = current.next
top += 1
# Fill the right column
for i in range(top, bottom + 1):
if current:
matrix[i][right] = current.value
current = current.next
right -= 1
# Fill the bottom row
for i in range(right, left - 1, -1):
if current:
matrix[bottom][i] = current.value
current = current.next
bottom -= 1
# Fill the left column
for i in range(bottom, top - 1, -1):
if current:
matrix[i][left] = current.value
current = current.next
left += 1
return matrix
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
new_reads
linked list with multiple books to verify that the function correctly fills the matrix in spiral order.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume M
and N
represent the dimensions of the matrix.
O(M * N)
because we traverse the entire matrix.O(M * N)
because we create an m x n
matrix.