## Amazon Interview Question for Quality Assurance Engineers

Country: India
Interview Type: In-Person

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

The answer is skipping. If you're starting at 1, and you're looking for 6, then you know that the best case scenario is the next five values increase by one each. So you skip 5 and check that value. You repeat the same step. It turns out the value at that position is 4. The best case scenario is the next two values increase by one each. So you jump two positions and there's your number.

The key is to figure out at each position how far the goal value is from that position's value and jump ahead by as many steps.

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

Is that true that your code in worst case needs n/2+1 steps to find the answer?

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

Thanks.

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

Here is a straighforward approach!
1. Subtract from last element in the array the number(let's say X) u want to find.
2. Go back that many indexes(result of subtraction above) in the array.
3. Check whether the number at current index is equal to X
4. Else subtract X from the number at current index.
5. Repeat steps 3-4 till start of array!!

Taking your example: Int arr[]={1,2,3,4,3,4,5,6,7} and to find 6
subtract: 7 - 6 =1
Go back one index: Value is 6.
Return.

Suppose u want to find 2:
subtract 7 - 2 = 5
Go back 5 indexes in the array: Value is 4
Check value: 2 ! =4
subtract 4- 2 = 2
Go back 2 indexes in the array : Value is 2
Return.

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

Here is the required function which takes up the mid every time and takes the absolute difference between key(to search) and the mid. Hence it element can only be found between (beg to mid-diff-1) to (mid+diff+1 to end)......
Here is the exact function for the same......
public static int Search(int[]arr,int beg,int end,int key){
print(arr,beg,end);
int mid=beg+(end-beg)/2;
if(arr[mid]==key)
return mid;
int result;
int diff=Math.abs(arr[mid]-key);
if(diff==0)
return mid;
if(mid+diff>end || mid-diff<0)
return -1;
else if(arr[mid-diff]==key)
return mid-diff;
else if(arr[mid+diff]==key)
return mid+ diff;
else{
result= Search(arr,beg,mid-diff-1,key);
if(result==-1)
result= Search(arr,mid+diff+1,end,key);
}
return result;

}
public static void print(int[]arr,int beg,int end){
System.out.println("\n");
for(int i=beg;i<=end;i++)
System.out.print(" "+arr[i]);
}
}

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

Why dont you use qsort and then apply bsearch to find the key you want ? It'simpler and less error prone than witchcraft.

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

Do you mean faster than O(n)?
Suppose array is of form
2 1 2 1 (2 1) ... 1 2 3 2 1 ... 2 1
Then we will have to traverse the whole array to find 3

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

``````def find(arr, n):
pos = 0
while pos < len(arr):
if arr[pos] == n:
return pos
pos += abs(arr[pos] - n)

assert find([1,2,3,4,3,4,5,6,7], 6) == 7
assert find([1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8], 8) == 17``````

if we want something quicker than linear search, we could try to choose the next pos smarter, but in worst case this is still O(n)

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

Is that true that your code in worst case needs n/2+1 steps to find the answer ? (if the difference between every consecutive elements would be exactly 1)

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

``We can first calculate the absolute-difference between first element and element to be found and move the difference no. of steps.If all are in continuous increasing or decreasing order element is found.If order is mixed(increasing + decreasing),We will again calculate the differnce and continue Till we reach our element or end of array.Its better than O(n) ,We dont need to traverse the whole array.``

``````int find(int arr[],int size,int element)
{
int difference=abs(element-arr[0]);
int index=0;
while(index<size)
{
while(difference--)
index++;
if(arr[index]==element)
{
printf("element found ");
return 0;
}
else
difference=abs(arr[index]-element);

}
printf("Element not found  ");
return 0;
}``````

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

Your algorithm works, but it is still O(N). In the worst case, you could be looking for 2 in an array like [1,0,1,0,1, 0, 1, 0, 1,...,0,1,2], which will cost you around N/2 searches.

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

public class FindElement
{
public int findValue(int[] input, int v) throws InvalidInputException
{
if(input==null||input.length==0)
{
throw new InvalidInputException(“The input array cannot be empty or null”);
}
int searchResult=searchValue(input, (v,0+v.length()-1)/2,0,v.length()-1);
return searchResult;
}

private int searchValue(int[] input, int idx,int value,int start, int end)
{
if(idx<start||idx>end)
{
return -1;
}
if(input[idx]==value)
{
return idx;
}
int diff=Math.abs(input[idx]-value);
int leftSearchResult=searchValue(input,idx-diff,value,start,idx-1);
if(leftSearchResult!=-1)
{
return leftSearchResult;
}
return (searchValue(input,idx+diff,value);

}
}

//Driver class
FindElement fe=new FindElement();
int elemIdx=fe.findValue(arr)//arr is an input array.

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

``````public class FindElement
{
public int findValue(int[] input, int v) throws InvalidInputException
{
if(input==null||input.length==0)
{
throw new InvalidInputException(“The input array cannot be empty or null”);
}
int searchResult=searchValue(input, (v,0+v.length()-1)/2,0,v.length()-1);
return searchResult;
}

private int searchValue(int[] input, int idx,int value,int start, int end)
{
if(idx<start||idx>end)
{
return -1;
}
if(input[idx]==value)
{
return idx;
}
int diff=Math.abs(input[idx]-value);
int leftSearchResult=searchValue(input,idx-diff,value,start,idx-1);
if(leftSearchResult!=-1)
{
return leftSearchResult;
}
return (searchValue(input,idx+diff,value);

}
}

//Driver class
FindElement fe=new FindElement();
int elemIdx=fe.findValue(arr)//arr is an input array.``````

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

``````public class FindElement
{
public int findValue(int[] input, int v) throws InvalidInputException
{
if(input==null||input.length==0)
{
throw new InvalidInputException(“The input array cannot be empty or null”);
}
int searchResult=searchValue(input, (v,0+v.length()-1)/2,0,v.length()-1);
return searchResult;
}

private int searchValue(int[] input, int idx,int value,int start, int end)
{
if(idx<start||idx>end)
{
return -1;
}
if(input[idx]==value)
{
return idx;
}
int diff=Math.abs(input[idx]-value);
int leftSearchResult=searchValue(input,idx-diff,value,start,idx-1);
if(leftSearchResult!=-1)
{
return leftSearchResult;
}
return (searchValue(input,idx+diff,value);

}
}``````

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

``````public class FindElement
{
public int findValue(int[] input, int v) throws InvalidInputException
{
if(input==null||input.length==0)
{
throw new InvalidInputException(“The input array cannot be empty or null”);
}
int searchResult=searchValue(input, (v,0+v.length()-1)/2,0,v.length()-1);
return searchResult;
}

private int searchValue(int[] input, int idx,int value,int start, int end)
{
if(idx<start||idx>end)
{
return -1;
}
if(input[idx]==value)
{
return idx;
}
int diff=Math.abs(input[idx]-value);
int leftSearchResult=searchValue(input,idx-diff,value,start,idx-1);
if(leftSearchResult!=-1)
{
return leftSearchResult;
}
return (searchValue(input,idx+diff,value);

}
}

//Driver class
FindElement fe=new FindElement();
int elemIdx=fe.findValue(arr)//arr is an input array.``````

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

These algorithms replace linear search with an odd recursive search that does pretty much the same thing. But I think they're missing the point: if you look at the first element (one-origin) and it's 1, you're looking for 6, and the successive elements differ by 1 or -1, then you can immediately know that the lowest index that contains "6" is index 6. So you can skip ahead to array[6] and check the value there--etc.

Is this the appropriate reading of the problem?

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

Yes,you nailed it.

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

``````def find_element(mylist,find_ele):
first=mylist[0]
n=find_ele-first
return mylist[n]
print find_element([1,2,3,4,5,6,7],7)``````

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

Will the input be given in the increasing order as shown? Or a input of 6,5,4,3,2,1 is also valid?

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

#include <iostream>
#include <vector>
#include <stdlib.h>

class Element {
public:
explicit Element(int inVal): value(inVal), visited(false) {
}

int getValue() {
return value;
}

int getValue() const {
return value;
}

bool iVisited() {
return visited;
}

bool isVisited() const {
return visited;
}

void setVisited() {
visited = true;
}

private:
const int value;
bool visited;
};

bool findElemInArray(std::vector <Element> & intVec, const int startIndex, const int number) {
if (startIndex < 0) {
return false;
}

if (startIndex > intVec.size()) {
return false;
}

if (number == intVec[startIndex].getValue()) {
return true;
}

if (false == intVec[startIndex].isVisited()) {
intVec[startIndex].setVisited();
if (number == intVec[startIndex].getValue()) {
return true;
}
const unsigned int absDiff = abs(intVec[startIndex].getValue() - number);
return (findElemInArray(intVec, startIndex - absDiff, number) || findElemInArray(intVec, startIndex + absDiff, number));
}

return false;
}

int main() {
unsigned int VEC_SIZE;
std::cin >> VEC_SIZE;

if (VEC_SIZE < 1) {
return 0;
}

std::vector <Element> intVec;
intVec.reserve(VEC_SIZE);

for (unsigned int i = 0; i < VEC_SIZE; ++i) {
int value;
std::cin >> value;
Element elem(value);
intVec.push_back(elem);
}

int valueToFind;
std::cin >> valueToFind;

std::cout << findElemInArray(intVec, 0, valueToFind) << std::endl;
return 0;
}

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

``````#include <iostream>
#include <vector>
#include <stdlib.h>

class Element {
public:
explicit Element(int inVal): value(inVal), visited(false) {
}

int getValue() {
return value;
}

int getValue() const {
return value;
}

bool iVisited() {
return visited;
}

bool isVisited() const {
return visited;
}

void setVisited() {
visited = true;
}

private:
const int value;
bool visited;
};

bool findElemInArray(std::vector <Element> & intVec, const int startIndex, const int number) {
if (startIndex < 0) {
return false;
}

if (startIndex > intVec.size()) {
return false;
}

if (number == intVec[startIndex].getValue()) {
return true;
}

if (false == intVec[startIndex].isVisited()) {
intVec[startIndex].setVisited();
if (number == intVec[startIndex].getValue()) {
return true;
}
const unsigned int absDiff = abs(intVec[startIndex].getValue() - number);
return (findElemInArray(intVec, startIndex - absDiff, number) || findElemInArray(intVec, startIndex + absDiff, number));
}

return false;
}

int main() {
unsigned int VEC_SIZE;
std::cin >> VEC_SIZE;

if (VEC_SIZE < 1) {
return 0;
}

std::vector <Element> intVec;
intVec.reserve(VEC_SIZE);

for (unsigned int i = 0; i < VEC_SIZE; ++i) {
int value;
std::cin >> value;
Element elem(value);
intVec.push_back(elem);
}

int valueToFind;
std::cin >> valueToFind;

std::cout << findElemInArray(intVec, 0, valueToFind) << std::endl;
return 0;
}``````

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

``````private static int FindNumber(int[] array, int index, int number)
{
if (array == null || array.Length == 0)
throw new ArgumentException("Parameter 'array' must not be null or empty.");

if (index < 0 || index > array.Length - 1)
throw new ArgumentException("Parameter 'index' is out of range.");

int current = array[index];
if (current == number)
return index;

int nextIndex = index + Math.Abs(current - number);

if (nextIndex > array.Length - 1)
throw new ApplicationException("Number is not found");

return FindNumber(array, nextIndex, number);
}``````

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

``````private static int Find(int[] array, int index, int number)
{
if (array == null || array.Length == 0)
throw new ArgumentException("Parameter 'array' must not be null or empty.");

if (index < 0 || index > array.Length - 1)
throw new ArgumentException("Parameter 'index' is out of range.");

int current = array[index];
if (current == number)
return index;

int nextIndex = index + Math.Abs(current - number);

if (nextIndex > array.Length - 1)
throw new ApplicationException("Number is nnot found");

return Find(array, nextIndex, number);
}``````

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

Hi,
The above solution looks to me as linear search but he clearly mentioned shouid not go with linear search.(say if an array has 1 million records it will take too much time to execute)

Please let me know if I am wrong.

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

Average case is log_2(N) assuming equal distribution between +1s and -1s.

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

``````public static int find(int[] values,int key,int start){
int i=values[start];
if(i==key)
return start;
int diff=(key-i)+start;
if(values[diff]==key){
return diff;
}if(values[diff]!=key){
return find(values,key,diff);
}``````

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

``````public static int find(int[] values,int key,int start){
int i=values[start];
if(i==key)
return start;
int diff=(key-i)+start;
if(values[diff]==key){
return diff;
}if(values[diff]!=key){
return find(values,key,diff);
}``````

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

``````public static int findNumber(int[] arr, int k)
{
for(int i = 0; i< arr.length;)
{
int temp1 = arr[i];
i += 2;
int temp2 = arr[i];
System.out.println(temp1+"\t"+temp2);
if(temp1 == temp2 && arr[i-1] == k)
{
return i-1;
}
else if(((temp1 == temp2-2) || (temp1-2 == temp2)) && (arr[i-1] == k))
{
return i-1;
}
}
return -1;
}``````

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

Here is a straighforward approach!
1. Subtract from last element in the array the number(let's say X) u want to find.
2. Go back that many indexes(result of subtraction above) in the array.
3. Check whether the number at current index is equal to X
4. Else subtract X from the number at current index.
5. Repeat steps 3-4 till start of array!!

Taking your example: Int arr[]={1,2,3,4,3,4,5,6,7} and to find 6
subtract: 7 - 6 =1
Go back one index: Value is 6.
Return.

Suppose u want to find 2:
subtract 7 - 2 = 5
Go back 5 indexes in the array: Value is 4
Check value: 2 ! =4
subtract 4- 2 = 2
Go back 2 indexes in the array : Value is 2
Return.

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

``````private static int search(int[] in, int key) {
int hi= in.length-1;
int low =0;
int count =0;
while(hi>=0&&low<in.length&&hi>=low){

if(in[low]==key){
count++;
low+=2;
}
else{
int diff= Math.abs(in[low]-key);
low+=diff;
}

if(in[hi]==key){
count++;
hi-=2;
}
else{
int diff= Math.abs(in[hi]-key);
hi-=diff;
}
}

return count;
}``````

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

``````private static int search(int[] in, int key) {
int hi= in.length-1;
int low =0;
int count =0;
while(hi>=0&&low<in.length&&hi>=low){

if(in[low]==key){
count++;
low+=2;
}
else{
int diff= Math.abs(in[low]-key);
low+=diff;
}

if(in[hi]==key){
count++;
hi-=2;
}
else{
int diff= Math.abs(in[hi]-key);
hi-=diff;
}
}

return count;
}``````

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

``````private static int search(int[] in, int key) {
int hi= in.length-1;
int low =0;
int count =0;
while(hi>=0&&low<in.length&&hi>=low){

if(in[low]==key){
count++;
low+=2;
}
else{
int diff= Math.abs(in[low]-key);
low+=diff;
}

if(in[hi]==key){
count++;
hi-=2;
}
else{
int diff= Math.abs(in[hi]-key);
hi-=diff;
}
}

return count;
}``````

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

``````private static int search(int[] in, int key) {
int hi= in.length-1;
int low =0;
int count =0;
while(hi>=0&&low<in.length&&hi>=low){

if(in[low]==key){
count++;
low+=2;
}
else{
int diff= Math.abs(in[low]-key);
low+=diff;
}

if(in[hi]==key){
count++;
hi-=2;
}
else{
int diff= Math.abs(in[hi]-key);
hi-=diff;
}
}

return count;
}``````

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

``````private static int search(int[] in, int key) {
int hi= in.length-1;
int low =0;
int count =0;
while(hi>=0&&low<in.length&&hi>=low){

if(in[low]==key){
count++;
low+=2;
}
else{
int diff= Math.abs(in[low]-key);
low+=diff;
}

if(in[hi]==key){
count++;
hi-=2;
}
else{
int diff= Math.abs(in[hi]-key);
hi-=diff;
}
}

return count;
}``````

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

``private static int search(int[] in, int key) {``

``int hi= in.length-1;``

``int low =0;``

``int count =0;``

``while(hi>=0&&low<in.length&&hi>=low){``

``if(in[low]==key){``

``count++;``

``low+=2;``

}

``else{``

``int diff= Math.abs(in[low]-key);``

``low+=diff;``

}

``if(in[hi]==key){``

``count++;``

``hi-=2;``

}

``else{``

``int diff= Math.abs(in[hi]-key);``

``hi-=diff;``

}

}

``return count;``

}

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

``````private static int search(int[] in, int key) {
int hi= in.length-1;
int low =0;
int count =0;
while(hi>=0&&low<in.length&&hi>=low){

if(in[low]==key){
count++;
low+=2;
}
else{
int diff= Math.abs(in[low]-key);
low+=diff;
}

if(in[hi]==key){
count++;
hi-=2;
}
else{
int diff= Math.abs(in[hi]-key);
hi-=diff;
}
}

return count;
}``````

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

``````public class ElementInSequentialArray {
public static void main(String[] args) {
int [] myArray = {11,9,7,5,3,1};
int myArrayn = 9;
int diff = myArray[1] - myArray[0];
int lastIndex = myArray.length;
if (diff>0 && (myArrayn > myArray[lastIndex-1]||myArrayn<myArray[0])){
System.out.print("number is beyond array limits");
} else if (diff<0 && (myArrayn < myArray[lastIndex-1]||myArrayn>myArray[0])) {
System.out.print("number is beyond array limits");
}
else {
int index = findElementIndex(myArrayn, myArray[0], Math.abs(diff));
if (myArray[index] == myArrayn){
System.out.print("Index is " + index);
} else {
System.out.print("Element not in array");
}
}
}
private static int findElementIndex(int myArrayn,int myArray0, int diff){
int index=0;
try{
index = (myArrayn - myArray0)/diff;
}
catch (ArithmeticException e){
System.out.print("the common difference is zero, all elements are same");
}
return Math.abs(index);
}
}``````

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

``````class Solution
{
public:
int Find(vector<int>& nums, int val)
{
return Find_Pvt(nums, val, 0, nums.size() - 1);
}

private:

int GetMax(int v1, int v2, int cnt)
{
int diff = (v1 + cnt) - v2;
return (v2 + (diff / 2));
}

int GetMin(int v1, int v2, int cnt)
{
int diff = (v1 + cnt) - v2;
return (v1 - (diff / 2));
}

int Find_Pvt(vector<int>& nums, int val, int start, int end)
{
if (start > end) return -1;
int mid = (end + start) / 2;

if (nums[mid] == val)
{
return mid;
}

//compute range for left and right array

if (nums[mid] < val)
{
int lmax = GetMax(nums[start], nums[mid], mid - start);
int rmax = GetMax(nums[mid], nums[end], end - mid);

if (lmax >= val)
{
int idx = Find_Pvt(nums, val, start, mid - 1);
if (idx != -1) return idx;
}

if (rmax >= val)
{
int idx = Find_Pvt(nums, val, mid + 1, end);
if (idx != -1) return idx;
}
}
else
{
//mid is greater than val
int lmin = GetMin(nums[start], nums[mid], mid - start);
int rmin = GetMin(nums[mid], nums[end], end - mid);

if (lmin <= val)
{
int idx = Find_Pvt(nums, val, start, mid - 1);
if (idx != -1) return idx;
}

if (rmin <= val)
{
int idx = Find_Pvt(nums, val, mid + 1, end);
if (idx != -1) return idx;
}
}

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

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

two approaches:

Approach1:
public boolean findNumberFromArrayOfDifference1(int array[], int k){
if(array == null || array.length == 0 ){
return false;
}

int nextHop = 0;
while(nextHop < array.length){
if(array[nextHop] == k)
return true;
nextHop += Math.abs(k - array[nextHop]);
}

return false;
}

Approach2:
public boolean findNumberFromArrayOfDifference1(int array[], int k, int start, int end)
{
if(start > end)
return false;

int mid = (start+end)/2;

if(array[mid] == k || array[start] == k || array[end] == k){
return true;
}

if(array[start] < k && array[mid] > k) {
return findNumberFromArrayOfDifference1(array, k, start+1, mid-1);
}
else if(array[mid] < k && array[mid] < end) {
return findNumberFromArrayOfDifference1(array, k, mid+1, end-1);
}
return false;

}

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