C++ With hashing you are doing it wrong, guys. This one with hashing beats 55%.


  • 0
    A

    Yes, yes i understand that "expected" algorithm is to screw up the original and then restore it. Now, consider real world. Can operator new throw? Yes. Suppose your list node had not just a simple int label but something decent and memory consuming. Could constructor of such node throw? Yes! So what if it threw in the middle? How would you restore consistency? Most copying algorithms must obey the "do not touch original" semantic. I.e. T Copy(const T& src).

    Well... OK. In real world i do also consider that throwing from memory allocation should dump the process state and never throw (blue screen). In such processes such algorithms do make sense.

    Anyway, i do not think any person can code the "expected" algorithm in 50min interview time if really met it first time. Maybe if interviewer gave tons of tips. But... here goes my "straightforward" and "not messing with the original" algorithm (which can be adopted to the exception recovery situation easily) AND with 49ms perf. I.e. statistically it is faster than 55% submissions. And the idea is that extra loop, counting the elements in the list to use it in hash table creation, does help speeding up the code 2 times.

    class Solution
    {
    public:
    	RandomListNode *copyRandomList(RandomListNode* head)
    	{
    		if (!head)
    			return nullptr;
    
    		size_t buckets = 0;
    		for (auto n = head; n; n = n->next)
    			++buckets;
    
    		unordered_map<RandomListNode*, RandomListNode*> map(buckets + 1);
    
    		RandomListNode* prev = head;
    		RandomListNode* headCopy = new RandomListNode(head->label);
    		RandomListNode* prevCopy = headCopy;
    
    		map[nullptr] = nullptr;
    		map[head] = headCopy;
    
    		while (prev->next)
    		{
    			auto nextCopy = new RandomListNode(prev->next->label);
    			prevCopy->next = nextCopy;
    			map[prev->next] = nextCopy;
    			prevCopy = nextCopy;
    
    			prev = prev->next;
    		}
    
    		prevCopy->next = nullptr;
    
    		auto curr = head;
    		auto currCopy = headCopy;
    
    		while (curr)
    		{
    			currCopy->random = map[curr->random];
    			curr = curr->next;
    			currCopy = currCopy->next;
    		}
    
    		return headCopy;
    	}
    };
    

Log in to reply
 

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