Ebay Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
So you get an array of such strings? Let's assume you do, say s[i] :
Ok, for each string, say string i:
1) Tokenize with separator .
2) Convert each token to an element of an int array a[i][j]
where i= denotes string , j= denotes token of string in order it appears
So say you have two strings: s[0]=3.1 , s[1]=3.1.3
This converts to a[0]={3, 1} , a[1]={3,1,3}
3) If some elements of a[i] have less "j" tokens, 0 fill them so the j-width is all the same
{You can precompute the largest j-width if needed}
4) Do necessary number of stable sorts of versions a[i] on j entries from "right to left"
{use > sort ordering, and you will get your answer as first element of a[i] }
Yes, I had essentially the same idea.
Radix sort usually using counting sort subroutine on each slot, but in this case we should allow for comparison sorts (stable) in case huge integers are allowed in each intermediate version number.
i.e.,
1.1020203030301.2.3040404.3.1.1
Would cause the usual counting sort (sub sort of radix sort) some troubles on two of the slots.
class main {
double arr[] = {2.2,3.4,4.5,1.2};
double latest;
public void test(){
for( int i=0;i<arr.length-1;i++){
if (arr[i] > arr[i+1]){
latest = arr[i];
}
else {
latest = arr[i+1];
}
}
System.out.println("latest version is "+ latest);
}
}
public class interview{
public static void main(String args[]){
main a = new main();
a.test();
}
}
// python
def greater(stra, strb):
a = stra.split()
b = strb.split()
for i in range(min(len(a), len(b)):
if a[i] > b[i] : return 1
elif a[i] < b[i] : return 0
else :
i++
j++
if len(b) >= len(a):
return "b"
else :
return "a"
As it is only required to find the latest version, you don't need to actually sort all of them.
First, convert the strings to vectors; e.g "3.12.4.7" to {3,12,4,7}( I use a string stream )
Then you have two options:
1.From left to right, for each token, find the max token, and erase all the vectors missing that token or less than the max token. Finally you will get only one vector.( Of course you can use a bool array instead of actually remove vectors)
2.Implement a compare functions for two vectors. Compare the first element till the last and return which vector is prior. Use this to traverse all the vectors to find the "max" vector.
Both require about O(k * n) time. K is the max length of the vector.
As it is only required to find the latest version, you don't need to actually sort all of them.
First, convert the strings to vectors; e.g "3.12.4.7" to {3,12,4,7}( I use a string stream )
Then you have two options:
1.From left to right, for each token, find the max token, and erase all the vectors missing that token or less than the max token. Finally you will get only one vector.( Of course you can use a bool array instead of actually remove vectors)
2.Implement a compare functions for two vectors. Compare the first element till the last and return which vector is prior. Use this to traverse all the vectors to find the "max" vector.
Both require about O(k * n) time. K is the max length of the vector.
public class Version {
public static void main(String[] args){
List<String> list = new ArrayList<String>();
list.add("172.1.1");
list.add("172.1");
list.add("166");
list.add("178");
list.add("172.10.1");
list.add("172.11.1");
list.add("172.12.1");
list.add("172.2.1");
list.add("172.21.1");
list.add("172.3.1");
list.add("174.12.2");
list.add("174.1.22");
for (String version : sortVersions(list)) {
System.out.println(version);
}
}
private static List<String> sortVersions(List<String> list) {
Collections.sort(list, new VersionNumberComparator());
return list;
}
}
public class VersionNumberComparator implements Comparator<Object>{
@Override
public int compare(Object o1, Object o2) {
String a = (String) o1, b = (String) o2;
long ai = parseString(a);
long bi = parseString(b);
if(ai == bi){
return 0;
}
return ai>bi?1:-1;
}
private long parseString(String s){
int index = 0;
int versionIndex =1;
int digitIndex =1;
long value = 0;
int size = s.length();
for(;index<=size;index++){
if(index==size){
while(digitIndex<=3*versionIndex){
value *= 10;
digitIndex++;
}
}else if(s.charAt(index) == '.'){
while(digitIndex<=3*versionIndex){
value *= 10;
digitIndex++;
}
versionIndex++;
}else{
char a = s.charAt(index);
int digit = Character.getNumericValue(a);
value = digit+ value*10;
digitIndex++;
}
}
return value;
}
}
public static void main(String[] args) {
String[] r = { "172.1.1", "174.12.22", "172.3.1" };
int max = -1;
int index = 0;
for (int i = 0; i < r.length; i++) {
String s = r[i].replace(".", "");
Integer it = Integer.parseInt(s);
if (max < it) {
max = it;
index = i;
}
}
System.out.println(r[index]);
}
Guys this code should work.... Please feel free to give scenario where it fail;
public static void main(String[] args) throws IOException, Exception {
List<String> list = new ArrayList<String>();
list.add("172.1.1");
list.add("172.1");
list.add("166");
list.add("178");
list.add("172.10.1");
list.add("172.11.1");
list.add("172.12.1");
list.add("172.2.1");
list.add("172.21.1");
list.add("172.3.1");
list.add("174.12.2");
list.add("174.1.22");
System.out.println("***********Before sort************");
System.out.println(list);
Collections.sort(list,new Comparator(){
@Override
public int compare(Object o1, Object o2) {
String [] sarr1=((String)o1).split("\\.");
String [] sarr2=((String)o2).split("\\.");
for(int i=0;i<sarr1.length;i++){
int val1=Integer.parseInt(sarr1[i]);
int val2=0;
if(sarr2.length>i){
val2=Integer.parseInt(sarr2[i]);
}
if(val1!=val2 ){
return val1-val2;
}
}
return 0;
}
});
System.out.println("*********After sort********");
System.out.println(Arrays.asList(list));
}
Last element will be the latest version..:)
private static String findLatest(String v1, String v2) {
String[] s1 = v1.split("\\.");
String[] s2 = v2.split("\\.");
for(int i = 0; i < s1.length && i < s2.length; i++) {
if(Integer.parseInt(s1[i]) == Integer.parseInt(s2[i]))
continue;
else
return Integer.parseInt(s1[i]) > Integer.parseInt(s2[i]) ? v1 : v2;
}
if(s1.length > s2.length)
return v1;
else
return v2;
}
public static void main(String[] args) {
String[] versions = {"1.2.0", "3.5", "3.5.0", "3.6.1", "3.50.0", "1", "1.0", "1.0.2", "2.7", "2.7.0"};
String max = compareVersions(asList(versions));
System.out.print("Final version is " + max);
}
private static String compareVersions(List<String> versions) {
return Collections.max(versions, new Comparator<String>() {
@Override
public int compare(String version1, String version2) {
String[] numbersV1 = version1.split("\\.");
String[] numbersV2 = version2.split("\\.");
int i = 0;
while (i < numbersV1.length && i < numbersV2.length) {
int n1 = Integer.parseInt(numbersV1[i]);
int n2 = Integer.parseInt(numbersV2[i]);
if (n1 == n2) {
i++;
} else {
if (n1 > n2) {
return 1;
} else {
return -1;
}
}
}
return 0;
}
});
}
public static String latestVersion(String str1,String str2)
{
StringBuffer s1 = new StringBuffer(str1.replace("." , ""));
StringBuffer s2 = new StringBuffer( str2.replace(".", ""));
if( s1.length()>s2.length()){
s2 = rightPad(s2,s1.length(),'0' );
}else{
s1 = rightPad(s1,s2.length(),'0' );
}
// System.out.println( "s1 " + s1.toString() + "s2 " + s2.toString());
return(Integer.parseInt(s1.toString())>Integer.parseInt(s2.toString())?str1 :str2);
}
public static StringBuffer rightPad(StringBuffer smallStr, int newLength, char paddingChar){
for(int i = smallStr.length();i < newLength; i++){
smallStr.append(paddingChar);
}
return smallStr;
}
There is error because if we compare "4.2" and "3.1.1" then we get 42 and 311 as integers, so 311 will be greater that 42 as integer, but 4.2 as version is latest.
Thanks for pointing that out. Missed the use case. I have added a right pad function that makes the numbers of equal length. This function can also be found as a part of org.apache.common.lan.StringUtils. My version ofcourse is my own implementation and uses Stringbuffers.
Th basic idea is to leverage the fact that the numerical values of version string denote higher numbers that their predecessor.
Yes. one pass is enough if you want the latest version.
However, if you also need the second latest, third latest, earliest etc...sorting is a good option.
class CustomComparator implements Comparator<String> {
@Override
public int compare(String v1, String v2) {
String[] tokens = v1.split("\\.");
String[] tokens2 = v2.split("\\.");
if(tokens.length != 3 || tokens2.length !=3) {
return 0;
}
int f1 = Integer.parseInt(tokens[0]);
int f2 = Integer.parseInt(tokens[1]);
int f3 = Integer.parseInt(tokens[2]);
int s1 = Integer.parseInt(tokens2[0]);
int s2 = Integer.parseInt(tokens2[1]);
int s3 = Integer.parseInt(tokens2[2]);
if(f1 == s1 && f2 == s2 && f3 == s3) {
return 0;
}
if(f1 > s1) {
return 1;
} else if(f1 == s1) {
if(f2 > s2) {
return 1;
} else if(f2 == s2) {
if(f3 > s3) {
return 1;
}
}
}
return -1;
}
}
public class FindVersionNumber {
public static void main(String[] args) {
List<String> versionNumbers = new ArrayList<String>();
versionNumbers.add("2.3.0");
versionNumbers.add("1.1.0");
versionNumbers.add("2.0.0");
versionNumbers.add("3.1.0");
versionNumbers.add("3.0.0");
Collections.sort(versionNumbers, new CustomComparator());
System.out.println("Latest="+versionNumbers.get(versionNumbers.size()-1));
}
}
Java 8 version (not tested, just executed with few different inputs):
public static String latestVersion(String... version) {
Arrays.sort(version, (self,other) -> {
String[] selfComponents = self.split("\\.");
String[] otherComponents = other.split("\\.");
int len = Math.min(selfComponents.length, otherComponents.length);
for (int i=0; i<len; i++) {
int cmp = selfComponents[i].compareTo(otherComponents[i]);
if (cmp == 0) continue;
else return cmp;
}
return self.length() > other.length() ? 1 : -1;
});
return version[version.length-1];
}
package gao.zone.study;
import java.util.StringTokenizer;
public class FindLatestVersion {
public static void main(String[] args) {
String[] versions = { "3.1", "3.2" ,"3.2.gao","3.2.zone"};
String v = latest(versions);
System.out.println(v);
}
private static String latest(String[] versions) {
if (versions.length == 0) {
return null;
}
String v = versions[0];
for (int i = 1; i < versions.length; i++) {
v = latest(v, versions[i]);
}
return v;
}
private static String latest(String version1, String version2) {
StringTokenizer st1 = new StringTokenizer(version1, ".");
StringTokenizer st2 = new StringTokenizer(version2, ".");
while (true) {
// the longer, the later.
if (!st1.hasMoreTokens()) {
return version2;
}
if (!st2.hasMoreTokens()) {
return version1;
}
String p1 = st1.nextToken();
String p2 = st2.nextToken();
int compare = comparePart(p1, p2);
if (compare > 0) {
return version1;
}
if (compare < 0) {
return version2;
}
}
}
private static int comparePart(String p1, String p2) {
// number bigger than string.
Integer num1 = null, num2 = null;
try {
num1 = Integer.parseInt(p1);
num2 = Integer.parseInt(p2);
} catch (NumberFormatException e) {
}
if (num1 == null) {
if (num2 == null) {
// compare as string
return p1.compareTo(p2);
}
assert num1 == null && num2 != null;
return -1;
}
assert num1 != null;
if(num2 == null) {
return 1;
}
assert num1 != null && num2 != null;
return Integer.compare(num1, num2);
}
}
public void findLatestVersionOfSoftware(String[] inputValues){
if(null!=inputValues){
String latestSoftwareVersion ="0.0";
for(String eachValue1:inputValues){
float eachValue1Float1 =Float.parseFloat(eachValue1);
for(String eachValue2: inputValues){
float eachValue1Float2 =Float.parseFloat(eachValue2);
if(eachValue1Float1 >eachValue1Float2)
latestSoftwareVersion=eachValue1;
else if(eachValue1Float1 <eachValue1Float2)
latestSoftwareVersion=eachValue2;
}
}
System.out.println("latest software:" +latestSoftwareVersion);
}
}
public void findLatestVersionOfSoftware(String[] inputValues){
if(null!=inputValues){
String latestSoftwareVersion ="0.0";
for(String eachValue1:inputValues){
float eachValue1Float1 =Float.parseFloat(eachValue1);
for(String eachValue2: inputValues){
float eachValue1Float2 =Float.parseFloat(eachValue2);
if(eachValue1Float1 >eachValue1Float2)
latestSoftwareVersion=eachValue1;
else if(eachValue1Float1 <eachValue1Float2)
latestSoftwareVersion=eachValue2;
}
}
System.out.println("latest software:" +latestSoftwareVersion);
}
}
public void findLatestVersionOfSoftware(String[] inputValues){
if(null!=inputValues){
String latestSoftwareVersion ="0.0";
for(String eachValue1:inputValues){
float eachValue1Float1 =Float.parseFloat(eachValue1);
for(String eachValue2: inputValues){
float eachValue1Float2 =Float.parseFloat(eachValue2);
if(eachValue1Float1 >eachValue1Float2)
latestSoftwareVersion=eachValue1;
else if(eachValue1Float1 <eachValue1Float2)
latestSoftwareVersion=eachValue2;
}
}
System.out.println("latest software:" +latestSoftwareVersion);
}
}
Here is a simple java version
public void findLatestVersionOfSoftware(String[] inputValues){
if(null!=inputValues){
String latestSoftwareVersion ="0.0";
for(String eachValue1:inputValues){
float eachValue1Float1 =Float.parseFloat(eachValue1);
for(String eachValue2: inputValues){
float eachValue1Float2 =Float.parseFloat(eachValue2);
if(eachValue1Float1 >eachValue1Float2)
latestSoftwareVersion=eachValue1;
else if(eachValue1Float1 <eachValue1Float2)
latestSoftwareVersion=eachValue2;
}
}
System.out.println("latest software:" +latestSoftwareVersion);
}
}
class Solution
{
private int isGreater(String v1, String v2)
{
String[] words1=v1.split("."), words2=v2.split(".");
for(int i=0; i<words1.length && words2.length; i++)
{
if(words1[i]>words2[i])
return true;
else if(words1[i]<words2[i])
return false;
}
if(i<words1.length) return true;
return false;
}
public String findLatestVersion(String[] versions)
{
String latestVersion=versions[0];
for(int i=1; i<versions.length; i++)
{
if(isGreater(versions[i], latestVersion))
{
latestVersion=versions[i];
}
}
return latestVersion;
}
}
class main {
double arr[] = {2.2,3.4,4.5,1.2};
double latest;
public void test(){
for( int i=0;i<arr.length-1;i++){
if (arr[i] > arr[i+1]){
latest = arr[i];
}
else {
latest = arr[i+1];
}
}
System.out.println("latest version is "+ latest);
}
}
public class interview{
public static void main(String args[]){
main a = new main();
a.test();
}
}
There is a solution. A method returns 0 if the versuions are equal, -1 if first version less then second, and 1 in case of first version above than second. First of all, I splited strings by parts and then walk on the parts with converting to int. Also, in case of comparing "1.0" and "1" the method returns equal.
public int Compare(string version1, string version2)
{
var versionParts1 = version1.Split('.');
var versionParts2 = version2.Split('.');
var maxLength = Math.Max(versionParts1.Length, versionParts2.Length);
for (var n = 0; n < maxLength; n++)
{
int part1 = 0, part2 = 0;
if (n < versionParts1.Length)
part1 = int.Parse(versionParts1[n]);
if (n < versionParts2.Length)
part2 = int.Parse(versionParts2[n]);
if (part1 < part2)
return -1;
if (part2 < part1)
return 1;
}
return 0;
}
Traverse through String array:
- PKT October 03, 2013--Fetch first version and save it in a string MaxVersion
--Fetch next string's numeric value before (.) dot and compare with MaxVersion's first numeric value before (.).....
--In case [MaxVersion's first numeric value before (.)] > [next string's numeric value before (.)] move to next string and repeat above step
-- In case [MaxVersion's first numeric value before (.)] < [next string's numeric value before (.)] ...... copy next string in MaxVersion.... fetch next string and repeat steps again...
--In case [MaxVersion's first numeric value before (.)] = [next string's numeric value before (.)] ... check for next numeric value between first and second (.) dot
We can optimize string to numeric conversion in case we have constrain on no/ of levels in version.... for ex 5 level of version.... 11.1.0.2.5