Test Assignment: C++ Programming
Test
Thank you for participating in our recruiting test. This assignment focuses on implementing a
data structure in C++. Below, you'll find task descriptions and guidelines to help you prepare and
perform well.
Task Description
The objective is to implement a member function called assign for the data structure interval_map<K,
V> . This data structure associates keys of type K with values of type V and is optimized for
situations where intervals of consecutive keys share the same value.
Provided Information
Base Structure: The class interval_map<K, V> is built on top of std::map .
Canonical Representation Requirement: Consecutive entries should not have the same
value, and the first entry should differ from the value in m_valBegin .
Initial State: The entire range of K is associated with an initial value passed to the
constructor.
Example Representation
Let’s consider an instance M of interval_map<int, char> with:
M.m_valBegin == 'A'
M.m_map == { (1, 'B'), (3, 'A') }
The mapping would then be:
...
-2 -> 'A'
-1 -> 'A'
0 -> 'A'
1 -> 'B'
2 -> 'B'
3 -> 'A'
4 -> 'A'
5 -> 'A'
...
Test Assignment: C++ Programming Test 1
Key Type Requirements ( K )
Supports copy and move construction, as well as copy and move assignment.
Supports comparison via operator< .
Does not support equality comparison or arithmetic operations.
Value Type Requirements ( V )
Supports copy and move construction, as well as copy and move assignment.
Supports equality comparison via operator== .
Does not support other operations.
Implementation Details
The assign() member function must:
1. Assign the given value val to the interval [keyBegin, keyEnd) . This interval includes keyBegin but
excludes keyEnd .
2. Overwrite any previous values in the specified interval.
3. Handle edge cases where !(keyBegin < keyEnd) by doing nothing.
To maintain performance and adhere to best practices, consider the following guidelines:
Efficiency Requirements:
Only one operation may have amortized time complexity of O(log N).
The remaining operations should have amortized time complexity of O(1).
Memory and Copy Efficiency:
Minimize copy constructions and assignments of types K and V .
Use std::forward where appropriate.
Validity of Iterators:
Avoid dereferencing end iterators.
Canonical Representation:
Ensure consecutive map entries do not have the same value.
Test Assignment: C++ Programming Test 2
Template Code
#include <map>
template<typename K, typename V>
class interval_map {
friend void IntervalMapTest();
V m_valBegin;
std::map<K,V> m_map;
public:
// constructor associates whole range of K with val
template<typename V_forward>
interval_map(V_forward&& val)
: m_valBegin(std::forward<V_forward>(val))
{}
// Assign value val to interval [keyBegin, keyEnd).
// Overwrite previous values in this interval.
// Conforming to the C++ Standard Library conventions, the interval
// includes keyBegin, but excludes keyEnd.
// If !( keyBegin < keyEnd ), this designates an empty interval,
// and assign must do nothing.
template<typename V_forward>
void assign( K const& keyBegin, K const& keyEnd, V_forward&& val )
requires (std::is_same<std::remove_cvref_t<V_forward>, V>::value)
{
// Implement the assign logic here
}
// look-up of the value associated with key
V const& operator[]( K const& key ) const {
auto it=m_map.upper_bound(key);
if(it==m_map.begin()) {
return m_valBegin;
} else {
return (--it)->second;
}
}
};
Test Assignment: C++ Programming Test 3
Evaluation Criteria
1. Type Requirements:
Adherence to the given specifications for K and V .
2. Correctness:
Functional behavior of the interval_map , including iterator validity.
Edge case handling.
3. Canonicity:
Proper representation in m_map without redundant entries.
4. Efficiency:
Amortized time complexity constraints.
Optimal number of comparisons and assignments.
Tips for Testing
Implement randomized tests to identify edge cases.
Validate iterator usage to prevent illegal dereferencing.
Ensure proper value mapping for edge intervals.
Use a checking STL implementation for debugging (e.g., Visual C++ or GCC).
By following these guidelines and constraints, you will be better prepared to produce a high-
quality implementation that meets the test requirements.
Good luck!
Test Assignment: C++ Programming Test 4
