Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
I don't think this code can handle the following case:
Given String str = "123", output "123.0.0.0", "12.3.0.0", "12.30.0.0", etc.
Actually I doubt the example given in the question is correctly answered. For str = "25525511135", there are four possible valid IP addresses:
255.255.111.35
255.255.110.135
255.255.101.135
255.255.11.135
package com.interview.question;
public class IpQuestionElegantSolution
{
public static void main(String[] args)
{
IpQuestionElegantSolution ipQuestion = new IpQuestionElegantSolution();
ipQuestion.generateIpUtil("25525511135", "", 0, 0);
}
public void generateIpUtil(String input, String output, int countDot, int val)
{
if (input.length() == 0)
{
if (countDot == 3 && !output.endsWith("."))
System.out.println(output);
}
else
{
output += input.charAt(0);
val = val * 10 + Character.digit(input.charAt(0), 10);
if (val <= 255)
{
if (countDot < 3)
{
generateIpUtil(input.substring(1), output + ".", countDot+1, 0);
}
generateIpUtil(input.substring(1), output, countDot, val);
}
}
}
}
ip = given string
parts = number of ip sections yet to be generated from remaining ip string ( start to end )
sub = saved valid ip formed till previous section
Each ip has 4 sections, each section can have at most 3 digits with maximum value of 255. If k sections are yet to be formed then length of remaining ip string ( start to end ) must be >= 3 and <= 3*k. When all 4 parts have been formed and no remaining characters are there in ip string ( start to end ) then print the valid ip formed ( stored in sub ).
Code : http://ideone.com/ht7al#ul_inouterr
void valid( char *ip, int start, int end, int parts, string sub )
{
if( !parts && start == end+1 ) {
sub.erase( --sub.end() ); //remove last '.'
cout << sub << endl;
return;
}
if( end-start+1 < parts || end-start+1 > 3*parts ) {
return;
}
sub +=ip[start];
valid( ip, start+1, end, parts-1, sub + '.' ); //ip address sub section can be 1 digit
sub += ip[start+1];
valid( ip, start+2, end, parts-1, sub + '.' ); //ip address sub section can be 2 digit
//3 digit ip section must be less than 256
if( (ip[start]-'0')*100 + (ip[start+1]-'0')*10 + (ip[start+2]-'0') < 256 ) {
sub += ip[start+2];
valid( ip, start+3, end, parts-1, sub + '.' ); //ip address sub section can be 3 digit
}
}
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int valid(string a, int i, int j , int k,int len)
{
int e = atoi(a.substr(0,i).c_str());
int b = atoi(a.substr(i,j-i).c_str());
int c = atoi(a.substr(j,k-j).c_str());
int d = atoi(a.substr(k).c_str());
if(b<=255 && c<= 255 && d <= 255 && b>0 && c> 0 && d>0 && e>0 && e<=255)
{
cout<<e<<"."<< b<<"."<<c<<"."<< d<<" \n";
return 1;
}
else
return 0;
}
int main()
{
string a;
cin >>a;
int len = a.length();
if(len >12 || len ==0 || len < 4)
cout<<"String invalid \n";
if(len <= 12)
{
for(int i =0 ; i < len; i++)
{
for(int j =i+1 ; j < len; j++)
{
for(int k =j+1 ; k < len; k++)
{
valid( a, i, j , k,len);
}
}
import java.util.ArrayList;
public class IP {
public static void main (String args[]){
String str = "25525511135";
IP.findips(str);
}
static ArrayList<String> uniquepermuations = new ArrayList<String>();
static int[] ipcombination = new int[4];
static int N;
static String ipstr;
private static void findips(String str) {
N = str.length();
ipstr = str;
if(N<4 || N>12)
System.out.println("wrong ip string");
else{
recurse(0, 0);
}
System.out.println();
printIps();
}
//went little crazy here.
private static void printIps() {
//loop thourgh each quartet mask
for(String strip : uniquepermuations){
char[] num = strip.toCharArray();
int startcount = 0;
boolean goodip = true;
String goodipstr = "";
//check the value in the ip if its acceptable
for(char mask: num){
int intmask = mask - 48;
int maskedval = Integer.parseInt(ipstr.substring(startcount, startcount + intmask));
if(maskedval >=0 && maskedval<=255){
goodipstr += ipstr.substring(startcount, startcount + intmask) + ".";
startcount += intmask;
}else{
goodip = false;
break;
}
}
//found the good ip
if(goodip==true)
System.out.println(goodipstr);
}
}
//trying to find out combinations of [3,3,3,2], [2,3,3,3],[[3,2,3,2],[3,3,2,3]. etc...
private static void recurse(int quatretindex, int totalsum){
if(quatretindex>4 ||totalsum >N)
return;
if(quatretindex==4 && totalsum == N){
addtouniquepermuations();
}
else{
if(quatretindex<=3)
for(int i=3;i>=1;i--){
ipcombination[quatretindex] = i;
recurse( quatretindex + 1, totalsum + i);
}
}
}
//take only unique ones.
private static void addtouniquepermuations() {
String newip = "";
for(int i=0;i<=3;i++){
newip += ipcombination[i];
}
boolean present = false;
for(String str: uniquepermuations)
{
if(str==newip){
present = true;
break;
}
}
if(present== false)
uniquepermuations.add(newip);
}
}
public class IpConverter
{
private const int MAX_IP_NUM = 255;
private const int MAX_BLOCK_INDEX = 4;
void process(List<int> currentIp, List<int> integerList, int currentInteger, int currentIpBlock)
{
if (currentInteger < integerList.Count && currentIpBlock < MAX_BLOCK_INDEX)
{
int oldvalue = currentIp[currentIpBlock];
int newNumberInCurrentBlock = currentIp[currentIpBlock] * 10 + integerList[currentInteger];
if (newNumberInCurrentBlock <= MAX_IP_NUM)
{
currentIp[currentIpBlock] = newNumberInCurrentBlock;
process(currentIp, integerList, currentInteger + 1, currentIpBlock);
process(currentIp, integerList, currentInteger + 1, currentIpBlock + 1);
}
if (currentInteger == ( integerList.Count - 1 ) && currentIpBlock == ( MAX_BLOCK_INDEX - 1 ))
Console.WriteLine(string.Format("Ip {0}.{1}.{2}.{3}", currentIp[0], currentIp[1], currentIp[2],
currentIp[3]));
currentIp[currentIpBlock] = oldvalue;
}
}
public void PrintAllIps(string input)
{
List<int> currentIp = new List<int> { 0, 0, 0, 0 };
List<int> integerList = input.Select(c => c - '0').ToList();
process(currentIp, integerList, 0, 0);
}
}
A simple backtracking solution. Quite similar to 8 queens problem.
public class ValidIP {
public static void main(String[] args) {
String str = new String("12221222");
System.out.println("All valid combinations are: \n");
int[] arr = new int[3];
printValidIP(str,0,str.length()-1,4,arr);
}
//Utility function
private static long intVal(String str,int start,int end){
String my = new String(str.substring(start,end+1));
return Long.parseLong(my);
}
private static void printValidIP(String str,int start,int end,int partsLeft,int dotIndexArray[]) {
//If at any point start>end, no need to print anything
if(start>end){
return;
}
//The base case when only one last part of IP is remaining
if(partsLeft == 1){
if(intVal(str,start, end) <= 255){
//This is a valid combination, print it
System.out.println("One valid ip is: "+str.substring(0, dotIndexArray[0]+1)+'.'+str.substring(dotIndexArray[0]+1, dotIndexArray[1]+1)+'.'+str.substring(dotIndexArray[1]+1, dotIndexArray[2]+1)+'.'+str.substring(dotIndexArray[2]+1, end+1));
return;
}
return;
}
for(int i = start;i<=end;i++){
if(intVal(str,start,i) <= 255){
dotIndexArray[4-partsLeft] = i;
printValidIP(str,i+1,end,partsLeft-1,dotIndexArray);
}
else{
break;
}
}
return;
}
}
import re
def exploreString( str, k ):
if k < 0 :
print( "k cannot be negative" )
return "NONE"
match = re.findall( r"([a-z])([1-9]*)", str )
print( match )
iter = 0
for pattern in match:
letter = pattern[0]
rep = pattern[1]
if rep == "" :
rep = "1"
print( letter, rep )
rep = int( rep )
if k >= iter and k < iter + rep:
return letter
else:
iter = iter + rep
return "NONE"
if __name__ == "__main__":
str = "a2b2cd2"
print( exploreString( str, 4 ) )
void printSoul(vector<int> sol)
{
cout<<endl;
for(vector<int>:: iterator it = sol.begin(); it != sol.end(); it++)
cout <<*it << ".";
}
void printValidIp(string ipn, vector<int> solution)
{
int val = 0;
for(int i = 0; i < ipn.size() && i <3 ; i++)
{
char c= ipn[i];
int dig = atoi(&c);
val = val*10+dig;
if( solution.size() <=2 )
{
if( val <= 255 )
{
solution.push_back(val);
printValidIp(ipn.substr(i+1), solution);
solution.pop_back();
}
}
else
{
if( ipn.size() >=4)
return;
if( ipn.size() == i+1 && val <= 255 )
{
solution.push_back(val);
printSoul(solution);
}
}
}
}
public void getIP(String input, int left, ArrayList<String> result, String partial){
if(isAppropriate(input) && left ==1){
result.add(partial+"."+input);
}
if(input.equals("")){
return;
}
for(int i =1;i<=input.length();i++){
String pre = input.substring(0,i);
if(isAppropriate(pre)&&left>1){
String path = partial +"."+pre;
getIP(input.substring(i), left-1, result, path);
}
}
}
public boolean isAppropriate(String value){
int result =0;
if(value == null || value.equals(""))return false;
while(!(value.equals(""))){
int t= value.charAt(0)-'0';
result = result *10+t;
value = value.substring(1);
}
if(result<256 && result >0){
return true;
}else{
return false;
}
}
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
public class Solution {
public static void main(String[] args) {
String input = "25525511135";
for (String s : ip(input, 3)) {
System.out.println(s);
}
}
public static ArrayList<String> ip(String s, int dot) {
ArrayList<String> r = new ArrayList<String>();
if (s == null || s.length() == 0)
return r;
if (dot == 0) {
int i = Integer.parseInt(s);
if (i < 256) {
r.add(s);
}
return r;
}
for (int i = 1; i <= Math.min(3, s.length()); i++) {
int n = Integer.parseInt(s.substring(0, i));
if (n < 256) {
for (String st : ip(s.substring(i), dot - 1)) {
r.add(n + "." + st);
}
}
}
return r;
}
}
better formating
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
public class Solution {
public static void main(String[] args) {
String input = "25525511135";
for (String s : ip(input, 3)) {
System.out.println(s);
}
}
public static ArrayList<String> ip(String s, int dot) {
ArrayList<String> r = new ArrayList<String>();
if (s == null || s.length() == 0)
return r;
if (dot == 0) {
int i = Integer.parseInt(s);
if (i < 256) {
r.add(s);
}
return r;
}
for (int i = 1; i <= Math.min(3, s.length()); i++) {
int n = Integer.parseInt(s.substring(0, i));
if (n < 256) {
for (String st : ip(s.substring(i), dot - 1)) {
r.add(n + "." + st);
}
}
}
return r;
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace IPAddressGenerator
{
class Program
{
static void Main(string[] args)
{
string input = "255255255255";
int partValue = 0;
if (input.Length > 12)
return;
for (int i = 1; i <= 3; i++)
{
if ((input.Length < i + 3) || (input.Length - i > 9))
continue;
string part1 = input.Substring(0, i);
if (!int.TryParse(part1, out partValue) || (partValue > 255))
continue;
string remainingStr1 = input.Substring(i);
for (int j = 1; j <= 3; j++)
{
if ((remainingStr1.Length < j + 2) || (remainingStr1.Length - j > 6))
continue;
string part2 = remainingStr1.Substring(0, j);
if (!int.TryParse(part2, out partValue) || (partValue > 255))
continue;
string remainingStr2 = remainingStr1.Substring(j);
for (int k = 1; k <= 3; k++)
{
if ((remainingStr2.Length < k + 1) || (remainingStr2.Length - k > 3))
continue;
string part3 = remainingStr2.Substring(0, k);
if (!int.TryParse(part3, out partValue) || (partValue > 255))
continue;
string part4 = remainingStr2.Substring(k);
if (!int.TryParse(part4, out partValue) || (partValue > 255))
continue;
Console.WriteLine(part1 + "." + part2 + "." + part3 + "." + part4);
}
}
}
}
}
}
private static void gen(String ip) {
int l = ip.length();
for(int i=1;i<=3;i++){
if(Integer.parseInt(ip.substring(l-i,l))>255){
//System.out.println(ip.substring(l-i,l));
continue;
}
for (int j = 1; j <= 3; j++) {
if(Integer.parseInt(ip.substring(l-i-j,l-i))>255){
//System.out.println(ip.substring(l-i-j,l-i));
continue;
}
for (int k = 1; k <= 3; k++) {
if(Integer.parseInt(ip.substring(l-i-j-k,l-i-j))>255||Integer.parseInt(ip.substring(0,l-i-j-k))>255||(l-i-j-k>3)){
//System.out.println(ip.substring(l-i-j-k,l-i-j)+" "+Integer.parseInt(ip.substring(0,l-i-j-k)));
continue;
}
System.out.println(ip.substring(0,l-i-j-k)+"."+ip.substring(l-i-j-k,l-i-j)+"."+ip.substring(l-i-j,l-i)+"."+ip.substring(l-i));
}
}
}
}
private static void gen(String ip) {
int l = ip.length();
for(int i=1;i<=3;i++){
if(Integer.parseInt(ip.substring(l-i,l))>255){
//System.out.println(ip.substring(l-i,l));
continue;
}
for (int j = 1; j <= 3; j++) {
if(Integer.parseInt(ip.substring(l-i-j,l-i))>255){
//System.out.println(ip.substring(l-i-j,l-i));
continue;
}
for (int k = 1; k <= 3; k++) {
if(Integer.parseInt(ip.substring(l-i-j-k,l-i-j))>255||Integer.parseInt(ip.substring(0,l-i-j-k))>255||(l-i-j-k>3)){
//System.out.println(ip.substring(l-i-j-k,l-i-j)+" "+Integer.parseInt(ip.substring(0,l-i-j-k)));
continue;
}
System.out.println(ip.substring(0,l-i-j-k)+"."+ip.substring(l-i-j-k,l-i-j)+"."+ip.substring(l-i-j,l-i)+"."+ip.substring(l-i));
}
}
}
}
public class FindAllIP {
public static boolean validate(final String ip) {
String PATTERN = "^((0|1\\d?\\d?|2[0-4]?\\d?|25[0-5]?|[3-9]\\d?)\\.){3}(0|1\\d?\\d?|2[0-4]?\\d?|25[0-5]?|[3-9]\\d?)$";
return ip.matches(PATTERN);
}
public static void getAllIP(String header,String rest,int dotCount, List<String> list) {
if(rest.length() == 0) {
return;
}
if(dotCount == 2) {
String ip = new StringBuilder(header).append(".").append(rest).toString();
if (validate(ip))
list.add(ip);
return;
}
String partial, possibleIP, extraStr;
for(int i=0; i < rest.length(); i++) {
partial = rest.substring(0,i+1);
extraStr= rest.substring(i+1);
possibleIP = new StringBuilder(header).append(".").append(partial).toString();
getAllIP(possibleIP,extraStr,dotCount+1,list);
}
}
public static List<String> generateIPs(String ipAddr) {
List<String> ipList = new ArrayList<>();
if (ipAddr == null || ipAddr.length()< 4 || ipAddr.length() > 12) {
return ipList;
}
String header , restOfString;
for(int i=0; i < ipAddr.length(); i++) {
header = ipAddr.substring(0,i+1);
restOfString = ipAddr.substring(i+1);
getAllIP(header,restOfString,0,ipList);
}
return ipList;
}
public class FindAllIP {
public static boolean validate(final String ip) {
String PATTERN = "^((0|1\\d?\\d?|2[0-4]?\\d?|25[0-5]?|[3-9]\\d?)\\.){3}(0|1\\d?\\d?|2[0-4]?\\d?|25[0-5]?|[3-9]\\d?)$";
return ip.matches(PATTERN);
}
public static void getAllIP(String header,String rest,int dotCount, List<String> list) {
if(rest.length() == 0) {
return;
}
if(dotCount == 2) {
String ip = new StringBuilder(header).append(".").append(rest).toString();
if (validate(ip))
list.add(ip);
return;
}
String partial, possibleIP, extraStr;
for(int i=0; i < rest.length(); i++) {
partial = rest.substring(0,i+1);
extraStr= rest.substring(i+1);
possibleIP = new StringBuilder(header).append(".").append(partial).toString();
getAllIP(possibleIP,extraStr,dotCount+1,list);
}
}
public static List<String> generateIPs(String ipAddr) {
List<String> ipList = new ArrayList<>();
if (ipAddr == null || ipAddr.length()< 4 || ipAddr.length() > 12) {
return ipList;
}
String header , restOfString;
for(int i=0; i < ipAddr.length(); i++) {
header = ipAddr.substring(0,i+1);
restOfString = ipAddr.substring(i+1);
getAllIP(header,restOfString,0,ipList);
}
return ipList;
}
Its a simple successfully submitted code on interviewbit,
I'm just placing three dots at different possible locations, validating it and printing it
public class Solution {
public ArrayList<String> restoreIpAddresses(String str) {
ArrayList<String> al=new ArrayList<String>();
int i,j,k,len=str.length();
if(len<4 || len>12)
return al;
int p1,p2,p3,p4;
for(i=1;i<len-2;i++){
p1=Integer.parseInt(str.substring(0,i));
if(validated(p1) ){
for(j=i+1;j<len-1;j++){
p2=Integer.parseInt(str.substring(i,j));
if(validated(p2)){
for(k=j+1;k<len;k++){
p3=Integer.parseInt(str.substring(j,k));
if(validated(p3)){
p4=Integer.parseInt(str.substring(k,len));
if(validated(p4)){
if(Integer.valueOf(p1).toString().length()+Integer.valueOf(p2).toString().length()+Integer.valueOf(p3).toString().length()+Integer.valueOf(p4).toString().length()==len)
al.add(makeIp(p1,p2,p3,p4));
}
}
}
}
}
}
}
return al;
}
private String makeIp(int p1, int p2, int p3, int p4) {
// TODO Auto-generated method stub
String op=""+p1+"."+p2+"."+p3+"."+p4;
return op;
}
private boolean validated(int p1) {
// TODO Auto-generated method stub
if(p1>=0 && p1<=255 )
return true;
return false;
}
}
public class Solution {
public ArrayList<String> restoreIpAddresses(String str) {
ArrayList<String> al=new ArrayList<String>();
int i,j,k,len=str.length();
if(len<4 || len>12)
return al;
int p1,p2,p3,p4;
for(i=1;i<len-2;i++){
p1=Integer.parseInt(str.substring(0,i));
if(validated(p1) ){
for(j=i+1;j<len-1;j++){
p2=Integer.parseInt(str.substring(i,j));
if(validated(p2)){
for(k=j+1;k<len;k++){
p3=Integer.parseInt(str.substring(j,k));
if(validated(p3)){
p4=Integer.parseInt(str.substring(k,len));
if(validated(p4)){
if(Integer.valueOf(p1).toString().length()+Integer.valueOf(p2).toString().length()+Integer.valueOf(p3).toString().length()+Integer.valueOf(p4).toString().length()==len)
al.add(makeIp(p1,p2,p3,p4));
}
}
}
}
}
}
}
return al;
}
private String makeIp(int p1, int p2, int p3, int p4) {
// TODO Auto-generated method stub
String op=""+p1+"."+p2+"."+p3+"."+p4;
return op;
}
private boolean validated(int p1) {
// TODO Auto-generated method stub
if(p1>=0 && p1<=255 )
return true;
return false;
}
}
void generateIPUtil( char* str, char* output, int depth, int countDot, int val ) { if( !*str ) { output[depth] = '\0'; if( countDot == 3 && output[depth-1] != '.' ) printf( "%s\n", output ); } else { output[depth] = *str; val = val * 10 + *str - '0'; if( val <= 255 ) { if( countDot < 3) { output[depth + 1] = '.'; generateIPUtil( str+1, output, depth+2, countDot+1, 0 ); } generateIPUtil( str+1, output, depth+1, countDot, val ); } } } void generateIP( char* str ) { char output[30]; generateIPUtil( str, output, 0, 0, 0 ); }Working code here: ideone.com/GMs87
- Aashish September 07, 2012