Book Display - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 30-40 mins
• 🛠️ Topics: Linked Lists, Matrices, Spiral Order Traversal

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What does the problem ask for?
  • A: The problem asks to create a m x n matrix and fill it with the values of a linked list in spiral order.
  • A: If there are remaining empty spaces, they should be filled with None.
• Q: What should be returned?
  • A: The function should return the generated matrix.

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](/codepath/compsci_guides/wiki/'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.

2: M-atch

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:

• Matrix Traversal: Traverse the matrix in a spiral order while populating it with values from the linked list.
• Boundaries Update: Use boundaries (top, bottom, left, right) to manage the direction of traversal and ensure the spiral order is maintained.

3: P-lan

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

• Forgetting to check if the linked list has been fully traversed before continuing to fill the matrix.
• Incorrectly updating the boundaries, leading to out-of-bounds errors.

4: I-mplement

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

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Example: Use the provided new_reads linked list with multiple books to verify that the function correctly fills the matrix in spiral order.

6: E-valuate

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.

• Time Complexity: O(M * N) because we traverse the entire matrix.
• Space Complexity: O(M * N) because we create an m x n matrix.