Restore IP Addresses

Restore IP Addresses

What is this problem about?

The Restore IP Addresses interview question gives you a string of digits and asks you to return all possible valid IPv4 addresses that can be formed by inserting exactly three dots into the string. A valid IPv4 address has four parts (octets), each being a number between 0 and 255, with no leading zeros (except "0" itself). The digit string must be fully consumed.

Why is this asked in interviews?

This problem is asked at Apple, Cisco, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe because it is a canonical backtracking problem with clear pruning conditions. IP address validation is directly relevant to networking software, firewall configuration, and log parsing. It tests systematic enumeration, constraint checking, and recognizing when to prune the search tree early.

Algorithmic pattern used

The pattern is backtracking with pruning. Use a recursive function that tracks the current position in the string, the current list of segments, and the number of segments formed. At each step, try taking 1, 2, or 3 digits as the next segment. Prune if: the segment has leading zeros (and length > 1), the segment value exceeds 255, or there aren't enough remaining digits to fill the remaining segments. When exactly 4 segments are formed and all digits are consumed, add the address to the result.

Example explanation

Input: "25525511135"

Backtrack:

• Segment 1: try "2", "25", "255".
  • Try "255": valid (≤ 255, no leading zero).
    • Segment 2: try "2", "25", "255".
      • Try "255": valid.
        • Segment 3: try "1", "11", "111".
          • Try "11": valid.
            • Segment 4: remaining "135" → value 135 ≤ 255 → valid!
            • Add "255.255.11.135".
          • Try "1": segment 4 = "1135" (4 digits) → value > 255 → prune. ...

Result: ["255.255.11.135", "255.255.111.35"].

Common mistakes candidates make

• Allowing leading zeros for segments longer than 1 character (e.g., "01" is invalid).
• Not pruning when remaining digits are too few or too many for the remaining segments.
• Forgetting to check that all digits are consumed when 4 segments are found.
• Generating segments longer than 3 characters, which can never be ≤ 255.

Interview preparation tip

For the Restore IP Addresses coding problem, the backtracking and string interview pattern is standard. List your pruning conditions before coding: leading zeros, value > 255, invalid remaining length. Interviewers at Cisco and Palo Alto Networks may ask you to extend this to IPv6 — show you can adapt the constraint checks. Practice clearly separating the "is this segment valid?" check from the "have we completed a valid address?" check.