# Do you know how to solve this? (ThinkCell interview task)

Page 1 of 1

## 2 Replies - 173 Views - Last Post: 06 February 2019 - 12:10 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=414799&amp;s=71cabdee56f2e242f153169bb6f184cf&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Harakiri

Reputation: 0
• Posts: 2
• Joined: 06-February 19

# Do you know how to solve this? (ThinkCell interview task)

Posted 06 February 2019 - 12:03 PM

interval_map<K,V> is a data structure that efficiently associates intervals of keys of type K with values of type V. 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. In case you are not entirely sure which functions std::map provides, what they do and which guarantees they provide, we provide an excerpt of the C++ standard here:

Each key-value-pair (k,v) in the std::map means that the value v is associated with the interval from k (including) to the next key (excluding) in the std::map.

Example: the std::map (0,'A'), (3,'B'), (5,'A') represents the mapping

0 -> 'A'
1 -> 'A'
2 -> 'A'
3 -> 'B'
4 -> 'B'
5 -> 'A'
6 -> 'A'
7 -> 'A'
... all the way to numeric_limits<int>::max()
The representation in the std::map must be canonical, that is, consecutive map entries must not have the same value: ..., (0,'A'), (3,'A'), ... is not allowed. 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

besides being copyable and assignable, is less-than comparable via operator<
is bounded below, with the lowest value being std::numeric_limits<K>::lowest()
does not implement any other operations, in particular no equality comparison or arithmetic operators
Value type V

besides being copyable and assignable, is equality-comparable via operator==
does not implement any other operations
You are given the following source code:

```#include <map>
#include <limits>

template<typename K, typename V>
class interval_map {
std::map<K,V> m_map;

public:
// constructor associates whole range of K with val by inserting (K_min, val)
// into the map
interval_map( V const& val) {
m_map.insert(m_map.end(),std::make_pair(std::numeric_limits<K>::lowest(),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.
void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
```

Is This A Good Question/Topic? 0

## Replies To: Do you know how to solve this? (ThinkCell interview task)

### #2 jimblumberg

Reputation: 5678
• Posts: 17,446
• Joined: 25-December 09

## Re: Do you know how to solve this? (ThinkCell interview task)

Posted 06 February 2019 - 12:08 PM

Okay you posted the assignment, including the provided text. But what have you tried?

You also need to ask a question, no one here is going to give you the solution. We will try to help you on your journey but you must first start the journey.

Jim

### #3 Harakiri

Reputation: 0
• Posts: 2
• Joined: 06-February 19

## Re: Do you know how to solve this? (ThinkCell interview task)

Posted 06 February 2019 - 12:10 PM

Ok. I will try to do something on my own and than ask again. Thanks!