CareerCup

It should be a HashMap, with key=numbers and value=count;
One HashMap for each stream. There is a another HashSet for the final calculation.

Consider these two stream are two FIFO queue. The actions can be enqueue and dequeue, each action will affect its corresponding hashmap and the final hashset.

Sort both the arrays using quick sort.
It takes O(nlogn) operations.
Take two indexes i and j for the arrays
while(i < size1 && j < size2)
{
if(a[i]==b[j])
{ printf("%d\n",a[i]);i++;j++}
if(a[i]<b[j]) i++;
if(a[i]>b[j]) j++;
continue;
}

we are talking about a stream of integers, so i would think either list could grow over time, so taking a LL or array approach is wrong in that case.
Here is a O(n) algorithm, assuming we can use extra space:
build a hash as we traverse elements from both lists A and B.
if an element is not in the list, just put it in the hash with value A if we are traversing A or B otherwise.
if the element is in the list already, if it maps to A and element is in A, do nothing. if the element is in the other list, right it down as part of the intersection, and change the value it maps to to "Both".
Thats only O(n).

There doesn't appear to be a justification for sorting. After all, the problem asks to find the intersection; it doesn't mention anything about priorities or sequences.

HashSet appears to be a viable solution; minimal space. If the lists are large, a HashTable may allocate unnecessary memory upfront, causing a memory leak.

construct the BST with larger array and search the elements in the smaller array in BST, if found print or store those numbers which are nothing but insersection.

arrays a[m],b[n] with m>n
constructing BST for 'a' would take O(log m) and searching the elements in 'b' would take O(n log m)... sounds reasonable.

Any comments??

Create 2 Bit Maps one each for the List. For example, for the list 24 45 56 12 34, will set the bits 24, 45 56 12 and 34. Do the same for the second list and set the corresponding bits in the second bit map. ANDing of the bit maps should give you the intersection. I think this should work without any sorting.

hi, Indian
I didn't get your solution. So you change 24 45 ... to 11000 101010 ... and get 2 maps, then do AND?

hey...
i think it all depends on how the lists are coming....
make a data structure in which we can remember from which list the element came
struct node{
int key;
int came_frm;//set as 1 if from A set as 2 if from B and set as 3
}
now make a hash map using this datastruct
node map[MAX];
for each new element if does not exist in the map just check
eg:

insert_fromA(int val)
{
if map[val]->came_frm==0 map[val]->came_frm=1;
else if(map[val]->came_frm==2) map[val]->came_frm=3;
else if(map[val]->came_frm==1) //do nothing;
}


insert_fromB(int val)
{
if map[val]->came_frm==0 map[val]->came_frm=2;
else if(map[val]->came_frm==1) map[val]->came_frm=3;
else if(map[val]->came_frm==2) //do nothing;
}

Print_Intersection(map[])
{
for(map.start to map.end)
if(map[val]->came_frm==3)// put in new set or print or watever
}

i donno how we could implement this map... :( even a RBtree can be made i suppose...with the same datastructure...

and if we have information associated with each record,....we may put some string * or sumthin thr

Use TRIEs instead, and treat integers as strings.... this should do better with nlogk where k=<max_len_of_int_str>

Use TRIEs instead, and treat integers as strings.... this should do better with nlogk where k=<max_len_of_int_str>

Use TRIEs instead, and treat integers as strings.... this should do better with nlogk where k=max_len_of_int_str

Use TRIEs instead, and treat integers as strings.... this should do better with nlogk where k=max_len_of_int_str