What data structure - Set, List or Dictionary - in Python will you use to store 10 million integers? Query operations consist of finding the number of times a number appears in the given set. What will be the worst case time and space complexity in all the cases?
This is a sample interview question. What would be the most appropriate answer?
The key to this question is the line that states:
"finding the number of times a number appears in a given set"
The set data structure is going to be incapable of keeping a count of how many times a number appears within the total dataset, and a List is going to be extremely costly to iterate over. Which leaves a dictionary as the only viable option.
Breaking down the options:
Set: A set automatically de-dupes values added to the set that already exist. So it would be impossible to query the frequency that a number appeared within the stored dataset using a set, because the answer for all numbers stored will be 1.
List: A list could be iterated over to determine the frequency of a given number within the list. However this is going to be O(n) operation, and for 10 million integers will not be efficient.
Dictionary: A dictionary allows you to store a key-value pair. In this case, you would store the number to be searched as the key, and the count of how many times it has been stored as the associated value. Because of the way that dictionaries will hash keys into distinct buckets (There can be collisions, but let's assume a non-colliding theoretical dictionary for now), the lookup time for a given key approaches O(1). Calculating the count however, is going to slow down a Dictionary; it will take O(n) time complexity to calculate the counts for all keys (because each key will have to be hit at least once in order to append it's count to the running count stored in the value).
Adding to the answer of @John Stark From the python wiki, the time complexity for querying in a set is O(n). This is because it uses a hash to get the value, but with (a LOT) of bad luck, you might have a hash collision for every key. In the vast majority of cases, however, you won't have collision. Also, because here the keys are integers, you reduce the hash collisions, if the range of integers is limited. In python 2 with the type int, you can't have collisions.
Add every number as number:1 in dict if number not in dict, else add 1 to Val of that Key. Then search for specific number as Key, the Val will be the number of times that appears.
