CareerCup

there is an easier solution for question 2:

int result = arr[0];
for(int i = 1;i < 199;i ++)result = result XOR arr[i];
return result;

when integer -> string, just extending the operator XOR would be OK.

hey was this for the phone interview or the onsite?

Also in your question do the numbers lie between 0 and 199?

Access time for hash table O(1), insert time O(1)

2 solutions for above question ( one with using hash map, 1 without using hashmap)

1. Without using HashMap
- Sort the list O(nlgn)
- Keep a counter c = 0, last digit = -1
Start scanning the list
if(lastDigit!= arr[i])
{ if(c==1)
{
print lastDigit;
lastDigit = arr[i];
c=1;
}
}
else
c++;
- Check separately for last number of array


Algorithm 2 : With HashMap
1. Insert all elements in hash map with value = 0
2. start scanning the array, search elements and increment count
hashmap[arr[i]]++;
3. start the scan again
if hashmap[arr[i]] == 1
print it.

It is very basic pseudo code, not in any specific language, customize it in the language you want.

One solution that came into my mind was to prepare a trie. If you get a string, insert into the trie. If you get the string again, delete the node from trie. At the end, we will left with only one string, which is the answer.

another is to get int[] for each string. and then simply xor. It does not include extra memory as well

Item* Reverse(Item* head)
{
if (!head || !head->next)
return head;
Item* last = head;
Item* newHead = head->next;
last->next = NULL;

while (newHead)
{
Item* temp = newHead;
newHead = newHead->next;
temp->next = last;
last = temp;
}
newHead = last;
return newHead;
}

Item* Reverse2(Item* head)
{
if (!head || !head->next)
return head;

Item* temp = head->next;
Item* newHead = Reverse2(head->next);
temp->next = head;
head->next = NULL;
return newHead;
}

Quote
when integer -> string, just extending the operator XOR would be OK.
UnQuote
I dont understand your point SunDavid.S
Please illaborate.

(1)best case = O(1); worst case = O(n);

(2)answer ^= a[i];

If there are numbers from 1 to 99 in the array...solution can be... Traverse the entire array...when a number is reached suppose n set, suppose array[n] is set to k, then set it to -k (i.e. it's negative value). When it is reached again, reset it to it's positive value. Again traverse array from 1 to 99 and see which index is still negative...that is the answer! Time O(n) and no extra space.

SunDavid.s is using:

((((a XOR b ) XOR c) XOR a) XOR c)
= (((( a XOR a) XOR b) XOR b) XOR c)
= ((( 0 XOR b) XOR b) XOR c)
= ( ( b XOR b) XOR c)
= (0 XOR c)
= c

Here when you do XOR of any number it does XOR(^) in the bits.
So finally when entire array is XORed,it will have bits left of the number which is not repeated and all other bits will be zeroed out by XOR.
For e.g if you have array [9] = {1,2,3,4,5,3,2,1,4}
Here array[0] = 1.
1 ^ 2 = 3
3 ^ 3 = 0
0 ^ 4 = 4
4 ^ 5 = 1
1 ^ 3 = 2
2 ^ 2 = 0
0 ^ 1 = 1
1 ^ 4 = 5
So, Final result is 5.

for question 3:


void ReverseLinkedList(Node **head)
{
Node *curEl = *head, *prevEl = NULL, *nextEl = NULL;

while(curEl)
{
*head = curEl;
nextEl = curEl->next;
curEl->next = prevEl;
prevEl = curEl;
curEl = nextEl;
}
}

I think extending the xor operator for string means :
implementing a function xorString to take two strings s1 and s2
-- it iterates through the characters of the strings s1 ans s2 and xors them .
-- and finally the result will be the concatenated value of these xor results .

XOR is the only answer you should give for such kind of interviews if you want to make a good impression upon the interviewer else do whatever you want and dont waste our time.

I think the answer remains same whether it is an integer or a string cause XOR is a bit wise operator and eventually everything (string or integer) is saved in bits.

let us consider 6 numbers with 2 repeated
1 4 3 4 5 3

3 & 4 are repeated.

XOR everything 1 ^ 4 = 5 ^ 3 = 6 ^ 4 = 2 ^ 5 = 1 ^ 3 = 2

Most of the above answers are for question "Find one & only one non-repeating number from an array.

I think for string, the XOR method doesn't work, because you can't restore the original string from the XOR results at the end

XOR indeed can be used for strings.

1. xor all strings' hashcode
2. Scan the strings to find one whose hashcode equals to the xor result.

Okay, here's what the function for xor strings should be like:
But, it's behaving weird, I'm gonna take a break, in the meantime..if somebody can spot, the bug, well, bingo then !

char * xorStrings(char *str1, char *str2){
	int i=0, n;
	int lenCommon;
	char *strShort, *strLong, *strXor;

	strShort = (strlen(str1) > strlen(str2))?str2:str1;
	strLong = (strlen(str1) > strlen(str2))?str1:str2;

	i = 0;
	lenCommon = strlen(strShort);
	n = strlen(strLong);
	strXor = (char*)malloc((size_t)sizeof(char) * (n+1));
	n -= lenCommon;


	while(lenCommon-- ){
		strXor[i] = strLong[i] ^ strShort[i];
		i++;
	}

	while(n--){
		strXor[i] = strLong[i] ^ 0;
		i++;
	}
	strXor[i] = '\0';
	return strXor;
}