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;
    }
};

@danielyoshizawa

if state is m_valBegin = 'A'; map = (0,'A'), (3,'B'); last call assign(5,10, 'C');
then it becomes (0,'A'), (3,'B'), (5,'C'), (10'A')
so query map[11] => A

in your example m_valBegin = (0,'A'), (3,'B'), (5,'C'); m_valBegin == 'A'
then query map[11] => C

Here's my try.

void assign(K const& keyBegin, K const& keyEnd, V const& val)
    {
        if (keyEnd < keyBegin) {
            return;
        }

        auto it_begin = m_map.lower_bound(keyBegin);
        auto it_Ubegin = m_map.upper_bound(keyBegin);

        auto it_end = m_map.upper_bound(keyEnd);

        if (m_map.size() == 0) {
            if (val == m_valBegin)
                return;
        }

        if (it_end != m_map.end()) {
            if (val == it_end->second) {
                return;
            }
        }
        if (it_begin != m_map.begin()) {
            if (val == std::prev(it_begin)->second) {
                return;
            }
        }

        if (it_begin == m_map.end()) {

            if (it_end != m_map.end() && it_Ubegin->first < it_end->first) {
                m_map.insert({keyEnd, it_Ubegin->second});
            }
            m_map.erase(it_Ubegin, it_end);
            m_map.insert({keyBegin, val});

        } else {
            if (it_end != m_map.end()) {
                m_map.insert({keyEnd, it_end->second});
            }
            m_map.erase(it_begin, it_end);
            m_map.insert({keyBegin, val});
        }
    }

with the test function:

void runIntervalMapTest() {

    std::srand(time(0));

    // Number of random test cases
    const int numTestCases = 1000;
    // Generate random test cases
    for (int i = 0; i < numTestCases; ++i) {

        interval_map<int,char> iMap('F');
        std::map<int, char> referenceMap;

        // Randomly generate startKey, endKey, and value
        int startKey = std::rand() % numTestCases;
        int endKey = startKey + std::rand() % 50;
        char value = static_cast<char>('A' + std::rand() % 26);

        // Perform the assignment in both the inter_map and referenceMap
        iMap.assign(startKey, endKey, value);
        for (int key = startKey; key <= endKey; ++key) {
            referenceMap[key] = value;
        }

        // Compare the results of inter_map with the referenceMap
        // and print an error message if they differ
        for (const auto& entry : referenceMap) {
            int key = entry.first;
            char expectedValue = entry.second;
            char actualValue = iMap[key]; // You may need a getValue() function in your inter_map class
            if (actualValue != expectedValue) {
                std::cout << "Test "<<i <<" failed: Key " << key << ", Expected " << expectedValue << ", Actual " << actualValue << std::endl;
            }
        }

    }
    std::cout << "Randomized test completed." << std::endl;
}

I attempted this test - they claimed to have liked my implementation, but are limiting feedback so the test can be re-used. I explain in greater detail here.

This version did not pass the running time test:

 void assign(K const& keyBegin, K const& keyEnd, V const& val)
    {
        if (!(keyBegin < keyEnd))
        {
            return;
        }

        auto endIt = m_map.lower_bound(keyEnd);
        if ((endIt == m_map.end()) || (keyEnd < endIt->first))
        {
            const auto& valEnd =
                (endIt == m_map.begin()) ? m_valBegin : std::next(endIt, -1)->second;
            if (!(valEnd == val))
            {
                endIt = m_map.emplace_hint(endIt, keyEnd, valEnd);
            }
        } else if (endIt->second == val)
        {
            ++endIt;
        }

        auto startIt = m_map.lower_bound(keyBegin);
        if ((startIt == m_map.begin()) && (val == m_valBegin))
        {
            if (startIt != endIt)
            {
                m_map.erase(startIt, endIt);
            }
            return;
        } else if ((startIt != m_map.begin()) && (val == std::next(startIt, -1)->second))
        {
            --startIt;
        } else
        {
            if (keyBegin < startIt->first)
            {
                startIt = m_map.emplace_hint(startIt, keyBegin, val);
            } else
            {
                startIt->second = val;
            }
        }

        if (++startIt != endIt)
        {
            m_map.erase(startIt, endIt);
        }
    }

Only way i've found to possibly improve it:

...
       auto endIt = m_map.lower_bound(keyEnd);
       if ((endIt == m_map.end()) ||
           (keyEnd < endIt->first))
       {
           if ((endIt == m_map.begin()))
           {
               if (!(val == m_valBegin))
               {
                   endIt = m_map.emplace_hint(endIt, keyEnd, m_valBegin);
               }
           } else if (!(val == std::next(endIt, -1)->second))
           {
               auto node  = m_map.extract(std::next(endIt, -1));
               node.key() = keyEnd;
               endIt      = m_map.insert(endIt, std::move(node));
           }
       } else if (endIt->second == val)
       {
           ++endIt;
       }
...

Cannot test since there are only two attempts

did u sucess in the test? share the solution

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

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

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
hey buddy i also have implemented something but i am unclear about some case what to do can you explain your code and possibilities through gmeet my email sakibshekhabd@gmail.com

reply fast just 2 hours left

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.

Can you please give the 1st solution?

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.

Can you give your 1st solution

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.

Finally ThinkCells will be able to interview someone for this 10 years🤣🤣🤣

Can you give your solution @netmonitoring

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

I have test link
email: githubrp@gmail.com

Can you give your solution @netmonitoring

I will provide the solution to the test link directly. Will not allow modify my solution. So if you are not ready to provide your link, do not share your contacts.

Also i will ask you not share my solution anywhere.

@netmonitoring what means test link?

@RutulPatel007 @netmonitoring @triptisingla @sakib-shekh …
Just remember this cartoon 🤣🤣🤣

This was my approach:

#include <bits/stdc++.h>
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 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).
void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
    // Check if the interval is valid
    if (!(keyBegin < keyEnd))
        return;

    // Initialize the map if it's empty
    if (m_map.empty()) {
        if (!(val == m_valBegin)) {
            m_map.insert(m_map.end(),std::make_pair(keyBegin, val));
            m_map.insert(m_map.end(),std::make_pair(keyEnd, m_valBegin));
        }
        return;
    }

    // Find a position to insert keyBegin
    auto insertPosBegin = m_map.lower_bound(keyBegin);
    bool insertBeforeBegin = false;

    // Check if keyBegin can be inserted before the beginning
    if (insertPosBegin == m_map.begin() && val == m_valBegin)
        return; // Value at the beginning cannot be equal to m_valBegin.

    // Check if keyBegin can be inserted before insertPosBegin
    if ((insertPosBegin == m_map.end()) || (insertPosBegin != m_map.begin() && (keyBegin < insertPosBegin->first || std::prev(insertPosBegin)->second == val)))
        --insertPosBegin;
    else if (insertPosBegin == m_map.begin() && keyBegin < insertPosBegin->first)
        insertBeforeBegin = true;

    // Find a position to insert keyEnd
    auto insertPosEnd = m_map.lower_bound(keyEnd);
    bool insertBeforeEnd = false;

    auto tempPos = insertPosEnd;

    // Check if keyEnd can be inserted before insertPosEnd
    if (insertPosEnd == m_map.end() || (keyEnd < insertPosEnd->first && insertPosEnd != m_map.begin()))
        --tempPos;
    else if (insertPosEnd == m_map.begin() && keyEnd < insertPosEnd->first)
        insertBeforeEnd = true;

    auto endElementPair =  std::pair<K,V>(keyEnd, (insertBeforeEnd ? m_valBegin : tempPos->second));

    // Insert or assign keyBegin
    if (insertBeforeBegin || !(insertPosBegin->second == val)) {
        insertPosBegin = m_map.insert(insertPosBegin, {keyBegin, val});
    }

    // Erase elements between keyBegin and keyEnd
    auto tempIter = insertPosBegin;
    if (insertPosBegin != m_map.end())
        ++tempIter;

    // Delete elements between inserted begin key and end key position
    if (tempIter != m_map.end() && !(keyEnd < tempIter->first)) {
        m_map.erase(tempIter, insertPosEnd);
    }

    // Insert or assign keyEnd
    if (!(insertPosBegin->second == endElementPair.second)) {
        insertPosEnd = m_map.insert(insertPosEnd, {endElementPair.first, endElementPair.second});
    }

    // Delete end element if its value is same as begin element value
    if (insertPosEnd != m_map.end() && insertPosBegin->second == insertPosEnd->second) {
        m_map.erase(insertPosEnd);
    }
}


    // 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 std::prev(it)->second;
        }
    }
};

// Driver or test code
int main() {
    interval_map<int,char> m('A');
    // calling of assign() function  
    m.assign(1, 3, 'B');
    m.assign(4, 8, 'F');
    m.assign(6, 11, 'V');
    m.assign(11, 15, 'F');
    m.assign(0, 3, '2');
    m.assign(0, 5, '3');
    m.assign(1, 5, '2');
    m.assign(1, 4, '2');
    m.assign(1, 4, '3');
    m.assign(1, 5, 's');
    m.assign(1, 5, 'r');
    m.assign(8, 10, 's');
    m.assign(4, 8, 's');
    m.assign(1, 8, 's');
    m.assign(1, 8, 'o');
    m.assign(1, 2, 'k');
    m.assign(-10, 4, 2);
    m.assign(-10, -2, 2);
    m.assign(-10, -2, 3);
    m.assign(-10, -2, 0);
    m.assign(-10, 0, 2);
    m.assign(-10, 3, 2);
    m.assign(-10, 3, 1);
    m.assign(-10, 1, 2);
    m.assign(-10, 4, 2);
    m.assign(-10, 8, 2);
    m.assign(-10, 3, 0);
    m.assign(0, 5, 0);
    m.assign(1, 5, 0);
    m.assign(1, 8, 0);
    m.assign(3, 4, 0);
    m.assign(3, 4, 1);
    m.assign(3, 5, 1);
    m.assign(3, 5, 2);
    m.assign(5, 8, 2);

    // loop for mapping key and its corresponding value
    for (int i = -2; i <= 19; ++i)
        std::cout << std::setw(2) << i << ' ' << m[i] << '\n';

}

But my program didn't pass the Correctness criteria. I don't know why. I have tested multiple test scenarios and it was working just fine. This test is so fucking baseless, it is concerning how a developer actually works in the job here.

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. Many solutions we receive do not create the data structure that was asked for, e.g., some interval ends up being associated with the wrong value. Others contain a code path that will eventually dereference an invalid or end iterator.

This is was how I implemented mine.

    #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
interval_map(V const& val)
: m_valBegin(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;
    auto itBegin = m_map.lower_bound(keyBegin);

    if (itBegin == m_map.end() || itBegin->first != keyBegin) {
        if (val != m_valBegin)
            m_map[keyBegin] = val;
        itBegin = m_map.lower_bound(keyBegin);
    } else {
        if (itBegin != m_map.begin() && std::prev(itBegin)->second == val)
            itBegin = m_map.erase(itBegin);
        else
            itBegin->second = val;
    }

    auto itEnd = m_map.lower_bound(keyEnd);

    if (itEnd == m_map.end() || itEnd->first != keyEnd) {
        if (val != m_valBegin)
            m_map[keyEnd] = itEnd == m_map.begin() ? m_valBegin : std::prev(itEnd)->second;
        itEnd = m_map.lower_bound(keyEnd);
    } else {
        if (itEnd != m_map.begin() && std::prev(itEnd)->second == val)
            itEnd = m_map.erase(itEnd);
        else
            itEnd->second = std::prev(itEnd)->second;
    }

    m_map.erase(std::next(itBegin), itEnd);

}

// 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 test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of int intervals to char.

@NIGHTMARE09 I also got the same error on my first trial then got this error on my second attempt

Type requirements are met: You must adhere to the specification of the key and value type given above. For example, many solutions we receive use operations other than those that are explicitly stated in the task description. We have to reject many solutions because they assume that V is default-constructible, e.g., by using std::map::operator[].
Atleast we tried :-)