Amazon Interview Question for Analysts






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.

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

Umm... What?

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

find only unique element?

- Anonymous August 19, 2011 | Flag
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

- airfang613 August 19, 2011 | Flag
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.

- anonymous August 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that should work :)

- someone August 19, 2011 | Flag
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

- Ravi August 25, 2011 | Flag
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

- Kranthi July 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think with given information its unsolvable :(

- insufficient August 19, 2011 | Flag Reply
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.

- modyjigar August 19, 2011 | Flag
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

- geeks August 20, 2011 | Flag Reply
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

- srinivas.kalyan August 23, 2011 | Flag Reply
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).

- lg August 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

space is not o(1) dude :(

- Anonymous November 17, 2011 | Flag
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;
}

- Anonymous August 25, 2011 | Flag Reply
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.

- Murugan August 25, 2011 | Flag
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));
}

}

- me August 31, 2011 | Flag Reply
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++;
}

}
}

- kk September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thoda explain to kardo shaktiman..

- ACP Pradyuman September 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 16, 2011 | Flag
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++;
}
}
}
}
}

- kk September 17, 2011 | Flag Reply
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.

- Khushboo April 23, 2012 | Flag Reply
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

- sudipto December 17, 2012 | Flag
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'

- KILVIS August 13, 2013 | Flag Reply
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

- Ashish July 23, 2014 | Flag Reply
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)

- ahalawatsunny August 26, 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