Amazon Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
public int compareVersions(String v1, String v2){
String[] sp1 = v1.split("\\.");
String[] sp2 = v2.split("\\.");
int min = sp1.length>sp2.length?sp2.length:sp2.length;
for(int i=0; i<min; i++){
int n1 = Integer.parseInt(sp1[i]);
int n2 = Integer.parseInt(sp2[i]);
if(n1==n2)
continue;
else{
return (n1-n2)>0?-1:1;
}
}
if(sp1.length!=sp2.length)
return sp1.length>sp2.length?-1:1;
else
return 0;
}
public int compareVersion(String v1, String v2){
String v1_ = v1.replaceAll("\\D", "");
String v2_ = v2.replaceAll("\\D", "");
if (v1_.isEmpty() && !v2_.isEmpty()) return 1;
else if ( !v1_.isEmpty() && v2_.isEmpty()) return -1;
else if ( v1_.isEmpty() && v2_.isEmpty()) return 0; // invalid inputs
return Integer.parseInt(v1_)>Integer.parseInt(v2_) ? -1 : 1;
}
private static int compareVersion(String ver1, String ver2) {
String[] str1 = ver1.split("\\.");
String[] str2 = ver2.split("\\.");
int loopCount = str1.length > str2.length ? str1.length : str2.length;
if (!str1[0].isEmpty() && !str2[0].isEmpty()) {
for (int i = 0; i < loopCount; i++) {
int v1 = Integer.parseInt(str1[i]);
int v2 = Integer.parseInt(str2[i]);
if (v1 == v2)
continue;
else if (v1 > v2) {
int v11 = Integer.parseInt(str1[i].substring(0, 1));
int v21 = Integer.parseInt(str2[i].substring(0, 1));
if (v11 >= v21)
return -1;
else
return 1;
} else if (v2 > v1) {
int v11 = Integer.parseInt(str1[i].substring(0, 1));
int v21 = Integer.parseInt(str2[i].substring(0, 1));
if (v21 >= v11)
return 1;
else
return -1;
}
}
} else if (str1[0].isEmpty() && str2[0].isEmpty()) {
return 0;
} else if (str1[0].isEmpty())
return 1;
else if (str2[0].isEmpty())
return -1;
else
return 0;
return 0;
}
You can remove all the dots except the first dot. This will result in a floating point number. We can directly do the fp comparison.
package zhang.juanyong.algorithms2;
import java.util.Queue;
import org.apache.commons.lang.StringUtils;
public class VersionComparator {
public static int compareVersion(String v1, String v2) {
Queue<Integer> q1 = new java.util.LinkedList<Integer>();
Queue<Integer> q2 = new java.util.LinkedList<Integer>();
loadVersion(q1, v1);
loadVersion(q2, v2);
int comp = 0;
while (!q1.isEmpty()) {
comp = q1.poll().compareTo(q2.poll());
if (0 != comp) {
return comp;
}
}
return comp;
}
private static void loadVersion(Queue<Integer> q, String version) {
String[] vNums = StringUtils.split(version, ".");
for (String v : vNums) {
q.add(Integer.valueOf(v));
}
}
public static void main(String[] args) {
String v1 = "10.3.4";
String v2 = "10.3.41";
System.out.println(String.format("compareVersion(%s, %s)=%s", v1, v2,
compareVersion(v1, v2)));
}
}
Many of these cases fall short for irregular inputs such as 10.0 < 10.0.1
Rather than cast to an integer, my example uses string comparison (character by character comparison like strcmp in c) to determine which number is larger.
import java.util.*;
public class Version {
public static int which(String version1, String version2) {
String[] versionParts1 = version1.split("\\.");
String[] versionParts2 = version2.split("\\.");
int maxLength = Math.max(versionParts1.length, versionParts2.length);
int compare = 0;
for(int i=0; i < maxLength && compare==0; i++) {
// version 2 is an extended version of version1
if(versionParts1.length==i) {
compare=1;
// version 1 is an extended version of version2
} else if(versionParts2.length==i) {
compare=-1;
} else {
compare = versionParts2[i].compareTo(versionParts1[i]);
}
}
return Integer.signum(compare);
}
public static void main(String[] args) {
System.out.println(which(args[0], args[1]));
}
}
- manish.ceg January 15, 2014