Cracking The Coding Interview/Q 2.1

From Software Engineers Wiki
Jump to: navigation, search

Write code to remove duplicates from an unsorted linked list.

How would you solve this problem if a temporary buffer is not allowed?

Answer #1

The brute-force implementation is, for each element, to traverse the remaining part of the list, and to remove the any duplicate. You need to be careful when removing an element. When the element is removed, the iterator pointing to the element is no longer valid. To traverse the list using the iterator, it needs to be moved back and find the next element in the list.

void remove_dup(std::list<int> &rlist)
{
        std::list<int>::iterator ir, ir2;

        for (ir = rlist.begin(); ir != rlist.end(); ++ir) {
                ir2 = ir;
                ++ir2;
                for (; ir2 != rlist.end(); ++ir2) {
                        if (*ir == *ir2) {
                                auto irtmp = ir2;
                                --irtmp;
                                rlist.erase(ir2);
                                ir2 = irtmp;
                        }
                }
        }
}

A test program:

void print_list(std::list<int> &rlist)
{
        std::list<int>::iterator il;

        for (il = rlist.begin(); il != rlist.end(); ++il)
                std::cout << *il << " ";

        std::cout << std::endl;
}

int main(void)
{       
        std::list<int> intlist { 9, 7, 5, 3, 1, 0, 0, 8, 6, 4, 2, 5, 1, 6, 2, 2 };

        print_list(intlist);
        remove_dup(intlist);
        print_list(intlist);
        
        return 0;
}       

And the test result:

9 7 5 3 1 0 0 8 6 4 2 5 1 6 2 2 
9 7 5 3 1 0 8 6 4 2 

Answer #2

Another implementation is making use of hash set. For each element, add the element to the hashmap. If the entry already exists in the hash map, do not add and remove it from the list. In C++, std::unordered_set<> implements a hash set where each elements are unique.

void remove_dup(std::list<int> &rlist)
{
        std::list<int>::iterator ir;
        std::unordered_set<int> hs;
        std::unordered_set<int>::iterator hs_ir;

        for (ir = rlist.begin(); ir != rlist.end(); ++ir) {
                if ((hs_ir = hs.find(*ir)) != hs.end()) {
                        auto irtmp = ir;
                        --irtmp;
                        rlist.erase(ir);
                        ir = irtmp;
                } else {
                        hs.insert(*ir);
                }
        }
}

The test result is same as above.

9 7 5 3 1 0 0 8 6 4 2 5 1 6 2 2 
9 7 5 3 1 0 8 6 4 2 
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox