Learn and practice the Two Pointers, Fast and Slow Pointers, and Modified Binary Search patterns to solve coding interview problems.

Educative-99 in Python: Accelerate Your Coding Interview Prep

This module groups together three of the most common patterns that may be used to solve problems where the input data is linear: Two Pointers, Fast and Slow Pointers, and Modified Binary Search. Both the Two Pointers and the Modified Binary Search patterns derive their power from their ability to efficiently reduce the size of the search space, that is, both exemplify the divide-and-conquer approach to problem-solving. The Fast and Slow Pointers pattern may be considered a variant of the Two Pointers pattern, where the two pointers move at different speeds in order to traverse the input list in a way that solves the given problem. After completing this module, we will have learned how to use this set of related patterns to solve a diverse range of problems.

Two Pointers & Co.

# Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Given the linked list `42 → 88 → 15` and `n = 2`, what is the resulting linked list after removing the nth node from the end?

Given the linked list <code>42 → 88 → 15</code> and <code>n = 2</code>, what is the resulting linked list after removing the nth node from the end?

Given the linked list `0 → 0 → 0 → 0 → 0` and `n = 5`, what is the resulting linked list after removing the nth node from the end?

Given the linked list <code>0 → 0 → 0 → 0 → 0</code> and <code>n = 5</code>, what is the resulting linked list after removing the nth node from the end?

Given the linked list `50 → 60 → 70 → 80` and `n = 3`, what is the resulting linked list after removing the nth node from the end?

Given the linked list <code>50 → 60 → 70 → 80</code> and <code>n = 3</code>, what is the resulting linked list after removing the nth node from the end?

Given the linked list `1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12` and `n = 6`, what is the resulting linked list after removing the nth node from the end?

Given the linked list <code>1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12</code> and <code>n = 6</code>, what is the resulting linked list after removing the nth node from the end?

Given the linked list `99 → 1` and `n = 1`, what is the resulting linked list after removing the nth node from the end?

Given the linked list <code>99 → 1</code> and <code>n = 1</code>, what is the resulting linked list after removing the nth node from the end?

Remove Nth Node From End of List

Remove Nth Node From End of List

# Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Can we avoid two passes through the linked list?

Counting the length $(L)$ and removing the $(L - n + 1)^\text{th}$ node takes two traversals. Is there a way to remove the node in just one pass?

What if we use two pointers?

Suppose you have two pointers. If you move the first pointer n steps ahead of the second, how does that help you know which node to remove when you reach the end?

After moving the first pointer $n$ steps, try moving both pointers together—one node at a time—until the first pointer reaches the end.
Where is the second pointer now, relative to the node you want to delete?

# Quick Fix\nYou are Edward, a Senior Software Engineer who specializes in coding interview patterns, data structures and algorithms, and is great at debugging issues in code.\n\n- Edward, please keep in mind that you do not have to print the data of the placeholders. Also, do not mention anything about yourself.\n\nEdward, you are given the following data in the placeholders:\n- Function name: `remove_nth_last_node`\n- Candidate's submitted solution code: USER_CODE\n- Error: ERROR_DESCRIPTION\n- Failed test case: FAILED_TEST_CASE\n- Coding language: `Python`\n\n- Edward, your task is to understand the type of error that is occurring in the coding language provided.\n- Once you've understood the error as per the error’s description, and why the test case failed, you will suggest how the candidate can improve their solution code to fix the error.\n- Edward, you will not give the corrected code, just a hint on what the error tells, and how to fix it.\n- Edward, please limit your response strictly to 100 words. No more words than the limit.

# Review Code\nEdward, your current task is to review the `remove_nth_last_node` function(s) and the other function(s) invoked in it/them.\n\n-Take your time and review the candidate's solution code.\n- Do not review any extra/helper files or functions not invoked in the solution function `remove_nth_last_node`.\n- Do not review the code of data structure objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. \n- Also, if the solution code doesn’t use the coding pattern stated above, then please encourage the candidate to reattempt the problem using that pattern corectly.

# Review time complexity\n- Please provide a brief time complexity analysis of the function(s) `remove_nth_last_node`. \n- While calculating time complexity, include the time complexity of built-in Python functions invoked by the code. \n- The answer should be to the point in approximately 60 words.

# Review space complexity\n- Please provide a brief space complexity analysis of the function(s) `remove_nth_last_node`. \n- While calculating space complexity, include the space complexity of built-in Python functions invoked by the code. \n- Do not include the space used for the input parameters and the space used for just returning an output (not used as a scratch space). \n- The answer should be to the point in approximately 60 words.

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        # Linked List Node Class
        class LinkedListNode:
            # __init__ will be used to make a LinkedListNode type object.
            def __init__(self, data, next=None):
                self.data = data
                self.next = next


        # Linked List Class
        class LinkedList:
            # __init__ will be used to make a LinkedList type object.
            def __init__(self):
                self.head = None

            # insert_node_at_head method will insert a LinkedListNode at head
            # of a linked list.
            def insert_node_at_head(self, node):
                if self.head:
                    node.next = self.head
                    self.head = node
                else:
                    self.head = node

            # create_linked_list method will create the linked list using the
            # given integer array with the help of InsertAthead method.
            def create_linked_list(self, lst):
                for x in reversed(lst):
                    new_node = LinkedListNode(x)
                    self.insert_node_at_head(new_node)
            
            # __str__(self) method will display the elements of linked list.
            def __str__(self):
                result = ""
                temp = self.head
                while temp:
                    result += str(temp.data)
                    temp = temp.next
                    if temp:
                        result += ", "
                result += ""
                return result

        def print_list_with_forward_arrow(linked_list_node):
            result = []
            temp = linked_list_node

            while temp:
                result.append(temp.data)
                temp = temp.next

            return result

        def remove_nth_last_node(head, n):
            right = head
            left = head

            for i in range(n):
                right = right.next
            
            if not right:
                return head.next
            
            while right.next:
                right = right.next
                left = left.next

            left.next = left.next.next

            return head

      

        input_linked_list = LinkedList()
        input_linked_list.create_linked_list(self.__inputs[0])

        # expected output
        output1 = remove_nth_last_node(input_linked_list.head,self.__inputs[1])
        expected = print_list_with_forward_arrow(output1)
        # actual output (from user's code)
        actual = self.__actual_outputs[0]
        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = []
        # store the 1st expected output that should be displayed to the user 

        if expected == actual:
            expected_outputs.append(expected)
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            expected_outputs.append(expected)
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

# Definition for a Linked List node
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from ds_v1.LinkedList.LinkedList import ListNode

def remove_nth_last_node(head, n):
    
    # Replace this placeholder return statement with your code
    return None



index (2).yaml

testcases:
  - name: "Test Case 1 - Single node list, remove only node (EC1)"
    inputs:
      - 1: [7]
      - 2: 1
    output:
      - 1: []
  - name: "Test Case 2 - Remove head node, n equals list length (EC2)"
    inputs:
      - 1: [3, 8, 12, 6]
      - 2: 4
    output:
      - 1: [8, 12, 6]
  - name: "Test Case 3 - Remove last node, n=1 (EC3)"
    inputs:
      - 1: [10, 20, 30, 40, 50]
      - 2: 1
    output:
      - 1: [10, 20, 30, 40]
  - name: "Test Case 4 - Remove middle node from medium list (EC4)"
    inputs:
      - 1: [4, 11, 23, 56, 78, 90, 15]
      - 2: 4
    output:
      - 1: [4, 11, 23, 78, 90, 15]
  - name: "Test Case 5 - Two-node list, remove first node (EC5)"
    inputs:
      - 1: [55, 77]
      - 2: 2
    output:
      - 1: [77]

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to the function.
 Store the result using the self.store_result(error_msg, status).
 Return: void
 """
 def is_valid_1d_array(arr):
 if not isinstance(arr, list):
 return False # Not a valid 1D array if it's not a list
 
 return all(isinstance(elem, int) and not isinstance(elem, bool) for elem in arr)

 # Inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 if not is_valid_1d_array(self.__inputs[0]):
 self.store_result(("Invalid test case."), ValidationFunction.FAIL) 
 elif len(self.__inputs[0]) < 1 or len(self.__inputs[0]) > 1000:
 self.store_result("Length of list should be between 1 and 1000", ValidationFunction.FAIL)
 elif any(x < -1000 or x > 1000 for x in self.__inputs[0]):
 self.store_result("Input 1 should contain values in range -1000 to 1000.", ValidationFunction.FAIL)
 elif self.__inputs[1] < 1 or self.__inputs[1] > len(self.__inputs[0]):
 self.store_result("Input 2 should be an integer between 1 and the total number of nodes in the list.", ValidationFunction.FAIL)
 else:
 self.store_result("", ValidationFunction.PASS)

Try to solve the Remove Nth Node from End of List problem.

Remove nth Node from End of List

Statement

Examples

Understand the problem

Figure it out!

Try it yourself