CareerCup

How about this -
USe a trie-like data structure storing all valid user names. Populate it using one pass over the first list, keep marking the words present.
Next, pass over the second list and keep looking up the trie for it.
Pick the ones already present in trie and report them.

Two approaches
1. Build Hash with smaller file and check for match in other Time O(n) Space O(n)
2. Sort both files (nlogn) and now find match with 2 fingered approach O(n) total complexity O(nlogn) + O(n) = O(nlogn)

What I would do, since clearly I cannot load both files in memory (probably not even each alone). I would still sort them (External merge sort, check wikipedia for that). Then I will load as much from each file as I can put into memory, for example 512kb from each file, and perform a merge sort where I only keep the last element and the list where it came from, if the came from different lists, I add it to my result set. When a chunk is over, I load the next chunk.

How about using Bloom Filters. It can help in finding whether the element is present or not.
Though, it might lead to false positives(showing element is present though it is not). In that case, go for other approaches like hash functions on smaller files.

You question about hashing that you just posted after this question was posted suggestion you already figured out what to do here.

This is a sort of open ended question. It is crucial to ask more details from the interviewer.

- Are we using a single core or a cluster of cpus?
- How much memory is available? Do the files fit in memory?
- Can we create auxiliary files?

Assuming 1 cpu core, a possible approach could be partition the usernames into buckets. Each bucket contains a portion of the valid usernames.

Assume for simplicity that the alphabet used in the usernames are only letters A-Z. One possible partition would be to split all usernames starting with A to one file, B to a another file, etc. Then, each file will have a fraction of the billion usernames and we can intersect the usernames from the log files.

The above approach is very simple and won't partition the usernames into the buckets uniformly. We should discuss it further with the interviewer. We could try to check the usual distribution of the usernames over the alphabet and partition (start with A is probably more likely than starting with Q). Of course we don't need to split just by the starting character, but the first 2, 3, etc chars.

Note: don't assume the usernames use the latin charset. Ask first if other chars like Chinese or Japanese are used (unicode in general).

Sorting looks to me over kill, rather i would create index of string hashcode and save info like {hashcode, stringFileLocationArray} in a avl tree. O(n)

Once this structure is in place then scan second file pick each user name lookup hash code in index (nlog n) if hash code matches then compare with actual string in file.

you can use chche of strings read from file some kind of (LRU etc) to speed up matching. You can also do some IO optimization by adding all matched (hash code) in a queue and order items in queue by order of file location.

I think a possible approach would be sorting both log files which will take O(nlogn) and, after that, read both files by chunks simply comparing the usernames and skipping when the username in one list is lower than the other one. Some kind of merge search...

First and foremost thing is to reduce the search Space. Every Name has vowels so basically use that property and generate words and reduce search space in both files and search only in that to determine the occurrence.

We can then hash them or sort them which ever way needed.

Use trie (dictionary) is better.

let the length of user name is O(k).

First, load the first file, and build a dictionary. O(kn) time and O(kn) space.

Second, load the second file, for each user, search whether it exists in the dictionary. If it exists, output it. O(kn) time.

In general case, k is a small constant. The algorithm can achieve O(n) time and use O(n) space.

how about start hashing both the files simulataneosly, take one username from one file, hashmap it (bucket hashing),, then take one user name from second file do the same. Do this till for all 2 billions usernames. Once done, Space O(2n) = O(n).
Pick any user name and you can check with O(1) if it has a duplicate. (worst case O(m) m being duplication constant or depends on the hashing function.
do this for all 2N records, which would be O(2n) = O(n)

I believe that the only way to solve that efficiently is to use famous B-Tree data structure. Building the tree will take O(N*Log(N)) but it shall be done only once. You can keep only some parts of the tree called pages in memory and the rest of them you can store on the file system so no problem with huge number of usernames and you wil still have O(Log N) to check if username already exists in the tree.

To avoid space complexity,
1) simply compare first string from File1 with all strings in File2.
2) Repeat the same for all strings in File1.

Time complexity: n^2 Space complexity: 0