think-cell

interval_map.cpp

/*

Task Description
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
*/

#include <map>
#include <limits>
#include <ctime>

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 ) {

			if (!(keyBegin < keyEnd)) return;

			std::pair<K,V> beginExtra;
			std::pair<K,V> endExtra;
			bool beginHasExtra = false;
			bool endHasExtra = false;

			typename std::map<K,V>::const_iterator itBegin;
			itBegin = m_map.lower_bound(keyBegin);
			if ( itBegin!=m_map.end() && keyBegin < itBegin->first ) {
				if (itBegin != m_map.begin()) {
					beginHasExtra = true;
					--itBegin;
					beginExtra = std::make_pair(itBegin->first, itBegin->second);
				}
				// openRange for erase is prevIterator
				// insert (prevIterator->first, prevIterator->second) as well!
			}

			typename std::map<K,V>::const_iterator itEnd;
			itEnd = m_map.lower_bound(keyEnd);
			if ( itEnd!=m_map.end() && keyEnd < itEnd->first ) {
				endHasExtra = true;
				typename std::map<K,V>::const_iterator extraIt = itEnd;
				--extraIt;
				endExtra = std::make_pair(keyEnd, extraIt->second);
				// closeRange for erase is this iterator
				// insert (keyEnd, prevIterator->second) as well!
			}

			// 4 canonical conflicts:
			//	 beginExtra w/ mid
			//	 before-mid w/ mid (beginHasExtra==false)
			//	 mid w/ endExtra
			//	 mid w/ after-mid (endHasExtra==false)

			bool insertMid = true;
			if (beginHasExtra) {
				if (beginExtra.second == val)
					insertMid = false;
			} else {
				if (itBegin != m_map.begin()) {
					typename std::map<K,V>::const_iterator beforeMid = itBegin;
					--beforeMid;
					if (beforeMid->second == val)
						insertMid = false;
				}
			}


			if (endHasExtra) {
				if ( (insertMid && endExtra.second == val) || (!insertMid && endExtra.second == beginExtra.second) )
					endHasExtra = false;
			} else {
				if ( (insertMid && itEnd!=m_map.end() && itEnd->second == val) || (!insertMid && itEnd!=m_map.end() && itEnd->second == beginExtra.second) )
					itEnd = m_map.erase(itEnd);
			}

			itBegin = m_map.erase(itBegin, itEnd);
			if (beginHasExtra)
				itBegin = m_map.insert(itBegin, beginExtra);
			if (insertMid)
				itBegin = m_map.insert(itBegin, std::make_pair(keyBegin, val));
			if (endHasExtra)
									m_map.insert(itBegin, endExtra);

// INSERT YOUR SOLUTION HERE
    }

    // look-up of the value associated with key
    V const& operator[]( K const& key ) const {
        return ( --m_map.upper_bound(key) )->second;
    }
};

If the new range intersects with the old one, should it overwrite the old range within the new one or should it ignore it?

for example first assign is -300:B 300:A (so all keys between -300 and 299 are B.
second assign fo example -500:F 500:S - what it this?
variant 1 - it just owerwrite previous -300:300 range with new bigger range - so in finish only one range will be in map
or
variant 2- it write ranges only -500 till -300 and 300 to 500 with new data (but keep old range -300:B 300:A untouched) - so in finish 3 ranges will be in map

Please answer on this!

Today, I attempted the test and unfortunately could not clear it.
I failed at check 1 "Type requirements: You must adhere to the specification of the key and value type given above."
I follow the given constraint in the problem that only move and copy operation/constructor allowed and only < or == . No other operation I used.
Also, I used custom type to explicitly delete other operations/constructors. In addition to this, I checked against the static assert on "std::is_default_constructible::value" and both key and value types passed.

I would like to know from my implementation what was required apart from what I have written.
Could you please share some insights on it? Or point me to a resource where I can understand this in more depth about the concept?
I am attaching my solution Please review it once.
I am looking forward to hearing from you.

`
template
void assign(K const& keyBegin, K const& keyEnd, V_forward&& val)
requires (std::is_same<std::remove_cvref_t<V_forward>, V>::value)
{
// invalid case
if (!(keyBegin < keyEnd))
{
return;
}

	//limit is whole map
	const auto& k_low = std::numeric_limits<K>::lowest();
	const auto& k_max = std::numeric_limits<K>::max();
	if (!(k_low < keyBegin) && !(keyBegin < k_low) &&
		!(k_max < keyEnd) && !(keyEnd < k_max))
	{
		m_map.clear();
		m_valBegin = std::forward<V_forward>(val);

		return;
	}

	//first assignment
	if (m_map.empty())
	{
		if (val == m_valBegin)
			return;

		(void) m_map.insert_or_assign(K(keyBegin), std::forward<V_forward>(val));
		(void) m_map.insert_or_assign(K(keyEnd), std::forward<V_forward>(m_valBegin));

		return;
	}

	using itr_t = std::map<K, V>::iterator;
	const auto& [key_begin_bounds_l, key_begin_bounds_u]  = m_map.equal_range(keyBegin);
	const auto& [key_end_bounds_l, key_end_bounds_u] = m_map.equal_range(keyEnd);

	bool is_key_begin_presend = key_begin_bounds_l != key_begin_bounds_u;
	bool is_key_end_presend = key_end_bounds_l != key_end_bounds_u;

	
	itr_t new_key_begin = key_begin_bounds_l;
	itr_t new_key_end = key_end_bounds_l;

	//If key is present then lower bound is where it found


	//Check if previous node value is same as current val
	bool is_pre_key_begin_val_same = false;
	if (key_begin_bounds_l != m_map.begin())
	{
		// if previous node's value same as current range value then to avoid duplication of val, skip addition of keyBegin
		auto it = key_begin_bounds_l;
		if ((--it)->second == val)
		{
			is_pre_key_begin_val_same = true;
		}
	}

	if (key_end_bounds_u != m_map.end())
	{
		// if next value is end of some range then to avoid duplication of val, skip addition of it
		if (key_end_bounds_u->second == m_valBegin)
		{
			if (is_pre_key_begin_val_same)
				// if it is in same key's range then e
				is_key_end_presend = true;
			else if (is_key_end_presend && key_end_bounds_l->second == val) //means key is being place in existing range
			{
				new_key_end = key_end_bounds_u;
			}
		}
	}

	if (!is_key_begin_presend && key_begin_bounds_l != m_map.begin())
	{
		// if previous node's value same as current range value then to avoid duplication of val, skip addition of keyBegin
		if (is_key_end_presend && is_pre_key_begin_val_same)
			return;
	}

	if (!is_key_end_presend)
	{
		V& last_range_val = m_valBegin;

		auto it = key_end_bounds_u;
		if (it != m_map.begin()) {
			last_range_val = (--it)->second;
		}

		if (!(last_range_val == val))
			// endKey not present in map, insert at end
			new_key_end = m_map.insert_or_assign(key_end_bounds_l, keyEnd, last_range_val);
	}

	if (!is_pre_key_begin_val_same)
	{
		if (!is_key_begin_presend)
		{
			new_key_begin = m_map.insert_or_assign(key_begin_bounds_l, keyBegin, std::forward<V_forward>(val));
			is_key_begin_presend = true;
		}
		else if ((key_begin_bounds_u == m_map.end() && key_begin_bounds_l != m_map.begin()) ||
			!(key_begin_bounds_l->second == val))
		{
			//its last position modify it here
			new (&key_begin_bounds_l->second) V(std::forward<V_forward>(val));
		}
	}
	else
	{
		// if last key present and incase KeyBeing match with existing keyEnd
		is_key_begin_presend = false;
	}

	if (is_key_begin_presend)
		std::advance(new_key_begin, 1);

	m_map.erase(new_key_begin, new_key_end);
	
}

`

I have two solutions for this task. First one passed successfully, due to that i had no chance to check if second solution is also correct. If somebody have a link to online test and wants to check my second solution write me a pm.

i have test link

Send me your direct contacts

Hi, could you check please my code: if (!(keyBegin < keyEnd)) return;

    // Find existing value at keyEnd
    auto itEnd = m_map.upper_bound(keyEnd);
    V valueAfter;
    if (itEnd == m_map.begin()) {
        valueAfter = m_valBegin;
    } else {
        valueAfter = std::prev(itEnd)->second;
    }

    // Find existing value at keyBegin
    auto itBegin = m_map.upper_bound(keyBegin);
    V valueBefore;
    if (itBegin == m_map.begin()) {
        valueBefore = m_valBegin;
    } else {
        valueBefore = std::prev(itBegin)->second;
    }

    // Remove all points in [keyBegin, keyEnd)
    itBegin = m_map.lower_bound(keyBegin);
    itEnd = m_map.lower_bound(keyEnd);
    m_map.erase(itBegin, itEnd);

    // If new value differs from value before keyBegin, add entry
    if (val != valueBefore) {
        m_map.insert_or_assign(keyBegin, std::forward<V_forward>(val));
    }

    // If value after keyEnd differs from new value, add entry
    if (valueAfter != val) {
        m_map[keyEnd] = valueAfter;
    }