Search in ArrayList using Comparator

Question

I had an interview today and I have given two java classes and asked to search dog details by registration number. I know that Java.util.ArrayList.contains(Object) but do not know how to implement when there are more than one fields.

The second question was: what is the most efficient search techniques you can use in this example? I thought about Collections.binarySearch but not sure that it is the most efficient in this example. If so, how can I implement it?

DogSort.java

public class DogSort {

public static void main(String[] args) {
    ArrayList<Dog> listDog = new ArrayList<Dog>();

    Scanner sc = new Scanner(System.in);

    listDog.add(new Dog("Max", "German Shepherd", "33"));
    listDog.add(new Dog("Gracie","Rottweiler","11"));
    Collections.sort(listDog, Dog.COMPARE_BY_NAME);
                System.out.println(listDog);
    }
}

Dog.java

class Dog {
    private String name;
    private String breed;
    private String registrationNumber;

public Dog(String name, String breed, String registrationNumber) {
        this.name = name;
        this.breed = breed;
        this.registrationNumber = registrationNumber;
    }

public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.name.compareTo(other.name);
        }
};
//getter and setter methods for all private variable

}

Override equals methods to check the equality of registration number in DOG class. https://stackoverflow.com/questions/8180430/how-to-override-equals-method-in-java — Ravi Sharma, Aug 29 '17 at 04:26
You can't use a binary search unless the list is sorted by the lookup field. — shmosel, Aug 29 '17 at 04:28

score 1 · Answer 1 · answered Aug 29 '17 at 05:50

I agree with @Pritam Banerjee's answer. The most efficient search technique is to use HashMap in this scenario. I would recommend to use HashSet but the HashSet#contains method returns boolean, so just use map. Here is the code snippet.

Just for Information When using hash based collection/map dont forget to implement hashCode and equals method properly.

public class DogSearch {
    public static void main(String[] args) {
        Map<String, Dog> dogs = new HashMap<String, Dog>();

        Dog max = new Dog("Max", "German Shepherd", "1001");
        Dog gracie = new Dog("Gracie", "Rottweiler", "1002");
        Dog luca = new Dog("Luca", "Labrador", "1003");
        Dog tiger = new Dog("Tiger", "Beagle", "1004");
        Dog meemo = new Dog("Meemo", "Bulldog", "1005");
        Dog lacie = new Dog("Lacie", "German Shorthaired Pointer", "1006");

        dogs.put(max.getRegistrationNumber(), max);
        dogs.put(gracie.getRegistrationNumber(), gracie);
        dogs.put(luca.getRegistrationNumber(), luca);
        dogs.put(tiger.getRegistrationNumber(), tiger);
        dogs.put(meemo.getRegistrationNumber(), meemo);
        dogs.put(lacie.getRegistrationNumber(), lacie);

        Dog result = dogs.get("1002");

        if (result == null) {
            System.out.println("Dog not found");
        } else {
            System.out.println(result);
        }
    }
}

class Dog {
    private String name;
    private String breed;
    private String registrationNumber;

    public Dog(String name, String breed, String registrationNumber) {
        this.name = name;
        this.breed = breed;
        this.registrationNumber = registrationNumber;
    }

    public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.name.compareTo(other.name);
        }
    };

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getBreed() {
        return breed;
    }

    public void setBreed(String breed) {
        this.breed = breed;
    }

    public String getRegistrationNumber() {
        return registrationNumber;
    }

    public void setRegistrationNumber(String registrationNumber) {
        this.registrationNumber = registrationNumber;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((breed == null) ? 0 : breed.hashCode());
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + ((registrationNumber == null) ? 0 : registrationNumber.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Dog other = (Dog) obj;
        if (breed == null) {
            if (other.breed != null)
                return false;
        } else if (!breed.equals(other.breed))
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        if (registrationNumber == null) {
            if (other.registrationNumber != null)
                return false;
        } else if (!registrationNumber.equals(other.registrationNumber))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Dog [name=" + name + ", breed=" + breed + ", registrationNumber=" + registrationNumber + "]";
    }

}

Time Complexity

Insertion : O(1)

Search : O(1)

score 0 · Answer 2 · answered Aug 29 '17 at 05:01

0

Add it to a HashMap with Registration as Key and Dog object as the value and then search the Map.

O(1) insertion and O(1) searching.

Binary Search O(log n).

answered Aug 29 '17 at 05:01

Pritam Banerjee

17,953
10
93
108

score 0 · Answer 3 · answered Aug 29 '17 at 06:14

For the first question ie to search details by registration number here is the code

import java.util.Comparator;
import java.util.TreeMap;

public class DogSort {

    public static void main(String[] args) {
        TreeMap<Integer, Dog> listDogs = new TreeMap<>();
        listDogs.put(33, new Dog("Max", "German Shepherd", "33"));
        listDogs.put(11, new Dog("Gracie", "Rottweiler", "11"));
        System.out.println(listDogs);
        System.out.println(listDogs.containsKey(11));
        System.out.println(listDogs.get(11));
    }
}

class Dog {
    private String name;
    private String breed;
    private String registrationNumber;

    public Dog(String name, String breed, String registrationNumber) {
        this.name = name;
        this.breed = breed;
        this.registrationNumber = registrationNumber;
    }

    public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.name.compareTo(other.name);
        }
    };

    @Override
    public String toString() {
        return "Dog [name=" + name + ", breed=" + breed + ", registrationNumber=" + registrationNumber + "]";
    }

}

It is very difficult to get the details of dog by registration number using arraylist, but with map it is quite easy.

And you can override the hashcode and equals method like this but the arraylist compare method works differently.

What you can do is you can write a method which can search details by registration number. The method will have to iterate the list and find the Dog object,and if the list is sorted then you need to implement your own binary search to get the Dog object according to the registration number.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class DogSort {

    public static void main(String[] args) {
        ArrayList<Dog> listDog = new ArrayList<Dog>();

        listDog.add(new Dog("Max", "German Shepherd", "33"));
        listDog.add(new Dog("Gracie", "Rottweiler", "11"));

        Collections.sort(listDog, Dog.COMPARE_BY_NAME);

        System.out.println(listDog);
        System.out.println(listDog.contains(new Dog("Max", "Rottweiler", "33")));
    }
}

class Dog {
    private String name;
    private String breed;
    private String registrationNumber;

    public Dog(String name, String breed, String registrationNumber) {
        this.name = name;
        this.breed = breed;
        this.registrationNumber = registrationNumber;
    }

    public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() {
        public int compare(Dog one, Dog other) {
            return one.name.compareTo(other.name);
        }
    };

    @Override
    public String toString() {
        return "Dog [name=" + name + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((registrationNumber == null) ? 0 : registrationNumber.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Dog other = (Dog) obj;
        if (registrationNumber == null) {
            if (other.registrationNumber != null)
                return false;
        } else if (!registrationNumber.equals(other.registrationNumber))
            return false;
        return true;
    }


}

Search in ArrayList using Comparator

3 Answers3