## Amazon Interview Question for Analysts

• 0
of 0 votes

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

Try XOR of all the numbers at 1 go. The final value of the xor of all elements will five you the value which is not repeated.

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

Umm... What?

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

find only unique element?

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

You are mixing up different problems. What you described works when all but one number appears odd times.

XOR in this case would just cancel out the number we want to find

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

Question as it is written down is ambiguous because is is not clear if numbers, while being un-ordered can be arranged into a continuous sequence. For example this sequence

``7 3 5 1 4 4 2 6``

has all numbers from 1 to 7 with 4 repeated twice. Summing them up as if there was no duplicated number and subtracting it from a sum of all number will give a duplicate number.

``````sum(7,3,5,1,4,4,2,6) = 32.
32 - 7*(7-1)/2 = 4.``````

XORing numbers is another, "tricky" solution I suppose...
However, if numbers in a set are not consecutive like

``1, 8, 9, 3, 4, 4, 11, 5``

Algorithm described above won't work.

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

that should work :)

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

Slight correction to the formula, sum - n * (n-1)/2. Which is in you case, 32 - 8(8-1)/2 = 4

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

what if the numbers are 10,20,30,10..
70-((4*3)/2)=64

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

I think with given information its unsolvable :(

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

I believe the question should be for an array of size n containing positive numbers from 0 - (n-1) where exactly one number is repeated.find the number which is repeated.

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

there should be range given if it is so we can solve it

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

randomized quicksort with three way partitioning is almost linear with few duplicates. it should do it

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

use hashtable to count and store the values along with teir count...then search where count =1..its O(n).

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

space is not o(1) dude :(

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

int unique(int *arr , int len)
{
int unique = 0,i = 0;
while(i < len)
{
unique ^= arr[i++];
}
return unique;
}

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

Assume the input is 1,1,2 the above program will return 2 which is wrong.

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

Hey... Check this out...

public class Dup {

private static int arraySum(int arr[]){
int arrySum = 0;
for(int i = 0; i < arr.length; i++){
arrySum = arrySum + arr[i];
}
return arrySum;
}

private static int arraySquareSum(int arr[]){
int arrySqSum = 0;
for(int i = 0; i < arr.length; i++){
arrySqSum = arrySqSum + (arr[i]*arr[i]);
}
return arrySqSum;
}

private static int naturalSum(int arr[]){
int arrSize = arr.length;
return (arrSize *(arrSize+1))/2;
}

private static int naturalSqSum(int arr[]){
int arrSize = arr.length;
return (arrSize*(arrSize+1)*(2*arrSize+1))/6;
}

private static int duplicate(int arr[]){

int duplicate =0, arrySum=0, arrySqSum=0, natSum=0, natSqSum=0;

arrySum = arraySum(arr);

arrySqSum = arraySquareSum(arr);

natSum = naturalSum(arr);

natSqSum = naturalSqSum(arr);

duplicate = (natSqSum - arrySqSum) / ( 2 * (natSum - arrySum)) - (natSum - arrySum)/2;

return duplicate;
}

private static int missing(int arr[]){
return (naturalSum(arr) + duplicate(arr) - (arraySum(arr)));
}

public static void main(String[] args) {
int arry[] = {7 ,3 ,5 ,1 ,4 ,4 ,2 ,6};
System.out.println("Duplicate Number: "+duplicate(arry));
System.out.println("Missing Number: "+missing(arry));
}

}

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

public static void getRepeatedElement(int[] a)
{
int i = 0;
int j = a.Length -1;
int n = a.Length;
while (i <= j)
{
if (i < j)
{
if (a[i] != a[j])
{
j--;
}

else if (a[i] == a[j])
{
Console.WriteLine("Repeated:" + a[i]);
break;
}
}
if( i== n-1)
{
Console.WriteLine("All Elements are Unique");
}
if (j == i)
{
j = n - 1;
i++;
}

}
}

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

Thoda explain to kardo shaktiman..

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

LOL ACP..there should be a like button here too..

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

c# code:
public static void singleNonrepeated( int[] a)
{
int i = 0, j = 1;

while (i < j)
{
if (j <= a.Length - 1)
{

if ((a[i] == a[j]))
{
j++;
Console.WriteLine("The Repeated Element:" + a[i]);
break;
}
else
{

if (j == a.Length - 1)
{
i++;
j = i + 1;
}
else
{
j++;
}
}
}
}
}

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

Find sum of first n numbers say n = 100.
sum of first n numbers would be (100*101)/2 = 5050
Sum of first n-1 numbers would be (99*100)/2 = 4950
Sum of all elements in the array O(n) complexity = x (say)
find difference 5050 - x = k (say)
Repeated number is 100 - k.

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

input is 1,2,2,4 the above program will return 3, not the repeated no
again for 1,2,3,2 the above program will return 2, repeated no

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

wht caan be done to find the no of duplicate elements witout the repatations of same number'

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

We can find out the duplicate element by using Set, list or trvaersing using loop on array.
Below link can be useful to find out the algorithm to find duplicate or repeated elements in an array in java

<a href="newtechnobuzzz.blogspot.in/2014/07/find-out-repeated-or-duplicate-element.html">Find out duplicate or repeated elements in an array in java</a>

newtechnobuzzz.blogspot.in/2014/07/find-out-repeated-or-duplicate-element.html

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

for(i=0;i<5;i++)
if (b[abs(b[i])]>0) then
b[abs(b[i])]=-b[abs(b[i])];

Complexity=o(n)
Aux Space=o(1)

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