Amazon Interview Question SDE1s
Country: United States
Interview Type: In-Person
Problem is that you don't check if the IP portions are valid. So if the last three digits were 258, you'd accept that, and it wouldn't be valid IP.
That said, that's a relatively easy check to add to your code. Before going into the next nested loop, check that the value is <= 255 and doesn't have leading zeros.
My solution
public static List<String> getAllValidIps(String inputIP) {
List<String> validIps = new ArrayList<String>();
if (inputIP == null) {
return validIps;
}
getAllValidIps(validIps, "", inputIP, 4);
return validIps;
}
private static boolean validate(String ip) {
try {
int number = Integer.parseInt(ip);
if (number < 0 || number >= 256) {
return false;
}
} catch (Exception e) {
return false;
}
return true;
}
private static void getAllValidIps(List<String> validIps, String current, String remaining, int left) {
if (left == 1) {
if (validate(remaining)) {
current = current + "." + remaining;
validIps.add(current);
}
} else {
for (int i = 1; i <= 3; i++) {
int remainingSize = remaining.length();
if (i <= remainingSize) {
String newString = remaining.substring(0, i);
String updatedCurrent = current;
if (validate(newString)) {
if (left == 4) {
updatedCurrent = newString;
} else {
updatedCurrent = current + "." + newString;
}
getAllValidIps(validIps, updatedCurrent, remaining.substring(i, remainingSize), left - 1);
}
}
}
}
}
//Given a string of numbers, returns an array of all possible IPV4 addresses
static int[][] findIPV4(String str)
{
//create list object
List list = new ArrayList();
//start processing list
addAddresses(0, str, 0, new int[4], list);
//return the list cast to an array of the correct type
return (int[][])list.toArray(new int[list.size()][]);
}
static void addAddresses(int octetIndex, String str, int startIndex, int[] address, List list)
{
//for lengths 1 to 3
for (int i = 1; i < 4; i++)
{
//if we're greater than string length, done
if (startIndex + i > str.length()) break;
//get this number as an int
int value = Integer.parseInt(str.substring(startIndex, startIndex + i));
//if this can't be an octetIndex, then we're done (three digits greater than 255)
if (value > 255) break;
//if octetIndex < 4, recurse
if (octetIndex < 3)
{
address[octetIndex] = value;
addAddresses(octetIndex + 1, str, startIndex + i, address, list);
continue;
}
//octetIndex = 3
//if we didn't use up the whole string, continue
if (startIndex + i != str.length()) continue;
//found one! copy and add to list
address[octetIndex] = value;
list.add(Arrays.copyOf(address, address.length));
}
}
Here is a similar idea in C++
bool isvalid(std::string& oct)
{
int num=atoi(oct.c_str());
if(num<0 || num>=256)
return false;
return true;
}
void dotMeBro(std::string& ip, std::vector<std::string>& results,int octs=4)
{
if(octs==1)
{
if(ip.length()<=3 && isvalid(ip))
results.push_back(ip);
return;
}
for(int i=1;i<=3;i++)
{
int sublen=ip.length()-i;
if(sublen<=0)
break;
if((sublen/(octs-1))==3 && (sublen%(octs-1))>0)
continue;
std::string my=ip.substr(0,i);
if(!isvalid(my))
break;
std::vector<std::string> myResults;
std::string subProblem=ip.substr(i);
//std::cout<<"i:"<<i<<" my:"<<my<<" sub:"<<subProblem<<std::endl;
dotMeBro(subProblem,myResults,octs-1);
for(std::vector<std::string>::iterator it=myResults.begin(); it!=myResults.end();++it)
{
results.push_back(my+"."+*it);
}
}
}
// All valid IP address combinations of a string in Python
def get_ipaddr_combs(ip_addr):
combs = ['']
preres = []
for i in xrange(4):
for prefix in combs:
for j in range(1, 4):
start = len(prefix)-i
end = len(prefix)-i+j
if start < len(ip_addr) and end <= len(ip_addr):
ip_part = ip_addr[start:end]
if 0 <= int(ip_part) <= 255:
if i < 3:
preres.append(prefix+ip_part+'.')
elif end == len(ip_addr):
preres.append(prefix+ip_part)
combs = preres
preres = []
return combs
// Here is the recursive logic
#include <iostream>
using namespace std;
#define EXACT_DOTS 3
#define MAX_GAP_BETWEEN_DOTS 3
//private
void generateIpV4(string& ipStr , string& opStr , int ipIndex , int opIndex, int dotCount , int prevDotPos)
{
if(opIndex - prevDotPos -1 <= MAX_GAP_BETWEEN_DOTS )
{
if(ipStr.size() + EXACT_DOTS == opIndex && dotCount == EXACT_DOTS)
{
cout<<"\n"<<opStr;
}
else
{
if(dotCount < EXACT_DOTS && prevDotPos + 2 <= opIndex)
{
opStr[opIndex] = '.';
opStr[opIndex + 1] = ipStr[ipIndex];
generateIpV4(ipStr , opStr , ipIndex + 1 , opIndex + 2 , dotCount + 1 , opIndex);
}
opStr[opIndex] = ipStr[ipIndex];
generateIpV4(ipStr , opStr , ipIndex + 1 , opIndex + 1 , dotCount , prevDotPos);
}
}
}
//public
void generateIpV4(string& ipStr)
{
if(ipStr.size() >= 4 && ipStr.size() <= 12)
{
// Just initializing a string with input size + exact number of dots
string opStr(ipStr + "...");
cout<<"\n\nGenerating IP addreses for "<<ipStr;
generateIpV4(ipStr , opStr , 0, 0, 0, -1);
}
else
cout<<"\n\nNo Ip addresses can be generated from string "<<ipStr;
}
int main()
{
string ip = "12345678";
generateIpV4(ip);
string ip1 = "1234";
generateIpV4(ip1);
string ip2 = "123";
generateIpV4(ip2);
string ip3 = "1234567812345678";
generateIpV4(ip3);
}
Here's a recursive approach with C#. Please feel free to highlight any areas that can be improved.
public List<string> GetPossibleIps(string ip)
{
return GetPossibleIps(ip, 4);
}
private List<string> GetPossibleIps(string ip, int sectionLeft)
{
List<string> allIps = new List<string>();
if (sectionLeft == 1)
{
if (IsValid(ip))
{
allIps.Add(ip);
return allIps;
}
else
{
return null;
}
}
for (int i = 1; i <= 3; i++)
{
if (ip.Length >= i)
{
string firstIDigit = ip.Substring(0, i);
if (IsValid(firstIDigit))
{
List<string> ipParts = GetPossibleIps(ip.Substring(i), sectionLeft - 1);
if (ipParts != null && ipParts.Count > 0)
{
PrependPartToParts(firstIDigit, ipParts);
allIps.AddRange(ipParts);
}
}
}
}
return allIps;
}
private void PrependPartToParts(string ipPart, List<string> ipParts)
{
for (int i = 0; i < ipParts.Count; i++)
{
ipParts[i] = ipPart + "." + ipParts[i];
}
}
private bool IsValid(string ipSection)
{
if (string.IsNullOrEmpty(ipSection) ||
(ipSection.Length > 1 && ipSection.Substring(0, 1).Equals("0")))
{
return false;
}
int number;
bool parsed = int.TryParse(ipSection, out number);
return parsed && (number >= 0 && number <= 255);
}
public class IPGenerator {
public static void main(String[] args) {
String s = "1111";
generateIP(s, "");
}
private static void generateIP(String s, String t) {
if (s.isEmpty()) {
int count = 0;
for (char c : t.toCharArray()) {
if (c == '.')
count++;
}
if (count == 4)
System.out.println(t.substring(0, t.length() - 1));
}
for (int i = 3; i > 0; i--) {
if (s.length() < i)
continue;
String temp = s.substring(0, i);
if (Integer.parseInt(temp) > 255)
continue;
generateIP(s.substring(i), t + temp + ".");
}
}
}
///
public class IPGenerator {
public static void main(String[] args) {
String s = "1111";
generateIP(s, "");
}
private static void generateIP(String s, String t) {
if (s.isEmpty()) {
int count = 0;
for (char c : t.toCharArray()) {
if (c == '.')
count++;
}
if (count == 4)
System.out.println(t.substring(0, t.length() - 1));
}
for (int i = 3; i > 0; i--) {
if (s.length() < i)
continue;
String temp = s.substring(0, i);
if (Integer.parseInt(temp) > 255)
continue;
generateIP(s.substring(i), t + temp + ".");
}
}
}
\\\
- m@}{ August 11, 2014/** * time: O(3^4) = O(1) * space: O(N) */ void printAllIps(String ipStr){ checkNotNull(ipStr); checkArgument(ipStr.length() > 3, "'ip' too short: %s", ipStr.length()); checkArgument(ipStr.length() < 13, "'ip' too long: %s", ipStr.length()); int arrLength = ipStr.length(); for( int i = 1; i < arrLength-2 && i-0 < 4; i++ ){ String firstPart = ipStr.substring(0, i); for( int j = i+1; j < arrLength-1 && j-i < 4; j++ ){ String secondPart = ipStr.substring(i, j); for( int k = j+1; k < arrLength && k-j < 4; k++ ){ String thirdPart = ipStr.substring(j, k); String fourthPart = ipStr.substring(k, ipStr.length()); if( fourthPart.length() < 4 ){ System.out.println( firstPart + "." + secondPart + "." + thirdPart + "." + fourthPart); } } } } }