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

I passed the test the other day! For those of you like me who will have nightmares if they don't find the solution, rest assured—it does have a solution. So keep trying

My solution ended up being 20 lines of code. You'd need to use basic algorithms you may not have used since you were in school.

Their code tests are good, but they may be stateless and might not account for some conditions, so they might tell you that your answer is wrong. For instance, you might be sure part of your code would only be executed on empty sets of data; therefore, you might not include some bits that would formally reduce the complexity. The test would fail there.

Read each requirement carefully and create tests for your code.

ChatGPT won't be much help with the problem itself, but if you can break it into parts, it may help you produce your solution faster.

Don't bother contacting them with your answer—they will reply with a prefabricated email that won't give you any useful information or review.

I'm missing a certification or badge for those who pass the test.

I encourage everyone to take the test. It's not a scam; it's just a fair way of choosing employees. If you like games, logic, and solving problems, it's something you'll enjoy. However, if you don't manage to get the answer, you may lose sleep for some time.

Good luck!

My code takes about 60 lines and I had a bit different message, when passed the test, see below:

I passed the test the other day! For those of you like me who will have nightmares if they don't find the solution, rest assured—it does have a solution. So keep trying
My solution ended up being 20 lines of code. You'd need to use basic algorithms you may not have used since you were in school.
Their code tests are good, but they may be stateless and might not account for some conditions, so they might tell you that your answer is wrong. For instance, you might be sure part of your code would only be executed on empty sets of data; therefore, you might not include some bits that would formally reduce the complexity. The test would fail there.
Read each requirement carefully and create tests for your code.
ChatGPT won't be much help with the problem itself, but if you can break it into parts, it may help you produce your solution faster.
Don't bother contacting them with your answer—they will reply with a prefabricated email that won't give you any useful information or review.
I'm missing a certification or badge for those who pass the test.
I encourage everyone to take the test. It's not a scam; it's just a fair way of choosing employees. If you like games, logic, and solving problems, it's something you'll enjoy. However, if you don't manage to get the answer, you may lose sleep for some time.
Good luck!

My code takes about 60 lines and I had a bit different message, when passed the test, see below:

can you write all the test cases with the correct output to fix our implementation, or explain the problem clearly, or send the passed code : ragabmx2002@gmail.com

@jonathan-ruiz Can you please send the test cases you used to test your solution so that I can keep trying and improve my solution, taking this test today. Thanks.
devansh2895@gmail.com

 auto endIt = m_map.lower_bound(keyEnd);

@maybesravan You are using too many methods of cost Log(N), you can achieve the expected result using just one check in the documentation the cost of the methods you are using.

Do you mean we have to avoid lower_bound method twice and just use it once?

@netmonitoring can you share you solution that passed on devanshchugh04@gmail.com

Here is one take without using upper/lower bound checks. I shortly checked against a normal array and if it is canonical, but didn't check the boundaries. One concern I had was whether the eraseEnd iterator will be invalidated if the lower bound is inserted but according to the standard it should not be the case for std::map. It is not a submitted code, so use the idea at your own risk.

PS: Really, we shouldn't use even insert() Then why are we using a map?

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
    // incorrect key
    if ( keyEnd <= keyBegin )
        return;

    const auto &[ upperBoundItr, upperBoundSuccess ] = m_map.insert( { keyEnd, val } );
    auto eraseEnd = upperBoundItr;

    // upper boundary should be the continuation of the previous range. if it is a new insertion
    // it should have the previous range value. if the insertion was not successful, the value should not change.
    if ( upperBoundSuccess ) {
        upperBoundItr->second = std::prev( upperBoundItr )->second;

        // if it is a new insertion, we need to check if the next boundary has the same value.
        if ( auto n = std::next( eraseEnd ); n != m_map.cend() && n->second == eraseEnd->second )
            m_map.erase( n );
    }

    const auto &[ lowerBoundItr, lowerBoundSuccess ] = m_map.insert_or_assign( keyBegin, val );
    auto eraseStart = std::next( lowerBoundItr );

    // if the end of the range has the same value, the end boundary should be removed.
    if ( lowerBoundItr->second == eraseEnd->second )
        eraseEnd = std::next( eraseEnd );

    // if the previous start boundary has the same value, remove the new duplicate.
    if ( lowerBoundItr != m_map.cbegin() && std::prev( lowerBoundItr )->second == val )
        eraseStart = lowerBoundItr;

    m_map.erase( eraseStart, eraseEnd );
}