CareerCup

Everyone know how to code , it will be better to discuss abt various approaches to attach this problem , it doesnt make any sense to copy-paste ur programming skills here .. we agree that who ever is pasting the code are excellant programmers who can code , but 99% of the people who visit this blog can code given ..

So pls people try to improve your thinking and various ways to attack any given problem and better to discuss abt which data structure is better for a given problem , that is more important than your code . pls avoid posting pages & pages of code , no one is going to appreciate you for that .thx for everyone .

create a new array of size arr1, lets say output array.   insert all elements of arr2 into hash
len = arr1.length;
for (i = 0; i < len; i++) {
    if (exists arr1[i] in hashmap) {
        output[i] = output[i-1] + 1;
    }
    else {
        output[i] = 0;
    }

    if (output[i] == arr2.length) {
       return j; //j is last index of arr1, which contains all elements of arr1 starting from j - arr2.length
     }
}

ex: arr1 = {4, 1, 6, 3, 5, 4, 3, 6, 8, 4, 1, 9, 5}
arr2 = { 4, 1, 6, 8, 9 }

ouput = {1, 2, 3, 0, 0, 1, 0, 1, 2, 3, 4, 5, 0 }

1. Store all the element of array 2 in hash table<value, index no in array 1 - initially 0 for all element).
2.Start searching array 1 elemnt in hash. If elemnet found update index value in hash.
3. now check in hash table forr start and end index.

class Program
{
static void Main(string[] args)
{
int[] a = { 1, 10, 2, 4,0, 5, 8,0,0, 9, 12, 3, 8, 9, 7, 9, 4 };
int[] b = { 12,5, 3,8, 9 ,0,0,0};
Print(a);
Print(b);
int sum = 0;
int mul = 1;
foreach (int i in b)
{
sum += i;
if (i != 0)
{
mul *= i;
}
}
int sum1 = 0, mul1 = 1;
int index = 0;
for (int i = 0; i < a.Length; i++)
{
sum1 += a[i];
if (a[i] != 0)
{
mul1 *= a[i];
}
if (i - index == b.Length - 1)
{
if (sum == sum1 && mul == mul1)
{
Console.WriteLine(index);
Console.WriteLine(i);
break;
}
sum1 -= a[index];
if (a[index] != 0)
{
mul1 /= a[index];
}
index++;
}
}
Console.Read();
}

public static void Print(int[] a)
{
Console.WriteLine();
foreach(int i in a)
{
Console.Write(i + " ");
}
}
}

This problem is similar to
question?id=248673 (not pasing link, since comment doesnt allow it)
with an additional constraint that the size of window should be number of elements in array2.

This problem is similar to
question?id=248673 (not pasing link, since comment doesnt allow it)
with an additional constraint that the size of window should be number of elements in array2.

1. find the XOR of the all the elements in the second array a2.
2. now, traverse the first array a1[i,j] s.t j-i+1 == no. of elements in a2 ,then take the xor of a2
3. if xor of a1 == xor a2 then ouput the a1[i,j]
else
i++,j++;
end

Can somebody prove the correctness of this algorithms,I am assuming that since XOR operations is associative operatoin so the o/p is independent of the oder of the inputs numbers.

small typo correction, in step 2 take xor of a1[i,j]

@Snowy
a1[] = {1,1,1,1,1,1}
a2[] = {2,2,2,2}

XOR of a1 to an = XOR of b1 to bn doesn't mean a1..an = b1..bn. Fails for

int arr1[] = {1, 1, 2, 2, 3, 3, 4, 4};
int arr2[] = {3, 4, 4};

bool FindSubSetContainingArray(int a[], int b[], int len1, int len2, int *firstIndex, int *lastIndex)
{
if(!a || !b || (len1 < len2) || (len1 <= 0) || (len2 <= 0) || !firstIndex || !lastIndex)
return false;
map<int, int> countMap;
vector <int> foundSoFar;
for(int i = 0; i < len2; i++)
{
map<int, int>::iterator foundVal = countMap.find(b[i]);

if(foundVal == countMap.end())
countMap.insert(pair<int, int>(b[i], 1));
else
{
int count = foundVal->second;
countMap.erase(foundVal);
countMap.insert(pair<int, int>(b[i], count + 1));
}
}
*firstIndex = -1;
*lastIndex = -1;
foundSoFar.clear();
for(int i = 0; i < len1; i++)
{
int current = a[i];
map<int, int>::iterator foundVal = countMap.find(a[i]);
if(foundVal == countMap.end())
{
if(*firstIndex != -1)
i = *firstIndex;
*firstIndex = -1;
*lastIndex = -1;
if(foundSoFar.size() > 0)
{
for(int j = 0; j < foundSoFar.size(); j++)
{
map<int, int>::iterator foundVal2 = countMap.find(foundSoFar[j]);

if(foundVal2 == countMap.end())
countMap.insert(pair<int, int>(foundSoFar[j], 1));
else
{
int count = foundVal2->second;
countMap.erase(foundVal2);
countMap.insert(pair<int, int>(foundSoFar[j], count + 1));
}
}
foundSoFar.clear();
}
}
else
{
int count = foundVal->second;
int key = foundVal->first;
countMap.erase(foundVal);
foundSoFar.push_back(key);
if(count > 1)
countMap.insert(pair<int, int>(key, count - 1));
if(*firstIndex == -1)
{
*firstIndex = i;
}
if(countMap.size() == 0)
{
*lastIndex = i;
return true;
}
}
}
return false;
}

u think a state machine would be a better way... with a starting point as any number you travel all othr numbers without repeating any number..and at the end if u reach the other end... you have your indices

i think just starting from index 0 in array 1,choose as many elements in array 2 contiguously n compute its sum n product n cmpare it with the sum n product of array 2.if they are equal then they contain the same set of integers otherwise move the index by 1 n repeat the same...........

For Venkatesh,

Wrong theory. Two sets (a,b,c} and (d,e,f) can have same product and sum.
You can try fixing different values for a,b and d,e to find out c and f.
Hence, solution and program are wrong.

I guess is ishan is partially correct , rather than adding the sub-elements, its good to compare the elements in array 1 with that of array 2 , and if for lenght of array2 number of elements are found continously in array1 , then we found the sequence ..

ishan is wrong in one case : first array 1 2 3 6 7 8
second array 2 4 5

here , 236 and 245 add up to same value , but not all the values are same ..

Hash table gives the most efficient solution - but doesn't handle duplicates. I now provide a scheme to handle duplicates with hash tables - without altering the overall complexity.

1> Maintain a flag with your main program, say "possible_find" initialized to zero.

2> Whenever you encounter the first positive match in the bigger array, increment its value by 1. You only increment again when the current search starting with the positive match in the above line doesn't terminate successfully and you find another positive match some point down the line - another possibility to find a solution, if there is one. So possible_find = 3 implies that you are analyzing the third possibility of finding a solution and that the first two were unsuccessful.

3> Maintain some count field with your hash table, initialize them all to zeros during hash table construction. Every-time you find a match increment the corresponding count by 1. Now comes the main logic - at any point during a possible find operation the value of any of your counts must not exceed your possible_find flag. If so, declare the current search failure and start another.

How about:
1. Sort arr2 (smaller in size than arr1) and preserve its sum too (call it sum2)
2. Iterate over arr1 with window of length = len(arr2) and if the sum2 matches the sum of the window, sort the window (in n.log(n), n being len(arr2)).
3. Then match the window with sorted arr1 (from #1 above)

It can be easily done in O(n): here is the pseudo code:
-insert all elements of arr2 in a hashtable of type <key,count>
-it=0;//iterator of arr1
-start=-1;//possible start of the solution
-it=0 to size[arr1]:
if arr1[it] present in hashtable with count>0:
do: nmatch++;
if(nmatch==1)start=it;
if(nmatch==size[arr2])report start as ans;
if present with count==0:
while(arr1[start]!=arr1[it])
hashtable[arr1[start]].count++;start++;nmatch--;
hashtable[arr1[start]].count++;nmatch--
//now,for arr1[it] (curr value)
//count is no longer 0
start++;//new possible start of the solution
it--;//reprocess this element,next time ,cancel the effect of it++
if not present:
while(start<it)
hashtable[arr1[start]].count++;start++;
//reset everything
nmatch=0,start=-1;

It can be easily done in O(n): here is the pseudo code:

-insert all elements of arr2 in a hashtable of type <key,count>

-it=0;//iterator of arr1

-start=-1;//possible start of the solution

-it=0 to size[arr1]:

if arr1[it] present in hashtable with count>0:

do: nmatch++;

if(nmatch==1)start=it;

if(nmatch==size[arr2])report start as ans;

if present with count==0:

while(arr1[start]!=arr1[it])

hashtable[arr1[start]].count++;start++;nmatch--;

hashtable[arr1[start]].count++;nmatch--

//now,for arr1[it] (curr value)

//count is no longer 0

start++;//new possible start of the solution

it--;//reprocess this element,next time ,cancel the effect of it++

if not present:

while(start<it)

hashtable[arr1[start]].count++;start++;

//reset everything
nmatch=0,start=-1;

bhaya words main explaination dede yaar.
I l b highly obliged.....

(1) Insert all numbers in 2nd array (and their counts) into a hashtable.
(2) For each number in the 1st array, if it's not a key in the hashtable, just ignore it. Otherwise decrement the count. If the count is now 0, increment a counter, which I call numZeros. Basically when numZeros is equal to the number of keys in the hashtable (numKeys), then we have found the sequence we need.
(3) Since the sequence should be the same length as the second array, after step (2) above, we need to kick out the number that's no longer covered by the current sequence. If that number is not a key in the hashtable, just ignore it. Otherwise we increment its count. If the count is now 1, that means the count was previously 0, and so we should now decrement numZeros.

Below is my code to hopefully make this more clear.

static int start(int[] arr, int[] arr2) {
  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  for(int i : arr2) {
    if(!map.containsKey(i))
      map.put(i, 0);
    map.put(i, map.get(i) + 1);
  }

  int numKeys = map.keySet().size();
  int numZeros = 0;
  int len = arr.length;
  int len2 = arr2.length;
  for(int i=0; i<len; i++) {
    int n = arr[i];
    if(map.containsKey(n)) {
      map.put(n, map.get(n)-1);
      if(map.get(n) == 0)
        numZeros++;
    }

    if(i>=len2) {
      n = arr[i-len2];
      if(map.containsKey(n)) {
        map.put(n, map.get(n)+1);
        if(map.get(n) == 1)
          numZeros--;
      }
    }

    if(numZeros == numKeys)
      return i-len2+1;
  }

  return -1;
}

snowy - Bingo ! It takes care of repeated numbers peacefully.

snowy - Bingo ! It takes care of repeated numbers peacefully.