CODEWITHSUNDEEP
javalogic
John Baum
John Baum

Reputation: 3331

Defining more efficient logic for given scenario

Got some interesting logic that I am trying to encode in the most efficient and readable way possible. I will lay out the scneario below (with a simulated/dummy context)

I have a data store of banks and their teller reviews (1-5 int field). A teller can optionally have a Customer Choice Winner (CCW) field. My requirements are as below to choose at most 5 tellers for a given bank to display to the user:

  1. If a teller is a CCW, choose it. If multiple tellers have CCW, use the teller reviews to break ties
  2. When there are no CCW, choose the teller with the greatest 4 rating teller review.

I have to do the above for 5 banks. The logic I was getting was have a for loop to go over the 5 banks and within each loop, go over all tellers for each bank 5 times (to pick 5 tellers). This seems to me to be really inefficient and unclear. Here is what I mean:

foreach (Bank b : banks) {
    List<Tellers> tellers = b.getTellers();

    foreach (Teller t : tellers) {
        List<Reviews> reviews = t.getReviews();

        ...// get 4 reviews following the above logic.
    }
}

Can anyone help me with a clearer and more efficient way to write this?

Thanks!

Upvotes: 2

Views: 83

Answers (1)

James Wierzba
James Wierzba

Reputation: 17548

The best solution for this is to sort the List<Teller>

You will have to define a compare function for the Teller object by implementing the Comparable interface.

This will let you run your algorithm in constant time (O(25) because of 5 tellers for 5 banks, which is really O(1))

At the cost of sorting it the first time, which will be O(nlogn)

Example code for your Teller class:

public class Teller implements Comparable
{

    private boolean ccw = false;
    private int rating;

    public boolean hasCCW() { return ccw; }
    public int getRating() { return rating; }

    //... your code

    @Override
    public int compareTo(Object o) 
    {
        Teller that = (Teller)o;
        //if this has ccw and that doesn't, this < that
        if(this.hasCCW() && !that.hasCCW()) 
        {
            return -1;
        }
        //else if this does not have ccw, and that does, this > that
        else if(!this.hasCCW() && that.hasCCW())
        {
            return 1;
        }
        //else they both have ccw, so compare ratings
        else
        {
            return Integer.compare(this.getRating(), that.getRating());
        }
    }

}

Then, your algorithm will just need to grab the first 5 tellers for each bank.

example:

//Sort the tellers:
//ideally, call this only once, and insert future Tellers in order (to maintain ordering)
for(Bank bank : banks)
{
    for(List<Teller> tellers : bank.getTellers())
    {
        Collections.sort(tellers);
    }
}

//then, to get your top tellers:
for(Bank bank : banks)
{
    Teller bestTeller = bank.getTeller(0);
    Teller secondBestTeller = bank.getTeller(1);
    //...
}

Upvotes: 1

Related Questions