CareerCup

Why not use the generic algorithms for set in STL?

const int SET_SZ = 12;
const int iArray1 [12] = { 100, 150, 200, 250, 225, 300,
325, 125, 400, 175, 600, 50 };
const int iArray2 [12] = { 275, 300, 325, 350, 375, 400,
75, 25, 450, 575, 600, 550 };

set<int> s1( iArray1, iArray1 + SET_SZ );
set<int> s2( iArray2, iArray2 + SET_SZ );
set<int> sr;

cout << "Computed intersection: " << endl;
set_intersection( s1.begin(), s1.end(),
s2.begin(), s2.end(),
ostream_iterator<int>(cout, ",") );

cout << endl << "Computed Union: " << endl;
set_union( s1.begin(), s1.end(),
s2.begin(), s2.end(),
ostream_iterator<int>(cout, ",") );

cout << endl << "Computed Difference: " << endl;
set_difference( s1.begin(), s1.end(),
s2.begin(), s2.end(),
ostream_iterator<int>(cout, ",") );

- STL Answer February 21, 2008 | Flag Reply

Bucket or hash array 1 using any standard indexing mechanism and use this index against 2nd array

- bnp July 19, 2007 | Flag Reply

bnp, do you mind elaborating?

- cb July 31, 2007 | Flag Reply

Complexity O(nlogn) ... Google onsite question

- Ani August 11, 2007 | Flag Reply

O( n log n ) is too slow. bnp's solution is better.

- been there September 01, 2007 | Flag Reply

I was asked same question for yahoo phone interview.....He was not satisfied with merge sort solution as it will require more space also....he was expecting solution without sorting so I think BNP solution is good fit for it. But more explanation is awaited...

- sp101 September 01, 2007 | Flag Reply

BNP can u elaborate please?

- Java Coder November 26, 2007 | Flag Reply

store array 1 and array 2 as a hashed array using the same standard function. O(n)

take indexes of array 1 to get the keys from array 2. O(n)

If it exists then there is a match i.e. intersection

- fish December 03, 2007 | Flag Reply

If buffer is allowed, then hash table will do. 0(n)

If no buffer is allowed, I can only think of merge sort. Any better idea?

- Lindos February 24, 2008 | Flag Reply

If someone could explain, Hows does the Hashtable / Hashset method work in O(n)?

Is this the correct implementation for that?

import java.util.*;

public class hash
{
public static void main( String[] args )
{
HashSet<String> set1 = new HashSet<String>();
set1.add( "ape" );
set1.add( "cat" );
set1.add( "bat" );

HashSet<String> set2 = new HashSet<String>();
set2.add( "bat" );
set2.add( "fox" );
set2.add( "ape" );

System.out.println( "1 = " + set1 + ", 2 = " + set2 );


set1.retainAll(set2); //Keep entries which exist in both
System.out.println( "Intersection = " + set1);

}
}

- Ronin February 24, 2008 | Flag Reply

Treeset is better for numbers as it sorts at insertion stage {{{ int[] arr1 = {1,2,3,4,5,6}; int[] arr2 = {5,6,7,8,9}; int[] arr3 = new int[arr1.length+arr2.length]; TreeSet h1 = new TreeSet(); for(int i=0;i<arr1.length;i++) { h1.add(arr1[i]); } for(int i=0;i<arr2.length;i++) { h1.add(arr2[i]); } Object[] obj = h1.toArray(); int[] intObj = new int[obj.length]; for(int i=0;i<obj.length;i++) { intObj[i] = (Integer)obj[i]; System.out.println(intObj[i]); } - Shree March 19, 2008 | Flag Reply

For Array1, Sort it using any Sorting mechanism and for Array2, use binary search for getting the intersaction.

- Puranik June 06, 2008 | Flag Reply