Post date: Aug 03, 2013 11:6:36 PM
Problem
I have heard this question many times in microsoft interviews.
Given two arrays find the intersection of those two arrays.
Besides using hash table can we attain the same time complexity that is O(m+n) by using some other approach.
Solution
1. Construct a tree for the first array
2. Find an element in the second array in the tree
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the intersection of those two arrays without hash
Created Date : 04-August-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <set>
#include <cassert>
using namespace std;
typedef struct binTree
{
int key;
bool first;
struct binTree* left;
struct binTree* right;
}BinTree;
BinTree* NewBinTreeNode(int value, bool first)
{
BinTree *node = new BinTree;
node->key = value;
node->first = first;
node->left = NULL;
node->right = NULL;
return node;
}
void AddBinTreeNode(BinTree **root, int value, bool first, set<int>& intersection)
{
if(*root == NULL){
*root = NewBinTreeNode(value, first);
}
else{
if(value < (*root)->key){
if((*root)->left == NULL){
(*root)->left = NewBinTreeNode(value, first);
}
else{
AddBinTreeNode(&((*root)->left), value, first, intersection);
}
}
else{
if((*root)->right == NULL){
if((*root)->key != value && first){
(*root)->right = NewBinTreeNode(value, first);
}
if((*root)->key == value && !first){
intersection.insert(value);
}
}
else{
if((*root)->key != value && first){
AddBinTreeNode(&((*root)->right), value, first, intersection);
}
if((*root)->key == value && !first){
intersection.insert(value);
}
}
}
}
}
void DelTree(BinTree *root)
{
if(root == NULL) return;
DelTree(root->left);
DelTree(root->right);
delete root;
}
void DoTest(int* arr1, int len1, int* arr2, int len2)
{
assert(arr1 != NULL && len1 > 0);
assert(arr2 != NULL && len2 > 0);
cout << "The first array is " << endl;
for(int i = 0; i < len1; ++i){
cout << setw(4) << arr1[i];
}
cout << endl;
cout << "The second array is " << endl;
for(int i = 0; i < len2; ++i){
cout << setw(4) << arr2[i];
}
cout << endl;
BinTree* root = NULL;
set<int> intersection;
for(int i = 0; i < len1; ++i){
AddBinTreeNode(&root, arr1[i], true, intersection);
}
for(int i = 0; i < len2; ++i){
AddBinTreeNode(&root, arr2[i], false, intersection);
}
cout << "The intersction is " << endl;
for(auto it = intersection.begin(); it != intersection.end(); ++it){
cout << setw(4) << *it;
}
cout << endl;
DelTree(root);
cout << "----------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr0[] = { 34, 8, 10, 3, 2, 80, 30, 33, 1};
int arr1[] = { 1, 2, 3,4,5,6,7,8,9};
DoTest(arr0, sizeof(arr1)/ sizeof(arr1[0]), arr1, sizeof(arr1)/ sizeof(arr1[0]));
int arr2[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1};
int arr3[] = { 1,2,3,4,5,6,7,8,9};
DoTest(arr2, sizeof(arr2)/ sizeof(arr2[0]), arr3, sizeof(arr3)/ sizeof(arr3[0]));
int arr4[] = { 10};
int arr5[] = { 1,2,3,4,5,6,7,8,9};
DoTest(arr4, sizeof(arr4)/ sizeof(arr4[0]), arr5, sizeof(arr5)/ sizeof(arr5[0]));
return 0;
}
Output
The first array is
34 8 10 3 2 80 30 33 1
The second array is
1 2 3 4 5 6 7 8 9
The intersction is
1 2 3 8
----------------------------------
The first array is
9 8 7 6 5 4 3 2 1
The second array is
1 2 3 4 5 6 7 8 9
The intersction is
1 2 3 4 5 6 7 8 9
----------------------------------
The first array is
10
The second array is
1 2 3 4 5 6 7 8 9
The intersction is
----------------------------------
Press any key to continue . . .