Last active
October 14, 2019 19:30
-
-
Save fabri1983/86406d412eb3f796c3b16ac13c0cbdcc to your computer and use it in GitHub Desktop.
Given a string S containing a sequence of positive integers, count how many valid IPv4 addresses it contains.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.List; | |
/** | |
* Given a string S containing a sequence of positive integers, | |
* count how many valid IPv4 addresses it contains. <br/> | |
* Example: <br/> | |
* S="1234" contains: 1.2.3.4 so count=1 <br/> | |
* S="5255255255" contains: 5.255.255.255 and 52.55.255.255 so count=2 <br/> | |
* S="999999999" count=0 <br/> | |
* <br/><br/> | |
* Max time for resolution: 60 minutes. | |
*/ | |
class Ipv4CombinationsCounter { | |
public static void main(String[] args) { | |
Ipv4CombinationsCounter sol = new Ipv4CombinationsCounter(); | |
System.out.println(sol.solution("1234")); // 1 | |
System.out.println(sol.solution("12222")); // 4 | |
System.out.println(sol.solution("5255255255")); // 2 | |
System.out.println(sol.solution("25525511135")); // 2 | |
System.out.println(sol.solution("1212121212")); // 10 | |
System.out.println(sol.solution("999999999")); // 0 | |
System.out.println(sol.solution("10234")); // 4 | |
} | |
public int solution(String S) { | |
// validate | |
if (!isNumber(S) || !validLength(S)) { | |
return 0; | |
} | |
// 3 is the max amount of digits in base 10 allowed to form a valid IPv4 octet. | |
int groupingMaxSize = 3; | |
List<String> candidates = generatePartitions(S, groupingMaxSize); | |
return countValidIpv4(candidates); | |
} | |
private List<String> generatePartitions(String s, int groupingMaxSize) { | |
// storing candidates in a list | |
List<String> bag = new ArrayList<String>(); | |
// avoid out of bound exceptions | |
int slength = s.length(); | |
// Nested complexity is 3 since we have to add up to 3 periods. | |
// In each nested level we took a pivot to then iterate over the rest of the string to add missing periods. | |
for (int i = 1; i <= groupingMaxSize && i < slength; i++) { | |
// this loop takes substring from j=i+1 and looping maxDigitsOctet times | |
for (int j = i + 1; j <= (i + groupingMaxSize) && j < slength; j++) { | |
// this loop takes substring from k=j+1 to k+groupingMaxSize, looping maxDigitsOctet times | |
for (int k = j + 1; k <= (j + groupingMaxSize) && k < slength; k++) { | |
String octet1 = s.substring(0, i); | |
String octet2 = s.substring(i, j); | |
String octet3 = s.substring(j, k); | |
// octet4: in case you want to extract up to groupingMaxSize then use: s.substring(k, Math.min(k+groupingMaxSize, slength)); | |
// otherwise giving the current problem definition we have to add the rest of the string. | |
String octet4 = s.substring(k); | |
String candidate = octet1 + "." + octet2 + "." + octet3 + "." + octet4; | |
bag.add(candidate); | |
} | |
} | |
} | |
return bag; | |
} | |
private int countValidIpv4(List<String> candidates) { | |
return (int) candidates.stream() | |
.filter( c -> isValidIpv4Format(c) ) | |
.count(); | |
} | |
private boolean isValidIpv4Format(String c) { | |
return Arrays.asList(c.split( "\\." )).stream() | |
.map( t -> Integer.valueOf(t) ) | |
.allMatch( i -> i.intValue() >= 0 && i.intValue() <= 255 ); | |
} | |
private boolean validLength(String s) { | |
if (s.length() < 4) { | |
return false; | |
} | |
return true; | |
} | |
private boolean isNumber(String s) { | |
// is it an invalid string | |
if (s == null || "".equals(s)) { | |
return false; | |
} | |
// check if the string content is a number | |
try { | |
long n = Long.parseLong(s); | |
// ensure is not negative | |
if (n < 0) { | |
return false; | |
} | |
} | |
catch (Exception e) { | |
// not a number | |
return false; | |
} | |
return true; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment