Yahoo Interview Question
Country: United States
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.
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).
This works perfectly. Following is the c++ code for it.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[]={1,2,3,4,5,7,1,1,1,1};
int b[]={1,2,3,5,9,10,3,3,3,3};
int c[]={1,2,9,9,9,6,7,9,9,4};
sort(a,a+10);
sort(b,b+10);
sort(c,c+10);
cout<<((a[0]==a[4])?(a[0]):(a[5]))<<endl;
cout<<((b[0]==b[4])?b[0]:b[5])<<endl;
cout<<((c[0]==c[4])?c[0]:c[5]);
}
Output
1
3
9
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....
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.
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)
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));
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
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)
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;
}
}
}
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 :)
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;
}
}
}
}
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]
'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.
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
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.
Hi,
even two sum , we need to loop through entire array. but as per the question , they allow only 2 steps itseems
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
- Vir Pratap Uttam April 12, 2015