Amazon Interview Question Quality Assurance Engineers
Country: India
Interview Type: In-Person
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.
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]);
}
}
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
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)
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;
}
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.
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.
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);
}
}
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.
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?
#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;
}
#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;
}
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);
}
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);
}
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;
}
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.
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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);
}
}
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;
}
};
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;
}
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.
- Observer June 16, 2015The 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.