Friday, January 7, 2011

An old interview question: counting in a list

You have a list of names which is so large that you cannot fit in memory and it is too expensive to sort. Count the number of duplicates in optimal space and time.
Pubblicato da a
Reazioni: 

1 comment:

  1. Two solutions:
    1) If the resulting dictionary can fit in memory we can use a std::map
    std::map
    2) If the resulting dictionary cannot fit in memory we can use a B+tree

    ReplyDelete

Subscribe to: Post Comments (Atom)