Fun solution with "detailed explanation".


  • 0
    A

    Hello!

    I met a similar question on real interview one day. There the problem sounded a bit more complex because we analyzed a stream and the size of this structure would be limited to N, where N could be 10, 100.. not a big number.

    As usually, I had some thinking process on the board. The interviewer "adjusted my thinking process to the solution he wanted" and asked to write one of the methods. Well... I did not do great because I kept thinking...

    A solved the task at home, sent the guy my solution and then asked... why on earth did he need O(1) from Min and Max calls? Having those calls in his problem were not really justified. Fine... the interviewer is "always right" but here I am playing a trick... I am submitting my solution which is O(N) for Min and Max but has significantly lower Const for Inc and Dec compared to other solutions. The code is below. And what I get for this solution from Leetcode judgment?

    15 / 15 test cases passed.
    Status: Accepted
    Runtime: 29 ms

    Your runtime beats 94.65% of the solutions

    So... dear author of this problem. You should have written perf tests clearly demonstrating your judgment intentions. Otherwise WTF O(1) is needed for?

    Now... I did submit my other solution with O(1). It is below. I am also providing my own test I am using. Runtimes of that test with x64 Release:

    My solution: 7.3 sec
    My "Fake with O(N) solution" 11 sec
    The C++ solution of another guy, which was voted: 36 sec

    The reason why another guys solution is so slow is because he did not do "important optimization" and literally followed the prototype of the class. Those prototypes on Leetcode for C++ are often bad. They are copy-paste adaptation from Java. In reality you can change them and their tests will work. This is what I did. This does not guarantee you a win (due to perf tests not written properly) but...

    And one more thing... Starting from Visual Studio 15 the STL version supports try_emplace methods for the containers like unordered_map. Leetcode does not accept that code. If I use try_emplace(key, val) instead of the one I used insert(make_pair(key, val)) then my code becomes even faster. For my test:

    My solution: 5.8 sec
    My "Fake with O(N) solution" 9.5 sec

    OK... Pieces of code.

    // Fake solution to test how good the perf tests on Leetcode for this tasks are
    class AllOneF
    {
    	unordered_map<string, size_t> _map;
    	const string* _min;
    	const string* _max;
    
    public:
    	/** Initialize your data structure here. */
    	AllOneF() : _min(nullptr), _max(nullptr)
    	{
    	}
    
    	/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    	void inc(const string& key)
    	{
    		_min = _max = nullptr;
    		++(_map.insert(make_pair(key, 0)).first->second);
    	}
    
    	/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    	void dec(const string& key)
    	{
    		_min = _max = nullptr;
    		
    		auto iter = _map.find(key);
    		if (iter == _map.end())
    			return;
    
    		if (--iter->second == 0)
    			_map.erase(iter);
    	}
    
    	/** Returns one of the keys with maximal value. */
    	const string& getMaxKey()
    	{
    		if (!_max)
    			ComputeMinMax();
    
    		return *_max;
    	}
    
    	/** Returns one of the keys with Minimal value. */
    	const string& getMinKey()
    	{
    		if (!_min)
    			ComputeMinMax();
    
    		return *_min;
    	}
    
    	void clear()
    	{
    		_min = _max = nullptr;
    		_map.clear();
    	}
    
    private:
    	void ComputeMinMax()
    	{
    		static string Empty;
    
    		size_t foundMin = numeric_limits<size_t>::max();
    		size_t foundMax = numeric_limits<size_t>::min();
    
    		_min = _max = &Empty;
    
    		for (auto& kv : _map)
    		{
    			if (kv.second < foundMin)
    			{
    				foundMin = kv.second;
    				_min = &kv.first;
    			}
    
    			if (kv.second > foundMax)
    			{
    				foundMax = kv.second;
    				_max = &kv.first;
    			}
    		}
    	}
    };
    
    // My O(1) solution
    class AllOne
    {
    	struct Hash
    	{
    		size_t operator()(const string* _Keyval) const
    		{
    			return reinterpret_cast<size_t>(_Keyval);
    		}
    	};
    
    	typedef unordered_set<const string*, Hash> Set;
    	typedef list<pair<size_t, Set>> List;
    
    	unordered_map<string, List::iterator> _map;
    	List _list;
    	List _sentinel;
    
    public:
    	/** Initialize your data structure here. */
    	AllOne()
    	{
    		_sentinel.emplace_back(make_pair(0, Set()));
    	}
    
    	/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    	void inc(const string& key)
    	{
    		auto insertResult = _map.insert(make_pair(key, _sentinel.begin()));
    		auto& mapIter = insertResult.first;
    
    		const string* keyAddr = &mapIter->first;
    
    		List::iterator listIter;
    		if (insertResult.second)
    		{
    			if (_list.empty() || _list.begin()->first != 1)
    				_list.emplace_front(make_pair(1, Set()));
    
    			listIter = _list.begin();
    		}
    		else
    		{
    			List::iterator& prevIter = mapIter->second;
    			size_t newCount = prevIter->first + 1;
    
    			List::iterator nextIter = prevIter;
    			++nextIter;
    
    			// Optimization. Not reallocating the node if...
    			if (nextIter == _list.end() || nextIter->first != newCount)
    			{
    				if (prevIter->second.size() == 1)
    				{
    					++prevIter->first;
    					return;
    				}
    
    				nextIter = _list.emplace(nextIter, make_pair(newCount, Set()));
    			}
    
    			Erase(prevIter, keyAddr);
    
    			listIter = nextIter;
    		}
    
    		listIter->second.emplace(keyAddr);
    		mapIter->second = listIter;
    	}
    
    	/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    	void dec(const string& key)
    	{
    		auto mapIter = _map.find(key);
    		if (mapIter == _map.end())
    			return;
    
    		const string* keyAddr = &mapIter->first;
    		List::iterator& prevIter = mapIter->second;
    		size_t newCount = prevIter->first - 1;
    
    		if (newCount == 0)
    		{
    			Erase(prevIter, keyAddr);
    			_map.erase(mapIter);
    			return;
    		}
    
    		List::iterator nextIter;
    		if (prevIter == _list.begin())
    		{
    			if (prevIter->second.size() == 1)
    			{
    				--prevIter->first; // We can reuse the same list node.
    				return;
    			}
    
    			nextIter = _list.emplace(prevIter, make_pair(newCount, Set()));
    		}
    		else
    		{
    			nextIter = prevIter;
    			--nextIter;
    			
    			if (nextIter->first != newCount)
    			{
    				if (prevIter->second.size() == 1)
    				{
    					--prevIter->first; // We can reuse the same list node.
    					return;
    				}
    
    				nextIter = _list.emplace(prevIter, make_pair(newCount, Set()));
    			}
    		}
    
    		Erase(prevIter, keyAddr);
    
    		nextIter->second.emplace(keyAddr);
    		mapIter->second = nextIter;
    	}
    
    	/** Returns one of the keys with maximal value. */
    	const string& getMaxKey() const
    	{
    		static string Empty;
    
    		if (_list.empty())
    			return Empty;
    
    		return **_list.back().second.begin();
    	}
    
    	/** Returns one of the keys with Minimal value. */
    	const string& getMinKey() const
    	{
    		static string Empty;
    
    		if (_list.empty())
    			return Empty;
    
    		return **_list.front().second.begin();
    	}
    
    	void clear()
    	{
    		_list.clear();
    		_map.clear();
    	}
    
    private:
    	void Erase(const List::iterator& listIter, const string* keyAddr)
    	{
    		if (listIter->second.size() == 1)
    			_list.erase(listIter);
    		else
    			listIter->second.erase(keyAddr);
    	}
    };
    
    // Competitor's solution
    class AllOneO {
    public:
    
    	void inc(string key) {
    
    		// If the key doesn't exist, insert it with value 0.
    		if (!bucketOfKey.count(key))
    			bucketOfKey[key] = buckets.insert(buckets.begin(), { 0,{ key } });
    
    		// Insert the key in next bucket and update the lookup.
    		auto next = bucketOfKey[key], bucket = next++;
    		if (next == buckets.end() || next->value > bucket->value + 1)
    			next = buckets.insert(next, { bucket->value + 1,{} });
    		next->keys.insert(key);
    		bucketOfKey[key] = next;
    
    		// Remove the key from its old bucket.
    		bucket->keys.erase(key);
    		if (bucket->keys.empty())
    			buckets.erase(bucket);
    	}
    
    	void dec(string key) {
    
    		// If the key doesn't exist, just leave.
    		if (!bucketOfKey.count(key))
    			return;
    
    		// Maybe insert the key in previous bucket and update the lookup.
    		auto prev = bucketOfKey[key], bucket = prev--;
    		bucketOfKey.erase(key);
    		if (bucket->value > 1) {
    			if (bucket == buckets.begin() || prev->value < bucket->value - 1)
    				prev = buckets.insert(bucket, { bucket->value - 1,{} });
    			prev->keys.insert(key);
    			bucketOfKey[key] = prev;
    		}
    
    		// Remove the key from its old bucket.
    		bucket->keys.erase(key);
    		if (bucket->keys.empty())
    			buckets.erase(bucket);
    	}
    
    	string getMaxKey() {
    		return buckets.empty() ? "" : *(buckets.rbegin()->keys.begin());
    	}
    
    	string getMinKey() {
    		return buckets.empty() ? "" : *(buckets.begin()->keys.begin());
    	}
    
    private:
    	struct Bucket { int value; unordered_set<string> keys; };
    	list<Bucket> buckets;
    	unordered_map<string, list<Bucket>::iterator> bucketOfKey;
    };
    
    // Perf Test code
    	vector<string> data(10000000);
    	for (auto& str : data)
    		str = string(32, char(rand() * 127 / RAND_MAX));
    
    	printf("Get ready!\n");
    
    	for (auto& s : data)
    	{
    		allo1.inc(s);
    		if (allo1.getMaxKey().size() == 0)
    			throw int(-1);
    		if (allo1.getMinKey().size() == 0)
    			throw - 1;
    	}
    
    	for (auto& s : data)
    	{
    		if (allo1.getMaxKey().size() == 0)
    			throw int(-1);
    		if (allo1.getMinKey().size() == 0)
    			throw int(-1);
    
    		allo1.dec(s);
    	}
    
    	if (allo1.getMaxKey().size() != 0)
    		throw int(-1);
    	if (allo1.getMinKey().size() != 0)
    		throw int(-1);
    
    	printf("Done!\n");
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.