Amazon Interview Question for Quality Assurance Engineers

Team: Kindle
Country: United States
Interview Type: Phone Interview

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

JavaScript

``````function occurences(n, arr) {
var first = -1;
var last = -1;
if (arr === null || arr.length === 0 || arr[0] > n || arr[arr.length - 1] < n) {
return [first, last];
}

for (var i = 0; i < arr.length; i++) {
var num = arr[i];
if (num === n) {
if (first < 0) {
first = i;
} else {
last = i;
}
} else if (num > n) {
return [first, last];
}
}
return [first, last];
}
console.log(occurences(7, [1, 2, 3, 6, 7, 7, 8]));``````

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

``````if (first < 0) {
last = first = i;
} else {
last = i;
}``````

Or you get [4, -1] for occurences(7, [1, 2, 3, 6, 7, 8])

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

``````// ZoomBA
a = [ 1,2,3,4,4,4,5,5,7,8 ]
def bin_search( a, n, i, j ){
while ( i <= j ){
mid = ( i + j )/2
if( a[mid] < n ){
i = mid + 1
}else if( a[mid] > n ){
j = mid - 1
}else{
return mid
}
}
return -1
}
def find_l_r( a, n ){
inx = bin_search( a , n , 0 , #|a| - 1 )
if ( inx < 0 ) return [ -1, -1 ]
l = inx ; r = inx
while ( inx >= 0 ){
l = inx
inx = bin_search ( a , n, 0, inx -1 )
}
inx = r
while ( inx >= 0 ){
r = inx
inx = bin_search ( a, n , inx + 1 , #|a| - 1 )
}
[ l, r ]
}
println( find_l_r ( a, 5 ) )``````

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

int[] a ={1,2,3,4,5,5,5,5,6,7}
For example: we need to find the start and end position of 5.
Perform a binary search to find 5
Once 5 is found, lets call it currentpos
From currentpos move towards start of the array to find an element that is different from 5 .
From currentpos move towards the end of the array to find an element that is different from 5

``````#include "stdio.h"
#include "stdlib.h"
int BinarySearch(int[],int,int,int);
void  main()
{
int CurrentPos=0,StartPos=0,EndPos=0;
int FindElement=0,Start,End,ArraySize;

int a[] ={1,2,3,4,5,5,5,5,6,7};

ArraySize=sizeof(a)/sizeof(int);

FindElement=7;

Start=0;
End=ArraySize;

CurrentPos=BinarySearch(a,FindElement,Start,End);

StartPos=CurrentPos;
EndPos=CurrentPos;

while(StartPos!=0)
{
if(a[StartPos-1]==a[StartPos])
{
StartPos--;
}
else{
break;
}

}

while(EndPos!=ArraySize-2)
{
if(a[EndPos+1]==a[StartPos])
{
EndPos++;
}
else{
break;
}

}
printf("%d's start position is %d ending position is %d",FindElement,StartPos,EndPos );
}

int BinarySearch(int a[],int FindElement,int Start,int End){
int MidPoint= (Start+End)/2;
if(a[MidPoint]==FindElement)
{
return MidPoint;
}
else if (a[MidPoint]>FindElement)
{
BinarySearch(a,FindElement,Start,MidPoint);
}
else if (a[MidPoint]<FindElement)
{
BinarySearch(a,FindElement,MidPoint,End);
}

}
if{

}else

if (a[startpos-1]==a[startpos])
{
startpos--;
}``````

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

resubmitting code

``````#include "stdio.h"
#include "stdlib.h"
int BinarySearch(int[],int,int,int);
void  main()
{
int CurrentPos=0,StartPos=0,EndPos=0;
int FindElement=0,Start,End,ArraySize;

int a[] ={1,2,3,4,5,5,5,5,6,7};

ArraySize=sizeof(a)/sizeof(int);

FindElement=5;

Start=0;
End=ArraySize;

CurrentPos=BinarySearch(a,FindElement,Start,End);

StartPos=CurrentPos;
EndPos=CurrentPos;

while(StartPos!=0)
{
if(a[StartPos-1]==a[StartPos])
{
StartPos--;
}
else{
break;
}

}

while(EndPos!=ArraySize-2)
{
if(a[EndPos+1]==a[StartPos])
{
EndPos++;
}
else{
break;
}

}
printf("%d's start position is %d ending position is %d",FindElement,StartPos,EndPos );
}

int BinarySearch(int a[],int FindElement,int Start,int End){
int MidPoint= (Start+End)/2;
if(a[MidPoint]==FindElement)
{
return MidPoint;
}
else if (a[MidPoint]>FindElement)
{
BinarySearch(a,FindElement,Start,MidPoint);
}
else if (a[MidPoint]<FindElement)
{
BinarySearch(a,FindElement,MidPoint,End);
}

}``````

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

In the case of {5, 5, 5}, this algorithm results in O(N) solution.

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

Python Solution: It will return the following

``````def getfirstlast(arr1):
first = {}
second = {}
for i in arr1:
first[i] =[arr1.index(i), arr1.count(i)]
for k,v in first.iteritems():
for j in v:
second[k] = [v[0],(v[0]+v[1]-1)]
return second

a =[1,2,3,4,5,5,5,5,6,7]
print getfirstlast(a)

''' Answer: {1: [0, 0], 2: [1, 1], 3: [2, 2], 4: [3, 3], 5: [4, 7], 6: [8, 8], 7: [9, 9]} '''``````

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

Dictionary structure: {Element: [Start index, Final index]}

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

java solution based on binary search

``````public class BinaryFirstLastIndex {

public int[] findFirstLastIndex(int[] input, int number) {
if (input == null) return new int[]{-1,-1};

int start = 0;
int end = input.length - 1;

while (start <= end) {
int middle = start + ((end - start) >> 1);
if (input[middle] > number) {
end = middle - 1;
} else if (input[middle] < number) {
start = middle + 1;
} else { // find first & last index
int first = findFirstIndex(input, middle, number);
int last = findLastIndex(input, middle, number);
return new int[]{first, last};
}
}

return new int[]{-1, -1};
}

private int findFirstIndex(int[] input, int index, int number) {
int i = index - 1;
for (; i >= 0; i--) {
if (input[i] != number) {
break;
}
}

return i + 1;
}

private int findLastIndex(int[] input, int index, int number) {
int i = index + 1;
for (; i < input.length; i++) {
if (input[i] != number) {
break;
}
}

return i - 1;
}
}``````

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

Guaranteed O(logN) solution. Comparing to Mailman's solution, after spot the value should still use binary search to find the first and last occurrence rather than linearly search forward and backward. Because it can cause O(N) solution in the worse case, for instance {5, 5, 5}.
For C++ implementation, refer to: cpluspluslearning-petert.blogspot.co.uk/2015/10/bs-find-first-and-last-of-given-number.html

Test

``````void TestFindTheFistAndLastOfGivenNumberInSortedArray()
{
std::vector<int> sortedArray;
size_t first, last;
{
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
1,
first,
last) == false);
}

{
sortedArray = { 5 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
1,
first,
last) == false);
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 0 && last == 0);
}

{
sortedArray = { 5, 6 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 0 && last == 0);

assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
6,
first,
last) == true);
assert(first == 1 && last == 1);
}

{
sortedArray = { 5, 5, 5, 5, 5 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 0 && last == 4);

assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
6,
first,
last) == false);
}

{
sortedArray = { 1, 2, 3, 5, 5, 5, 5, 5, 6, 7, 8 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 3 && last == 7);
}
}``````

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

``````def occourance(l, n):
for i in range(0, len(l)):
if l[i] == n:
last= i
for i in range(0, len(l)):
if l[i] == n:
first= i
break
return ("the first occurance is at %ith 'index' and the last occurance is at %ith 'index'" %(first, last))

list1 = [5, 2, 3, 4, 5, 5, 7, 8, 5, 9]
z = occourance(list1, 5)
print(z)``````

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

def first_last(list, num):
first, last = -1,-1

for i, x in enumerate(list):
print str(x) + " " + str(num)
if (first == -1 and x == num):
first = i
if (first != -1 and x != num):
last = i - 1
break

return first, last

print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 4) --> (4, 8)
print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 6) --> (11, 11)

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

def first_last(list, num):
first, last = -1,-1

for i, x in enumerate(list):
print str(x) + " " + str(num)
if (first == -1 and x == num):
first = i
if (first != -1 and x != num):
last = i - 1
break

return first, last

print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 4) --> (4, 8)
print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 6) --> (11, 11)

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

def first_last(list, num):
first, last = -1,-1

for i, x in enumerate(list):
print str(x) + " " + str(num)
if (first == -1 and x == num):
first = i
if (first != -1 and x != num):
last = i - 1
break

return first, last

print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 4) --> (4, 8)
print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 6) --> (11, 11)

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

def first_last(list, num):
first, last = -1,-1

for i, x in enumerate(list):
print str(x) + " " + str(num)
if (first == -1 and x == num):
first = i
if (first != -1 and x != num):
last = i - 1
break

return first, last

print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 4) --> (4, 8)
print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 6) --> (11, 11)

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

``````def first_last(list, num):
first, last = -1,-1

for i, x in enumerate(list):
print str(x) + "  " + str(num)
if (first == -1 and x == num):
first = i
if (first != -1 and x != num):
last = i - 1
break

return first, last

print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 4) --> (4, 8)
print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 6) --> (11, 11)``````

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

``````def first_last(list, num):
first, last = -1,-1

for i, x in enumerate(list):
print str(x) + "  " + str(num)
if (first == -1 and x == num):
first = i
if (first != -1 and x != num):
last = i - 1
break

return first, last

print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 4) --> (4, 8)
print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 6) --> (11, 11)``````

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

``````def first_last(list, num):
first, last = -1,-1

for i, x in enumerate(list):
print str(x) + "  " + str(num)
if (first == -1 and x == num):
first = i
if (first != -1 and x != num):
last = i - 1
break

return first, last

print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 4) --> (4, 8)
print first_last([1,2,2,3,4,4,4,4,4,5,5,6,7,8], 6) --> (11, 11)``````

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

public class Test {

public static void main(String args[]){
int arr[] = {1,2,3,3,3,4,5,5};
int i =0;
int fo = -1;
int lo = -1;

while(i < arr.length){
fo = i;
int flag = 1;
while(i+1 < arr.length && arr[i] == arr[i+1]){
i++;
}
lo = i;

System.out.println("Value : " + arr[fo] + "First Occurences " + fo + "Last Occurences " + lo );
i++;

}

}

}

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

public class Test {

public static void main(String args[]){
int arr[] = {1,2,3,3,3,4,5,5};
int i =0;
int fo = -1;
int lo = -1;

while(i < arr.length){
fo = i;
int flag = 1;
while(i+1 < arr.length && arr[i] == arr[i+1]){
i++;
}
lo = i;

System.out.println("Value : " + arr[fo] + "First Occurences " + fo + "Last Occurences " + lo );
i++;

}

}

}

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

Worst Case: O(k + log n) => where k is the number of occurrences of a number in the list

``````public void Algorithm(int k){
int min = this.Run(0, this.size - 1, k);
int max = min;
while(min != -1){
this.posA = (min < this.posA)? min : this.posA;
min = this.Run(0, min-1, k);
}
while(max != -1){
this.posB = (max > this.posB)? max : this.posB;
max = this.Run(max+1, this.size - 1, k);
}
}

int Run(int i, int j, int s){
if((i > j) || (j < i) || (j >= this.size)){
return -1;
}
int mid = (i + j)/2;
System.out.println(mid);
int element = this.numList.get(mid);
if(element == s){
return mid;
}
else{
if(this.numList.get(mid) > s){
return Run(i, mid - 1, s);
}
else{
return Run(mid + 1, j, s);
}
}
}``````

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

``````public class BSearch {

private static int searchF(int[] in, int low, int high, int key) {
if( low >= high) return low;

int mid = low + (high -low)/2;

if(in[mid] == key) {
if(mid > 0 && in[mid-1] == key) {
return searchF(in, low, mid-1, key);
} else{
return mid;
}
}if(in[mid] > key) {
return searchF(in, low, mid-1, key);

} else {
return searchF(in,mid+1, high, key);
}
}

private static int searchL(int[] in, int low, int high, int key) {
if( low >= high) return low;

int mid = low + (high -low)/2;

if(in[mid] == key) {
if(mid < high && in[mid+1] == key) {
return searchL(in, mid+1,high, key);
} else{
return mid;
}
}if(in[mid] > key) {
return searchL(in, low, mid-1, key);

} else {
return searchL(in,mid+1, high, key);
}
}

public static Occurences search(int[] in, int key) {
int first = searchF(in, 0, in.length-1, key);
int last = searchL(in, 0, in.length-1, key);
return new Occurences(first, last);
}

public static void main(String[] args) {
System.out.println(" " + search(new int[]{1,2,3,4,4,5,5,5,6}, 4));
}
}

class Occurences {
int first = -1;
int last = -1;
Occurences(int f, int l) {
first = f;
last = l;
}

public String toString() {
return first + " " + last;
}``````

}

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

Javascript:

``````function findOcc(arr, num) {

var start = -1;
var count = 0;
for(var i=0; i<arr.length; i++) {
if(arr[i] === num ) {
start = i;
count++;
}
}
console.log('Start'+ (start-count+1)+' End '+ start);
}

findOcc([1,1,1,1,2,3,4,5,5,5,5,6], 1);``````

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

``````using System;
using System.Collections.Generic;

namespace FindFirstLastOccurance
{
// Find the first and last occurance for a number in given sorted array
class Program
{
static void Main(string[] args)
{
var input = new int[]{ 1, 2, 3, 4, 5, 5, 7, 8 };

var positions = FindFirstLast(input, 7);
foreach (var item in positions)
{
Console.WriteLine(item);
}
}

public static List<int> FindFirstLast(int[] sortedArray, int number)
{
if (sortedArray == null) return null;
if (sortedArray.Length == 0) return null;
if (sortedArray.Length == 1) return new List<int> { 0, 0 };
List<int> returnArray = new List<int>();

for (int i = 0; i < sortedArray.Length; i++)
{
if(sortedArray[i]==number)
{
}
}

return returnArray;
}
}
}``````

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

``````import java.util.*;
public class FristAndLastOccurenceInSortedArray {
public static void main(String[] args) {
int[] arr = {1,2,4,4,4,5,6,7,9,10};
printFirstAndLastOccurence(arr, 4);
}
private static void printFirstAndLastOccurence(int[] arr, int key) {
Stack<Integer> stk1 = new Stack<Integer>();
stk1.push(0);
stk1.push(arr.length - 1);
int first = 0;
int last = 0;
while (!stk1.isEmpty()) {
int high = stk1.pop();
int low = stk1.pop();
int mid = (low + high) / 2;
if (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == key) {
if (first == 0 && last == 0) {
first = mid;
last = mid;
} else if (mid < first) {
first = mid;
} else if (mid > last) {
last = mid;
}
}
if (key <= arr[mid]) {
stk1.push(low);
stk1.push(mid - 1);
} else {
stk1.push(mid + 1);
stk1.push(high);
}
}
}
System.out.println("First : " + first + " Last : " + last);
}
}``````

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

int a[]= {1,2,3,4,5,6,2,6};
int n =2;
List<Integer> m = new ArrayList<Integer>();
int i =0;
while(i<a.length)
{
if(a[i]==n)
{

i++;
}

i++;
}
m.sort(null);
System.out.println("First Occurance is:"+m.get(0));
System.out.println("Last Occurance is:"+m.get(m.size()-1));

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

The code snippet below prints the start and end index of each item in a given array. If there are consecutive instances of a particular number, it determines and prints the start and end index for it.

If the array is such: a[5] = {2, 2, 3, 2, 2}, it treats the two sets of 2's separately, returning different start/end indexes for each set.

``````#include <stdio.h>
#include <stdlib.h>
#define LENGTH 8
int main(void)
{
int arr[LENGTH] = {1,2,3,4,5,5,7,8};
int i = 0, p1_moved = 0, p2_moved = 1;
int *p1 = arr, *p2 = p1+1;

do {
if (*p1 == *p2) {
printf("The first position of number %d is index %d\n", arr[i], i);
while (*p1 == *p2) {
i++;	// array index will increment until a mismatch is encountered
if (p1_moved)
p1++;
else
p2++;
}  // end inner while loop
printf("The last position of number %d is index %d\n", arr[i], i);
} // end main if loop
else
printf("The first and last position of number %d is index %d\n", arr[i], i);
i++;
if (p1_moved) {
p2 = p1 + 1;		//align p2 to the right of p1
p2_moved = 1;		//set p2_moved
p1_moved = 0;		//clear p1_moved
}
else {
p1 = p2 + 1;		//align p1 to the right of p2
p1_moved = 1;		//set p1_moved
p2_moved = 0;		//clear p2_moved
}
} while (i < LENGTH);
system("pause");
}``````

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

input array is sorted.

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.