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.

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