CareerCup

public class Pattern {

public static void main(String[] args){

int[] input={1,2,3,4,7,6,5,2,3,4,1,2}; //N
int startIndex=0;
int runs=10; //M
int no = 10; //K
int diff = 10; //L


while(startIndex+1<input.length){

if(input[startIndex]<no || input[startIndex+1]<no || Math.abs(input[startIndex]-input[startIndex+1])>diff )
continue;

Mode mode=getMode(input[startIndex],input[startIndex+1]);
System.out.print("{"+input[startIndex]+",");
++startIndex;
while(startIndex+1<input.length){

if(input[startIndex]>no || input[startIndex+1]>no || Math.abs(input[startIndex]-input[startIndex+1])>diff )
break;

if(mode==getMode(input[startIndex],input[startIndex+1])){

System.out.print(input[startIndex]+",");
++startIndex;
}
else
{
break;
}
}

System.out.println(input[startIndex]+"}");
--runs;

if(runs<=0)
return;

}

//System.out.println("Hi");
}

private static Mode getMode(int num1,int num2){

if(num1>num2)
return Mode.Decreasing;
else
return Mode.Increasing;


// return null;
}

}

enum Mode{Increasing,Decreasing}

lets take an array A[1...P] (P > N).

We make an array with the runs arr[1.. P] R where all the elements from single run (except the last one which goes in the next sequence) are colored the same (have same number).

(All the sub arrays bellow are marked just with indexes)
Follow L Rule: So lets split the array to a sub arrays that follow the L rules. We make an help array B[1..P](I used it to build R array) which we fill with the difference between the current and previous elements (B[i] = A[i] - A[i - 1]) and we split the array on the point where abs(B[i]) > L. Now we have sub arrays that follow the L rule.

Follow the K rule: here we just split the sub arrays from above(after L rule) on the points where A[i] > K;

Follow the N and M rule: here we iterate all possible sub arrays with length = N and count the color change in R to be equal to M.
If tall the rules are true we count++;

It seems there is a mistake in the task description. Any valid sequence can be converted to infinite number of valid sequences by subtracting 1,2,3,... from every element (numbers can be negative by definition). So, with this description amount can be either 0 or infinity.

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class GoogleSequence {


	class Seq {

		private LinkedList<LinkedList<Integer>> sets;

		public Seq(LinkedList<LinkedList<Integer>> sets) {
			this.sets = sets;
		}
		
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return sets.toString();
		}
	}
	
	public LinkedList<Seq> calculate(int N, int M,
			int K, int L) {
		// pos seq of N
		// with M runs
		// nums in seq <= K
		// adj diff <=L

		LinkedList<LinkedList<Integer>> lists = new LinkedList<LinkedList<Integer>>();

		for (int j = 0; j < N; j++) {
			int size = lists.size();

			if (size == 0) {
				for (int i = 1; i <= K; i++) {
					LinkedList<Integer> newL = new LinkedList<Integer>();
					newL.add(i);
					lists.add(newL);
				}
			}

			LinkedList<Integer> list = null;
			for (int s = 0; s < size; s++) {
				list = lists.get(s);
				LinkedList<Integer> newL = new LinkedList<Integer>(list);
				for (int i = 1; i <= K; i++) {
					LinkedList<Integer> temp = new LinkedList<Integer>();
					if (i == 1) {
						list.offerLast(i);
					} else {
						temp.addAll(newL);
						temp.offerLast(i);
						lists.offerLast(temp);
					}
				}
			}

		}


		LinkedList<Integer> pk = lists.peekLast();
		LinkedList<Seq> finalLists = new LinkedList<Seq>();

		for (LinkedList<Integer> list : lists) {
			int index = 0;
			LinkedList<LinkedList<Integer>> sets = new LinkedList<LinkedList<Integer>>();
			while (list.size() > 0 && (index+1)<list.size()) {
				int prev = list.get(index);
				int next = list.get(index+1);
				
				if (prev + L != next && prev - L != next) {
					List<Integer> sub = list.subList(0, index+1);
					sets.add(new LinkedList<Integer>(sub));
					if (list.size() >= index){
						list = new LinkedList<Integer>(list.subList(index+1,
								list.size()));
					index = 0;
					}
				}else{
					index++;
					if (index+1==list.size()){
						sets.add(list);
					}
				}

			}

			if (sets.size() == M) {

				finalLists.add(new Seq(sets));
			}

		}

		return finalLists;

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		GoogleSequence seq = new GoogleSequence();
		System.out.println("Type four numbers, N M K L");
		LinkedList<Seq> lists = seq.calculate(sc.nextInt(),
				sc.nextInt(), sc.nextInt(), sc.nextInt());
		System.out.println("POSSIBLE:" + lists.size());

		for (Seq linkedList : lists) {
			System.out.println(linkedList.toString());
		}

	}
}

I have tweak the code a bit

package com.algorithms;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class GoogleSequence {

	public class Seq {

		private LinkedList<LinkedList<Integer>> sets;

		public LinkedList<LinkedList<Integer>> getSets() {
			return sets;
		}

		public Seq(LinkedList<LinkedList<Integer>> sets) {
			this.sets = sets;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return sets.toString();
		}
	}

	public LinkedList<Seq> calculate(int N, int M, int K, int L) {
		// pos seq of N
		// with M runs
		// nums in seq <= K
		// adj diff <=L

		LinkedList<LinkedList<Integer>> lists = new LinkedList<LinkedList<Integer>>();

		// Get all combinations of sequnces up to N
		for (int j = 0; j < N; j++) {
			int size = lists.size();

			// If lists is empty add the first up to K numbers
			if (size == 0) {
				for (int i = 1; i <= K; i++) {
					LinkedList<Integer> newL = new LinkedList<Integer>();
					newL.add(i);
					lists.add(newL);
				}
			}

			LinkedList<Integer> list = null;

			// Iterate up to the current size of the list.
			// Add up to K to the end of each sublist
			// The iterations follow this pattern,
			// 1,2,3,4,... K
			// 11,21,31,41,12,22,...,13,23.....K1
			for (int s = 0; s < size; s++) {
				list = lists.get(s);
				LinkedList<Integer> newL = new LinkedList<Integer>(list);
				for (int i = 1; i <= K; i++) {
					LinkedList<Integer> temp = new LinkedList<Integer>();
					if (i == 1) {
						list.offerLast(i);
					} else {
						temp.addAll(newL);
						temp.offerLast(i);
						lists.offerLast(temp);
					}
				}
			}

		}

		LinkedList<Integer> pk = lists.peekLast();
		LinkedList<Seq> finalLists = new LinkedList<Seq>();

		for (LinkedList<Integer> list : lists) {
			
			
			int index = 0;
			LinkedList<LinkedList<Integer>> sets = new LinkedList<LinkedList<Integer>>();
			
			while (list.size() > 0 && (index + 1) < list.size()) {
				
				int prev = list.get(index);
				int next = list.get(index + 1);

				
				//Check if pattern exists , if it doesnt then add the new set
				if (prev + L != next && prev - L != next) {
					List<Integer> sub = list.subList(0, index + 2);
					sets.add(new LinkedList<Integer>(sub));
					
					if (list.size() >= index+1) {
						
						list = new LinkedList<Integer>(list.subList(index+1 ,
								list.size()));
						index = 0;
						if (list.size()==1) {
							sets.add(new LinkedList<>(list));
						}
					}
					
				} else {
					
					index++;
					if (index + 1 == list.size() || list.size()==1) {
						sets.add(new LinkedList<>(list));
					}
				}

			}
			
			if (sets.size() == M) {
				finalLists.add(new Seq(new LinkedList<LinkedList<Integer>>(sets)));
			}
		}

		return finalLists;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		GoogleSequence seq = new GoogleSequence();
		System.out.println("Type four numbers, N M K L");
		LinkedList<Seq> lists = seq.calculate(sc.nextInt(), sc.nextInt(),
				sc.nextInt(), sc.nextInt());
		System.out.println("POSSIBLE:" + lists.size());

		for (Seq linkedList : lists) {
			System.out.println(linkedList.toString());
		}

	}
}

public class SequenceResult
        {
            public enum SortType
            {
                ASC,
                DESC
            }

            public List<int> Sequence = new List<int>();
            public SortType Sort { get; set; }

        }


        public List<SequenceResult> SegmentArray(int[] input)
        {
            List<SequenceResult> result = new List<SequenceResult>();

            if (input == null || input.Length <2)
            {
                throw new ArgumentException();
            }

            SequenceResult segment = new SequenceResult();
            segment.Sequence.Add(input[0]);
            segment.Sequence.Add(input[1]);
            result.Add(segment);

            if (input[1] > input[0])
            {
                segment.Sort = SequenceResult.SortType.ASC;
            }
            else
            {
                segment.Sort = SequenceResult.SortType.DESC;
            }

            for (int i = 2; i < input.Length; i++)
            {
                SequenceResult.SortType sort = input[i] > input[i - 1] ? SequenceResult.SortType.ASC : SequenceResult.SortType.DESC;

                if (sort == segment.Sort)
                {
                    segment.Sequence.Add(input[i]);
                }
                else
                {
                    segment = new SequenceResult();
                    segment.Sort = sort;
                    segment.Sequence.Add(input[i - 1]);
                    segment.Sequence.Add(input[i]);
                    result.Add(segment);
                }
            }

            return result; 
        }

Test:
[TestMethod()]
public void SegmentArrayTest()
{
Google1 target = new Google1();
int[] input = { 1, 2, 3, 4, 7, 6, 5, 2, 3, 4, 1, 2 };

List<Google1.SequenceResult> actual;
actual = target.SegmentArray(input);

actual.ForEach(m => {
Console.Write(m.Sort + "{");
m.Sequence.ForEach(n =>
{
Console.Write(n + " ");
});
Console.Write("}\r\n");
});
}

Result:
ASC{1 2 3 4 7 }
DESC{7 6 5 2 }
ASC{2 3 4 }
DESC{4 1 }
ASC{1 2 }

This is a tested code in C++:

static int seqRun (int N, int M, int K, int L)
	{
		int result = 0;
		for (int i = 1; i <= K; i++)
		{
			vector<int> seq;
			seq.push_back(i);
			result += seqRun(N,M,K,L,0,-1,seq);
		}
		return result;
	}
	static int seqRun (int N, int M, int K, int L, int run, int direct, vector<int> seq)
	{
		int seq_len = seq.size();
		if (run > M)
			return 0;
		if (seq_len == N)
		{
			if (run < M)
				return 0;
			for (int i = 0; i < N; i++)
				cout << seq[i] << ' ';
			cout << endl;
			return 1;
		}
		int result = 0;
		int last_val = seq.back();
		for (int i = last_val-L; i < last_val; i++)
		{
			if (i > 0)
			{
				vector<int> seq2 = seq;
				seq2.push_back(i);
				if (direct == 0)
				{
					result += seqRun(N,M,K,L,run,0,seq2);
				}
				else
				{
					result += seqRun(N,M,K,L,run+1,0,seq2);
				}
			}
		}
		for (int i = last_val+1; i <= last_val+L; i++)
		{
			if (i <= K)
			{
				vector<int> seq2 = seq;
				seq2.push_back(i);
				if (direct == 1)
				{
					result += seqRun(N,M,K,L,run,1,seq2);
				}
				else
				{
					result += seqRun(N,M,K,L,run+1,1,seq2);
				}
			}
		}
		vector<int> seq2 = seq;
		seq2.push_back(last_val);
		result += seqRun(N,M,K,L,run,-1,seq2);

		return result;
	}

1) Do some pre-processing. For any sequence with N elements, split it into multiple continuous sub sequences:

1.1) Iterate all the elements in the seq, if it is > K, split the seq into two sub sequences that is separated by this element. For example, if K = 4, {1,2,3,4,7,2,3,4,1,2} will become {1,2,3,4}, {2,3,4,1,2} since 7 > 4 and it cannot be a continuous part of the sequence according to the problem description.

1.2) Iterate all sequences in step 1.1, and calculate the difference between adjacent elements, if the difference is > L, split the sequence into two sub sequences. For example, if L=2, {2,3,4,1,2} will become {2,3,4}, {1,2} since 4-1=3>2

After pre-processing, the remaining sequences will satisfy the requirement for K and L. The problem is turned into calculating the total number of runs for all these sequences. If the total number of runs is equal to M, the raw sequence is okay and should be counted.

2) To calculate every run of a subsequence after pre-processing, it is quite simple. I will use an example to illustrate it. Only increasing run will be shown here, and decreasing run can be figured out with the same method. Just compare the number with its previous one, and keep tracking from the first number if it is increasing, if in position i, there is one element is decreasing, start a new run from i+1. For sequence {1 2 3 2 6 4}, you will get several runs {1,2,3}, {2,6}, {4}.

I am not completely sure if a run like {1,2,3} should be counted multiple times because it contains {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3} essentially. If it is needed, it can be calculated easily with some combination formula.

3) Sum all the number of runs to see if it is equal to M.

Use the wiki/Longest_increasing_subsequence algorithm
Change the condition of increasing to increasing or decreasing..

Using DP may solve this problem.

why do we need dynamic programming or longets increasing subsequence. as it is either conitnuously increasing or decreasing we can use brute force approach to check continuous numbers and find the sequence.