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

}

}``````

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

can you define two steps?

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

``````Arrays.sort(a);
System.out.println((a == a) ? a : a);``````

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

Comment hidden because of low score. Click to expand.
0

but the complexity os o(nlogn) ..

Comment hidden because of low score. Click to expand.
-1

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

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 or A will be one of them for sure. We just need to discard one out of A and A.

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

let me know if this is wrong....

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

{
if(a==a)
print a
else if(a==a)
print a
else
print a
}

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

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) {
return -1;
}
}
return arr;
}

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

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 == a)
return a;	// a & a are part of duplicate sequence
else if(a == a)
return a;	// a to a are duplicates
else
return a;	// a to a are duplicates``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````if(a == a || a == a)
return a;	// a is part of duplicate sequence
else
return a;	// a to a are duplicates``````

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)

Comment hidden because of low score. Click to expand.
0

please gve the final and correct ans

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;
intArray = 27;
intArray = 91;
intArray = 84;
intArray = 71;
intArray = 65;
intArray = 71;
intArray = 31;
intArray = 71;
intArray = 71;
intArray = 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;
}
}
}``````

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.

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;

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
where x= 10-i
& i = first
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, element at index 5 is the duplicate entity :)

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

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]

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

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

step 1: sort array in ascending order
step 2:
compare a against a,
if a == a return a
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 == a return a
else
return a

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

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.

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.

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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 == a)
return a;
else
return a;

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

Comment hidden because of low score. Click to expand.
0

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

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.

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