CareerCup

The sequence can be described as the numeric description of previous row i.e [number of repetition followed by the number ]

for example: 4th row is 1,2,1, 1 which means previous row (3rd row) contains One 2, and one 1 ( so 3rd row: 2, 1)

Similarly, given 8th row 1,1,1,3,2,1,3,2,1,1 its numeric description will be as follows
Three consecutive 1s, One 3, One 2, One 1, One 3, One 2, Two 1s
So 9th row becomes : 3,1,1,3, 1, 2, 1, 1, 1, 3, 1,1, 2,1

Second part of the question is fairly straightforward

1 -- start
1,1 -- 1 appears once in previous row
2,1 -- 1 appears twice in previous row
1,2,1,1 -- 2 appears once, 1 appears once in previous row
--------------

for the second part,
we can move back to only oe 1 in the array.

1. Take first number as n. then repeat the second number n times.
2. Now, take third number as n, Repeat fourth number n times.
--
--
Keep doing this.

At any step, if you an odd length array or have same number to be repeated continuously, then the array is invalid.

It is obvius that odd length is invalid.
For second point, consider 1, 1, 1, 1
It will create
1, 1
1
But it is not valid as its sequence should have been 2, 1 and not 1, 1, 1, 1

#include <iostream>
#include <vector>
using namespace std;

bool is_valid(vector<int> a)
{   int n=a.size(),i,j;
    if(n&1) return false;
    for(j=3;j<n;j+=2) if(a[j-2]==a[j]) return false;
    else return true; 
}
vector<int> pre_row(vector<int> a)
{   int i,j;
    vector<int> ret;
    for(i=0;i<a.size();i+=2)
    while(a[i]--) ret.push_back(a[i+1]);
    return ret;   
}
main()
{   int b[]={1,3,4,1,1,3};
    vector<int> a(b,b+sizeof(b)/sizeof(int));
    for(;a.size()>1;)
    {
       if(is_valid(a)) a=pre_row(a);
       else            break;     
    }
    puts(a.size()==1?"Valid":"InValid");
    system("pause");
    return 0;
}

WTH did they ask this really ?

Which company?

what is the solution for second part of the question?

whats the solution for second part?

3 1 1 3 1 2 1 1 1 3 1 2 2 1.
MUST RIGHT!

brilliant

Regarding the second part of question:

public boolean isValidSequence(int[] a) {
	int i = 0;
	int j = 1;
	int value = 0, repeat = 0, current = 0;

	while (i < a.length && j < a.length) {
	    value = a[i];
	    repeat = a[j];
	    current = a[++j];
	    while (repeat > 0) {
		if (value != current) {
		    return false;
		}
		value = a[++i];
		repeat--;
	    }
	    j++;
	}

	return true;
    }