2 Replies - 173 Views - Last Post: 06 February 2019 - 12:10 PM Rate Topic: -----

#1 Harakiri   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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   User is online

  • member icon

Reputation: 5678
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#3 Harakiri   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1