Yahoo Interview Question
Software Engineer / DevelopersDo XOR between 2 consecutive elements - n/2 operations
Worst case. XOR result will not be zero. Then take first 4 (2 windows) elements. Do 4 comparisons to get the non-unique number.
Total worst case = n/2+4 operations.
your logic won't work for the following example:
1,2,1,2,1,2,1,2,3,2
here XOR is non zero for all the elements
non unique number in first 4 is 1 and 2.
I think it's pretty simple.
Need to consider only three possibilities.
1) Numbers are arranged alternatively as in x1-U-x2-U-x3-U..
2) Number is of the form U-x1-x2-U
3) Any other combination.
Now we need to do only this:
While iterating each element check whether:
a) its equal to its next value, or
b) its equal to its next to next value, or
c) its equal to its next to next to next value.
Hence O(n)
Yes. Because 1 appears only 2 times here. The questions says the number must repeat n/2 ,i.e, 3 times. Put one more 1 anywhere in the sequence and my solution will work.
We can have two temp variables to store the element of the array at the time when we traversing, since there is 1 element with n/2 occurences and other elements are all unique, at some point when we found the two temp variables are the same (or when we found same value when replacing a temp variable with the element in the array), that is the non-unique element ( this will always happen as well )
Let's assume the elements are in integer type
// assume n > 2, it's trivial if n <= 2
public int NonUniqueElement(int* arr, int n)
{
int* tempArr = new int[2];
tempArr[0] = arr[0];
tempArr[1] = arr[1];
ind = 2;
int tmpInd = 0;
while(ind < n)
{
if((tempArr[0] == tempArr[1])
||(tempArr[tmpInd] == arr[ind]))
{
return tempArr[0];
}
tempArr[tmpInd] = arr[ind];
tmpInd = (tmpInd+1)%2;
ind++;
}
// this shouldn't happen
return -inf;
}
We can keep a window of size 3 and move it over the entire input array. It will always happen that non-unique element will occur twice or thrice in some window.
The time complexity is O(N).
-The above code is simply using this fact.
Keep a counter (maximum number of occurences found so far) and one or that element. Make a hash map. Traverse through the array, for a particular element check if it exists in a hash map, if yes increase the value field by 1 and check if that is the greater than the counter..Replace if yes..in the end the counter would have the number and the other var would have the element.
your logic won't work for the following example:
1,2,1,2,1,2,1,2,3,2
here XOR is non zero for all the elements
non unique number in first 4 is 1 and 2,
In the problem it is clearly mentioned that the n/2 elements are unique.
So the input 1,2,1,2,1,2,1,2,3,2 is not correct according to problem definition.
Total worst case = n/2+4 operations.(looks correct).
Correct me if I am wrong.
I think it's pretty simple.
Define the whole array in a set of two:
i.e. a[10] = {(a,b),(c,d),(e,f),(g,h),(i,j)}
so there is only one distinct possibility of having the unique element in each set once.
so the code would be like:
for(i=0;i<n;i=i+2)
if(a[i]=a[i+1])
unique = a[i];
if(unique == NULL)
check(which number is repeating in first two sets, i.e. 4 numbers)
This is based on the property of the majority element in an array. Google: array majority element and see the solution.
The credit goes to the person who posted the algorithm. I am just pasting the code for convenience:
int find_majority(int *a, int n)
{
int count = 1;
int currentIndex = 0;
int i;
for (i = 1 ; i < n; i ++)
{
if (a[i] == a[currentIndex])
count++;
else
count--;
if (count == 0)
{
currentIndex = i;
count = 1;
}
}
return a[currentIndex];
}
Majority element means that it has to occur n/2+1 times, here it is only n/2. Your solution will fail for alternating elements, like 1-2-1-3.
The only solution that comes to my mind is with window of size 4 and checking whether there are any two elements that are same in that window. Please post if there is a better algorithm available.
The key here is that the other n/2 elements are unique. (If they're not, it'd be a bit harder)
With space :
Use HashSet, if you find an element twice, then this is the element...(since all other elements are unique, none of them can repeat)
Without space :
A 3-element window should work. We slide the window over the array until we find a window with an element repeated twice or thrice >> that's our element.
It works because the n/2 other elements are UNIQUE.
public class n2uniqeandn2repeatsameElement {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]= {1,2,3,4,1,1,1,1,5,6};
int i =0;
int l= a.length;
if(a[i]==a[l-1]||a[i]==a[l-2]||a[i+1]==a[l-1])
{
System.out.println( a[i]);
}
else
{
while(i+1<l)
{
if(a[i]==a[i+1])
{
System.out.println(a[i]);
break;
}
else
i++;
}
}
}
}
int run()
{
///int A[] = {1, 3, 5, 2, 2, 2};
///int A[] = {2, 1, 3, 5, 2, 2};
int A[] = {2, 1, 2, 3, 2, 5};
int more = A[0];
for(int i = 1; i < sizeof(A)/sizeof(A[0]); i ++)
{
if((A[i] == more) || (A[i] == A[0])) {printf("X number is : %d\n", A[i]); break;}
else more = A[i];
}
return 0;
}
Find one occurrence where two consecutive numbers are the same, that's the non-unique number. O(n) comparisons.
The only case where there won't be any pair of the non-unique number (with n/2 occurrences) will be when they are all on all odd or all even positions in the array.
Eg [1,100,2,100,3,100,4] OR [100,1,100,2,100,30]. In this case just compare the first and the third number, if they are the same first number is the non-unique number else the second one is. 1 more comparison.
So worst case will be n+1 comparisons, which is O(n)
With space, hashtable Time: O(n) Space: O(n)
- Anonymous November 04, 2010Without space, check wether head and tail are the same,
if same, then we know the non-unique element.
if not, we compare three elements at one time to find out the non-unique element.
Time: O(n), Space: No.