CPP Practice Questions

std::nth_element is a partial sorting algorithm that rearranges elements in a range such that the element at the n-th position is the element that would be in that position in a fully sorted sequence. All of the elements before this n-th position are less than or equal to the elements after the n-th position. It has an average linear time complexity, making it much more efficient than a full sort (std::sort or std::stable_sort) for finding medians or other selection tasks.

The code configures the std::cout stream with three manipulators:

1. std::setw(8): Sets the field width for the next output operation to 8 characters.
2. std::setfill('*'): Sets the character used for padding to '*'.
3. std::left: Sets the alignment to left-justify the output within the field.

The string "A42" has 3 characters. It will be placed in an 8-character field. Because of std::left, it is aligned to the left, and the remaining 5 characters are padded with the fill character '*' on the right. The final output is therefore |A42*****|.

std::bind2nd(std::greater (), 10) (deprecated in C++11, removed in C++17) builds a unary predicate returning x > 10. The most concise, idiomatic lambda replacement is [](int x){ return x > 10; }. Wrapping std::greater () inside a lambda is equivalent but needlessly verbose, the std::bind(std::greater (), std::placeholders::_1, 10) form works but is not a lambda, and a lambda with a defaulted second parameter is not the intended unary predicate (default arguments on lambdas are allowed since C++14 but obscure the intent).

The undo functionality is a classic example of a Last-In, First-Out (LIFO) data structure, which is perfectly modeled by a stack. The std::stack container adapter provides the required push and pop operations, which map directly to adding a state and performing an undo. By default, std::stack uses std::deque as its underlying container. std::deque is an excellent choice here because it provides amortized constant-time push and pop operations at the back (which std::stack uses), satisfying the performance requirement. While a raw std::deque could be used, std::stack more clearly expresses the LIFO intent of the design.

std::map with the default comparator needs only two things from the key type: (1) the map must be able to store its own copy of the key in each node, so the key must be copy-constructible (or at least move-constructible, since C++11, if keys are always moved/emplaced in); (2) because the default comparator is std::less , which calls operator<, the class must provide an accessible operator< that forms a strict weak ordering. A default constructor, operator== (key equivalence is !(a<b) && !(b<a)), and a virtual destructor are not required.

std::map with the default comparator needs only two things from the key type: (1) the map must be able to store its own copy of the key in each node, so the key must be copy-constructible (or at least move-constructible, since C++11, if keys are always moved/emplaced in); (2) because the default comparator is std::less , which calls operator<, the class must provide an accessible operator< that forms a strict weak ordering. A default constructor, operator== (key equivalence is !(a<b) && !(b<a)), and a virtual destructor are not required.

The key requirement is to preserve the original insertion order for entries with identical timestamps. The std::stable_sort algorithm is specifically designed for this purpose. It guarantees that the relative order of equivalent elements remains unchanged after sorting. std::sort does not provide this guarantee and may reorder elements with equal keys, which would violate the forensic analysis requirement. The other options are incorrect because std::partition only groups elements based on a predicate without fully sorting them, and std::sort on its own is insufficient.

std::deque provides constant-time insertion and removal at both the front and the back (push_front/pop_front/push_back/pop_back) and constant-time random access via operator[]/at(), meeting every requirement. std::vector has O(1) random access and amortized O(1) back operations, but inserting or erasing at the front shifts every element (O(n)). std::list and std::forward_list offer no index access, and std::stack exposes only one end and no random access.

std::remove_if (and std::remove) cannot alter the size of the container because it only has access to iterators, not the container object itself. It works by moving all elements that do not match the removal criteria to the front of the range and returns an iterator pointing one past the last element that was kept. The elements from this new logical end to the container's actual end are left in a valid but unspecified state. The correct way to physically remove the elements is to call the container's erase method with the iterator range returned by remove_if, a pattern known as the 'erase-remove idiom'.

std::map is an ordered associative container, typically implemented as a red-black tree. To maintain order and determine the correct position for each key, it needs a way to compare two keys. By default, it uses std::less , which in turn calls operator< on the key objects. Therefore, the UserSession struct must provide a public operator< that establishes a strict weak ordering among its instances. Alternatively, a custom comparator function object could be provided as a template argument to the map, but the most common solution is to overload operator<.

This approach is the most efficient because it leverages the fact that the input vectors are already sorted. std::merge, std::set_intersection, and std::set_difference are all linear time O(N+M) algorithms when operating on sorted ranges. std::merge efficiently creates the consolidated list. std::set_intersection produces the common trades, and std::set_difference produces the trades in the first range but not the second. Any approach involving re-sorting (like concatenation followed by std::sort) would be less efficient, with a complexity of O((N+M)log(N+M)).