Amazon Interview Question SDE-2s
Country: United States
We can ask usage of this operation, I my view if we are going to call multiple times then
we can dedup this array and create another one with starting index for each numbers
say if i/p array is 111122334455
then normalize it to i/p ->12345
and index Array -> 046810
find element index in the i/p array and then get the IndexArray[index] value..
any other solution ?
and if its one time activity then binary search and then move toward left to locate 1st, if found
We can ask usage of this operation, I my view if we are going to call multiple times then
we can dedup this array and create another one with starting index for each numbers
say if i/p array is 111122334455
then normalize it to i/p ->12345
and index Array -> 046810
find element index in the i/p array and then get the IndexArray[index] value..
any other solution ?
and if its one time activity then binary search and then move toward left to locate 1st, if found
Hi tiwaripradeep123,
They wanted an efficient solution with less space consumption and time consumption. I also proposed a solution of having a binary search, traversing towards left first to find a presence of element and travelling towards right. But its worst case is O(n) not O(log n) like binary search. Because we are traversing all element atleast once. Please correct me if I am wrong.
Why cant we use simple binary search, and move back to starting position, untill we will not get a mismatch.
1. Find index i with binary search
2. Now traverse array from index i to backward to find the starting position.
Or for better time complexity we can use .. Interpolation Search: A search algorithm better than Binary Search
Use deferred binary search that will return 1st occurrence of an element with O(lgn)
----->
int binary_search(int A[], int key, int imin, int imax)
{
// continually narrow search until just one element remains
while (imin < imax)
{
int imid = midpoint(imin, imax);
// code must guarantee the interval is reduced at each iteration
assert(imid < imax);
// note: 0 <= imin < imax implies imid will always be less than imax
// reduce the search
if (A[imid] < key)
imin = imid + 1;
else
imax = imid;
}
// At exit of while:
// if A[] is empty, then imax < imin
// otherwise imax == imin
// deferred test for equality
if ((imax == imin) && (A[imin] == key))
return imin;
else
return KEY_NOT_FOUND;
}
I have created a recursive version of satveer code, please correct me if I am wrong,
public static int binSrchFirstIndex(int[] arr, int st, int end, int key, int pos){
if(st > end)
return -1;
int mid = (st+end)/2;
if(arr[mid] == key){
if(pos == -1){
pos = mid;
}
else if(mid < pos){
pos = mid;
}
}
//Performing full left search first
int pos1 = binSrchFirstIndex(arr,st,mid-1,key,pos);
if(pos == -1 && pos1 >=0){
return pos1;
}
else if(pos1 >=0 && pos1 < pos){
return pos1;
}
//Goes here only if we are not able to find element in Left full search.
pos1 = binSrchFirstIndex(arr,mid+1,end,key,pos);
if(pos == -1 && pos1 >=0){
return pos1;
}
else if(pos1 >=0 && pos1 < pos){
return pos1;
}
return pos;
}
This is a generic program with 0 based index. For this problem the kidx would be 0.
I use a binary search to complete the program.
int indexKthElementInASortedArray(int kIdx, int elementInArray, int sortedArr[], int count)
{
int idx = indexOfElementInArray(elementInArray, 0, count-1, sortedArr);
while (sortedArr[idx] == elementInArray) {
idx--;
}
if (sortedArr[idx+kIdx+1]==elementInArray) {
return idx+kIdx+1;
}
else
return -1;
return -1;
}
int indexOfElementInArray(int elementInArray, int lo, int hi, int input[])
{
int midIdx = (lo+hi)/2;
if (hi<lo) {
return -1;
}
if (midIdx<=0)
return midIdx;
int midElement = input[midIdx];
if (elementInArray>midElement) {
return indexOfElementInArray(elementInArray, midIdx+1, hi, input);
} else if (elementInArray<midElement) {
return indexOfElementInArray(elementInArray, lo, midIdx-1, input);
} else {
return midIdx;
}
}
1. variant algorithm of normal binary search
int bsearchFirst(vector<int> a, int val) {
if(0 == a.size()) return -1;
int s = 0;
int e = a.size() - 1;
while(s < e) {
int m = (s + e) / 2;
if(a[m] == val) {
e = m;
}
else if(a[m] > val) {
e = m - 1;
}
else {
s = m + 1;
}
}
return (val == a[s]) ? s : -1;
}
int bsearchLast(vector<int> a, int val) {
if(0 == a.size()) return -1;
int s = 0;
int e = a.size() - 1;
while(s < e - 1) {
int m = (s + e) / 2;
if(a[m] == val) {
s = m;
}
else if(a[m] > val) {
e = m - 1;
}
else {
s = m + 1;
}
}
return (val == a[e]) ? e : (val == a[s]) ? s : -1;
}
package com.test;
public class ArrayIndex {
/**
* @param args
*/
public static void main(String[] args) {
int[] sortedArray = {2,4,5,7};
int pos = 0;
int searchNum = 1;
for (int i : sortedArray) {
if(searchNum==i){
System.out.println(pos);
break;
}else if (searchNum < i) {
System.out.println("Array doesn't contain the number");
break;
}
pos++;
}
}
}
int findFirestIndex(int arr[],int size,int num)
{
int low,mid,high,firstIndex;
firstIndex = -1;
low = 0;
high = size - 1;
while(low<high)
{
mid = (low + high) / 2;
if(arr[mid] == num)
{
firstIndex = mid;
high = mid - 1;
}
else if(arr[mid] > num)
low = mid + 1;
else
high = mid - 1;
}
return firstIndex;
}
#include<iostream>
#include<algorithm>
#include<limits>
int ans=INT_MAX;
using namespace std;
//O(logn)
int solve(int bot[],int n,int k)
{
int low=0,high=n-1;
int mid;
while(low<=high)
{
mid=low+(high-low)/2;
if(bot[mid]<k)
low=mid+1;
else if(bot[mid]>k)
high=mid-1;
else{
ans=min(ans,mid);
high=mid-1;
}
}
return ans;
}
int main()
{
int a[1001],n,k;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
cin>>k;
cout<<solve(a,n,k);
}
- Satveer Singh June 06, 2014//Binary Search in a sorted array //First occurance & last occurance of a num //Time complexity Log(n) //space complexity -inplace int BinarySearchFirstOccuranceIndex(int arr[], int n, int num) { int low = 0; int high = n-1; int index = -1; while(low <= high) { int mid = low + (high-low)/2; if(arr[mid] == num) { high = mid-1; index = mid; } else if(arr[mid] < num) { low = mid+1; } else { high = mid-1; } } return index; } int BinarySearchLastOccuranceIndex(int arr[], int n, int num) { int low = 0; int high = n-1; int index = -1; while(low <= high) { int mid = low + (high-low)/2; if(arr[mid] == num) { low = mid+1; index = mid; } else if(arr[mid] < num) { low = mid+1; } else { high = mid-1; } } return index; } int main() { int arr[] = {1,1,2,2,2,3,3,3,3,4,4,6}; cout<<BinarySearchFirstOccuranceIndex(arr,12,6)<<endl; cout<<BinarySearchLastOccuranceIndex(arr,12,3)<<endl; return 0; }