Amazon Interview Question
Country: India
In fact Br array lets us know the sequences that yield the solution.
No of solutions is Number of consecutive 0's * Number of consecutive 1's in the Br array.
int main()
{
int a[] = {1,7,4,9,2,5,7,8,9,2,5,3,7,3,8,1,3,7,9,10};
int i=0, n=20;
int prevSign,curSign,prevCount,curCount,prevIndex,curIndex;
prevCount = 0;
for(i = 0; i < n; i++)
{
if(a[i] < a[i+1])
{
curSign = 1;
}
else
{
curSign = 0;
}
if(i == 0)
{
prevSign = curSign;
curIndex = i;
curCount = 1;
}
else
{
if(prevSign == curSign)
{
if(prevCount < curCount)
{
prevCount = curCount;
prevIndex = curIndex;
}
curIndex = i;
curCount = 0;
}
else
{
prevSign = curSign;
curCount = curCount + 1;
}
}
}
printf("prevCount = %d\t, prevIndex = %d\n",prevCount,prevIndex);
printf("curCount = %d\t, curIndex = %d\n",curCount,curIndex);
if(prevCount > curCount)
{
i = prevIndex;
n = prevIndex + prevCount + 1;
}
else
{
i = curIndex;
n = curIndex + curCount + 1;
}
for(i;i <= n; i++)
printf("%d\t",a[i]);
return 0;
}
Start with cur_len = 1 and max_len = 1
Do one pass from 2 to N:
- If (a[i] == 0) then continue with the next iteration (skip a[i] as described in the question)
- else check if((a[i] - a[i-1])*(a[i-1] - a[i-2]) < 0 )
- if yes, then cur_lenght++ and if (cur_len > max_len) max_len = cur_len
- if no, then cur_len = 1 and continue with the next iteration
I think It could be solved in O(n). Two Iteration is enough.
select 1st element.
First lets assume that the diff of 1st from 2nd is +ve then we will go for next element if nth-(n-1)th is +ve or 0 then we move ahead else we select nth element and move till nth-(n-1)th is -ve. and so on.
Second lets assume that the diff of 1st from 2nd is -ve then we will go for next element if nth-(n-1)th is -ve or 0 then we move ahead else we select nth element and move till nth-(n-1)th is +ve. and so on.
We count the number of selected elements which will give us the ans.
In other words:
Keep the first element. Then find the monotone growing or shrinking parts of the sequence and keep the last element from all of these sequences.
E.g.
1<3<5<6>2<8<9>3>1<7>3
^ ^ ^ ^ ^ this is where
the "directions" are changing.
So 1, 6, 2, 9, 1, 7, 3.
I found this solution but I don't see/can't prove why this is good :(
Sry, My bad,.... We can do this only one Iteration, as mentioned by peter.
@peter Suppose we select a monotonous increasing seq. then (and we are at nth position) it is possible that (n+1)th element may lie between (n-1) and nth now by selecting (n-1)th element we are actually skipping one peak.
Actually this "peak" stuff came into my mind as well during having lunch :)
Imagine that the numbers are heights on a terrain and you walk uphill/downhill. The end of the monotonous sequences are the peeks and valley-lows.
Alright, here's a formal proof. Suppose you want to find the maximum zigzag subsequence in an array of length n. Consider this with the idea that you've already started accumulating a zig-zag subsequence before and now you have a specific direction you need to go in. Let's say it's up, without loss of generality.
Now, the elements you can choose from for your next subsequence element are all the elements that are greater than your current element and to the right in the array you're inspecting. Consider the next such element (the element that is greater than your current element and involves skipping over the fewest number of elements). Examine the upward run that starts from that element (by upward run, I mean the run of consecutive increasing elements). That could be just that element alone, or could include any number of consecutive elements. My goal is to prove that taking the highest element in that run is necessarily optimal.
This can be done in 2 parts. 1) Prove that taking the largest element in the run is at least as good as taking any of the other elements in the run; and 2) prove that taking the largest element in the run is at least as good as not taking any element at all in the run.
Part 1: Suppose you take a non-largest element in the run. You can't take any other elements in the run, because you now need to go down. But your ability to go down (the number of entries in the array that come after the run that qualify as "down") can only increase if you take the largest element in the run. So taking the largest element in the run is always at least as good (because it leaves you with all your previous options and can give you more).
Part 2: Suppose you don't take any element in the run, not even the last element, call it P for "peak". That implies that the next element you take into your subsequence is some element later in the input than P (or if you reach the end of the array, that's clearly suboptimal too). Consider this element you end up taking. By the logic of part 1, this element would have to have a value larger than the value of P to not be suboptimal. Let's call it P'. But we know P is followed immediately by an element with lower value, which would also have a lower value than P' (since P' > P). So if we include all 3 of the elements P, element after P, and P', this is clearly a more optimal situation. We'll still be heading down after including all 3 of those elements, so this situation is exactly identical to choosing P' directly except that it includes 2 additional elements. Choosing P' as the next element for the subsequence is thus guaranteed to be worse than choosing P.
Therefore, it is optimal to choose the peak point as the next element for the subsequence.
1.iterate through array as O(n) complexity
2.set flag to 1 if 2 consecutive no's are in increasing and set it to -1 if negative.
3.if there is 0 then skip and keep the location of last no. for consecutive no. say index.
4.compare currentindex-th element with index-th element. if flag changes increase lastindex else set startindex=currentindex
The following program will output the longest zig zag sub sequence-
#include<stdio.h>
#include<conio.h>
int main() {
int input[] = {1,7,4,1,7,4,9,2};
int count=0,LargestCount=0;
for(int i=1;i<((sizeof(input)/sizeof(input[0]))-1);i++) { //Here end before ARRAY_LENGTH-1
if(((input[i-1]-input[i])>0)&&((input[i]-input[i+1])<0))
{
count++;
}
else if (((input[i-1]-input[i])<0)&&((input[i]-input[i+1])>0))
{
count++;
}
else{
if(count>LargestCount) LargestCount = count;
count=0;
}
if(count>LargestCount) LargestCount = count;
}
printf("The longest sequence is %d\n",LargestCount);
getch();
}
<pre lang="" line="1" title="CodeMonkey91642" class="run-this">void longest_zigzag(int *input, int N)
{
int *diff = new int [N-1];
for (int i = 0; i < N-1; ++i) {
diff[i] = input[i] - input[i+1];
}
int start = 0, end = 0;
int max_start = 0, max_end = 0, max_len = 0;
for (int i = 0; i < N-2; ++i) {
if (diff[i] * diff[i+1] >= 0) {
start = i + 1;
end = i + 2;
}
else {
end++;
}
if (end - start > max_len) {
max_len = end - start;
max_start = start;
max_end = end+1;
}
}
for (int i = max_start; i < max_end; ++i) {
cout << input[i] << " ";
}
</pre><pre title="CodeMonkey91642" input="yes">int32_t input[] = {1,4,7,8,9,6,2,10,5,8,3,6,2,11,12};
output:
6 2 10 5 8 3 6 2 11</pre>
a linear solution for this problem . although its more than O(n) but will never be O(n*2)..used DP to solve it
int ZigZagLength(vector<int> a){
int n=a.size();
int DP[n][2];
DP[0][0]=1;
DP[0][1]=0;
DP[1][0]=2;
DP[1][1]=0;
int j;
for(int i=2;i<n;i++){
if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){
DP[i][0]=DP[i-1][0];
DP[i][1]= i-1;
}
if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])<0){
DP[i][0]=DP[i-1][0]+1;
DP[i][1]= i-1;
}
else{
j = DP[i-1][1];
while(j>0){
if((a[i]-a[j])*(a[j]-a[DP[j][1]])<0){
DP[i][0]=max(DP[j][0]+1,DP[i-1][0]);
if(DP[i][0]==DP[j][0]+1)
DP[i][1]=j ;
else
DP[i][1]= i-1;
break;
}else
j= DP[j][1];
}
if(j==0){
DP[i][0]=DP[i-1][0];
DP[i][1]=DP[i-1][1];
}
}
}
return DP[n-1][0];
}
import java.util.*;
import java.io.*;
import java.lang.*;
class Zigzag {
public static void main (String[] args){
int[] Output = null;
int[] input = {1,7,4,9,2,5,7,8,9,2,5,3,7,3,8,1,3,7,9,10};
Output = zigzag(input);
for(int i=0;i<Output.length;i++)
System.out.println(Output[i]);
}
public static int[] zigzag(int[] input){
int i,j;
int m = 1;
int[] output = new int[100];
//output[0] = input[0];
output[0] = input[0];
for(i=0;i<input.length;)
{
if(input[i]<input[i+1])
{
for(j=i+1;j<input.length;j++)
{
if(input[j]<=input[j+1]) //looking for the peak
{
if(j==input.length-2)
{
output[m] = input[input.length-1];
int[] finalO = new int[m+1];
System.arraycopy(output,0,finalO,0,finalO.length);
return finalO;
}
continue;
}
if(input[j]>input[j+1]) //there is a turn-point
{
output[m] = input[j];
m++;
i = j;
break;
}
}
}
else if(input[i]>input[i+1])
{
for(j=i+1;j<input.length;j++)
{
if(input[j]>=input[j+1])
{
if(j == input.length-2)
{
output[m] = input[input.length-1];
int[] finalO = new int[m+1];
System.arraycopy(output,0,finalO,0,finalO.length);
return finalO;
}
continue;
}
if(input[j]<input[j+1])
{
output[m] = input[j];
m++;
i = j;
break;
}
}
}
else
i++;
}
return null;
}
}
import java.util.*;
import java.io.*;
import java.lang.*;
class Zigzag {
public static void main (String[] args){
int[] Output = null;
int[] input = {1,7,4,9,2,5,7,8,9,2,5,3,7,3,8,1,3,7,9,10};
Output = zigzag(input);
for(int i=0;i<Output.length;i++)
System.out.println(Output[i]);
}
public static int[] zigzag(int[] input){
int i,j;
int m = 1;
int[] output = new int[100];
//output[0] = input[0];
output[0] = input[0];
for(i=0;i<input.length;)
{
if(input[i]<input[i+1])
{
for(j=i+1;j<input.length;j++)
{
if(input[j]<=input[j+1]) //looking for the peak
{
if(j==input.length-2)
{
output[m] = input[input.length-1];
int[] finalO = new int[m+1];
System.arraycopy(output,0,finalO,0,finalO.length);
return finalO;
}
continue;
}
if(input[j]>input[j+1]) //there is a turn-point
{
output[m] = input[j];
m++;
i = j;
break;
}
}
}
else if(input[i]>input[i+1])
{
for(j=i+1;j<input.length;j++)
{
if(input[j]>=input[j+1])
{
if(j == input.length-2)
{
output[m] = input[input.length-1];
int[] finalO = new int[m+1];
System.arraycopy(output,0,finalO,0,finalO.length);
return finalO;
}
continue;
}
if(input[j]<input[j+1])
{
output[m] = input[j];
m++;
i = j;
break;
}
}
}
else
i++;
}
return null;
}
}
static int findLongestSubseq(int []seq){
int []sum = new int[seq.length];
int []len = new int[seq.length];
int max = 1;
int pi =-1;
int ni =-1;
for (int i = 0; i < sum.length-1; i++) {
int diff = seq[i] - seq[i+1];
sum[i] = diff;
if(diff > 0 )
pi = i;
else
ni=i;
if(i==0)
len[i] = 1;
else{
if( (diff > 0 && sum[i-1] < 0) || (diff < 0 && sum[i-1] > 0 ) )len[i] = len[i-1]+1;
else if(diff < 0){
if(pi != -1)len[i] = len[pi]+1;else len[i] = 1;
}else if(diff >0){
if(ni != -1)len[i] = len[ni]+1;else len[i] = 1;
}
}
max = Math.max(len[i], max);
}
return max+1;
}
1.iterate through array as O(n) complexity
2.set flag to 1 if 2 consecutive no's are in increasing and set it to -1 if negative.
3.if there is 0 then skip and keep the location of last no. for consecutive no. say index.
4.compare currentindex-th element with index-th element. if flag changes increase lastindex else set startindex=currentindex
<pre lang="" line="1" title="CodeMonkey68799" class="run-this">import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class ZigZagTest {
public static void main(String[] args) {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] array = null;
System.out.print("Enter Inputs: ");
try {
array = bf.readLine().split("\\s");
} catch (IOException e) {
e.printStackTrace();
}
int j = 0, k = 0;
for (int i = 0; i < array.length - 2; i++) {
if ((Integer.parseInt(array[i]) > Integer.parseInt(array[i + 1]))
&& Integer.parseInt(array[i + 1]) < Integer
.parseInt(array[i + 2])) {
j++;
} else if ((Integer.parseInt(array[i]) < Integer
.parseInt(array[i + 1]))
&& Integer.parseInt(array[i + 1]) > Integer
.parseInt(array[i + 2])) {
j++;
} else {
j = 0;
}
if (k < j) {
k = j;
}
}
System.out.println(k + 2);
}
}
</pre><pre title="CodeMonkey68799" input="yes">
1 7 4 9 2 5</pre>
My solution is
i) Sort the array using quicksort
ii) Calculate the number of integers which are not repeated in the array.
iii) return the number as that could be longest subsequence zig zag to be found
#include <stdio.h>
main()
{
int a[] = {1,7,4,9,2,5,7,8,9,2,5,3,7,3,8,1,3,7,9,10};
int i=0, n=20;
int p_old=0, q_old=0, p_new=0, q_new=0;
while(q_new < n-1)
{
q_new = subseqfn(q_new, a, n);
if((q_old - p_old) < (q_new - p_new))
{
//save these indices to compare with the size of next subsequence if exists
p_old = p_new;
q_old = q_new;
}
p_new = q_new;
}
printf("Longest subsequence is: " );
for(i=p_old;i<=q_old;i++)
printf("%d\t", a[i]);
}
int subseqfn(int q, int a[], int n)
{
int k = q, i, positive=10; //set positive to some random value for every subsequence
for(i=q;i<n-1,k<n-1;i++,k++)
{
if(a[i+1] - a[i] > 0)
{
if(positive == 1)
return k;
else
positive = 1;
}
else
{
if(positive == 0)
return k;
else
positive = 0;
}
}
return k;
}
int alternate(int a,int b){
if(a == b) return 0;
if ((a > 0 && b < 0)|| a < 0 && b > 0 ) return 1;
return 0;
}
int getLongestsquence(int a[],int size){
if(size <= 2) return size;
int currPos = 0;
int maxI = 0;
int max = 2;
int currSize = 2;
int diffant = a[1] - a[0];
int diff = 0;
for(int i =1;i< size -1;i++){
diff = a[i+1] - a[i];
if(alternate(diffant,diff) == 1){
currSize++;
}
else{
if(currSize > max){
maxI = currPos;
max = currSize;
}
currPos = i;
currSize = 1;
}
diffant = diff;
}
if(currSize > max){
maxI = currPos;
max = currSize;
}
return max;
}
Here is both proof and algorithm:
- Doctor.Sai December 19, 2011Let the original array A be of length n. Build another array B of length n-1 of only 0s and 1s. B[i] = 0 if a[i]-a[i+1] >=0 else B[i] = 1. This can be done in O(n). Now we have an array of only 0s and 1, now the problem is to find alternating continuous 0s and 1s. A continuous sub array array in B of 0s will be represented by any one of its elements. For example:
If B is = [0,0,0,0,0, 1,0,0,0,1,0,1,1,1,0] then we can reduce B to Br which = [0,1,0,1,0,1,0] in O(n) , infact we just need to find the size of Br which can be done by just one iteration. And that my friend is the answer to the given problem. So total complexity is O(n) + O(n) = O(n).
Let me know if this explanation is not enough.