0

I have two lists with two different type of objects each, List list1 and List list2. The object at position i in list1 is related with that at position i in list2.

I have to answer queries of the type, given an object A return the object B at the same position in list2, and viceversa, given an object B return the object A at the same position in list1.

The trivial solution would be an O(n) search for each query. I'm looking for possible solutions to improve it. So far, what I have are two dictionaries, one Dictionary<A, B> dicAtoB and Dictionary<B, A> dicBtoA where I inserted all the elements from the lists in each of them. I'm asking for some other solutions as in mine the elements are inserted twice, and I have to use this two extra dictionaries and...I don't know what else but I just don't like mine to much.

Improve this question
5
  • Does it TLE? What's the actual problem? I don't think there is a better way unless the objects have some special attribute. Commented Jan 19, 2018 at 7:30
  • Related: stackoverflow.com/questions/32761880/… Commented Jan 19, 2018 at 7:32
  • Nop, the speed is ok, but beyond that I also have the concern about good programming practices for the specific case. Thanks Commented Jan 19, 2018 at 7:41
  • What error are you getting here and can you post an example input and desired output for it ? Thank you Commented Jan 19, 2018 at 7:57
  • Don't try to solve a simple scenario duplicating data without reason. If your list is non-ordered, you find a value with a linear serch. If it's ordered in a meanigful way (e.g. you can define a predecessor and a successor of a given value in the list) use a binary search. Since the indexed element has a direct correspondance in the second list, you only need the index. No interval tree needed. Commented Jan 19, 2018 at 8:43

1 Answer 1

Reset to default
0

Two suggestions:

  • List is backed by an array, so you could take advantage of random access. Instead of supplying instance of A, supply index i (if possible) and get instance of B in O(1) by invoking bList[i]
  • extend classes A and B to include references to the related object from the other class. It would make your insert and remove operations more complex, but search operation will be O(1), which is a justified tradeoff in case that you are doing a lot of search operations
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.