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]));

- jooka October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- Anonymous November 12, 2015 | Flag
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 ) )

- NoOne October 08, 2016 | Flag Reply
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--;
}

- Mailman October 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
	        }

}

- Mailman October 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- peter tang October 28, 2015 | Flag
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]} '''

- revanthpobala October 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- revanthpobala October 26, 2015 | Flag
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};
            }
        }

        // not found
        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;
    }
}

- zaitcev.anton October 27, 2015 | Flag Reply
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);
    }
}

- peter tang October 28, 2015 | Flag Reply
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)

- anish531213 November 04, 2015 | Flag Reply
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)

- Anonymous November 19, 2015 | Flag Reply
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)

- Anonymous November 19, 2015 | Flag Reply
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)

- IM November 19, 2015 | Flag Reply
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)

- IM November 19, 2015 | Flag Reply
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)

- IM November 19, 2015 | Flag Reply
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)

- IM November 19, 2015 | Flag Reply
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)

- arun.1202.java November 19, 2015 | Flag Reply
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++;

}

}

}

- Here is the simplied version November 26, 2015 | Flag Reply
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++;

}

}

}

- Here is the simplied version November 26, 2015 | Flag Reply
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);
			}
		}
	}

- sojourner6 December 09, 2015 | Flag Reply
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;
    }

}

- Guru January 19, 2016 | Flag Reply
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);

- Suchita January 31, 2016 | Flag Reply
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);
            }
            Console.ReadLine();
        }

        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)
                {
                    if (returnArray.Count == 0) returnArray.Add(i);
                    else returnArray.Add(i++);
                }   
            }

            return returnArray;
        }
    }
}

- ajay.majgaonkar February 13, 2016 | Flag Reply
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);
	}
}

- anand June 05, 2016 | Flag Reply
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)
{

m.add(i);
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));

- chanthini March 31, 2020 | Flag Reply
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");
}

- Anonymous October 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

input array is sorted.

- ragmo2223 November 03, 2015 | Flag


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