Yahoo Interview Question


Country: United States




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

package com.algorithm.amazon;

import java.util.Arrays;

public class DuplicateNumbers {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 1, 2, 2, 2, 2, 4, 3, 2, 5, 6 };
		Arrays.sort(arr);
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] == arr[i - 1]) {
				System.out.println(arr[i]);
				return;
			}
		}

	}

}

- Vir Pratap Uttam April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

can you define two steps?

- aka August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

Arrays.sort(a);
      System.out.println((a[0] == a[4]) ? a[0] : a[5]);

This works assuming Arrays.sort(a) is considered as one step.

- sam.gvp August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but the complexity os o(nlogn) ..

- gopi.komanduri August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

Sure the complexity is O(nlogn). To my knowledge, Number of steps is no way related to the Complexity (space/time). Complexity refers to relative performance of the program. You can write 10 lines of code that still has the complexity of O(n).

If the question is about the Complexity, then O(n) is the best. To be precise, O(6) (which makes no sense) since you will be comparing utmost 6 elements. Also, to my understanding people don't talk about complexity in terms of a specific integer like O(2). It has to be generic like O(n).

- sam.gvp August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

Let us say the array is A.

The good hint to keep in mind is that - out of 10, 5 elements have same value, so if we sort the array these 5 elements can be from any index to that index+4 in the sorted array. But elements in A[4] or A[5] will be one of them for sure. We just need to discard one out of A[4] and A[5].

steps:
1) Sort the array
2) Compare element number 4 and 5 in the sorted array, if a[3] ==a[4] then print [4], else print a[5].

let me know if this is wrong....

- Narendra August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

2,2,2,2,2,3,4,5,6,7
In this case your logic does not work as the 6th element is not the duplicate number.

- Raghvr September 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. sort the array in ascending order : O(nlogn)
2. compare the last 2 elements i.e. a[8] and a[9]
3. if the 2 elements are the same, then that is the repeated element
4. if the 2 elements are different, then a[4] will be the repeated element
(explanation : since the repeated element can be a[4] to a[8], or a[3] to a[7], or a[2] to a[6], or a[1] to a[5], or a[0] to a[4]; in all these possibilities, a[4] will return the repeated element)

- nharryp November 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{
if(a[3]==a[4])
print a[3]
else if(a[4]==a[5])
print a[4]
else
print a[5]
}

- Mukul Bahuguna January 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

step1 short the array
for(int i=0;i<n-1;i++)
{
if(arr[i]==arr[i+1])
{
found;
break;
}
}

- Ashok Gowla August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

There can be three cases:
1. {1,2,3,4,5,7,1,1,1,1} // 1 is the answer
2. {1,2,3,5,9,10,3,3,3,3} // 3 is the answer
3. {1,2,9,9,9,6,7,9,9,4} // 9 is the answer

If we use quick select for the 5th position (5 is half of 10)
Array will be sorted like
1. {1,1,1,1,1, other numbers greater than 1}
2. {numbers less than 3, 3,3,3,3,3, numbers greater than 3}
3. {1,2,7,6,8,9,9,9,9,9}

In any case, you can do quick select for 5th index number.
Then, for case.1 and case.2, you can simply check that there are 5 numbers of this value.
In case.3, all numbers from index.5 to index.9 will be equal.

Codes:

public static int findFiveTimesRepetiveNum(int[] arr) {
	assert(arr != null || arr.length == 10);
	int selectedNum = arr[quickIndexSelect(arr, 5)];
	int count = 0;
	for (int i : arr) {
	  if (i == selectedNum) {
		count++;
	  } 
	}

	if (count == 5) return selectedNum; // It covers case.1 and case.2
	for (int j = 5; j < arr.length; j++) {
	  // In case.2, we need to figrue out all numbers from index 5~inedx.9 are equal
	  if (arr[j] != arr[5]) {
		return -1;
	  }
	}
	return arr[5];
  }
  
  public static void main (String[] args) {
	int[] case1 = new int[]{1,2,3,4,5,7,1,1,1,1};
	int[] case2 = new int[]{1,2,3,5,9,10,3,3,3,3};
	int[] case3 = new int[]{1,2,9,9,9,6,7,9,9,4};
	
	print("Expect 1: " + findFiveTimesRepetiveNum(case1));
	print("Expect 3: " + findFiveTimesRepetiveNum(case2));
	print("Expect 9: " + findFiveTimesRepetiveNum(case3));
	
	int[] canNotFound = new int[]{1,2,3,4,5,6,7,8,9,10};
	print("Expect -1(Can not found): " + findFiveTimesRepetiveNum(canNotFound));

- soodongStudying August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

assumed array index starts from 1 - 10 & array is sorted. if array is NOT sorted then solution is not possible 

if(a[5] == a[6])
	return a[5];	// a[5] & a[6] are part of duplicate sequence
else if(a[4] == a[5])
	return a[5];	// a[1] to a[5] are duplicates
else
	return a[6];	// a[6] to a[10] are duplicates

- Anonymous August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

if(a[4] == a[5] || a[5] == a[6])
	return a[5];	// a[5] is part of duplicate sequence
else
	return a[6];	// a[6] to a[10] are duplicates

- Anonymous August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The obvious idea is to use xor.

In first step, xor every consequitive element and you found the element, if the xor is zero.

There is a problem when same elements are alternate:
1 6 2 6 3 6 4 6 5 6

In this case, xor with next to next element, this will find the element in this special case.

The complexity is O(n)

- Bala January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please gve the final and correct ans

- priyanka December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1: Sort the array.
Step 2: Find the difference between the next index element and the current index element. If the difference is 0, then the number either at current or next index is the repeating number.

Example:

public static void findRepeatingNumber() {
	int[] intArray = new int[10];
	intArray[0] = 27;
	intArray[1] = 91;
	intArray[2] = 84;
	intArray[3] = 71;
	intArray[4] = 65;
	intArray[5] = 71;
	intArray[6] = 31;
	intArray[7] = 71;
	intArray[8] = 71;
	intArray[9] = 71;
	System.out.println("Original Array: " + Arrays.toString(intArray));
	Arrays.sort(intArray);
	System.out.println("Sorted Array: " + Arrays.toString(intArray));
	int diff = 0;
		for (int i = 0; i < 9; i++) {
		diff = intArray[i + 1] - intArray[i];
		if (diff == 0) {
			System.out.println("Repeating number: " + intArray[i]);
			break;
		}
	}
}

- vijayinani August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if there is no restriction on extra space, then have a HashSet and add the values. When ever you encounter a duplicate value, return it.

- 4661 August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1: Calculate sum1 and sum2, where sum1 = all the elements in the array and sum2 is the sum of those 6 six unique numbers.

Step2 : Calculate the repeated number as: repeated_number = (sum1 - sum2) / 4;

- shivshnkr August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

its a finite array,arr[] of length 10
so start by doing a simple algorithm
add i,x element
where x= 10-i
& i = first
add arr[i]+arr[x]=y
then calculate z=y-arr[x]
& do the above step till i=4
if z is common for any, then you got the duplicate entity
if no common value is found, the arr[5], element at index 5 is the duplicate entity :)

- abhushan.26 August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution below is particularly tuned for just this problem (not generic), but serves the purpose for the mentioned problem. The solution i think is basically O(n-1).

public class TwoStep {

	public static void main(String[] args) {
		Integer[] numList = {5,2,1,5,3,4,5,6,5,5};
		
		//we do numList.length-1 so that we don't get the array out of bounds exception when accessing the value at i+1
		for(int i=0; i < numList.length-1 ; i++){	
			//We check if value at i == i+1 
			//or
			// if i-1 >=0 and i-1 == i+1
			//then i+1 should be the matched value
			//since we know there is only one value that is going to be repeated
			//we can break the loop at this point and print out the output
			if((numList[i] == numList[i+1]) || (i-1 >= 0 && numList[i+1] == numList[i-1])){				
				System.out.println(numList[i+1]); 
				break;
			}
		}
	}
}

- jack August 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Friends I have designed this algorithm which takes constant time and whatsoever may be the position of the duplicate elements one of the conditions specified in my algo will always satisfy. But please do correct me if any of the cases which u have tried proves me wrong..

Here 's my code.
i- first elemnt
J-last element
Mid = (i+j/2)

if(a[i]==a[i+1])
return a[i]

Elseif(a[j]==a[j-1])
Return a[j]

elseif(a[i]==a[j])
return a[i]

elseif(a[mid]==a[mid-1] ||a[mid]==a[mid+1])
return a[mid]

- soundarya August 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if my array is as below, then your algorithm may not work.
1 2 2 3 4 2 5 2 2 6

- dirishkumar August 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My algo works even in taht case.. check the below comment for my approach

- gopi.komanduri August 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

'two steps' means that scan the array twice´╝čIf it is, we can do like this:
For first time scan, every time we see two different number, we 'delete' them from the array. At last, there is two cases: (a)only one same number left, so it is the number repeated for 5 times(b)there are two different numbers left, named A and B, we choose one of them(e.g. A) and scan the array again, count the times it repeated. If count == 5, A is the number we want, If not, B is the result. Noted that we don't need to delete number really, we only use a parameter to count different numbers we see when we scan, If it is 2, we reset count = 0.

- qindazhu August 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

step 1: sort array in ascending order
step 2:
compare a[4] against a[5],
if a[4] == a[5] return a[4]
else
#two possible outcome
#either the 5 repeated numbers are in the first 5 slots of the array or in the last 5
if a[3] == a[4] return a[4]
else
return a[5]

- Tony August 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findDuplicate(int a[]){
		
		if(a.length <= 0)
			return -1;
		
		int dupVal = a[0];
		int count = 1;
		
		for(int i = 1; i < a.length; i++){
			if(a[i] == dupVal){
				count ++;
				if(count == 5)
					break;
			} else {
				count --;
			}
			
			if(count <= 0){
				count = 1;
				dupVal = a[i];
			}
		}
		
		return dupVal;
	}

- bari October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since there's nothing mentioned about memory, why not have 6 pointers and compare their values. Since there are 5 unique numbers, when you take 6 pointers, the repeating number will be present twice.

- Veena December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since there's nothing mentioned about memory, why not have 6 pointers and compare their values. Since there are 5 unique numbers, when you take 6 pointers, the repeating number will be present twice.

- Veena December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solving this in 2 steps:

Consider a hashset: hs, uniqueSum which is sum of all unique numbers initialized to 0 and a totalSum which is a sum of all numbers in the array.

Step 1:

foreach x in array:
    if (hs.add(x) is true): // note: Java's hashset returns true if element is not already present in it
        uniqueSum += x;
    totalSum += x;

Step 2:

duplicateNumber = (totalSum - uniqueSum) / 4

So e.g. array = {1,2,3,4,5,6,5,5,5,5}
uniqueSum = 20; totalSum = 40
duplicateNumber = 5

- tushar2702 January 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Does the initial array is known?

If yes, sum the initial array and then sum the modified array.

Get difference of both the summations and divide the result by 4.

- tihor August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,
even two sum , we need to loop through entire array. but as per the question , they allow only 2 steps itseems

- gopi.komanduri August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If interviewer does not consider summation a single step, completely agree with you :)

- tihor August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

---all the cases except will be covered in while loop ..except when the repeated number is in alternative position...
while (i<n)
{
if (a[i] =a[i+1])
return a[i];
}
---will cover the case when array will be like ...121314... or 213141...
if(a[0] == a[2])
return a[0];
else
return a[1];

- kartikkhatri01 August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

take two pointers , point one at first and one at third. keep on moving one step each till those two point to same value. .
ex: 1a2a3a4a5a .. these two meet at a's which are after 1 , and after 2 .. (in one move)
12aa3a4a5a .. these two meet a's which are before 3 and after 3 ..(3 steps)
123aaa4a5a .. two meet which are after 4 and seond a after 3 ...
1234aaaa5a .. 12345aaaaa .. straight

- gopi.komanduri August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh misread the question ..sorry .. when u mean two steps , u mean using any 2 operations???

- gopi.komanduri August 03, 2014 | Flag


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