Well I had this question at job interview for google, or rather I received a phonecall by someone claiming it was for an interview. They presented some questions and one of them was to implement some code using only pen&paper (I thought it was odd to ask it that way, but back in 2007 I accepted the challange anyway)

They asked me to implement a set using arrays or std::vector. It contains only unique integers and I had to implement A union B \ A intersect B.

I had only 20 minutes to solve it and only a pen and paper (no pc, no internet). And write proper c++ code that handles empty arrays and variable size arrays.

The code I came up with was not optimal and larger than needed, but it did work and you can take a peep at it here (as requested it had to handle empty and variable size arrays and did not have to be optimal code): intersect.cpp. Though I was not satisfied with the runtime complexity off O(N*M) for arrays A and B of lengths N and M respectively (because of the nested forloop used to get the intersection). So I came up with a more optimal solution.

By just concatenating A and B, sorting it and then removing duplicates we have performed the same operation but then in O( (N+M) * log(N+M) ) average case (worst case for the sort can still be O( (N+M)^2 ).

typedef vector array;

void unionMinusIntersect( const array& a, const array& b, array& result ){
  result.assign( a.begin(), a.end() );                  // result = a; element copy
  result.insert( result.end(), b.begin(), b.end() );    // append elements in b to result

  sort( result.begin(), result.end() ); //sort to quickly find unique elements to remove
  
  //we loop and remove all duplicates (both elements so for 122466 we remove 22 and 66, leaving 14
  array::iterator pos = result.begin();
  while( pos!=result.end() ){
    if( ((pos+1) != result.end()) && 
        (*pos == *(pos+1)) ){
        array::iterator newpos = pos-1;
        result.erase( pos, pos+2 );  //removes at pos and pos+1
        pos = newpos;
    }
    pos++;
  }  
}

Here is the complete optimized file optimized.cpp.

And some output:

walter-schreppers-computer:~ wschrep$ ./optimized 
A= 1 2 3 6 
B= 2 3 5 6 
unionMinusIntersect (A,B,result)= 1 5 
testing empty inputs... done.

Back to archive