Learn essential coding patterns to answer problems and prepare for tech companies' interviews.

Ace the Java Coding Interview

This module teaches us the underlying patterns behind common coding interview questions. By learning these essential patterns, we'll be able to assess the problem statement and unpack and answer any problem the right way. This approach was created by FAANG’s hiring managers to help us prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon.

By the end of this module, we'll have the skills we need to unlock even the most challenging questions, grok the coding interview, and level up our career with confidence.

Coding Interview Patterns

# 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?

from linked_list_node import LinkedListNode

# Template for the linked list
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

# Template for 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

# Template for printing the linked list with forward arrows

def print_list_with_forward_arrow(linked_list_node):
    temp = linked_list_node
    while temp:
        print(temp.data, end=" ")  # print node value
        
        temp = temp.next
        if temp:
            print("→", end=" ")
        else:
            # if this is the last node, print null at the end
            print("→ null", end=" ")

# 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: `removeNthLastNode`\n- Candidate's submitted solution code: USER_CODE\n- Error: ERROR_DESCRIPTION\n- Failed test case: FAILED_TEST_CASE\n- Coding language: `Java`\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 `removeNthLastNode` 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 `removeNthLastNode`.\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) `removeNthLastNode`. \n- While calculating time complexity, include the time complexity of built-in Java 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) `removeNthLastNode`. \n- While calculating space complexity, include the space complexity of built-in Java 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 {
//     int val;
//     ListNode next;

//     // Constructor
//     public ListNode(int val) {
//         this.val = val;
//         this.next = null;
//     }
// }
import ds_v1.LinkedList.ListNode;
import java.util.*;

class Solution {
    public static ListNode removeNthLastNode(ListNode head, int n) {
        
        // Replace this placeholder return statement with your code
        
        return head;
    }
}

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