Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Write psuedocode to determine the number of pairs of values in an input file that are equal. If your first try is quadratic, think again and develop a linearithmic solution.

I found this question in a textbook and I'm not sure how to write this algorithm. My guess at first was to write it along the formula nC2 = (n(n+1))/2. Any help is appreciated.

share|improve this question
2  
Hint: what changes if you sort the values before? What is the running time order for sorting? Can you even do better utilizing a dictionary? –  Doc Brown Sep 26 '12 at 6:21
    
Its a confusingly worded question, is it asking for you to spot when a value is in a file twice, or is it asking you to spot pairs whose value match (so spotting if file has 109 and 2, but also 106 and 5)? –  colinjack Jul 23 '13 at 14:36

1 Answer 1

I don't want to give you the code but some hints. The first thing to pay attention is that the exercise is asking for a linearithmic solutions. This means that you algorithm may consume N log (N) time to execute where N is the number of entries (values in the file in your case).

So the basic structure of the algorithm needed seems to be one loop through all the entries and one binary search inside the loop. To do a binary search you need an ordered entry, so order it. At the end you algorithm may look something like:

  1. Order the file
  2. Loop through the file
  3. Binary read the file during the loop
  4. Check the current value in the loop and the result of the binary search
share|improve this answer

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.