Amazon Interview Question
Quality Assurance EngineersTeam: Kindle
Country: United States
Interview Type: Phone Interview
// 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 ) )
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--;
}
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);
}
}
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]} '''
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;
}
}
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);
}
}
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)
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)
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)
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)
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)
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)
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)
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)
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++;
}
}
}
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++;
}
}
}
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);
}
}
}
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;
}
}
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;
}
}
}
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);
}
}
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");
}
JavaScript
- jooka October 30, 2015