Find longest subarray with equal sum

Problem:
Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value.

Solution:
This is same as finding the longest subarray with sum zero in the array C[i] = A[i] - B[i].

Prefix sums + hashtable should give it.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=25036663

Find a subarray divisible by 7

Problem:
WAP a program to find a contineous subset whose sum is divisible by 7. We are given a array of number (negative+positive).
calculate the complexity of your algorithm

Solution:
So, we want to find sub-set [i, j], such that

a[i]+a[i+1]+ ... a[j] ) % k = 0

with k == 7, that really does not matter
________________________________________________
Let's calculate the sum of elements from 1 to i by mod k for each i:

s[i] = (a[1] + a[2] + ... + a[i]) % k

And we can note that, if there is such [i, j] that we are looking for, then:

s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0

So, for each s[i] == s[j], sum of sub-set [i, j] is divisible by k.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5812734516002816

Longest chain of non-overlapping intervals (activity selection)

Problem:
You are given pairs of numbers. In a pair the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b<c.So you can form a long chain in the similar fashion. Find the longest chain which can be formed

Solution:
This is known as Activity selection problem. Using a greedy algorithm to find a solution will always result in an optimal solution:

Sort the set of activities by finishing time (f[i])
S = {1}
f = f[1]
for i=2 to n
   if s[i] ≥ f
      S = S U i
      f = f[i]
endfor

Basically, we always choose an interval with the minimum possible finish-time, thus allowing us to build the longest chain using the rest of the intervals.

Complexity:

time - O(n log n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=5068766153015296
http://en.wikipedia.org/wiki/Activity_selection_problem