CareerCup

consecutive elements sequence... this is a google interview question... this was discussed earlier.

can you please provide discussion link?

id=9783960

I think the Google interview asked for a subset of the array, this question asks for a subarray. The obvious solution is checking all possible subarrays, but there must be a better solution...

'id=9783960' it's a different problem.
Here it is asked to find a SUBARRAY (contiguous part) that can be transformed to a sequence of consecutive integers, i.e.:

a = {4,5,1,5,7,4,3,6,3,1,9}
the subarray is: {5,7,4,3,6} because these numbers can be arranged as: {3,4,5,6,7}

ok, here is an algorithm I had in mind:

The idea is if the numbers of a subarray can be arranged in consecutive way that their sum can be evaluated as follows:
max*(max+1)/2 - min*(min-1)/2
where 'max' and 'min' are the maximal and minimal numbers in a subarray.

So the algorithm is go through the array updating 'max' and 'min', as well as the current sum.
In each step we check if computed sum equals to the value returned by the formula above.
If so, we have found a subarray with the given properties.
We keep the longest one seen so far.

Since we have to consider all possible array suffixes, the complexity is O(n^2)

Anonymous (above): what if an integer is repeated?

that's the trick:

if the number is repeated in subarray, the actual sum
will differ from the one provided by the formula.
Consider:

{5,7,4,3,6}
min = 3, max = 7. The sum is 25 which agrees with the formula.

suppose now we have a subarray: {5,7,4,3,4}
min/max are the same but the sum now is: 23, hence this
subarray is wrong.

Sum doesn't work. What if
{6,7,3,3,6} => sum = 25 with min = 3, max = 7

Learn to test a method b4 posting!

If just sum doesn't work, how about using both sum and product? 2520 is the product for min = 3 and max = 7.. 6,7,3,3,6 yields 2268.. So the series isn't apt for 3 - 7.. If both sum and product should be same, I can't think of a case that would break this..

but as this algorithm is O(n^2) I believe there must be a better way to do it..

yeah, but the product can easily overflow 32-bit ints

we can use some kinda of Chinese remaindering, that is
computing the product modulo two or more prime numbers
which give the correct result with high probability..

another idea: besides computing the sum
between min and max, we can also xor
all numbers in the subarray with consecutive ints in [min..max]
to check if the result is 0

nothing but all crappy idea! What the fuck of using xor? Sum+Mul together fails for many inputs. Search stackoverflow.

ok @anonymous2: can you break this ?
here I use the combination of sum and xor tests
to avoid situations like {6,7,3,3,6} as above

I'd appreciate if you can find a counterexample that does not work

// find a longest subarray which consists of consecutive ints
// of a given array
void longest_subarray(int *a, int n) {
    int p1 = 0, p2 = 0; // bounds for subarray found so far
    int i, j;
    for(i = 0; i < n - 1; i++) {
        int ch = a[i], sum = ch, xsum = ch;
        // indices of min-max chars in the range [i; j]
        int minc = ch, maxc = ch, xorc = ch;
        for(j = i + 1; j < n; j++) {
            int ch = a[j];
            xsum ^= ch,  sum += ch; // compute two sums '+' and 'xor'
            if(ch < minc)
                minc = ch;
            else if(ch > maxc)
                maxc = ch;
            // if no of elements is not equal => no need to make tests
            if(maxc - minc != j - i)
                continue;

            int sum_check = maxc*(maxc+1) / 2 - minc*(minc-1)/2;
            if(sum_check == sum && j - i > p2 - p1) {
                int xcheck = 0;
                for(int m = minc; m <= maxc; m++)
                    xcheck ^= m;
                if(xsum == xcheck) {
                    p1 = i, p2 = j; // found a match
                    printf("found match: %d %d\n", p1, p2);
                }
            }
        }
    }
    for(i = p1; i <= p2; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main() {
    int a[] = {11,1,23,6,7,3,3,6,3,3,4,2,235,2,234,234};
        //{5,5,1,6,7,3,2,4,3,1,9};
    int n = sizeof(a) / sizeof(int);
    longest_subarray(a, n);
    return 1;
}

So are you saying first find the expected sums & xor of [min..max] and then see if they are the same as the subarray with the same min & max?

If so, consider {1 2 2 5 5 6}. I think it will produce the same sum & xor, assuming my program below works properly. Basically given a min & max, my program will try to generate a random array with numbers between min & max, then explicitly set the first element to min and last element to max. Then it computes their sum & xor and checks if it's unique.

I have seen others suggest computing sum of squares etc as well, which also don't work. Even if they do, trying to prove that it works will probably be very difficult during an interview.

static void test(int min, int max) {
	int expectedSum = 0;
	int expectedBits = 0;
	for(int i=min; i<=max; i++) {
		expectedSum += i;
		expectedBits ^= i;
	}
	int diff = max-min;
	int len = diff+1;
	int arr[] = new int[len];
	Random r = new Random();
	while(true) {
		for(int i=1; i<len-1; i++) {
			arr[i] = r.nextInt(diff) + min;
		}
		arr[0] = min;
		arr[arr.length-1] = max;
		int sum = 0;
		int bits = 0;
		for(int i=0; i<len; i++) {
			sum += arr[i];
			bits ^= arr[i];
		}

		if(sum == expectedSum && bits == expectedBits) {
			HashSet<Integer> set = new HashSet<Integer>();
			for(int i : arr) {
				set.add(i);
			}
			if(set.size() != len) {
				for(int i : arr)
					System.out.print(" " + i);
				break;
			}
		}
	}
}

but how do you precisely determine if elements in the queue form a sequence ?

suppose you array starts with '6 8 4 5 7' (which form a sequence 4 5 6 7 8)
so at the beginning min = 6 and max = 8
but the next element we encounter is 4 which is neither one above
max nor one below min..

furthermore you cannot just simply pop up elements from the queue
if they do not form a sequence at this step as they can be a part of, perhaps, longer sequence

This is not bullet proof and lot of sort calls are used. The code can be improved but the general idea is important.

public class ContiniousSubarray {

	public ContiniousSubarray() {

	}

	public void start() {
		int[] arr = new int[] { 4, 5, 1, 5, 7, 4, 3, 6, 3, 1, 9, 5, 7, 2 ,11,15,12,14,14,15,13};
		calculate(this.fromArray(arr));
	}

	private void calculate(List<IntStruct> original) {

		if (original.size() < 2) {
			return;
		}

		boolean contIdx = isContinuousIndex(original);
		boolean cont = isContinuous(original);

		if (cont && contIdx) {
			// Solution !!
			System.out.println("*******SOLUTION FOLLOWING*************");
			printArray(original);
			return;
		}

		if (contIdx) {
			List<LinkedList<IntStruct>> subArrays = getPossibleSubArrays(original);
			for (LinkedList<IntStruct> l : subArrays) {
				calculate(l);
			}
		}else if(cont){
			List<LinkedList<IntStruct>> subArrays = getPossibleSubArraysFromIndexes(original);
			for (LinkedList<IntStruct> l : subArrays) {
				calculate(l);
			}
		}

	}

	private List<LinkedList<IntStruct>> getPossibleSubArrays(List<IntStruct> original) {

//		System.out.println("Looking in the following array for continuous subarrays:");
//		printArray(original);
		Collections.sort(original, valuesComparator);
//		printArray(original);

		List<LinkedList<IntStruct>> subarrays = new ArrayList<LinkedList<IntStruct>>();
		LinkedList<IntStruct> curSublist = new LinkedList<ContiniousSubarray.IntStruct>();


		IntStruct cur = null;

		for (int i = 1; i < original.size(); i++) {
			cur = original.get(i);
			IntStruct prev = original.get(i - 1);

			if (cur.value - prev.value > 1) {
				subarrays.add(curSublist);
				curSublist.add(prev);
				curSublist = new LinkedList<ContiniousSubarray.IntStruct>();
			} else {
				curSublist.add(prev);
			}
		}

		if(null != cur) {
			curSublist.add(cur);
		}
		subarrays.add(curSublist);

		Collections.sort(original, indexComparator);

		return subarrays;
	}


	private List<LinkedList<IntStruct>> getPossibleSubArraysFromIndexes(List<IntStruct> original) {

//		System.out.println("Looking in the following array for continuous subarrays:");
//		printArray(original);
		Collections.sort(original, indexComparator);
//		printArray(original);

		List<LinkedList<IntStruct>> subarrays = new ArrayList<LinkedList<IntStruct>>();
		LinkedList<IntStruct> curSublist = new LinkedList<ContiniousSubarray.IntStruct>();


		IntStruct cur = null;

		for (int i = 1; i < original.size(); i++) {
			cur = original.get(i);
			IntStruct prev = original.get(i - 1);

			if (cur.index - prev.index > 1) {
				subarrays.add(curSublist);
				curSublist.add(prev);
				curSublist = new LinkedList<ContiniousSubarray.IntStruct>();
//				curSublist.add(cur);
			} else {
				curSublist.add(prev);
			}
		}

		if (null != cur) {
			curSublist.add(cur);
		}
		subarrays.add(curSublist);

//		Collections.sort(original, indexComparator);

		return subarrays;
	}

	private boolean isContinuous(List<IntStruct> list) {
		boolean ret = true;

		Collections.sort(list, valuesComparator);

		for (int i = 1; i < list.size(); i++) {
			if (list.get(i).value - list.get(i - 1).value > 1) {
				ret = false;
				break;
			}
		}

		Collections.sort(list, indexComparator);
		return ret;
	}

	private boolean isContinuousIndex(List<IntStruct> list) {

		Collections.sort(list, indexComparator);

		for (int i = 1; i < list.size(); i++) {
			if (list.get(i).index - list.get(i - 1).index > 1) {
				return false;
			}
		}
		return true;
	}

	private void printArray(List<IntStruct> structure) {
		System.out.println("Array : ");
		StringBuilder sb = new StringBuilder();

		for (IntStruct str : structure) {
			sb.append(str.value);
			sb.append(";");
		}
		System.out.println(sb.toString());
	}

	private LinkedList<IntStruct> fromArray(int[] array) {

		LinkedList<IntStruct> list = new LinkedList<ContiniousSubarray.IntStruct>();

		for (int i = 0; i < array.length; i++) {
			IntStruct str = new IntStruct(array[i], i);
			list.add(str);
		}

		return list;
	}

	public static class IntStruct {
		int value;
		int index;

		/**
		 * @param value
		 * @param index
		 */
		public IntStruct(int value, int originalIdx) {
			super();
			this.value = value;
			this.index = originalIdx;
		}
	}

	private Comparator<IntStruct> valuesComparator = new Comparator<ContiniousSubarray.IntStruct>() {

		@Override
		public int compare(IntStruct o1, IntStruct o2) {
			return o1.value - o2.value;
		}
	};

	private Comparator<IntStruct> indexComparator = new Comparator<ContiniousSubarray.IntStruct>() {

		@Override
		public int compare(IntStruct o1, IntStruct o2) {
			return o1.index - o2.index;
		}
	};

}

Sorry! posted at wrong location

The time complexity is O(nlogn) and space is O(n), most of time is spent in sorting

I didn't had time to test your code, but supposing you add a "2" at the end of the list, then your result would be 2,3,4,5,6,7 which I don't think is the desired result. In this case the solution should still be 3,4,5,6,7 (if I understood the requirements correctly).

PS: In the problem description, the hint answer is sorted in it's original position :
a = {4,5,1,----5,7,4,3,6----,3,1,9}
max subarray = {5,7,4,3,6}

So I am pretty much convinced that we are talking about a contiguous array. The example was given in this way because they wanted to make their lives simpler and have the counter-example at their fingertips (a 2 at the end of the array) and they also wanted the naive sort then search for contiguous array solution to work.

On first thought. If the requirement is continuous subarray, then my result is not right. In your counter-example, adding 2 will result in 1,2,3,4,5,6. But if we add the requirement that we should output its original position, then I don't think sorting will be possible here because we can't locate their original positions even with hashmap because of duplicate elements.

could you elaborate more on your soln ?

just don't say dp.. talk more about the recursive function..

Just a little modification to above algo.
after we have (3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)

start splitting at each position one by one and see if maxIndex -minIndex + 1 == length of partition
1. partition is (3,0) and (4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
for left it is 0-0+1 == 1, so possible with len = 1
for right it is 8-1+1 !=7
2. partition is (3,0)(4,1) and (5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
for left, 1-0+1 ==2, len = 2, maxlen becomes 2
for right, 8-2+1 != 6
3. partition is (3,0)(4,1)(5,8) and (6,2)(7,3)(8,4)(9,6)(10,5)
for left, 8-0 + 1 != 3
for right, 6-2 +1 == 5, len = 5, maxlen becomes 5
and so on

at the end you have the ans.

You didn't handle duplications

Your solution will fail for input: {10, 16, 9, 14, 15, 16, 17, 12, 18} in more than 1 place.
You didn't handle duplication and no one promises that 2 partitions will solve it. for this one the right partitioning is:
(9,1)(10,0)(12,7) - (14,3)(15,4)[(16,1)|(16,5)](17,6) - (18,8)
since the answer is (14,3)(15,4)(16,5)(17,6)

(9,2)*