## Amazon Interview Question for Quality Assurance Engineers

Team: Kindle
Country: India
Interview Type: In-Person

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

Time: O(n) Space: O(n)
Use hashMap to mark every element encountered so far. The first element that is already in map is the output, print that number and return.

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

How is the space O(n)?? Because it depends on the number in the array right.
Say if n=10, and largest element in the array is m~99999999. Array which we have to create should be of length m.
If there is any other to get the hashmap please explain

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

Use AVL trees to store elements and search in it...like STL hashmaps....logn for searching n inserting...so space is 0(n) n is number of nodes and time is n logn n...even if we search in hash maps they internally uses red black tres.

or

0(m) space..as above mentioned comment
thnx

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

You don't need a HashMap. A Set would work and require less space.

``````public Integer getDuplicate(int[] numbers) {
Set<Integer> freq = new HashSet<Integer>();
for (int i = 0; i < numbers.length; i++) {
if (!freq.contains(numbers[i])) {
freq.put(numbers[i]);
} else {
return number[i];
}
}

return null;
}``````

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

``````import java.util.HashMap;

public class FirstDupicate {

public  static void main(String []args)
{
int []arr= {4,3,5,6,5,7,8,4};
int duplicate=-1;
HashMap<Integer,Integer> hm=new HashMap<Integer, Integer>();

for(int i:arr){
System.out.print(i+",");
if(null==hm.get(i))
{
hm.put(i,i);
}
else{
duplicate=i;
break;
}
}
System.out.println(duplicate);
}
}``````

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

This is my C++ version with O(n) time, O(n) space.

``````#include <iostream>
#include <unordered_set>
#include <vector>

template <typename T>
typename std::vector<T>::iterator find_first_duplicate(std::vector<T>& arr) {
std::unordered_set<T> set;
for (auto it = arr.begin(); it != arr.end(); it++) {
const T& elem = *it;
if (set.count(elem))
return it;
set.insert(elem);
}
return arr.end();
}

int main() {
std::vector<int> arr{4,3,1,2,5,9,5,4};
auto it = find_first_duplicate(arr);
if (it != arr.end())
std::cout << "first duplicate: " << *it << std::endl;
return 0;
}``````

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

Time O(n) Space(n). Finding a number which have Closest duplicate. Below method will return 5 as answer not 4 since 5 has closest duplicate then 4.

``````public static int FindClosestDuplicate(int[] arr)
{
if (arr == null) return -1;

Dictionary<int, int> elePos = new Dictionary<int, int>();

int minDiff = int.MaxValue;
int duplicate = -1;
for (int i = 0; i < arr.Length; i++)
{
if (elePos.ContainsKey(arr[i]))
{
int pos = elePos[arr[i]];
int diff = i - pos;
if (diff < minDiff)
{
minDiff = diff;
duplicate = arr[i];
}
}
else
}

return duplicate;
}
}``````

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

srinivas , sorting will change the index , so how will you know that which element is first repeated/duplicate .. best way is using hashing .. if there is any other way other than using hashing with o(n), i would like to know .

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

``````public class FindingFirstDuplicateElement {

/**
* @param args
*/
public static void main(String[] args) {

int[] data = { 4, 3, 1, 2, 5, 9, 5, 4 };
Map<Integer, Integer> lookup = new HashMap<Integer, Integer>();
for (int temp : data) {
if (lookup.containsKey(temp)) {
System.out.println(temp);
} else {
lookup.put(temp, 1);
}
}
}``````

}}

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

I agree that hashset should be used since it also has a method that returns false if the element being added is duplicate.Moreover for Performance both hashmap and hashset are same,but this code makes it much simpler.

``````import java.util.HashSet;

public class FirstDupicate {
//Use hashset because it has a function that can be used for finding the duplicates (public boolean add(obj) )
public  static void main(String []args)
{
int []arr= {4,3,5,6,5,7,8,4};
int duplicate=-1;
HashSet<Integer> hs=new HashSet<Integer>();
boolean isUnique=false;
for(int i:arr){

if(!isUnique)
{
duplicate=i;
break;
}
}
System.out.println(duplicate);
}
}``````

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

For simplicity, assume that the values of the array A are all positive integers and A has length N (In the general case, hash the values of A into the positive integers). Now, count sort the values A[i] of A, starting from i=0, noting that the first bin to obtain two elements will be the first duplicate.

``````Let B = array of length max{ A[i] }

for i=0, i < B.length, i++
B[i]=0

for i=0, i < N, i++
if B[A[i]]    //returns true when B[A[i]]=1, aka A[i] has already appeared
return i    //index of the first duplicate
B[A[i]]++``````

Since we begin with i=0, we are assured to return the first duplicate.

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

import java.util.*;
public class Firstduplicate {
public static void main(String[] args) {
// TODO code application logic here
HashSet hs = new HashSet();
int[] array = {4,3,1,2,5,9,5,4};
int i=0;
{
i++;
}
System.out.println(array[i]);
}
}

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

O(n) time and O(n) space

``````public static int firstDuplicate(int[] input)
{
Set<Integer> uniqes = new HashSet<Integer>();

for(int i=0;i<input.length;i++)
{
if(uniques.contains(input[i]))
return input[i];
uniques.put(input[i]);
}
}``````

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

Recursive version

``````int getDuplicateElement(int[] numbers, int j, int dupElement, int difference)
{
if(j + 1 == numbers.length)
{
return dupElement;
}

for(int i = j + 1; i < numbers.length; i++)
{
if(numbers[j] == numbers[i] && difference > (i - j))
{
dupElement = numbers[i];
difference = i - j;
break;
}
}

return getDuplicateElement(numbers, j + 1, dupElement, difference);
}``````

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

``````Here is the C++ code:
//!!!Finding first duplicate element in the array

string strArr = "43125954";
int cPntr = 0;
int lPntr = 0;

for (int i = 0; i < strArr.length(); i++)
{
for (int j = (i+1); j < strArr.length(); j++)
{
if (strArr[i] == strArr[j])
{
cPntr = j;
}
}

if ( cPntr < lPntr)
lPntr = cPntr;
else
lPntr = cPntr;

}
cout << strArr[lPntr] << " is the first duplicate elements in the string";
cout << endl;``````

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

d = []
for i in a:
if i in d:
print i
break
else:
d.append(i)

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

public static void fPrintDuplicate(int []arr) {

//Time complexity is more, as all elements till end needs to be worked
int asum=0;
int n = arr.length;
int esum = n*(n+1)/2; //expected sum;
for(int i=0;i<arr.length;i++)
asum += arr[i];
System.out.println("esum="+esum); //expected sum;
System.out.println("asum="+asum); //actual sum
int missing = n - (asum+1 - esum) ;
System.out.println("Missing number = "+missing);
int duplicate = missing - 1;
System.out.println("Duplicate number = "+duplicate);

}

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

we sort elements and compare with side element.....

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

``````int firstDup(int[] str) {
int len = str.length;
Map map = new HashMap();
int loc = len;
int lastValue = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (str[i] == str[j]) {
if (loc > j) {
loc = j;

}
}
}
}
return str[loc];
}``````

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

OR

``````int firstDup(int[] str) {
int len = str.length;
int loc = len;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (str[i] == str[j]) {
if (loc > j) {
loc = j;

}
}
}
}
return str[loc];
}``````

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.