9 weeks ago

John 910

Hyderabad

This was asked to my friend in Chargebee Internship OA yesterday. I have my test scheduled for tomorrow, can you someone help me.

Question

You are given 2 arrays A[a1, a2, ......, aN] and B[b1, b2, ....., bM] of length N and M respectively. Array A corresponds to Alice's array and array B corresponds to Bob's array. Alice wants to check the number of Alice's subarray which matches Bob's array. Alice's definition of a match is as follows.

1. She takes an element from Bob's array (which is not previously taken) and deletes the particular element from it. As a result, the length of Bob's array is reduced to M-1 after every deletion and then performs the following:

      - She takes her array, and for every subarray of length M-1, she checks if it is equal to any permutation of Bob's 
         array. If any permutation of Bob's array is equal to Alice's subarray of length M1, a match is found corresponding 
         to that subarray.
   

1. Bob's array is restored.

2. She does steps 1-2 till she has selected-deleted-restored every element from Bob's array once.

Task

Determine all the distinct starting indexes of Alice's subarray in ascending order, which matched Bob's array. If no subarray matched with Bob's array, -1 should be printed.

Notes

• Assume 1-based indexing.
• A subarray is a contiguous part of the array
• A permutation of an array is any rearrangement of the elements of that array

Example

Assumptions

N=5

A = [1, 2, 2, 1, 1]

B = [1, 2, 1]

Approach

• When you delete the 1st element from B, it becomes [2, 1]. You can see in array A the subarray of length 2 starting for index 1 is [1, 2] and as [1, 2] is the permutation of [2, 1], you have a match corresponding to this subarray. Similarly, the subarray starting at index 3 is also a match. So you get 2 matches corresponding to index 1 and index 3. Now the array B is restored, B = [1, 2, 1]
• Now when you delete the 2nd element from B, it becomes [1, 1]. For this, you can find 1 match corresponding to the subarray starting from index 4.
• Removing 3rd element is of no use as we had already removed 1 before and checked for it.
• Therefore, the corresponding indexes are [1, 3, 4].

Function description

Complete the function solve provided in the editor. This function takes the following 4 parameters:

• N. Represents the size of Alice's array A
• A[a1, a2, ......, aN] : Represents the elements of Alice's array A
• M. Represents the size of Bob's array B
• B[b1, b2...,bM]: Represents the elements of Bob's array B

The function's return type is an array, which should contain the starting indices of Alice's subarray, which matched with Bob's array in ascending order. If no subarray matched with Bob's array, it should contain -1.

Input format

Note:

This is the input format that you must use to provide custom input (available above the Compile and Test button).

1. The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
2. For each test case:

• The first line contains a single integer N denoting the length of Alice's array
• The second line contains N space-separated integers denoting the elements of array A
• The third line contains a single integer M denoting the length of Bob's array
• The fourth line contains M space-separated integers denoting the elements of array B.

Output Format

For each test case, print a line containing space-separated starting indices of Alice's subarray, which matched Bob's array in ascending order, and if no match is found, -1 should be printed.

Constraints

I don't remember the constraints, will update when I get them.

8 months ago

Akshay Sharma 990

Chandigarh

It would be a great help if u provide the range of every element of a[i] and b[i] and the constraints (n,m)

Assuming test cases are not that tight :

Let's Understand the problem more clearly :

1. we are given two arrays of length N and M
2. Provided with three operations (first-> choose some a[i] that is not previously taken, Secondly delete that index and Third restore that index)
3. after breaking down further the questions simply means that we are given an array B delete one index and find all its permutations in array A and keep track of all the indexes and we will keep deleting and restoring one element from the array B until all the elements of array B are not chosen .

Solution :

1. First we need to find that every element in array B is either chosen or not so we will be using a map or freq array to keep that count.
2. We can definitely be going to do brute force by following the steps asked in the question but I think it will give a TLE for larger constraints.
3. So the solution that comes to mind would be to store the occurrence of every element in both arrays and while iterating over the occurrence of 2nd array name B . Reduce the B[i] with one and check if we can get same occurrence or greater while iterating over map of array A, If yes we will be storing the index of such subarray.
4. Just keep in mind we can use any permutation of array A as a subarray So we need to find the first index where subarray B element matches with A. (Note: It will be better to use Map to store occurrence of all the elements in both array )

7 days ago

admin 1.6k

Hyderabad

Let's break down the problem a bit.

We'll first create a count array for all subarrays of size M-1. We'll have a total of M-1 count arrays in order.

Count array is nothing but an array storing the count of each element in that subarray. Let the array be 'count', then count[i] is the count of element i.

We'll create similar count arrays for the second array after removing each element one by one. Then see in which position this count array is in the previously created count array list. That's the index to be added.