Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I've heard this interview question asked a lot and I was hoping to get some opinions on what good answers might be: You have a large file 10+ GB and you want to find out which element occurs the most, what is a good way to do this?

Iterating and keeping track in a map is probably not a good idea since you use a lot of memory, and keeping track as entries come in isn't the greatest option since when this question is posed the file usually already exists.

Other thoughts I had included splitting the file to be iterated through and processed by multiple threads and then have those results combined, but the memory issue for the maps is still there.

share|improve this question
2  
What are the elements of the file? Are they strings? If you take characters for elements, then the map would not have a memory problem. If elements are words, then again I think it would not be a problem. If you have all possible substrings, then you can have problems... –  Nejc Dec 10 '12 at 7:45
1  
If the condition was "an element that appears more than half the total elements" then there was a linear solution. –  st0le Dec 10 '12 at 9:20
    
I believe the elements are usually strings. But I don't see how the map isn't an issue. In the worse case where every element is unique, haven't you just doubled your memory requirement? –  Pat Dec 10 '12 at 15:35
1  
If the Boyer-Moore majority candidate algorithm is applicable, it runs in linear time and is in-place. –  Juho Dec 10 '12 at 23:34
add comment

3 Answers 3

The obvious answer is of course to keep a hash map and store a counter of the occurrence of elements as you move through the file as Nejc already suggested. This is (in terms of time complexity) the optimal solution.

If however, your space requirements are tight you can perform an external sort on the file and then find the longest consecutive run of equal elements. The following should have a constant memory footprint and can be done in $\Theta(n\log{n}).$

share|improve this answer
    
Could you elaborate more on the Huffman encoding approach? I've written a Huffman encoder before but its been awhile, how exactly would you use it in this case? –  Pat Dec 10 '12 at 15:38
    
@Pat Nevermind that part it was too early in the morning and somehow I thought it would makes sense to compress the input. –  Jernej Dec 11 '12 at 18:13
add comment

When you have a really large file and many elements in it, but the most common element is very common -- occurs $> 1/k$ fraction of the time -- you can find it in linear time with space $O(k)$ words ( the constant in the $O()$ notation is very small, basically 2 if you don't count the storage for auxiliary things like hashing). Moreover, this works great with external storage, as the file is processed in sequence one element at a time, and the algorithm never "looks back". One way to do this is via a classical algorithm by Misra and Gries, see these lecture notes. The problem is now known as the heavy hitters problem (the frequent elements being the heavy hitters).

The assumption that the most frequent element appears $> 1/k$ fraction of the time for $k$ a small number may seem strong but it is in a way necessary! I.e. if you will have sequential access to your file (and in case the file is huge random access will be too expensive), any algorithm which always finds the most frequent element in a constant number of passes will use space linear in the number of elements. So if you don't assume something about the input you cannot beat a hash table. The assumption that the most frequent element is very frequent is maybe the most natural way to get around the negative results.

Here is a sketch for $k = 2$, i.e. when there is a single element that occurs more than half the time. This special case is known as the majority vote algorithm and is due to Boyer and Moore. We will keep a single element and a single count. Initialize the count to 1 and store the first element of the file. Then process the file in sequence:

  • if the current element of the file is the same as the stored element, increase the count by one
  • if the current element of the file is different from the stored element, decrease the count by one
  • if the updated count is 0, "kick out" the stored element and store the current element of the file; increase the count to 1
  • proceed to the next element of the file

A little bit of thinking about this procedure will convince you that if there exists a "majority" element, i.e. one that occurs more than half the time, then that element will be the stored element after the whole file is processed.

For general $k$, you keep $k-1$ elements and $k-1$ counts, and you initialize the elements to the first $k$ distinct elements of the file and the counts to the number of times each of these elements appears before you see the $k$-th distinct element. Then you run essentially the same procedure: an element's count is increased each time it is encountered, all element counts are decreased if an element that is not stored is encountered, and when some count is zero, that element is kicked out in favor of the current element of the file. This is the Misra-Gries algorithm.

You can of course use a hash table to index the $k-1$ stored elements. At termination, this algorithm is guaranteed to return any element that occurs more than $1/k$ fraction of the time. This is essentially the best you can do with an algorithm that makes constant number of passes over the file and stores only $O(k)$ words.

One final thing: after you found $k$ candidate "heavy hitters" (i.e. frequent elements), you can make one more pass over the file to count the frequency of each element. This way you can rank the elements between each other and verify whether all of them occur more than $1/k$ fraction of the time (if there are less than $k-1$ such elements, some of the elements returned by the algorithm might be false positives).

share|improve this answer
    
You can not use the Boyer-Moore or the Misra-Gries-Demaine algorithms. The problem as stated is different: you are not searching for a majority element, but for an element whose occurrences are >= of the occurrences of all of the elements. Here is a simple counterexample. Let n be the total number of elements, such that n = 2k + 1. Let the first k elements be 0, the next k elements be 1 and the last element be 2. The Boyer-Moore algorithm will report the last element, 2, as the potential majority candidate. But, for this particular instance, the output must be either 0 or 1. –  Massimo Cafaro Dec 11 '12 at 19:08
    
@MassimoCafaro i cannot parse the phrase "whose occurrences...the elements". anyways, it is well known that finding the most frequent element in $O(1)$ passes required $\Omega(n)$ memory! so if you want small memory footprtint, you need to make an additional assumption, the heavy hitter assumption being the most natural one to me. –  Sasho Nikolov Dec 12 '12 at 0:02
    
I have just pointed out that if you make a wrong assumption, you may get wrong results. What is better, a small memory footprint and a potentially incorrect result or the correct result even though it costs you some more memory ? If I had to choose a potentially incorrect result, I would go for a randomized algorithm rather than for Boyer-Moore assuming something I do not know it is actually true. –  Massimo Cafaro Dec 12 '12 at 6:45
    
@MassimoCafaro that is not a tradeoff you need to take. as i pointed out a single pass over the file easily verifies if the assumption is satisfied! –  Sasho Nikolov Dec 12 '12 at 16:48
    
@MassimoCafaro and this is only the trivial solution! the assumption can be verified with high probability with a CM sketch with no additional passes. –  Sasho Nikolov Dec 12 '12 at 16:57
show 1 more comment

If the most common element is more common than the next common element by a substantial margin, and the number of different elements is small compared to the file size, you can randomly sample a couple of elements and return the most common element in your sample.

share|improve this answer
    
Moreover, if there are a small number of elements occurring many times, you can find them by sampling, and then count only these elements exactly. –  Max Dec 10 '12 at 12:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.