Interval map implementation

First write test code:This is to test the type requirements

class Value {char a;public:Value(char _a){ a = _a; }bool operator==(const Value& _val) const;friend ostream& operator<<(ostream& os, const Value& val); // ONLY FOR TESTING, NOT RELATED TO SOLUTION};bool Value::operator==( const Value& _val ) const{return ( a == _val.a ) ;}// operator<< is implemented ONLY FOR TESTING PURPOSEostream& operator<<(ostream& os, const Value& val){os << val.a;return os;}class Key {int a;public:Key(int _a){ a = _a; }Key(){ a = 0; }bool operator<(const Key& _key) const;friend ostream& operator<<(ostream& os, const Key& _key); // ONLY FOR TESTING, NOT RELATED TO SOLUTION};bool Key::operator<( const Key& _key ) const{return ( a < _key.a ) ;}// operator<< is implemented ONLY FOR TESTING PURPOSEostream& operator<<(ostream& os, const Key& _key){os << _key.a;return os;}

Now the implementation

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {K last = m_map.rbegin()->first;K first = m_map.begin()->first;if (!(keyBegin < keyEnd) ) return;if ( keyBegin < first ) return;if( last < keyEnd) return ;for (auto it = m_map.begin(); it!=m_map.end(); ++it){if((*it).first < keyBegin) continue;else{(*it).second=val;it++;auto tmp=it;while((*it).first < keyEnd){it++;}m_map.erase(tmp, it);break;}}}

Another Solution

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {K last = m_map.rbegin()->first;K first = m_map.begin()->first;if (!(keyBegin < keyEnd) ) return;if ( keyBegin < first ) return;if( last < keyEnd) return ;auto itr1 = m_map.find(keyBegin);auto itr2 = m_map.find(keyEnd);(*itr1).second=val;itr1++;m_map.erase(itr1,itr2);cout << endl << endl;}

The two solutions above from Vivek do not work. This is the simplest and shortest implementation I could come up with:

if (not (keyBegin < keyEnd) )return;auto beginLowerBound = m_map.lower_bound(keyBegin);auto endLowerBound = m_map.lower_bound(keyEnd);std::optional<std::pair<K,V>> additionalElement;if (endLowerBound == m_map.end() || keyEnd < endLowerBound->first)additionalElement = std::pair(keyEnd, operator[]( keyEnd ));else if (beginLowerBound == m_map.end() || keyBegin < beginLowerBound->first)additionalElement = std::pair(keyEnd, operator[]( keyBegin ));if (beginLowerBound != m_map.end())m_map.erase(beginLowerBound, endLowerBound);m_map.insert(std::pair(keyBegin, val));if (additionalElement)m_map.insert(additionalElement.value());

I just had the same interview. My approach was different to all above - but worked. I've spent a lot of effort for testing-scenarios. Unfortunately I was using the [] operator for assigning map-values. That required the use of default constructor - which apparently was not allowed (nowhere clearly stated though). Despite the fact they recommended testing with <int, char> - which of course both have default constructor.

if (!(keyBegin < keyEnd))return;auto upper_bound_end = m_map.upper_bound(keyEnd);auto upper_bound_end2 = upper_bound_end;upper_bound_end2--; auto uper_bound_begin = m_map.upper_bound(keyBegin); auto uper_bound_begin2 = uper_bound_begin;uper_bound_begin2--;bool flag = false;bool flag2 = false;if (!((uper_bound_begin2)->second == val))flag = true;V tmp;if (!((upper_bound_end2)->second == val)){flag2 = true;tmp = (upper_bound_end2)->second;} for (auto it = uper_bound_begin; it != upper_bound_end;){it = m_map.erase(it);}if (flag == true)m_map[keyBegin] = val;if (flag2 == true)m_map[keyEnd] = tmp;

This is my solution that can replace the assign function in the question above. The original question was asking for implementing it as a class member function but the question here omitted the class part. So, you can disregard the template and interval_map<K, V> to be able to match the solution in the question, like the other answers in this page.

When implementing, I imagined the assign function as painting a new color over an existing color in a strip. The map here contains only the starting point and the color (i.e. value) in the strip for each painted region.

template <typename K, typename V>void interval_map<K, V>::assign(const K& keyBegin, const K& keyEnd, const V& val){using iterator = typename std::map<K, V>::iterator;if ( !(keyBegin < keyEnd) )return;// Handle keyEnd first to not impact the handling of keyBegin.iterator it1 = m_map.upper_bound(keyEnd);--it1; // it1 points to the greatest interval whose key <= keyEnd. It exists always.V& old_val = it1->second;++it1;if ( old_val != val )// If old_val from the greatest interval does not equal the desired val, we cut// off the interval at keyEnd unless the interval already starts with keyEnd, in// which case we do nothing.// If old_val equals val we set up to erase up to that interval.it1 = m_map.try_emplace(it1, keyEnd, std::move(old_val));// Now it1 points to the first interval starting from keyEnd that has a value// different than `val`, or m_map.end() if no such interval exits.iterator it0 = m_map.lower_bound(keyBegin);--it0; // it0 points to the greatest interval whose key < keyBegin. It exists always.if ( it0->second != val ){// If the greatest interval has a value different than `val`, we create a new// interval at keyBegin, or if there already exists an interval starting at// keyBegin we change the value.// If the greatest interval has `val` as the value we make it our interval to// cover [keyBegin, keyEnd).++it0;it0 = m_map.insert_or_assign(it0, keyBegin, val);}// Now it0 points to the first interval that covers keyBegin and has the value `val`.// Extend it0 until it1, that is, erase all iterators {it | it0 < it < it1}.++it0;m_map.erase(it0, it1);}

FYI, I also wrote a verify function that can be called after each assign to verify the validity of the whole map. Hope this can help to understand the property of the map to satisfy across assign operations.

template <typename K, typename V>void interval_map<K, V>::_verify(const K& keyBegin, const K& keyEnd, const V& val) const{// 1. m_map should be non-empty.assert( m_map.begin() != m_map.end() );auto it = m_map.begin();V prev_val = it->second;while ( ++it != m_map.end() ){// 2. Adjacent intervals should have different values.assert( prev_val != it->second );prev_val = it->second;}auto it0 = --m_map.upper_bound(keyBegin);auto it1 = --m_map.lower_bound(keyEnd);// 3. There should be only one interval that covers [keyBegin, keyEnd).assert( it0 == it1 );// 4. The interval should have the disired value.assert( val == it0->second );}

Try this code:

#include <iostream>#include <map>using namespace std;template < typename K, typename V >class interval_map {std::map < K, V > m_map;public:// constructorinterval_map(Vconst & val) {m_map.insert(m_map.begin(), std::make_pair(std::numeric_limits < K > ::lowest(), val));}// insert an interval and valuevoid insert(Kconst & keyBegin, Kconst & keyEnd, Vconst & val) {// check if the interval is validif (!(keyBegin < keyEnd))return;// find the entry for the interval startauto lb = m_map.lower_bound(keyBegin);if (lb != m_map.begin() && (--lb) -> second == val) {++lb;}// remove all entries in the intervalauto up = m_map.upper_bound(keyEnd);while (lb != up) {lb = m_map.erase(lb);}// insert the new intervalm_map.insert(lb, std::make_pair(keyBegin, val));m_map.insert(up, std::make_pair(keyEnd,m_map.find(keyBegin) -> second));}};

Your solution is wrong, you have to delete every subinterval that is contained on the new interval.

also the employer requested to use at most only one function maximum to be log(n), the upper_bound and lower_bound are log(n), and inserttion also without a hint. you have to always keep the iterator for the hint to be constant time.

this code passes (with all the requirements for canonicity and types of v and k).

enter code herevoid assign( K const& keyBegin, K const& keyEnd, V const& val ){if(!(keyBegin < keyEnd))return;if( m_map.empty() ){if( val == m_valBegin )return;m_map.insert({keyBegin, val});m_map.insert({keyEnd, m_valBegin});return;}K end_interval = m_map.rbegin()->first;auto iter = m_map.end();if( end_interval < keyEnd ){m_map.insert( m_map.end(), pair<K,V>( keyEnd, m_valBegin) );iter--;iter--;} else {iter = m_map.lower_bound(keyEnd);V nextIntervalValue = iter->second;if( !(nextIntervalValue == val) ){iter = m_map.insert_or_assign( iter, keyEnd, prev(iter)->second );iter--;}}while( keyBegin < iter->first ){if(iter == m_map.begin()){m_map.erase(iter);break;}m_map.erase(iter--);}K begin_interval = m_map.begin()->first;if(keyBegin < begin_interval){if( !(val == m_valBegin) )m_map.insert_or_assign( m_map.begin(),keyBegin, val );} else {V previousIntervalValue = (--iter)->second;if( !(val == previousIntervalValue ) )m_map.insert_or_assign( iter, keyBegin, val );}}

on main some simple tests:

int main(){//first test caseinterval_map<int, char> fooh { 'z' };fooh.assign(2,5,'a');fooh.print();std::cout << fooh[6] << std::endl << std::endl;//second test case// expected : z b zfooh = interval_map<int, char>{'z'};fooh.assign(1,4,'b');cout << fooh[0] << " " << fooh[1] << " " << fooh[5] << endl; //third test case// expected: Afooh = interval_map<int, char>{'z'};fooh.assign(1,6,'A');fooh.assign(2,4,'B');cout << fooh[5] << endl;fooh.print();//forth test casefooh = interval_map<int, char>{'z'};//expected [0,'a'],[1,'z']fooh.assign(0,1,'a');fooh.print();//fifth test case// expected [0,'f']fooh = interval_map<int, char>{'z'};fooh.assign(1,2,'c');fooh.assign(2,3,'d');fooh.assign(3,4,'e');fooh.assign(4,15,'g');fooh.assign(0,10,'f');fooh.print();cout << endl;//sixth test case// expected: 0,'d' 2,'c' fooh = interval_map<int, char>{'z'};fooh.assign(1,4,'c');fooh.assign(0,2,'d');fooh.print();cout << endl;

return 0;}

full working code below with test in main ()(but employer said incorrect usage of template types)

#define _ITERATOR_DEBUG_LEVEL 2#define _SECURE_SCL 1#define _HAS_ITERATOR_DEBUGGING 1#include <iostream>#include <iomanip>#include <cassert>#include <map>template<typename K, typename V>class interval_map { V m_valBegin;std::map<K, V> m_map;public:// constructor associates whole range of K with valinterval_map(V const& val): m_valBegin(val){}void assign(std::map<K, V> const& testMap) {m_map = testMap;}// 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.// look-up of the value associated with keyV 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;}}void print() {std::cout << '\n' << m_valBegin << '\n';for (auto it = m_map.begin(); it != m_map.end(); ++it) {std::cout << it->first << ", " << it->second << '\n';}}void assign(K const& keyBegin, K const& keyEnd, V const& val) {if (!(keyBegin < keyEnd)) return;if (m_map.empty()) {if (m_valBegin == val)return;m_map.insert({ keyBegin, val });m_map.insert({ keyEnd, m_valBegin});return;}auto startIt = m_map.lower_bound(keyBegin);bool doErase = true;if (startIt == m_map.end())doErase = false;auto endIt = m_map.upper_bound(keyEnd);auto upperVal{ m_valBegin };if (endIt == m_map.begin())doErase = false; elseupperVal = (--endIt)->second;if (endIt != m_map.end())endIt++;if(doErase)m_map.erase(startIt, endIt);m_map.insert({ keyBegin, val });m_map.insert({ keyEnd, upperVal });// ensure canonical - further downstartIt = m_map.lower_bound(keyBegin);assert(startIt->second == val); // go back to prev interval (it can have value = val)if (startIt != m_map.begin()) {startIt--;// then our inserted value is the first equal to valif (startIt->second != val) startIt++;}// skip first repeating value (first one should be left - others deleted)if(!(startIt == m_map.begin() && val == m_valBegin))startIt++; while(startIt != m_map.end()){ auto tmpKey = startIt->first;if ((startIt++)->second == val)m_map.erase(tmpKey);else break;}}};int main() {interval_map<int, char> mymap{ 'a' };//mymap.assign({ {10,'c'},{20,'a'},{30,'c'},{40,'i'},{50,'c'},{60,'i'} }); //mymap.assign(65, 68, 'z'); mymap.print();while (1) { mymap.print();int start, end;char ch;std::cout << "\n\n Enter start, end, char: ";std::cin >> start >> end >> ch;mymap.assign(start, end, ch);}}