Microsoft Interview Question Software Engineer in Tests
@IMAH- I was not mentioning about any standard library atoi function in c or c++, you can write your own atoi that returns null(using a nullable int type in c#) or throws an exception when it finds a character not in the range of '0'-'9' in the character array.
@VVG- No builtin functions..
@ C#
when you say you validated the strings for characters, did you check each character for digit i.e isdigit(ipaddress[i]) ?
Solution could be:
1) check if the string contains numbers only.
2) Check numbers are seperated by '.' .
3) take all the substring and convert it to int using atoi() , number should be between 0 and 255.
Anything wrong with this ?
I was asked the same question. The idea is to how efficiently it handles all the valid cases and how do u split the address/string on the DOT.
i=0; j=0; word = &ipv4[0];
while(ipv4[i] != '\0') {
if(ipv4[i++] == '.') {
ipv4[i-1] = '\0';
IsValid(word);
word = &ipv4[i];
}
}
In IsValid, handle the case for valid IP byte. Can use atoi() function.
How about this in .NET.
bool flag = false; ;
System.Net.IPAddress ipAddress;
if (System.Net.IPAddress.TryParse(ip, out ipAddress))
{
switch (ipAddress.AddressFamily)
{
case System.Net.Sockets.AddressFamily.InterNetwork:
flag = true;
break;
case System.Net.Sockets.AddressFamily.InterNetworkV6:
flag = true;
break;
default:
flag = false;
break;
}
}
return flag;
Hi All,
I have written this code that validates the IPv4 address in O(n) time. I checked this code and it seems to be working fine for me. Please let me know your comments
//Here is the code
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
int main(int argc, char*argv[]){
char str[] ="247.128.5.31";
int dot_count =0;
int sum =0;
int index =0;
if(str[strlen(str)-1]=='.'){
cout<<"Invalid IP"<<"-----"<<"Last character is a dot"<<endl;
cin.get();
exit(0);
}
for(int i=(strlen(str)-1);i>=0;i--){
if(str[i]=='.'){
if(sum>255){
cout<<"Invalid IP"<<"------"<<"Exceeds 255"<<endl;;
cin.get();
exit(0);
}
else{
sum =0;
index =0;
dot_count++;
}
}
else{
char ch = str[i];
int power = (pow((float)10,(float)index));
sum+= atoi(&ch)*power;
cout<<sum<<endl;
index++;
}
}
if(dot_count!=3){
cout<<"Invalid IP"<<"-----"<<"Does not have 3 dots"<<endl;
cin.get();
exit(0);
}
if(sum>255){
cout<<"Invalid IP"<<"------"<<"Exceeds 255"<<endl;
cin.get();
exit(0);
}
cout<<"Great!!! Valid IP Addr"<<endl;
cin.get();
return 0;
}
Try character as input and not integer say A.B.11.4. It fails. Coz for invalid input atoi returns 0..But we can handle this well in Java , coz java's parseInt throws exception when it comes across a character and it throws java.lang.NumberFormatException..Hence we can put it in a try catch block to handle it and continue the loop..
PLEASE GIVE UR COMMENTS OT FEEDBACK
u also need to check if we have only 4 parts to the ip.Like there can be cases where you have xx.xxx.xxx.xxx.xx.
Also, we need to check if each part does not contain more than 3 digits. (Can it?)
We need to check if each of those is a digit and not any other character.
atoi can be used if we know that they r all numbers and will not return 0 as input will be valid.
Assumption
1. IP is provided in integer format.
2. 0.0.0.0 to 255.255.255.255 are considered to be valid IP address.
3. No use of String and IP library
Rules
1. String containing 4 integer numbers separated by period(.)
2. All 4 numbers should be in range 0 <= d <= 255.
Exceptions
1) Unknown character
2) Out of range
3) Invalid format
Scope
1. Extending to support both integer and hexadecimal numbers
2. Validation on the basis of different classification of IP address like class A, B, C
C#
public static bool validateIpV4(string str)
{
int numberOfDots = 0, currentNum = 0, multiplier = 1;
for (int i = str.Length - 1; i >= 0; --i)
{
if (str[i] == '.')
{
numberOfDots++;
if (currentNum > 255) return false;
currentNum = 0; multiplier = 1;
}
else
{
if (char.IsDigit(str[i]))
{
currentNum += (str[i] - '0')*multiplier;
multiplier = multiplier*10;
}
else return false;
}
}
return numberOfDots == 3;
}
{
bool validateIP( char* s )
{
bool isValid = true;
int temp = 0;
int length = 0;
while( s[length] )
{
isValid &= ( isDigit(s[length]) || isDot(s[length]) );
++length;
}
isValid &= ( length<16 && length>6 );
if( isValid )
{
int j = -1;
for( int i=0; i<4; ++i )
{
++j;
temp = -1;
while( !isDot(s[j]) && s[j] )
{
if( temp == -1 )
temp = s[j] - '0';
else
temp = temp*10 + s[j] - '0';
++j;
}
isValid = ( temp > -1 && temp < 256 );
if( !isValid )
break;
}
}
return isValid;
}
}
Here's java implementation:
public static boolean validateIP(String ip) {
if(ip==null || ip.endsWith("."))
return false;
String[] tokens = ip.split("\\.");
System.out.println("Length " + tokens.length);
if(tokens.length != 4)
{
return false;
}
for(String block: tokens)
{
int val = 0;
try{
val = Integer.parseInt(block);
}catch(NumberFormatException nfe) {
nfe.printStackTrace();
return false;
}
if(val < 0 || val > 255)
return false;
}
return true;
}
void Isipvalid(char* ip)
{
int i=0;
int j=0;
int dotcount = 0;
bool fail = false;
while(ip[j] != '\0')
{
int sum = 0;
i = j;
while(ip[i] !='.')
{
if(ip[i] == '\0')
break;
if((i-j) >3)
{
fail = true;
break;
}
int val = ip[i]-'0';
if(val >=0 && val <=9)
{
sum = sum * 10 + val;
}
else
{
fail = true;
break;
}
i++;
}
if(ip[i] == '.')
dotcount++;
if(sum > 255 || dotcount > 3){
fail = true;
break;
}
cout<<"\nsum is:"<<sum;
j = i +1;
}
if(fail || dotcount<3)
cout<<"failled";
else
cout<<"passed";
}
static int
inet_pton4(src, dst)
const char *src;
u_char *dst;
{
static const char digits[] = "0123456789";
int saw_digit, octets, ch;
u_char tmp[NS_INADDRSZ], *tp;
saw_digit = 0;
octets = 0;
*(tp = tmp) = 0;
while ((ch = *src++) != '\0') {
const char *pch;
if ((pch = strchr(digits, ch)) != NULL) {
u_int new = *tp * 10 + (pch - digits);
if (new > 255)
return (0);
*tp = new;
if (! saw_digit) {
if (++octets > 4)
return (0);
saw_digit = 1;
}
} else if (ch == '.' && saw_digit) {
if (octets == 4)
return (0);
*++tp = 0;
saw_digit = 0;
} else
return (0);
}
if (octets < 4)
return (0);
memcpy(dst, tmp, NS_INADDRSZ);
return (1);
}
Source code taken from libc
Over 20 replies, I didn't see a correct answer.
For interview questions, you shall not use String lib, IP lib or Preg match.
----------
Here follows a Java solution with a dozen test cases:
public class validateIP {
public static boolean validateIPAddr(String ipstr){
if(ipstr==null || ipstr.length()<7) return false;
char[] ipchars=ipstr.toCharArray();
int index=0,count=0;
while(index<ipchars.length){
index=parseNextPiece(ipchars,index);
if(index<0) return false;
count++;
}
if(count!=4)return false;
return true;
}
private static int parseNextPiece(char[] ipchars, int index) {
if(ipchars==null || index>=ipchars.length)return -1;
if(!isNumber(ipchars[index]))return -1; //first char must be a number
StringBuffer strb=new StringBuffer();
int ip;
while(index<ipchars.length){
if(ipchars[index]=='.'){
break;
}
if(isNumber(ipchars[index])){
strb.append(ipchars[index]);
if(strb.length()>3){
System.out.println(strb.toString());
return -2;
}
}else{
return -3;
}
index++;
}
ip=Integer.parseInt(strb.toString());
if(ip<0 || ip>255)return -4;
if((ip<10 && strb.length()>1)||(ip<100 && strb.length()>2))return -5;
System.out.println(strb.toString());
return index+1;
}
private static boolean isNumber(char c) {
if(c>='0' && c<='9')return true;
return false;
}
}
Test Case
/**
*
* @author Sun
*/
public class validateIPTest {
public validateIPTest() {
}
@Test
public void testValidateIPAddr() {
String test="1.23.12.123";
assertTrue(validateIP.validateIPAddr(test));
test="0.0.1.0";
assertTrue(validateIP.validateIPAddr(test));
test="255.255.255.255";
assertTrue(validateIP.validateIPAddr(test));
}
@Test
public void testValidateIPAddrFail() {
String test;
test="010.255.255.255";
assertFalse(validateIP.validateIPAddr(test));
test="110.255.255.001";
assertFalse(validateIP.validateIPAddr(test));
test="110.255.255.00";
assertFalse(validateIP.validateIPAddr(test));
test="110.255..10";
assertFalse(validateIP.validateIPAddr(test));
test="110.255.111.10.22";
assertFalse(validateIP.validateIPAddr(test));
test="110.10.22";
assertFalse(validateIP.validateIPAddr(test));
test="110.10.22.a";
assertFalse(validateIP.validateIPAddr(test));
test="110.10.-1.255";
assertFalse(validateIP.validateIPAddr(test));
test="110";
assertFalse(validateIP.validateIPAddr(test));
test="0.";
assertFalse(validateIP.validateIPAddr(test));
test="...";
assertFalse(validateIP.validateIPAddr(test));
test=null;
assertFalse(validateIP.validateIPAddr(test));
test="";
assertFalse(validateIP.validateIPAddr(test));
}
}
time/space = O(n)/O(n)
int validate_IP(char *ip)
{
regex_t regex;
int reti;
char *buf;
char *p;
int t;
regcomp(®ex, "^(([0-9]{1,3}[\.]){3}[0-9]{1,3})$",0);
reti = regexec(regex, ip, 0, NULL, 0);
if(reti==REG_NOMATCH)
return 0;
buf=(char *)malloc(strlen(ip)+2);
strcpy(buf, ip);
*(buf+strlen(ip))='.';
(buf+strlen(ip)+1)=0;
p=strtok(ip,".");
while(p!=NULL)
{
t=atoi(p);
if(!(t>=0 && t<=255))
{
free(buf);
return 0;
}
p=strtok(NULL, ".");
}
free(buf);
return 1;
}
how would you check for invalid input? atoi returns zero for any invalid input and also zero is valid in above problem!
- IMAH September 04, 2010In other words just by seeing output "0" you cannot decide whether input was 0 or invalid.