3/20/25, 9:54 PM Recruiting test | think-cell
Recruiting test
Test assignment
Thank you for participating in our recruiting test. This will be a C++ programming test!
How to prepare for this test
Task Description
interval_map<K,V> is a data structure that associates keys of type K with values of type
V. It is designed to be used efficiently in situations where intervals of consecutive keys are
associated with the same value. Your task is to implement the assign member function of
this data structure, which is outlined below.
interval_map<K, V> is implemented on top of std::map. For more information on
std::map, you may refer to cppreference.com .
Each key-value pair (k,v) in interval_map<K,V>::m_map means that the value v is
associated with all keys from k (including) to the next key (excluding) in m_map. The
member interval_map<K,V>::m_valBegin holds the value that is associated with all
keys less than the first key in m_map.
Example: Let M be an instance of interval_map<int,char> where
M.m_valBegin=='A',
M.m_map=={ (1,'B'), (3,'A') },
Then M represents the mapping
...
-2 -> 'A'
-1 -> 'A'
0 -> 'A'
1 -> 'B'
2 -> 'B'
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 1/9
3/20/25, 9:54 PM Recruiting test | think-cell
3 -> 'A'
4 -> 'A'
5 -> 'A'
...
The representation in the std::map must be canonical, that is, consecutive map entries
must not contain the same value: ..., (3,'A'), (5,'A'), ... is not allowed. Likewise,
the first entry in m_map must not contain the same value as m_valBegin. Initially, the whole
range of K is associated with a given initial value, passed to the constructor of the
interval_map<K,V> data structure.
Key type K
supports copy and move construction, as well as copy and move assignment,
is less-than comparable via operator<,
does not implement any other operations, in particular no equality comparison or
arithmetic operators.
Value type V
supports copy and move construction, as well as copy and move assignment,
is equality-comparable via operator==,
does not implement any other operations.
First evaluation
#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))
{}
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 2/9
3/20/25, 9:54 PM Recruiting test | think-cell
// Assign value val to interval [keyBegin, keyEnd).
// Overwrite previous values in this interval.
// Conforming to the C++ Standard Library conventions, the inter
// 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
{
// Empty interval check
if (!(keyBegin < keyEnd)) {
return;
}
// Store the forwarded value
V value(std::forward<V_forward>(val));
// Find the position where keyBegin should be inserted
auto itBegin = m_map.lower_bound(keyBegin);
// Determine value before keyBegin
V valBeforeKeyBegin;
if (itBegin == m_map.begin()) {
valBeforeKeyBegin = m_valBegin;
} else {
valBeforeKeyBegin = std::prev(itBegin)->second;
}
// Find the position where keyEnd should be inserted
auto itEnd = m_map.lower_bound(keyEnd);
// Determine value at keyEnd
V valAtKeyEnd;
if (itEnd == m_map.begin()) {
valAtKeyEnd = m_valBegin;
} else {
auto prevItEnd = std::prev(itEnd);
valAtKeyEnd = prevItEnd->second;
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 3/9
3/20/25, 9:54 PM Recruiting test | think-cell
// Erase all elements in the range [keyBegin, keyEnd)
m_map.erase(itBegin, itEnd);
// Insert the interval with the new value if it differs from the pre
if (!(valBeforeKeyBegin == value)) {
m_map.insert_or_assign(keyBegin, value);
}
// Insert the end point with the original value at that position
// if it differs from the new value
if (!(value == valAtKeyEnd)) {
m_map.insert_or_assign(keyEnd, valAtKeyEnd);
}
// Clean up entries where value equals m_valBegin at the start
while (!m_map.empty() && m_map.begin()->second == m_valBegin) {
m_map.erase(m_map.begin());
}
// Clean up consecutive entries with the same value
if (!m_map.empty()) {
auto it = m_map.begin();
while (it != m_map.end()) {
auto next = std::next(it);
if (next != m_map.end() && it->second == next->second) {
m_map.erase(next);
} else {
++it;
}
}
}
// 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()) {
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 4/9
3/20/25, 9:54 PM Recruiting test | think-cell
return m_valBegin;
} else {
return (--it)->second;
}
}
};
// Many solutions we receive are incorrect. Consider using a randomized
// to discover the cases that your implementation does not handle correc
// We recommend to implement a test function that tests the functionalit
// the interval_map, for example using a map of int intervals to char.
Unfortunately, this program failed to meet the criterion marked in red:
Type requirements: You must adhere to the specification of the key and value type
given above.
? Correctness (not checked): Your program should produce a working interval_map
with the behavior described above. In particular, pay attention to the validity of
iterators. It is illegal to dereference end iterators. Consider using a checking STL
implementation, such as the one shipped with Visual C++ or GCC.
? Canonicity (not checked): The representation in m_map must be canonical.
? Running time (not checked): Imagine your implementation is part of a library and
should therefore be big-O optimal:
The assign function should have amortized time complexity of O(log N), where N is
the number of elements in m_map.
Minimize the number of copy-constructions and copy-assignments performed on K
and V. Make use of std::forward where applicable.
Only one operation may have amortized time complexity of O(log N). The rest must
have amortized time complexity of O(1).
Given the constraints above, avoid comparing K and V more often than necessary
because you don't know how fast these operations are.
Otherwise, favor simplicity over minor speed improvements.
Second chance
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 5/9
3/20/25, 9:54 PM Recruiting test | think-cell
Unfortunately, your first try failed. We'll give you a final chance to fix your code:
You are given the following source 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 inter
// 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
{
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 6/9
3/20/25, 9:54 PM Recruiting test | think-cell
g ) {
m_map.erase(m_map.begin());
}
// Remove consecutive entries with the same value
if (!m_map.empty()) {
auto it = m_map.begin();
auto next = it;
++next;
while (next != m_map.end()) {
if (it->second == next->second) {
// Save the key to erase and advance the
iterator
next = m_map.erase(next);
} else {
it = next;
++next;
}
}
}
// 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;
}
}
};
// Many solutions we receive are incorrect. Consider using a randomized
// to discover the cases that your implementation does not handle correc
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 7/9
3/20/25, 9:54 PM Recruiting test | think-cell
// We recommend to implement a test function that tests the functionalit
// the interval_map, for example using a map of int intervals to char.
You can download this source code here: Download
Your task is to implement the function assign. Your implementation is graded according
to the following criteria, in this order:
Type requirements: You must adhere to the specification of the key and value type
given above.
Correctness: Your program should produce a working interval_map with the
behavior described above. In particular, pay attention to the validity of iterators. It is
illegal to dereference end iterators. Consider using a checking STL implementation,
such as the one shipped with Visual C++ or GCC.
Canonicity: The representation in m_map must be canonical.
Running time: Imagine your implementation is part of a library and should therefore
be big-O optimal:
The assign function should have amortized time complexity of O(log N), where N is
the number of elements in m_map.
Minimize the number of copy-constructions and copy-assignments performed on K
and V. Make use of std::forward where applicable.
Only one operation may have amortized time complexity of O(log N). The rest must
have amortized time complexity of O(1).
Given the constraints above, avoid comparing K and V more often than necessary
because you don't know how fast these operations are.
Otherwise, favor simplicity over minor speed improvements.
Don't rush through the test. We wouldn't give you this assignment if it was trivial.
When you're done, please complete the form and click Compile . You can improve and
compile solutions as often as you like.
Compile
Looks good! Your program compiles without errors.
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 8/9
3/20/25, 9:54 PM Recruiting test | think-cell
Your next step is to make sure that your program is correct and meets all the requirements
listed above. You may want to review these criteria and test against them. If you find any
errors or weaknesses in your program, you can edit your solution above and recompile as
often as you like.
You should be very sure that you fixed all issues. This will be your final submission, so you
will not be able to fix your code afterwards.
We'll evaluate your program using our automated tests and provide immediate feedback.
Once you submit a correct solution, we'll invite you to an online interview with our
technical team.
If you're sure that your program is correct and ready for submission, please click
Submit for final evaluation
https://server.think-cell.com/portal/en/recruitingtest.srf?sid=Zca36rNxKwwi8zBZNk2RAcF8Oe9s8FBp30xjmEOQaWQeyoBOa190Hs4qqLOjtiiG#… 9/9
