Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
nice... binary search makes it faster than other linear(backward) search of exact position and stack pop out versions... just little modification.. your algo still needs to store array A before discarding few elements.. lets say arrayList<int[]>.. store into index 0 only if previous content length is less than current.. (like what swathi mentioned in her algo.. )
Got O(n) solution with O(n) space complexity.
Start scanning the array from left to right... Have an empty stack..
1) if the current element is greater than the next element then push the element on to the stack..
2) else pop the stack untill the current element fit into the stack...
3) Make a note of the maximum sequence that is possible while you are moving between step1 to step2.
Example - array = {1 4 8 2 5 7 3 4 6}
push element 1 {1}
push element 4 (as it satisfies the increasing property) {1,4}
push element 8 {1,4,8}
try to push element 2 but since 2 is greater than 8 it breaks our property so pop untill the property satisfied. Also make a note of max seq possible so far {1,4,8}
now the stack content is {1,2}
push element 5 {1,2,5}
push element 7 {1,2,5,7}
now 3 breaks the rule so pop until the property satisfies and the max seq possible so far is {1,2,5,7}
now the stack contents are {1,2,3}
push element 4 {1,2,3,4}
push element 6 {1,2,3,4,6}
Hope i made my algo clear...
In your algorithm, the first element of the array is always part of the final result. What if the first element is not part of the longest subsequence?
I dont think the algorithm is correct.
It will fail for the following case.
{1,4,8,2,9,}
Yes Swathi algorithm will fail.
I will extend the Swathi Algorithm:
Start scanning the array from left to right... Have an empty array/vector..
1) if the current element is greater than the next element then push the element on to the array..
2) else Using binary Search, find the element in the array and replace the number just greater than equal to the current element.
3) Whatever remains in the array/vector will be the maximum subsequence
It is O(N log N) time and O(N) space complexity
This is a famous DP problem, and you can find the O(N^2) solution for it. However, I couldnt think of an O(NlogN) soln.
Also, to the one who posted, you mentioned constant space? I think its O(N) .. right ?
I don't think there's a constant time solution. From Wikipedia, the O(nLogN) solution:
L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L
such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)
Modified my original post .. I mena O(nlogn) instead of O(n).
And I was talking about contact space, not time ..
^^ I think the above will work.. ordering and position is not required. only subsequence required. but a better alternative would be this..
do a counting sort like iteration on the array. like so..
for i=0 to n
b[a[i]]++;
now b contains the count of each number.
next take two pointers on b. increment second if value in b > 0. set a when first value >0 found.. when second encouters 0 take difference of positions and change maximum..
which means 2 passes.. and O(n) solution..with O(n) space
please do tell if im wrong...
cheers
code for 2nd iteration in case u didnt get it
*p , *q = b;
while(*q != '\o')
{
if(*q == 0)
{ *q++;
}
else
{
p=q;
while(*q != 0)
{ q++; }
max = (p-q);
}
}
do a quick sort which is o(nlogn). Then iterate the soreted array in 1 1 pass.
o(nlogn+n) still o(nlogn)
I think that would be incorrect because if you did a quicksort all of your numbers would monotonically increase :)
0. let the given array be called B.
- Dr.Sai December 12, 20111. keep an array A of size n fill in the first element.
2. keep the current size as s=1. keep a current index i (=0 to start with).
3. for each element x that is going to follow in B do a binary search in A starting from 0 ending at i to find out where x fits in A, say it fits in position k. Let us analyze k.
4.If the last element in A is smaller than x. then s=s+1 i=k+1. Go to step 3.
5. if k <i ,i=k, but s remains where it was earlier. Go to step 3.
At the end s will tell the size of the longest blah balh.
O(nlog(n)) is as follows: n for each element log(n) for the binary search we do for each element.
This is one of those algorithms that is not very intuitive, like the two stack solution for a iterative post order binary Tree traversal. Try to mug it.