## Amazon Interview Question

• 1
of 1 vote

Country: India

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

``````public int findRepeatingNumber(int[] array, int n) {
int sumOfSequence = (n*(n+1))/2;

for (int element : array) {
sumOfSequence -= element;
}

return Math.abs(sumOfSequence);
}``````

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

This is the right approach, taken O(n) time and O(1) space

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

This doesn't cover the case in which more than one number repeats.

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

``````public static int repeatedNumber(final List<Integer> a) {
if (a.size() > 1) {
int slow = a.get(0);
int fast = a.get(a.get(0));
while (slow != fast) {
slow = a.get(slow);
fast = a.get(a.get(fast));
}

fast = 0;
while (fast != slow) {
slow = a.get(slow);
fast = a.get(fast);
}
return slow;
}

return -1;``````

}

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

Can You Please Explain the algorithm.Why this is working..?
I think first part is hare and tortoise but what is the use of second loop.

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

``````int ans = -1;
if (A.size() > 1) {
int slow = A;
int fast = A[A];
while (slow != fast) {
slow = A[slow];
fast = A[A[fast]];
}

fast = 0;
while (fast != slow) {
slow = A[slow];
fast = A[fast];
}
ans = slow;
}
return ans;``````

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

SumoftheStream - (n(N+1)/2)

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

``````def foo(n):
for i in range(0,len(n)):
if(n[abs(n[i])]>=0):
n[abs(n[i])] = -n[abs(n[i])]
else:
print abs(n[i])``````

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

There are 3 restrictions in the question and above 3 solutions which uses arrays fail to satisfy at least one of the restriction:

1. The additional space complexity should be less than O(n)
--> Means we can not use array as that will require O(n) space to hold all elements

2. The input is coming as a stream
--> This means you can not use array again as you dont have all the data at the same time. You can read each input and add it to the array but that will violate restriction 1.

3. Time complexity is linear. O(n)
--> So we can not run loop inside a loop or go back and forth in the array.

``````Solution:
=======
Since the input is coming as a stream of integer, the logical solution is to create a binary search tree (BST) as the integers come in.

For each input, insert the integer in BST.
If you find the integer already present you found the repeating element which is the answer.
If integer is not present in the BST, add that integer.

Space complexity < O(N)
This approach would take less than the max number of elements in the input as in the worst case last element will match the existing element and we wont have to store that last element

Time complexity is O(N)
Worst case time complexity for searching a number.
As pointed out in the comment, the time complexity for constructing BST is O(nlogn). But the question asks for linear time complexity for searching a number which is O(n)``````

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

Time complexity is O(nlogn) and not O(n) because its a BST

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

``````public int repeatingNumber(int[] array, int n) {
int sumOfSequence = (n*(n+1))/2;

for (int element : array) {
sumOfSequence -= element;
}

return Math.abs(sumOfSequence);
}``````

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

python implementation:

``````arr = [1,2,3,4,2,6,5,7,9,0,8]

temp={}
for i in arr:
if not temp.has_key(i):
temp[i]=1
else:
print i
break``````

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

Let
Array a = {1,2,3,4,5,5}
n = 5
Find the arithmetic sum of n integers n=5 means arithmetic sum=15
Next sum all the elements in array sum=20

missing number = sum - arithmetic sum = 20 - 15 = 5

``````public class Test {

public static int findRepeat(int[] a) {
int n = a.length-1;
int r1 = n*(n+1)/2;
int sum=0;
for(int i=0;i<=n;i++) {
sum+=a[i];
}

return sum-r1;
}

public static void main(String[] args) {
int[] a = {1,2,3,4,5,5};
System.out.println(findRepeat(a));

}

}``````

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

will incoming stream be a structured so as to fit in binary search tree.that is if incoming stream is 1,2,3,4,5.?how will we build bst without looking all the elements.we can build BST out of sorted int array(but again this violates your not storing all the stuff in the element).
I think the best would be to do arraylist/set to store the stuff.that is keep on adding in arraylist,untill you hit same element again.(if(set.contains(incoming element) do a break and come out of the loop in this way you won;t have stored all the elements and and search is also linear,unless specified way the data is coming on stream,I think only viable solution is to use arraylist or set to do a contains/add method and break if it return true.

import java.util.ArrayList;
import java.util.Random;

public class FindDuplicates {

public static void main(String[] args) {
// TODO Auto-generated method stub

Random random = new Random();
ArrayList<Integer> arrayList = new ArrayList<>();
int randomnumber = 0;
for (int i = 0; i < 1000; i++) {
randomnumber = random.nextInt(10);
if (arrayList.contains(randomnumber)) {
break;
}
}

System.out.println(randomnumber +">>>>>>>>>>>>" +"has already been processed ");

}

}

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

``````package com.amazon.set1;

public class LinearNumberExample {
public static void main(String[] args) {
int[] array = { 1,2,3, 4, 5, 5 };
//A.P to find the actual final element which is to be present.
int finalTerm = 1 + (array.length - 1) * 1;
//A.P to find the sum which is to be
int sum = array.length * (1 + finalTerm) / 2;
// As we iterate, we get to the difference in between the actual and the hypothetical.
for (int i = 0; i < array.length; i++) {
sum -= array[i];
}
if(sum==0)
{
System.out.println("No Duplicates");
return;
}
//By subtracting, we get the index of where the duplicate lies.
System.out.println(array[array.length-Math.abs(sum)]);
}
}``````

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

``````package com.amazon.set1;

public class LinearNumberExample {
public static void main(String[] args) {
int[] array = { 1,2,3, 4, 5, 5 };
//A.P to find the actual final element which is to be present.
int finalTerm = 1 + (array.length - 1) * 1;
//A.P to find the sum which is to be
int sum = array.length * (1 + finalTerm) / 2;
// As we iterate, we get to the difference in between the actual and the hypothetical.
for (int i = 0; i < array.length; i++) {
sum -= array[i];
}
if(sum==0)
{
System.out.println("No Duplicates");
return;
}
//By subtracting, we get the index of where the duplicate lies.
System.out.println(array[array.length-Math.abs(sum)]);
}
}``````

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

public class LinearNumberExample {
public static void main(String[] args) {
int[] array = { 1,2,3, 4, 5, 5 };
//A.P to find the actual final element which is to be present.
int finalTerm = 1 + (array.length - 1) * 1;
//A.P to find the sum which is to be
int sum = array.length * (1 + finalTerm) / 2;
// As we iterate, we get to the difference in between the actual and the hypothetical.
for (int i = 0; i < array.length; i++) {
sum -= array[i];
}
if(sum==0)
{
System.out.println("No Duplicates");
return;
}
//By subtracting, we get the index of where the duplicate lies.
System.out.println(array[array.length-Math.abs(sum)]);
}
}

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

``````public class RepeatedInteger {

public static void main(String[] args) {
int[] arr = {2 ,1, 3,2,4};
int n=5;

int result=0;
for (int i=0; i<n;i++){
result^=arr[i];
}

for (int i=1; i<n; i++){
result^=i;
}

System.out.println(result);
}
}``````

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

In the problem, it is not mentioned that the number will repeat only once, your solution will fail for 3 3 3 3 3
kindly correct me if I'm heading in the wrong direction.
Solution that I found:
{{
int repeatedNumber(const vector<int> &V) {
if (V.size() <= 1) return -1;
int valueRange = V.size() - 1;
int range = sqrt(valueRange);
if (range * range < valueRange) range++;
int count[range + 1];
memset(count, 0, sizeof(count));

for (int i = 0; i < V.size(); i++) {
count[(V[i] - 1) / range]++;
}

int repeatingRange = -1;
int numRanges = ((valueRange - 1) / range) + 1;
for (int i = 0; i < numRanges && repeatingRange == -1; i++) {
if (i < numRanges - 1 || valueRange % range == 0) {
if (count[i] > range) repeatingRange = i;
} else {
if (count[i] > valueRange % range) repeatingRange = i;
}
}
if (repeatingRange == -1) return -1;
memset(count, 0, sizeof(count));
for (int i = 0; i < V.size(); i++) {
if ((V[i] - 1) / range == repeatingRange) count[(V[i] - 1) % range]++;
}
for (int i = 0; i < range; i++) {
if (count[i] > 1) {
return repeatingRange * range + i + 1;
}
}
return -1;
}
}}

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

In the problem, it is not mentioned that the number will repeat only once, your solution will fail for 3 3 3 3 3
kindly correct me if I'm heading in the wrong direction.
Solution that I found:
{{int repeatedNumber(const vector<int> &V) {
if (V.size() <= 1) return -1;
int valueRange = V.size() - 1;
int range = sqrt(valueRange);
if (range * range < valueRange) range++;
int count[range + 1];
memset(count, 0, sizeof(count));

for (int i = 0; i < V.size(); i++) {
count[(V[i] - 1) / range]++;
}

int repeatingRange = -1;
int numRanges = ((valueRange - 1) / range) + 1;
for (int i = 0; i < numRanges && repeatingRange == -1; i++) {
if (i < numRanges - 1 || valueRange % range == 0) {
if (count[i] > range) repeatingRange = i;
} else {
if (count[i] > valueRange % range) repeatingRange = i;
}
}
if (repeatingRange == -1) return -1;
memset(count, 0, sizeof(count));
for (int i = 0; i < V.size(); i++) {
if ((V[i] - 1) / range == repeatingRange) count[(V[i] - 1) % range]++;
}
for (int i = 0; i < range; i++) {
if (count[i] > 1) {
return repeatingRange * range + i + 1;
}
}
return -1;
}}}

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

``````int ans = -1;
if (A.size() > 1) {
int slow = A;
int fast = A[A];
while (slow != fast) {
slow = A[slow];
fast = A[A[fast]];
}

fast = 0;
while (fast != slow) {
slow = A[slow];
fast = A[fast];
}
ans = slow;
}
return ans;``````

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

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

``````int find_rep(int arr[],int n)
{
for(int i=0;i<n;++i)
{
if(arr[abs(arr[i])]<0)
return abs(arr[i]);
else
{
arr[abs(arr[i])] = -arr[abs(arr[i])];
}
}
return -1;
}``````

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

``````public class FindRep {

public static void main(String[] args){

int[] arr = {1,3,1,4,5,6,7,8,2,9};
FindRep rep = new FindRep();
System.out.println(rep.FindRepNum(arr));

}

public int FindRepNum(int[] arr1){

HashSet myset = new HashSet();

for(int i: arr1){

if(myset.contains(i)){
return i;
}else{
}
}
return -1;
}

}``````

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

package com.amazon.set1;

public class LinearNumberExample {
public static void main(String[] args) {
int[] array = { 1,2,3, 4, 5, 5 };
//A.P to find the actual final element which is to be present.
int finalTerm = 1 + (array.length - 1) * 1;
//A.P to find the sum which is to be
int sum = array.length * (1 + finalTerm) / 2;
// As we iterate, we get to the difference in between the actual and the hypothetical.
for (int i = 0; i < array.length; i++) {
sum -= array[i];
}
if(sum==0)
{
System.out.println("No Duplicates");
return;
}
//By subtracting, we get the index of where the duplicate lies.
System.out.println(array[array.length-Math.abs(sum)]);
}
}

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

You can use xor.

``````public int findRep(int[] arr)
{
if(arr==null ||arr.length==0)
{
return -1;
}
int xor=arr;
int result=-1;
for(int i=0;i<arr.length;i++)
{
xor^=arr[i];
if(xor==0)
{
result=arr[i];
break;
}
}
return result;
}``````

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.