Yahoo Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
2
of 2 vote

With space, hashtable Time: O(n) Space: O(n)
Without 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.

- Anonymous November 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Do 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.

- V September 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous October 23, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

understand the question first please

- Terry November 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- chandransuraj February 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

will your solution still hold for 1,2,3,4,5,1?

- son_of_a_thread August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

By the way its me(chandransuraj) posted by mistakes as anonymous

- chandransuraj August 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Nat September 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code has bug: does not work for ABCADA. In fact I think this method is wrong.

- papaya September 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int Find_NonUnique(int *a,int n)
{
int i;
if(n < 4)
return 0;
for(i = 0 ;i < n-1 ;i += 2)
if(a[i] == a[i+1])
return a[i];
if(a[0] == a[2] || a[0] == a[3])
return a[0];
else if(a[1] == a[2] || a[1] == a[3])
return a[1];
}

- Venkat September 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- cool September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It fails for 3453

- TheSnoopyMe September 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we simply just find the median number? The (expected) algorithm complexity in this case is in linear order.

- BXH September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can just use a Hashtable and go through the array,entering every value into the Hashtable if not present yet, first duplicate we find is a non-unique value.

- Anonymous September 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous November 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Mustafa January 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Rashmit April 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Never mind

- chandransuraj August 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

- Anonymous April 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ibakar August 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Majority element doesn't means that the number has to be repeated more than n/2 times.It simply means that the element which repeats the max time in the array

- bashrc June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
     int i, element;
     int arr[8] = {2, 3, 4, 5, 1, 1, 1, 1};
     for (i = 2; i < 8; i++) {
     if   (arr[i] == arr[i-1] || arr[i] == arr[i-2]) {
               element = i;
          }
     }
     printf("%d\t", arr[element]);
}

- code February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- moh.ezz8 March 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if u use 3 window method how will it work for 1,2,3,1

- praneethreddybokka March 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}
}
}

}

- praneethreddy.bokka March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- zombie June 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sendtonirav February 02, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More