Amazon Interview Question Software Engineer / Developers
I don't think your algo is O(n).
Consider this array
100 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 101
where 90 <-> means 90, 89 , 88 upto 80 etc.
Now if you run your algo whenever you hit a 8 you will backtrack to the begining and add everything to the stack again expect the 8. so worst case will be n^2 right.
I don't think your algo is O(n).
Consider this array
100 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 101
where 90 <-> means 90, 89 , 88 upto 80 etc.
Now if you run your algo whenever you hit a 8 you will backtrack to the begining and add everything to the stack again expect the 8. so worst case will be n^2 right.
Not really... Consider this
100 8 90 <-> 80
and what happens when you encounter a 9.
Now if this is a stack you will have to pop everything from 80 <-> 90 ... remove 8 and update its nearest great as 9 and push 90 <-> 80 again.
so al the segments labelled 90 <-> 80 get pushed and popped over and over again.
Even if you don't done use a stack you will have to backtrack one by one untill your reach an 8
Actually it works.
For the array: 100 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 101
Stack at each step
100 : 100
8 : 100 8
90 : 100 90 //pop 8 & push 90, it's CGE(closest greatest elm) is 90
89<->80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 8 90 <-> 80 9 all goes on stack(Max:100, min:8)
once you encounter 101, all the elements are popped and assigned 101 as CGE
push 101 on stack continue
Therefore, O(n).
Also, we don't have to push the same element twice. We compare the current element with Min & Max before push.
sorry...messed up with the explanation
90 : 100 90 //pop 8 & push 90, it's CGE(closest greatest elm) is 90
89<->80 9 8 goes on stack
now if we encounter 90, all the elements till 89 are popped from the stack & 90 is pushed
so stack will be: 100 90 90
the process continues
This isn't really O(n), see because the statement
pop all elements < A[i]
this is really a loop and would require popping all the elements currently in the stack and pushing back those that are greater than A[i]. Unless you can prove this loop/popping would run for a constant number of elements, I am not sure how the algo you suggested is O(n)?
The elements in the stack will always be stored in descending order. So the statement pop all elements < A[i] is same as pop elements till element >= A[i]. And push A[i].
There by maintaining descending order. So, each element will be pushed once and popped once. Hence O(n).
Yes this work.
Observe that the following invariant holds: At anytime, if the stack is non-empty, then the elements are in decreasing order (or non-increasing) from the bottom to the top.
Now on getting a new element, the algorithm either pushes a smaller element on top, or pops off some elements till the invariant holds with the new element on the stack and for these popped of elements, the closest greater element is the new element we are trying to add.
I doubt that this can run in O(n) time. It should be O(nlog n)time.
Although the above code can be improved by traversing list from right. Below i have given code to do this. This has running time O(nlog n) and space complexity(n).
// Maintain a stack which may go up to max n. Say stack[0..n-1]
function main(){
O[0..n-1] = {NULL,NULL,...,NULL};
stack[0..n];
_stack_i = -1; // Stack Index
PUSH(stack,-1); // Push -1(i.e. No match) to stack
O[n-1] = TOP(stack); // Last element of list has no match
for(i = n-1 ; i >= 0 ; i--){
if(A[i] >= A[i+1])// If array elements are in decreasing
O[i] = TOP(stack); //order from right to left, then no change in match
else{
O[i] = FETCH_AND_POP_GREATER_KEY(A[i], stack); // fetch match > key(i.e. A[i]) and make this as new match for further processing
PUSH(A[i+1], stack);
}
}
PRINT O[0..n-1];
}
function TOP(stack){
if(_stack_i < 0)
return NULL;
else
return stack[_stack_i];
}
function PUSH(elem, stack){
stack[++_stack_i] = elem;
}
### Below function finds the element, from stack, which is higher than 'key'and pops all elements <= key.
function FETCH_AND_POP_GREATER_KEY(key, stack){
index = mod_binary_search(key, 1, _stack_i, stack);
if(index > 0)
_stack_i = index;
else
_stack_i = 0;
return stack[_stack_i];
}
### Below function finds index of element which is just next higher to the search 'key' element. NOTE : stack is already sorted in descending order. (Avg running time O(log n))
function mod_binary_search(key, start, end, array){
if(start > end)
return -1;
if(start == end){
if(array[start] > key)
return start;
else
return -1;
}
index = (end-start)/2;
if(array[index] < key)
return mod_binary_search(key,index+1,end,array);
if(array[index] >= key)
{
if(index > start && array[index-1] < key){
return index;
}
return mod_binary_search(key, start, index-1, array);
}
}
your solution is wrong because consider a case like
7 6 5 4 10 9 8, in that case you would have considered the popping out for all elements.
And when did popping out all the elements from the stack became O(1)
There are two kind of analysis: worst case analysis, amortized analysis.
The worst case for this problem is definitely O(n2), but amortized cost is O(n), which is good enough in general.
@Ipranjul and @Anonymous. Wtf are you guys talking about?
The solution given works for your example in O(n) time. No quadratic worst case etc.
It is O(n) worst case. PERIOD.
It's sad that I actually have to read your solution to understand what the question is asking about. Sounds like it should be "closest greater element" instead of "closest greatest element".
Anyways, sounds like you don't really need the max variable here. You can just pop until the top element is greater than A[i].
Extension to that question , find the next greatest element of particular number in the sequence.
For the first problem some of the ideas which i got are :
1)Run two for loops and check for all cases which has a value more than current value . Time complexity 0(n2)
2)Finding all the increasing sequences
3)Patience sorting with multiple buckets also help but not memory efficient.
4)Form a Binary Tree of the nodes , in the given order . The given Node contains infomation of index value , for every given node find the succesor which has index greater than current index , still worst case 0(n2)
O(nlogn) is possible.
Say there was a datastructure which supported this:
- Insert (key, value) - Insert key with value value.
- GetLeastValue(key1, key2) - Of all keys k such that key1 < k < key2 , return the value which is the least.
With trees, we can do both operations in O(log n) time.
Total complexity: )(nlogn)
create a binary search tree with the given values in the array which will take O(nlogn) time now for each element in the array find the element in the binary search tree and find the immediate successor of that node.... this will take O(nlogn)
thus total of : O(nlog n) + 0(nlogn) = 0(nlogn)
I think this would be the best way to approach this problem. The stack solution seems over complicated.
Multiple problems with this solution. Consider something like: 10 11 12 9 8 6 7 1000.
If the stack is (10), when we see 11, we pop 10, update it, and then don't do anything to the stack. The stack is now empty and 11 will never get updated.
If you push 11 onto the stack after popping, you still have a problem. Let's say I've processed 10 11 12 9 8 6 so far. The stack is now (12 9 8 6). When I see 7, I'll
pop off 6 and set min=8. So, what, now I see 1000. I pop everything and I never updated 6 and the previously updated elements will never be updated, so only 12 9 8
are updated. Even if I push 7 onto the stack, then only 12 9 8 7 get the correct value.
The correct solution for this one is 7 for all indices except the last index.
Algorithm is O(n), but the solution is incorrect.
This is solvable in O(n) time and space though using the RMQ algorithm, but there should be a simpler way.
Can somebody please explain the problem a little bit better? I got confused, what does "closest greatest" mean?
Say for an array: 1 100 1000, for A[0], 100 would be the closest element that is greater than itself, but 1000 would be the greatest element, I guess the question was referring to the first scenario?
It'd be great if you can post some examples. Thanks!
{{public static void next(int[] a,int x){
int i=0,j=a.length;
int next=(int)Math.pow(2,31);
int inext = 0;
int count=0;
int diff=(int) Math.pow(2,31);
for(i=0;i<j;i++){
if(a[i]>x){
next=a[i];
if((next-x)<diff){
inext=next;
diff=next-x;
next=0;
}
}else{
count++;
}
}if(count<i)
System.out.println(inext);
else{
System.out.println("No larger elements");
}
}
}}
Could anyone please explain the pproblem with a simple example....From the question what I understood was, In an array of elements, find the closest greatest element,
Eg: A[] ={5, 8, 20, 1, 4}
Solution:(8, 20,null, 4, 5}
Closest to A[0] = 8
Closest to A[1] = 20
Closest to A[2] = none
Closest to A[3] = 4
Closest to A[4] = 5
If this is the problem, we could do the following steps:
1. Sort the array A[] into B[], O(nlogn)
2. In one pass of B make an entry into Hashtable<B[i], B[i+1]>
3.The successor of any index in A[] can be in obtained using the Hash<A[i]>
Please correct me if I am wrong
No, i think your understanding is not correct.
The solution to your example = {8, 20, null, 4, null}
For every element - A[i], we need to find an element x such that x is to the right of A[i] and x>A[i]. The first such x needs to be computed for every A[i].
std::vector<int> input; //contains the input array
std::map<int,int> outputmap; //contains the output as a map
std::stack<int> current; // a stack to maintain pairs that have not been found yet
for ( size_t i = 0; i < input.size() ; ++i )
{
while( current.size() > 0 && current.top() < input[i] )
{
int topElement = current.top();
outputmap[topElement] = input[i];
current.pop();
}
current.push( input[i] );
}
Analysis:
1. The naïve solution yield O(N^2) solution as for each element we findMax() on the right subarray.
2. We can see that if a[i+1] < a[i], it should be somehow remember but findMax( ) redundancy compare many times.
3. Instead of looping from left to right we can use a stack-based approach and run backward. Having the stack keeping a[k] if a[k] is greater than the array to its left down to a[i] (i is our iterator). Hence, the closest greatest element to the right of a[i] is stack.top( ).
4. The improved solution is O(N)
Pseudo Code:
int array[N]
int answer[N]
find_closest_greatest( ){
Stack<int> stack = new Stack<int>();
for(int i=N-1; i>-1; i--){
if(stack.empty( ) || stack.top < a[i])
stack.push(a[i]);
else; //do nothing
answer[i] = stack.top( );
}//endfor
}//end function
int result[1024];
int totallen;
void init() {
for(int i = 0; i < 1024; i++)
result[i] = -1024;
}
void solve(int a[], int len){
init();
stack<int> stk;
stk.push(0);
int min = a[0];
int max = a[0];
for(int i = 1; i < len; i++){
if(a[i] <= min) {
stk.push(i);
min = a[i];
}else if(a[i] > max) {
while(!stk.empty()){
int t = stk.top();
stk.pop();
result[t] = a[i];
}
max = a[i];
stk.push(i);
}
else if(a[i] > min && a[i] <= max) {
while(!stk.empty()) {
int t = stk.top();
if(a[t] < a[i])
{
stk.pop();
result[t] = a[i];
}
else
break;
}
stk.push(i);
min = a[i];
}
}
}
#include "stdafx.h"
#include "iostream"
using namespace std;
int FindLargest(int *a, int start, int n)
{
if(start < n-1)
{
int val = a[start];
int i = start+1;
for(i = start+1; i < n; i++)
{
if(a[i] <= val)
{
continue;
}
else
{
break;
}
}
if(i < n)
{
cout << val << a[i] << endl;
if(start+1 == i -1)
{
cout << a[start+1] << a[i] << endl;
}
else
{
FindLargest(a,start+1,i);
}
FindLargest(a,i, n);
return i;
}
else
{
FindLargest(a,start+1,n);
}
}
else
{
return -1;
}
}
void PrintArray(int *a, int n)
{
cout << "Array" << endl;
for(int i = 0; i < n; i++)
{
cout << a[i] << " " ;
}
cout << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[]={2,8,4,1,6,9,3};
PrintArray(a,7);
FindLargest(a,0,7);
return 0;
}
stack containing those elements whose closest greater element yet to be found. unprocessed elements
1st element pushed
Iterate over to get next greater if(next greater element found) --> print pair. Pop the element from stack as its pair foun
push current value in stack so that current element pair can be found
NGE()
for each i from 1 to n-1
while(a[i] > pe)
print pe --> a[i]
if(stack is empty)
break
s.push(a[i])
pe = s.pop()
s.push(a[i])
if(pe)
s.push(pe)
1. Create a stack of n elements. Push A[0] onto stack.
- Guest123 August 22, 20112. Maintain two variables Min, Max. Initially Min = Max = A[0].
3. for i: 1 to n-1
if A[i] <= Min
Push A[i] onto stack
Min = A[i]
else if A[i] > Max
'i' will be the closest greatest element to the right for all
the elements in the stack
Pop all the elements in the stack and update the result array
else (if A[i] > Min & A[i] <= Max)
pop all elements < A[i]
'i' will be the closest greatest element to the right for all
the popped elements
Update Min = topmost element on the stack
Space: O(n)
Time : O(n)