## Goldman Sachs Interview Question for Developer Program Engineers

Comment hidden because of low score. Click to expand.
0
of 0 vote

not sure about a set but map is implemented using a redblack tree. complexity for all operations is O(logn)

Comment hidden because of low score. Click to expand.
0

Yes, it`s RB tree, in both map and set.

Comment hidden because of low score. Click to expand.
0
of 0 vote

using 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) .

Comment hidden because of low score. Click to expand.
0

wiki: "The usual implementation is a self-balancing binary search tree".
stl_map.h: "/// This turns a red-black tree into a [multi]map. "

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.