Selective DNA Deletion - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Linked Lists, Selective Deletion

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 selectively delete nodes from a linked list based on two integers m and n.
  • Q: What should be the output?
    • A: The output should be the head of the modified linked list after applying the deletions as per the given rules.
HAPPY CASE
Input: dna_strand = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9, Node(10)))))))))), m = 2, n = 3
Output: 1 -> 2 -> 6 -> 7 -> 11
Explanation: After retaining 2 nodes and deleting 3, the modified linked list is obtained.

EDGE CASE
Input: dna_strand = None, m = 2, n = 3
Output: None
Explanation: An empty linked list should return None.

EDGE CASE
Input: dna_strand = Node(1), m = 1, n = 1
Output: 1
Explanation: With only one node, retaining and then trying to delete another node doesn't affect the list.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List problems involving Selective Deletion, we want to consider the following approaches:

  • Pointer Manipulation: Use pointers to traverse the list and selectively retain or delete nodes.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list, retaining the first m nodes and deleting the next n nodes. We repeat this process until we reach the end of the list.

1) Initialize a pointer `current` to the head of the list.
2) While `current` is not None:
    a) Retain the first `m` nodes by moving the `current` pointer `m-1` times.
    b) If `current` becomes None, return the modified list.
    c) Start deleting the next `n` nodes by advancing another pointer.
    d) Link the `current` node to the node after the `n` deleted nodes.
    e) Move `current` to the next node after the deletions.
3) Return the modified head of the list.

⚠️ Common Mistakes

  • Failing to handle cases where the list ends before completing the m or n nodes.
  • Incorrectly linking the nodes after deletion, leading to broken or incorrectly formed lists.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# Function to edit the DNA sequence
def edit_dna_sequence(dna_strand, m, n):
    current = dna_strand
    
    while current:
        # Retain the first m nodes
        for i in range(1, m):
            if current is None:
                return dna_strand
            current = current.next

        if current is None:
            return dna_strand

        # Now current is at the m-th node
        # We will delete the next n nodes
        temp = current.next
        for j in range(n):
            if temp is None:
                break
            temp = temp.next

        # Connect the m-th node to the node after the n deleted nodes
        current.next = temp

        # Move current to the next retained node
        current = temp

    return dna_strand

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 dna_strand linked list to verify that the function correctly edits the list according to the m and n values.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the linked list.

  • Time Complexity: O(N) because each node is visited at most once.
  • Space Complexity: O(1) because only a constant amount of extra space is used for pointers.