Bird
Raised Fist0
Interview PrepbacktrackingmediumAmazonFacebookGoogle

Restore IP Addresses

Choose your preparation mode4 modes available

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Steps
setup

Initialize stack with starting state

The algorithm initializes the stack with a tuple containing start index 0 and an empty path, representing no segments chosen yet.

💡 This setup is crucial as it sets the starting point for exploring all possible segmentations.
Line:stack = [(0, [])] # (start index, path)
💡 The stack holds states to explore; starting with no segments chosen and at the beginning of the string.
📊
Restore IP Addresses - Watch the Algorithm Execute, Step by Step
Watching each segment choice and pruning decision helps you understand how the algorithm efficiently avoids invalid IP segments and collects valid addresses.
Step 1/16
·Active fillAnswer cell
enterings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Remaining
start=0, path=[]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=0, path=[]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=3, path=['255']
Partial: [255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
Partial: [255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
Partial: [255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=6, path=['255', '255']
Partial: [255, 255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='11'segment='111'
Partial: [255, 255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='11'segment='111'
Partial: [255, 255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=8, path=['255', '255', '11']
Partial: [255, 255, 11]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='135'
Partial: [255, 255, 11]
backtrackings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='135'
Partial: [255, 255, 11, 135]
Found 1: [255.255.11.135]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=9, path=['255', '255', '111']
Partial: [255, 255, 111]
Found 1: [255.255.11.135]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='35'
Partial: [255, 255, 111]
Found 1: [255.255.11.135]
backtrackings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='35'
Partial: [255, 255, 111, 35]
Found 2: [255.255.11.135] [255.255.111.35]

Key Takeaways

The algorithm uses a stack to iteratively explore all possible segmentations, avoiding recursion overhead.

This is hard to see from code alone because the stack manipulation and pruning logic are intertwined.

Pruning based on remaining characters and segments drastically reduces the search space.

Visualizing pruning decisions clarifies why some paths are abandoned early.

Valid segments must not start with zero unless they are '0', and must be <= 255, which guides segment validation.

Seeing each segment validation step helps understand these constraints concretely.

Practice

(1/5)
1. You need to place n queens on an nxn chessboard so that no two queens threaten each other (no two queens share the same row, column, or diagonal). Which algorithmic approach guarantees finding all valid solutions efficiently by pruning invalid partial placements early?
easy
A. Backtracking with pruning to avoid columns and diagonals already attacked
B. Greedy algorithm that places queens row by row choosing the first safe column
C. Dynamic programming to count valid queen placements using subproblems
D. Breadth-first search exploring all board states level by level

Solution

  1. Step 1: Understand problem constraints

    The problem requires placing queens so none attack each other, which involves checking columns and diagonals.
  2. Step 2: Identify algorithm that prunes invalid states early

    Backtracking with pruning efficiently avoids exploring invalid partial solutions by tracking attacked columns and diagonals.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Backtracking prunes invalid states early [OK]
Hint: Pruning columns and diagonals is key to efficient search [OK]
Common Mistakes:
  • Thinking greedy placement always works
  • Assuming DP applies directly
  • Confusing BFS with pruning
2. You are given a partially filled 9x9 grid where each row, column, and 3x3 sub-box must contain digits 1 through 9 without repetition. Which algorithmic approach guarantees finding a valid solution if one exists?
easy
A. Greedy algorithm that fills cells with the first valid digit found
B. Breadth-first search exploring all possible digit placements simultaneously
C. Dynamic programming by storing subproblems of partially filled grids
D. Backtracking with constraint propagation and heuristic ordering of empty cells

Solution

  1. Step 1: Understand problem constraints

    The problem requires filling cells respecting row, column, and box constraints, which is a classic constraint satisfaction problem.
  2. Step 2: Identify algorithm that guarantees solution

    Backtracking with constraint propagation prunes invalid choices early, and heuristic ordering reduces branching, ensuring completeness and efficiency.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Constraint propagation + heuristic ordering is standard for Sudoku solvers [OK]
Hint: Constraint satisfaction problems need backtracking with pruning [OK]
Common Mistakes:
  • Assuming greedy or BFS alone can solve Sudoku efficiently
3. You are given a 2D grid of letters and a list of words. You need to find all words that can be formed by sequentially adjacent letters (horizontally or vertically) without reusing the same cell in a single word. Which algorithmic approach best guarantees an efficient solution for this problem?
easy
A. Use dynamic programming to store subproblems of partial word matches.
B. Use a greedy search that picks the next letter with the highest frequency in the grid.
C. Use backtracking combined with a Trie data structure to prune invalid prefixes early.
D. Search each word independently using DFS without any prefix pruning.

Solution

  1. Step 1: Understand problem constraints

    The problem requires searching multiple words in a grid with adjacency and no reuse constraints, which is expensive if done naively.
  2. Step 2: Identify efficient pruning technique

    Backtracking with a Trie allows pruning search paths early when no word prefix matches, avoiding redundant searches.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Trie pruning reduces search space drastically compared to naive DFS [OK]
Hint: Trie + backtracking prunes invalid prefixes early [OK]
Common Mistakes:
  • Thinking greedy or DP alone can solve adjacency constraints efficiently.
4. What is the time complexity of the optimal palindrome partitioning algorithm that uses backtracking with dynamic palindrome checks by expanding around centers for palindrome verification on a string of length n?
medium
A. O(n^2) because palindrome checks are done in constant time using DP
B. O(n^3) due to checking all substrings and palindrome verification
C. O(2^n) since all partitions are generated without extra palindrome checks
D. O(n * 2^n) because each character can start a partition and palindrome checks are O(n)

Solution

  1. Step 1: Identify number of partitions

    There are up to 2^(n-1) ways to partition a string of length n.
  2. Step 2: Analyze palindrome check cost

    Using expand around center, palindrome check per substring is O(n) worst case, done during backtracking.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Combining partitions and palindrome checks yields O(n * 2^n) [OK]
Hint: Partitions grow exponentially; palindrome checks add linear factor [OK]
Common Mistakes:
  • Assuming palindrome checks are O(1) without DP
  • Confusing total partitions with time complexity
  • Ignoring recursion stack space
5. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?
def permuteUnique(nums):
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res
medium
A. Line with 'if i > start and nums[i] == nums[i-1]: continue' (duplicate skipping condition)
B. Line with 'nums.sort()' (sorting input before recursion)
C. Line with 'nums[start], nums[i] = nums[i], nums[start]' before recursion (swap)
D. Line with 'for i in range(start, len(nums)):' (iteration over indices)

Solution

  1. Step 1: Analyze duplicate skipping condition

    The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.
  2. Step 2: Verify other lines

    Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Incorrect duplicate skipping causes duplicate permutations [OK]
Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]
Common Mistakes:
  • Skipping duplicates by only comparing adjacent elements without usage tracking