Pairs of strings in reverse order in a list of more than million strings?

Question

Recently asked during some interview that "How to find reverse of all strings if exists in a list of more than million strings?

For E.g. str[1] = "abc", I need to check for "cba" exactly, no anagrams.

Method 1. Store all the strings in a hashset, start traversing from the first string and check for the reversed form exists in Hashset. if yes, then pair else move to next element.

Can you suggest any method if memory is the constraint?

Answer 1

If allowed, you could in-place sort the strings so when you look up the reverse of a string you can do a binary search.

Answer 2

You can use a Bloom Filter which will tell you if a string already exists within a hash table like structure, but each bucket is only 0 or 1 so very little space is used.

Exactly 1 000 000 bits == 125 KB