Goldman Sachs Interview Question
Developer Program Engineersusing a map would make the operations O(1) or constant time as it uses the Hashtable implementations , and a set uses a red black tree which is having a time complexity of O(Logn) .
Taken from wikipedia:
SET:
Under the hood, the sorted set is implemented using a balanced binary search tree, making them specially efficient for operations that insert or remove elements from the container, as well as those that test to see whether a particular value exists in it. Due to the tree implementation, these operations are performed in logarithmic time - O(logn), unlike other C++ containers like lists and vectors, where similar operations would take linear time - O(n). The latter implies that each element in the container would have to be examined, whereas the former would halve the space needing to be examined at each step. A set is not limited in its size, and expands or contracts as elements are added to or removed from the collection.
There are 2 types of sets available in the C++ STL - Sets and Multisets. In the former, every element is unique and insertions of values that are already present in the container are ignored. In the multiset container however, multiple occurrences of the same value are allowed.
MAP:
The class template std::map<Key, Data, Compare, Alloc> is a standard C++ container. It is a sorted associative array of unique keys and associated data.[1] The types of key and data may differ, and the elements of the map are internally sorted from lowest to highest key value. Since each key value is unique, if an object is inserted with an already existing key, the object already present in the map does not change.[2] A variation on the map, called the multimap, allows duplicate keys.
Iterators and references are not invalidated by insert and erase operations, except for iterators and references to erased elements. The usual implementation is a self-balancing binary search tree (but any other data structure that respects the complexity constraints can be used, like a skip list).
not sure about a set but map is implemented using a redblack tree. complexity for all operations is O(logn)
- blueskin.neo December 03, 2010