Tag Archives: amazon interview question

write a method power(a,n) that computes power of number a in O(logn)

0
Posted on by

Time complexity: O(logn)

Since the problem gets divided into half in each stage of recursion the time complexity is O(logn)

#include<iostream>
using namespace std;
long long int power(long long int a,long long int n){
long long int halfpow;
if(n==0)
return (long long int)1;
halfpow=power(a,n/2);
if(n%2==0){
return halfpow*halfpow;
}
else{
return a*halfpow*halfpow;
}
}
int main(){
cout<<power(10,10);
}
view raw power.cpp hosted with ❤ by GitHub

Given an Array A[], find the maximum j – i such that A[j] > A[i]. For example Input { 34,8,10,3,2,80,30,33,1} and Output 6 (j=7, i=1) Time Complexity should be less then O(n^2)

0
Posted on by
/*
* Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
*
* Solution :
* Create 2 arrays
* 1)LeftMin : stores the minimum element to the left of arr[i] including arr[i]
* 2)RightMax : stores the maximum element to the right of arr[i] including arr[i]
* Initialize maxDiff=-1
* Create a loop comparing leftMin[i] and RightMax[j] starting with i=0 and j=0 till i or j reaches n
* If LeftMin[i]>RightMax[j]{
maxDiff=max(maxDiff,j-i)
* j++
* }
* else
* i++
*
* maxDiff holds the maximum j-i
*/
#include<iostream>
using namespace std;
int max(int a,int b){
if(a>b)
return a;
else
return b;
}
int min(int a,int b){
if(a>b)
return b;
else
return a;
}
int findMaxDiff(int arr[],int n){
int LeftMin[n];
int RightMax[n];
LeftMin[0]=arr[0];
for(int i=1;i<n;i++)
LeftMin[i]=min(LeftMin[i-1],arr[i]);
RightMax[n-1]=arr[n-1];
for(int i=n-2;i>=0;i--)
RightMax[i]=max(RightMax[i+1],arr[i]);
int i=0;
int j=0;
int maxDiff=-1;
while(i<n&&j<n){
if(LeftMin[i]<RightMax[j]){
maxDiff=max(maxDiff,j-i);
j++;
}
else
i++;
}
return maxDiff;
}
int main(){
int arr[]={34, 8, 10, 3, 2, 80, 30, 33, 1};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = findMaxDiff(arr, n);
cout<<maxDiff;
return 0;
}
view raw findmaxidexdiff.cpp hosted with ❤ by GitHub

You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .

0
Posted on by

Time complexity : O(n)

Space complexity: O(1)

We implement count sort technique to get the frequency of the elements 1 to n

[gist https://gist.github.com/vishnujayvel/5998457]

Find a sorted subsequence of size 3 in linear time

0
Posted on by

Given an array of n integers, find the 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time. If there are multiple such triplets, then print any one of them.

Examples:

Input:  arr[] = {12, 11, 10, 5, 6, 2, 30}
Output: 5, 6, 30

Input:  arr[] = {1, 2, 3, 4}
Output: 1, 2, 3 OR 1, 2, 4 OR 2, 3, 4

Input:  arr[] = {4, 3, 2, 1}
Output: No such triplet


    

      

        

  

    
    


        



  


  

        

          
          #include<iostream>
        

        

          
          using namespace std;
        

        

          
          void findSubsequence(int arr[],int n){
        

        

          
                  int max=n-1;
        

        

          
          	int min=0;
        

        

          
          	int *larger=new int[n];
        

        

          
          	int *smaller=new int[n];
        

        

          
          	
        

        

          
          	//store the index of the element smaller than arr[i] (on its left side)
        

        

          
          	//in smaller[i] or -1 if there is no such element
        

        

          
          	smaller[0]=-1;//its obvious since theres no element in the left of arr[0]
        

        

          
          	for(int i=1;i<n;i++ ){
        

        

          
          		if(arr[i]>arr[min]){
        

        

          
          			smaller[i]=min;
        

        

          
          		}
        

        

          
          		else{
        

        

          
          			smaller[i]=-1;
        

        

          
          			min=i;
        

        

          
          		}
        

        

          
          		
        

        

          
          	}
        

        

          
          	//store the index of the element larger than arr[i] (on its right)
        

        

          
          	//in larger[i] or -1 if there is no such element
        

        

          
          	larger[n-1]=-1;//since theres no element in the right of arr[n-1]
        

        

          
          	for(int i=n-2;i>=0;i--){
        

        

          
          		if(arr[i]<arr[max]){
        

        

          
          			larger[i]=max;
        

        

          
          			
        

        

          
          		}
        

        

          
          		else{
        

        

          
          			larger[i]=-1;
        

        

          
          			max=i;
        

        

          
          		}
        

        

          
          	}
        

        

          
          	//find the first number which has smaller element on its left and larger element
        

        

          
          	//on its right
        

        

          
          	for(int i=0;i<n;i++){
        

        

          
          		if(smaller[i]!=-1&&larger[i]!=-1){
        

        

          
          			cout<<endl<<arr[smaller[i]]<<' '<<arr[i]<<' '<<arr[larger[i]];
        

        

          
          			return;
        

        

          
          			
        

        

          
          		}
        

        

          
          	}
        

        

          
          	cout<<"NO such triplet";
        

        

          
          	return;
        

        

          
          }
        

        

          
          int main(){
        

        

          
          	int arr[]={34,56,45,51,69,70};
        

        

          
          	findSubsequence(arr,6);
        

        

          
          }
        

  





    


  




      

      

        view raw
        
          triplet.cpp
        
        hosted with ❤ by GitHub