## Amazon Interview Question

Country: India

Comment hidden because of low score. Click to expand.
4
of 4 vote

Here is both proof and algorithm:
Let 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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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;
}

Comment hidden because of low score. Click to expand.
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``````

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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 :(

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@Peter: I'm convinced this is correct. I proved the correctness of this in my head.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

Comment hidden because of low score. Click to expand.
0

A typo in above.it will never be O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is topcoder problem definition. violates their copyright. should be removed from here?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the same problem asked in TCCC'03 Semifinal 3. The top submission is at

community.topcoder.com/stat?c=problem_solution&cr=107835&rd=4493&pm=1259

You need a top coder login to view the top submission.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

<pre lang="" line="1" title="CodeMonkey68799" class="run-this">import java.io.BufferedReader;
import java.io.IOException;

public class ZigZagTest {

public static void main(String[] args) {
String[] array = null;
System.out.print("Enter Inputs: ");
try {
} 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>

Comment hidden because of low score. Click to expand.
0

No...you're allowed to skip elements to achieve a larger subsequence than what might be possible with a contiguous subsequence alone. It's in the problem statement.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

You cannot change the order of the elements in the sequence, you can leave out a few if you like, but not allowed to reorder.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

this will output: 8 9 2 5 3 7 3 8 1 3

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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;

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.