Algorithm to Pick object from list based on object attributes

Question

There is an object, Cars, which is defined as,

class Cars{
      String make;
      String model;
      String year;
....
}

Couple of restriction on the Object:

make, model and year can take any value.
there can't be two objects with the same set of attributes. For instance, there can't be a car1 = { make : "Audi", model : "A6", year : "2008" } and a car2 = { make : "Audi", model : "A6", year : "2008"}

Let's say I talk to a service which gives me a list of all the car objects. I have an input (make,model,year). My job is to pick the car object from the list(returned by service). I should do so such that I will pick the object which matches as many attributes as possible.

Let me give an example. Lets suppose I get list of 5 cars from the service,

car1 = { make : "",     model : "A6", year : "2008" }
car2 = { make : "Audi", model : "",   year : "2008" }
car3 = { make : "Audi", model : "A6", year : "" }
car4 = { make : "",     model : "",   year : "" }
car5 = { make : "BMW",  model : "M3", year : "2009" }

If my input is

{make : "Audi", model : "A6", year : "2008"}

I should be able to pick just one car from the list. If same number of parameters match, I should give preference in the order make > model > year. In the above case, I should pick car3.

Also if my input is

{ make : "Mercedes", model : "C300", year : "2008" }

I should pick car4 = { make : "", model : "", year : "" } (The generic one)

Any suggestions on solving this issue and/or pseudo-code?

What did you try? What happens in your example if I have 2 cars, one with {make: 'Audi', model: '', year: ''} and one with {make : "", model : "A6", year : "2008"}? — Holt
– Holt, Commented Jul 27, 2015 at 18:46
In that case I would choose the second one. The preferential treatment applies only when we have cars with same number of matching parameters. — user3704576
– user3704576, Commented Jul 27, 2015 at 19:14

bcorso · Accepted Answer · 2015-07-28 07:29:10Z

Note that, we don't need to do any sorting here, just find the max score. Sorting makes your solution O(NlogN), whereas finding a max is O(N).

public Car getBestSelection(List<Car> cars, String make, String model, String year){
    Map<Car, Integer> scoreMap = new HashMap<>(cars.size());

    // Find scores for all valid cars
    for(Car car : cars)
        if(isValidCar(car, make, model, year))
            scoreMap.push(car, calcScore(car, make, model, year));

    // find max score
    Car maxCar;
    int maxScore;
    for(Map.Entry<Car, Integer> e : scoreMap.entrySet()){
        if(e.getValue() > maxScore){
            maxScore = e.getValue();
            maxCar = e.getKey();
        }
    }

    return maxCar;
}

public int calcScore(Car car, String make, String model, String year){
    int makeScore  = car.make.equals(make)   ? Math.pow(2,2) : 0;
    int modelScore = car.model.equals(model) ? Math.pow(2,1) : 0;
    int yearScore  = car.year.equals(year)   ? Math.pow(2,0) : 0;

    return makeScore + modelScore + yearScore;
}

public boolean isValidCar(Car car, String make, String model, String year){
    return (car.make.equals("") && car.model.equals("") && car.year.equals("")) ||
           (car.make.equals(make) || car.model.equals(model) || car.year.equals(year));
}

bcorso · Accepted Answer · 2015-07-27 18:59:50Z

1

I would consider using a database table to store these entries:

Table cars:

|  make  |  model  | year |
+--------+---------+------+
|  ...   |   ...   | ...  |

Then you can select the best entry with a SQL statement:

SELECT * FROM cars
WHERE make  IN('Audi', '')
AND   model IN('A6',   '')
AND   year  IN('2008', '')
SORT BY make DESC, model DESC, year DESC
LIMIT 1

The DESC is because otherwise the '' will show up first.

The LIMIT 1 is to select the top candidate from the rows, according to your sort order.

Case 1: {make : "Audi", model : "A6", year : "2008"}

|  make  |  model  | year |
+--------+---------+------+
|  Audi  |   A6    |  ''  |  <--- LIMIT 1 selects this one
|  Audi  |   ''    | 2008 |
|   ''   |   A6    | 2008 |
|   ''   |   ''    |  ''  |

Case 2: { make : "Mercedes", model : "C300", year : "2008" }

|  make  |  model  | year |
+--------+---------+------+
|   ''   |   ''    |  ''  |  <---- LIMIT 1 selects this one

edited Jul 27, 2015 at 18:59

answered Jul 27, 2015 at 18:52

bcorso

47.5k10 gold badges66 silver badges76 bronze badges

1 Comment

user3704576 Over a year ago

I'm sure this is an equally good solution, but I was looking for solution without a db.

Louis Ricci · Accepted Answer · 2015-07-28 12:14:17Z

Step 1) Find all of the items that meet any of your criteria.

Step 2) Sort the results by a score that puts your criteria in order of importance.

Here's some pseudo code in JavaScript (you can migrate it to Java).

var list = [
    {a: "a1", b: "b1", c: "c1"},
    {a: "a1", b: "b1", c: "c2"},
    {a: "a1", b: "b2", c: "c1"},
    {a: "a1", b: "b2", c: "c2"},
    {a: "a2", b: "b1", c: "c1"},
    {a: "a2", b: "b1", c: "c2"},
    {a: "a2", b: "b2", c: "c1"},
    {a: "a2", b: "b2", c: "c2"}
];

function findAny(a, b, c) {
    // get a list of all of the items that match any case
    var found = list.filter(function(record) {
        return record.a == a || record.b == b || record.c == c;
    });
    // sort the items be the calculated score high to low
    function score(record) {
        var score = 0;
        if(record.a == a) { score += Math.pow(2, 2); }
        if(record.b == b) { score += Math.pow(2, 1); }
        if(record.c == c) { score += Math.pow(2, 0); }
        // setting the score on the record for education
        record.score = score;
        return score;
    }
    return found.sort(function(a, b) { return score(b) - score(a); });
}

var result = findAny("a2", "b2", "c2");
console.log(JSON.stringify(result, null, "\t"));

The result of the above would be

[
    {
        "a": "a2",
        "b": "b2",
        "c": "c2",
        "score": 7
    },
    {
        "a": "a2",
        "b": "b2",
        "c": "c1",
        "score": 6
    },
    {
        "a": "a2",
        "b": "b1",
        "c": "c2",
        "score": 5
    },
    {
        "a": "a2",
        "b": "b1",
        "c": "c1",
        "score": 4
    },
    {
        "a": "a1",
        "b": "b2",
        "c": "c2",
        "score": 3
    },
    {
        "a": "a1",
        "b": "b2",
        "c": "c1",
        "score": 2
    },
    {
        "a": "a1",
        "b": "b1",
        "c": "c2",
        "score": 1
    }
]

EDIT If you only want the result(s) with the best score.

function findAnyBest(a, b, c) {
    function score(record) {
        var score = 0;
        if(record.a == a) { score += Math.pow(2, 2); }
        if(record.b == b) { score += Math.pow(2, 1); }
        if(record.c == c) { score += Math.pow(2, 0); }
        return score;
    }
    var highScore = 0;
    var found = [];
    list.forEach(function(record) {
        var currentScore = score(record);
        if(currentScore > highScore) {
            // new high score throw out the old ones
            found = [record];
            highScore = currentScore;
        } else if(currentScore === highScore) {
            found.push(record);
        }
    });
    return found;
}

jenova · Accepted Answer · 2015-07-28 14:44:38Z

0

The above answers are mostly correct but they do not actually solve the problem to the specifications. When using an exponential model to determine how well the car matches, the highest match will always win. This means that matching on make alone (4 points) will score higher than matching on both model and year (2 + 1 = 3 points). This is the opposite of what should happen given the comments on the initial question.

It would be better to use a linear model (e.g. make = 4 points, model = 3 points, and year = 2 points). This way, matching on any two criteria will win over matching a single criterion.

answered Jul 28, 2015 at 14:44

jenova

562 bronze badges

Collectives™ on Stack Overflow

Algorithm to Pick object from list based on object attributes

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related