Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Question: You are given a raw IP address string without period separators between the digits. Return all valid IP addresses that can be created from the raw IP string where it is your job to place the periods.
This is sort of a knowledge question but if you get this in an interview you’d probably get the constraints, otherwise, it is the interviewer’s fault for being a bad interviewer since general SWE questions should primarily be about problem solving skills and not domain specific knowledge/facts.
Whenever we hear “compute” or “generate” we know that we will have to do some sort of repeated looping or recursion in a backtracking approach. For this problem, we can do either.
Approach 1 (iteration)
A triple nested set of for loops where in each section we create a part of the IP string, validate that section we just snipped out and then continue on to generate the rest of the IP string
Approach 2 (backtracking)
The 3 Keys To Backtracking:
Our Choice:
– We will take snippets of substrings 1-3 characters long
Our Constraints:
– We cannot have a value greater than 255 or less than 0 in any subsection.
– We cannot have a leading 0 in any subsection
Our Goal:
– Get 4 valid subsections out of the raw string that we started with that will comprise the fully valid IP recomposition
We can make progress through the string, slowly decoding it in all ways possible by taking a snippet, validating it, and then continuing on in the generation path.
Since we will be using recursion, each recursive call will express all possible ways to arrange a certain subsection of the string that is…
Until we reach the base case which is when we have all 4 segments filled out (and by default, our index pointer has progressed to the string’s length).
Complexities
Time: O(1)
– Off the bat, we know that we will have a constant time complexity because there are a limited amount of IP addresses (2^32 to be exact) so our time complexity will fall as O(1) (“constant”)
Space: O(1)
– By the same line of reasoning, our space complexity is O(1)
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This is problem 7.10 in the book Elements of Programming Interviews by Adnan Aziz
