CareerCup

Here is the working code....I tried to test all the test cases....please let me know if it breaks somewhere

import java.util.*;
public class Test {

public static void main(String[] args) {
String[] A = { "apple", "banana", "mango", "potato","apple","potato" };
String[] B= { "apple", "brinjal", "mango", "Raadish","onion","banana","apple" };
String [] C=getIntersection(A,B);
for(String s: C)
System.out.println(s);
}




public static String[] getIntersection(String[] A,String[] B){
int len;
len=A.length>B.length?A.length:B.length; //get the upper bound of length
Map<Mark,Integer> map=new HashMap<Mark,Integer>();
for(int i=0;i<len;i++){
if(i<A.length){
if(map.containsKey(new Mark(A[i],1))) //if map has entry with same string from B add one to it
map.put(new Mark(A[i],1),(map.get(new Mark(A[i],1))+1));
else if (!map.containsKey(new Mark(A[i],0))) //else add the string as A's entry
map.put(new Mark(A[i],0),1);
}
if(i<B.length){
if(map.containsKey(new Mark(B[i],0))) //if map has entry with same string from A add one to it
map.put(new Mark(B[i],0),(map.get(new Mark(B[i],0))+1));
else if (!map.containsKey(new Mark(B[i],1))) //else add the string as A's entry
map.put(new Mark(B[i],1),1);
}
}
ArrayList<String> arr=new ArrayList<String>();
for(Mark m: map.keySet()){
if(map.get(m)>1)
arr.add(m.s); //add in arraylist as we are not sure how much strings are there, creating bigger array may be a bad idea
}
String[] strarr=new String[arr.size()];
arr.toArray(strarr);
return strarr;
}

}

//class Mark used as key in map, No fancy error checking, no optimization done for hashcode.
class Mark{
String s;
int flag;
Mark(String s1,int b){
s=s1;
flag=b; //Here flag=1 represents String B arrays entry and flag=0 represents String A arrays entry
}
public boolean equals(Object o){
Mark m=(Mark)o;
return (this.s).equals(m.s) && this.flag==m.flag;
}
public int hashCode(){
return 5;
}
}

string[] A = { "apple", "banana", "mango", "potato","apple" };
string[] B = { "apple", "brinjal", "mango", "Raadish","onion","banana" };
string[] temp=new string[10];
Hashtable hash = new Hashtable();
for (int i = 0; i < A.Length; i++)
{

hash[A[i]] = i;

}
int k = 0;

for (int j = 0; j < B.Length; j++)
{
if (hash.Contains(B[j]))
{
temp[k] = B[j];
k++;
}

}

for (int i = 0; i < temp.Length; i++)
{
Console.WriteLine(temp[i]);

}

How can you do it without 2 loops... ??

vector<string> a,b,out;
set<string> hash;

vector<string> const_iterator i;

for(i = a.begin() ; i!= a.end() ; ++i)
{
  hash.insert(*i);
}

for(i=b.begin() ; i!= b.end() ; ++i)
{
 if(hash.find(*i) != hash.end())
   out.push_back(*i);
}

// out is the output vector

Use recursion! XD

But seriously if we want to stay away from O(Na x Nb) complexity I would sort both lists. Then we use a while loop with two pointers: i and j
While i < len(A) and j < len(B):

if A[i] = B[j]:
add it to an output array

elif A[i] < B[j]:
i ++

elif B[j] < A[i]:
j ++

else:
error

That should give us worst case complexity: Na log(Na) + Nb log(Nb) + (Na + Nb)

pick first array,build a trie using all strings in it, then for each string in second array do a trie lookup. insertion and search in trie is O(l) where l is the length of string.

look on this logic:
to do this question in one loop we ave to take some extra space okay so
suppose i define a node like this:
struct node
{
char item;
int list1;
int list2;
};
now just use it like hash map take a array of struct node
struct node hashmap[256];
or whatever size accord to alphabets in strings so now in just one loop u can do have to chcek that if both list1 and list 2 are 1 then take in the resul other wise do traverse the list
code of this
struct node hash[256];
// s3 is the output :)
void intersect(char *s1,char *s2,char *s3)
{
int n1,n2,i,j;
n1=strlen(s1);
n2=strlen(s2);
for(i=0;i<n1||i<n2;i++)
{
if(i<n1)
{
if(hash[s1[i]]->list2&&!hash[s1[i]]->list1)
{
s3[j++]=s1[i];
hash[s1]->list1=1;
}
else
{
hash[s1[i]]->list1=1;
}
}
if(i<n2)
{
if(hash[s2[i]]->list1&&!hash[s2[i]]->list2)
{
s3[j++]=s2[i];
hash[s2[i]]->ist2=1;
}
else
{
hash[s2[i]]->list2=1;
}


}


}

}

//Here it is in Java :)

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Map;

public class TestIntersection {

public static void main(String[] args) {
String[] A = { "apple", "banana", "mango", "potato","apple","potato" };
String[] B= { "apple", "brinjal", "mango", "Raadish","onion","banana","apple" };
String [] C= getIntersection(A,B);
for(String s: C)
System.out.println("C: " + s);
}

public static String[] getIntersection( String[] a, String[] b)
{
ArrayList<String> foo = new ArrayList<String>();
HashMap mappy = new HashMap();
int sizeOfa = a.length;
int sizeOfb = b.length;
for( int i = 0; i < sizeOfa + sizeOfb; i++)
{
if(i < sizeOfa){
if(mappy.get(a[i]) == null){
mappy.put(a[i], "0");
System.out.println("Putting : " + a[i]);
}
}else{
String bElem = b[i-sizeOfa];
if(mappy.containsKey(bElem)){
if ( ((String)mappy.get(bElem)).equals("0") ){
mappy.put(bElem, "1");
foo.add(bElem);
}
}

}
}
return foo.toArray(new String[0]);
}

}

I was asked a similar question for a Google interview - but without the requirement that there has to be only one loop.

But in the followup question I was asked what if the two are sorted? In that case one can use only one loop instead of two.

Any question starts in humble manner, which will be subsequently tweaked or made completex, to see how you perform..
This problem is a pure a trade off between speed and space.. when sorted, is it the simplest to solve.

can somebody describe the question with an example plz?? thanx.

package main.java.test;

import java.util.HashMap;

public class IntersectionImpl {

public static void main(String[] args) {
String[] f = { "1", "2", "9", "19", "29", "44", "0" };
String[] s = { "10", "20", "90", "19", "290", "440", "100" };
intersection(f, s);


}

private static void intersection(String[] a, String[] b) {
int sizeOfA = a.length;
int sizeOfB = b.length;

int len = sizeOfA + sizeOfB;
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < len; i++) {
if (i < sizeOfA) {

map.put(a[i], 0);

} else {
if (map.get(b[i-sizeOfA]) == null) {
map.put(b[i-sizeOfA], 0);
} else {
System.out
.println("Intersection has been found at:" + (i-sizeOfA)+" element of array b which is "+b[i-sizeOfA]);
}
}
}

}
}

1. Sort both arrays
2. Initialize the index S1 = 0, S2 =0;
while(true)
{

if( value at s1 < value at 2)
s1++;
else if ( value at s1 > value at s2)
s2++;
else
print this information

if(s1 is out of bound || s2 is out of bound)
break;
}

void intersectionOfArrays(int a[],int b[])
{
List list =new ArrayList() ;
List intersection =new ArrayList();
for (int i = 0; i < a.length; i++) {
list.add(a[i]);
}
for (int i = 0; i < b.length; i++) {
if(list.contains(b[i]))
intersection.add(b[i]);
}
System.out.println(intersection+"");
}
just use stirng rather than integer array

import java.util.Enumeration;
import java.util.Hashtable;
class HashT
{
public static void main(String[] args)
{
String[] A = { "apple", "banana", "mango", "potato","apple" };
String[] B = { "apple", "brinjal", "mango", "Raadish","onion","banana" };
 
Hashtable hash = new Hashtable();
for (int i = 0; i < A.length; i++)
hash.put(A[i],0);
 
for (int j = 0; j < B.length; j++)
if (hash.containsKey(B[j]))
hash.put(B[j],1);
else
hash.put(B[j],0);
 
Enumeration e=hash.keys();
while(e.hasMoreElements())
{
String tr = (String) e.nextElement();
System.out.println(tr+"\t"+hash.get(tr));
}
}
}

output:
banana 1
apple 1
Raadish 0
onion 0
brinjal 0
potato 0
mango 1

those keys with value 1 are present in both the arrays

String[] intersect(String[] A, String[] B) {

   List result =  org.apache.commons.collections.ListUtils.intersect(java.util.Arrays.asList(A), java.util.Arrays.asList(B));
return list.toArray(new String[0]);

}

given string length m and n, the lower bound for complexity is Theta(m+n). I don't see any points about " without 2 loops ". You may use some fancy API or algorithm on the surface, but in theory, you just HAVE to traverse them all.