Searching for a matching items in between two sets with "complex in" condition

user_7737304 0
Viewed 88

Lets say I have two sets:

set1 = set(("a", "b", 5), ("a", "c", 3))
set2 = set(("a", "b", 3), ("a", "b", 7))

Each item has 3 values:

  1. first index (first part of the key) e.g. "a"
  2. second index (second part of the key) e.g. "b"
  3. third index (timestamp last part of the key) e.g 5

I want to search for all of the elements of set 1, that have the corresponding item in set2, where the corresponding item is any item that has the same value at both the first and second index, but the value of the timestamp of the matching item from the set2 must be lower than the timestamp of the item from the set1.

From the example the matching item would be:

  1. ("a", "b", 5) ("a", "b", 3) timestamp of 3 < 5
  2. āœ“ ("a", "b", 5) ("a", "b", 7)
  3. ("a", "c", 3) ("a", "b", 3) "c" != "b"
  4. ("a", "c", 3) ("a", "b", 7) "c" != "b"

Now the problem is I need to search for the items in set2 in n.log(n) time. That is why I am trying to keep the values in the set. If I was looking for the items without the timestamp:

set1 = set(("a", "b"), ("a", "c"))
set2 = set(("a", "b"), ("a", "b"))

I could do:

for item from set1:
  if item in set2:
    print("Found matching item")

But with the timestamp, I can't figure out how to implement this without two for loops.

set time-complexity python
2 Answers

You can create a dictionary from set2 where the key is the first two parts of the tuple, and the value is a list of all the timestamps. Then you can find the matching key and test if the timestamp in set1 is lower than any of them.

d = {}
for item in set2:
    d.setdefault(item[0:2], []).append(item[2])

for item in set1:
    if any(item[2] > x for x in set2.get(item[0:2], [])):
        print("Found match")
user_14918950

Here's an O(n) solution with O(n) additional space to store the dict2 -

set1 = {("a", "b", 5), ("a", "c", 3)}
set2 = {("a", "b", 3), ("a", "b", 7)}

dict2 = {}
for item in set2:
    dict2[item[:2]] = max(dict2.get(item[:2], float('-inf')), item[2])

for item in set1:
    if dict2.get(item[0:2], float('-inf')) > item[2]:
        print("Found match")
        print("Match -", item, item[0:2] + (dict2.get(item[0:2]),))

outputs -

Found match
Match - ('a', 'b', 5) ('a', 'b', 7)

We create a new dict2 which stores the two keys and the max timestamp seen in the set2, and then we loop through items in set1 to see if for the same key if the max timestamp is larger than the timestamp in set1 for the same key.

user_86770710
Related