CareerCup

Cannot understand the question - Please re-state. What do you mean by " Find array b is found continuously in array a".

This is what I would have done.

- For each value in arrB, use binary search to find if value exists in arrA
- If any value does not exist in arrA, return false
- If all values exist:
- Find min of arrB
- Find max of arrB
- Find index in arrA at which min of arrB is present; let's call it minIndex
- Find index in arrA at which max of arrB is present; lets call it maxIndex
- If ((arrB.size() - 1) != (maxIndex - minIndex)), return false
- else return true

There might be some better way of solving this; suggestions are always welcomed.

bnv\
km

Create hash of array b from ints to counts (occurrences in b).
Use sliding window approach on a where window size is size of b. As you encounter new values in a, keep a counter of how many you encounter before the value changes. When value changes, see if count encountered is the same as that in the hash. If not, toss out the current sliding window and start a new one.

The special case is when the value is the first or last in b. In this case, the count encountered in a must be >= that in b, but doesn't have to be the same.

Alternatively, convert the array a and b into arrays of arrays where for example, a[0].length = number of occurrences of a[0].
Ex. [1, 1, 1, 2, 2, 3, 3, 3] -> [[1, 1, 1], [2, 2], [3, 3, 3]]
Apply sliding window similar to before, except now you simply need to compare a[i][0] === b[i][0] && a[i].length === b[i].length. If this is false, restart the sliding window, otherwise continue.
This has the benefit of simplifying the sliding window when dealing with duplicate values.

As the first array is sorted,  so we don't need to binary search all elements of b in a. We can just (modified)bsearch first element of array b in array a and then can check if it continuously matches or not. Please point out if i am wrong or missing something important.

int bsearch(int a[],int l,int r,int e) {
    if( (r-l) > 1 ){
        int m = (l+r)/2;
        if ( e < a[m] )
            return bsearch(a,l,m-1,e);
        return bsearch(a,m,r,e);
    }
    return ( (a[r] == e ) ? r : ( (a[l] == e) ? l : -1 ) );
}
bool check(int a[],int n,int b[],int m,int &f,int &l) {
    int firstRightIndex = bsearch(a,0,n-1,b[0]);
    if( firstRightIndex == -1 ) {
        cout <<" Err : first index not found "<<endl;
        return false;
    }

    int prev = b[0];
    int i = 0,j;
    while(b[i] == prev) i++;

    if(firstRightIndex - i + 1 < 0 || a[ firstRightIndex - i + 1] != b[0] ) {
        cout << "out of Index "<<endl;
        return false;
    }

    f = firstRightIndex - i + 1;

    for(i=f,j=0;i<n && j<m;i++,j++) {
        if( b[j] != a[i] )  {
            cout << "Not proper subarray"<<endl;
            return false;
        }
    }
    l = i;
    return true;
}

int main()
{
    int a[] = {1,2,2,3,3,3,3,4,4,5,5,5,6,6,7,8};
    int sz_a = sizeof(a)/sizeof(a[0]);

    int b[] = {1,2,4,5,5,5,6,6,7};
    int sz_b = sizeof(b) / sizeof(b[0]);
    int f =-1,l = -1;
    cout << "Result : "<< ( check( a, sz_a, b , sz_b , f ,l) ? "True" : "False")<<endl;

    cout<<"Matched from "<<f<<" to "<<l<<endl;
    cout<<"Matched array : ";
    if( f != -1 && l != -1) {
        for(int i=f;i<l;i++)
            cout<<a[i]<<" ";
    }
    cout<<endl;

    return 0;
}

i think the question is to figure out the longest subarray from second array which also an subarray of first array.
here is the solution of this problem

Assuming the Array A is sorted in non decreasing order
Figure out the sorted subarrays from Array B and check if they are also present in Array A.
	i = 0, j = 0
	For i from 0 to A.Size
		If A[i] > A[i-1]
			j++
		else
			if j > i
				check if Array B[i,...j] is alos present in A[1,M]
				if Yes, and j-i > currentMax then j-i is the current max size which is present upto this point
			end
			i = j;
		end
	end
	Return CurrentMAx and I, J, which are correspond to max

Complexity : Space O(1)
Time : O(M*K) where K is number of sorted subarrays of A.