CareerCup

I think xor method can be applied even for objects provided , we XOR that attributes of object from which equivalence of object is defined. :)

for. e.g

struct point
{
   int x , int y , int z
};

x = all X xored;
y = all Y xored;
z = all z xored;

What do you mean by "even for objects provided" -> that's only true for special cases. What if my object is of the class -

Class Foo{
    private:
         int c;
         string goo;
    public:
         int d;
         string metoo;
}

For the generic term object, I cannot think beyond dict/map/hashtables. Unless the interviewer boils down the definition of his objects to a level that I can play the XOR trickery.

I am not clear about the question. why can't you just go over the array and use a hashmap to find the count of each element.It's just O(n). And what is this XOR solution?

Yes the interviewer wanted the most generic answer, when object could be absolutely any kind of object.When I said I would use hashtable he seemed to agree to it.

Each Object would have a different hashcode so it would me mapped to different key. This may be a problem...

If the hashcodes are same then we can still go for XOR on hashcodes of the object . In this case we can save space..ie the problem can be still solved in O(n) time and O(1) space.

What is the XOR Solution?

Please describe the xor solution.

import java.util.HashMap;
import java.util.Iterator;


public class odd_count_of_a_number_in_ll {

/**
* @param args
*/

static HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();

static class node
{
int info;
node link;
public node(int info)
{
this.info=info;
link=null;
}
}

public static node insert(node root,int val)
{
node n= new node(val);
if(root == null)
return n;

node cur=root;
while(cur.link!=null)
cur=cur.link;
cur.link=n;
return root;

}


public static void inserthm(node root)
{
node ptr=root;
while(ptr!=null)
{
int tmp=ptr.info;
if(hm.get(tmp)== null)
hm.put(tmp, 1);
else
hm.put(tmp, hm.get(tmp)+1);
ptr=ptr.link;
}
}


public static int chk()
{
Iterator<Integer> it = hm.keySet().iterator();
int tmp;
while(it.hasNext())
{
int key = it.next();
int val = hm.get(key);
if(val%2 != 0)
return key;
}
return -1;
}


public static void print()
{
Iterator<Integer> it = hm.keySet().iterator();

while(it.hasNext())
{
int key = it.next();
int val = hm.get(key);
System.out.println("key::"+key+" value::"+val);

}

}



public static void main(String[] args)
{
node root = new node(1);
root=insert(root, 2);
root=insert(root, 1);
root=insert(root, 2);
root=insert(root, 3);
root=insert(root, 4);
root=insert(root, 4);


node troot=root;
while(troot!=null)
{
System.out.println("ll ::"+troot.info);
troot=troot.link;
}

inserthm(root);
int tmp1;


print();

tmp1 = chk();
if(tmp1== -1)
{
System.out.println("All values are of even count");
}
else
{
System.out.println("Value that has odd count ::"+tmp1);
}
root=root.link;





}
}

Can we XOR the address of the object as every object has unique address.