-2

I have two lists like this (list of Map<String,Object>):

list1 : [("name","Tom"),("age","35"),("score",99.1)], [("name","Mary"),("age","20"),("score",62.2)]
list1 : [("name","Mary"),("age","20"),("score",62.6)], [("name","Tom"),("age","35"),("score",98.9)]

I want to verify if two lists are the same. But when the "score" is less than 1, I should see it as the same. For example, 99.1 and 98.9 should be regarded as the same score.

Two lists are unordered.

How could I achieve this in O(n) ?

hawarden_
  • 1,904
  • 5
  • 28
  • 48
  • A very basic approach is to loop though one of the maps (entryset) and do a check on map2 contains on the key https://stackoverflow.com/questions/46898/how-do-i-efficiently-iterate-over-each-entry-in-a-java-map – Kenneth Clark Jan 13 '21 at 08:08
  • 1
    @Gurkan İlleez No, hashcode cannot tell if two "score" have an absolute difference less than 1 – hawarden_ Jan 13 '21 at 08:10
  • @Kenneth Clark the difficulty is how to tell which map in list 1 corresponds to which in list 2 ? I can do a brute force but I don't think it's optimal; it will be O(n*n) – hawarden_ Jan 13 '21 at 08:11

2 Answers2

3

How could I achieve this in O(n) ?

Mathematically impossible.

Some notes:

  • Having a Map<String, Object> is non-idiomatic java. Make a class, for example named Person, with this information.
  • Fastest time you can do this as a general principle is O(n logn): Sort both lists (2x O(nlogn)), then go through both lists simultaneously, which you can do strictly increasing, and compare: 2x O(n). 2O(nlogn)+2O(n), which boils down to O(n logn). But sorting these is more convoluted than it needed to be due to having a Map<String, Object> instead of a Person.

An alternate option is to insert all data straight into a self-sorting construct, which would be a TreeMap, for example, using e.g. somebody's Name as the key.

Checking if any two given scores are within a point of each other is trivial: if (Math.abs(scoreA - scoreB) < 1) will do it.

rzwitserloot
  • 85,357
  • 5
  • 51
  • 72
-3

Depends on type of variable used for the scores but essentially the same. If you are using float you should use %.0f or if you are using double, you should use %.0d. I hope that is the case and that it helps.

dhpdude
  • 5
  • 1