CareerCup

Maybe this, in Python:

def sets_overlap(idx1, idx2, length):
    return min(idx1, idx2) + length > max(idx1, idx2)

def same_relative_weight(lst, idx1, idx2, length):
    sum1 = sum((i+1)*x for i,x in enumerate(lst[idx1:idx1+length]))
    sum2 = sum((i+1)*x for i,x in enumerate(lst[idx2:idx2+length]))
    if sum1 == sum2:
        return True
    #try reversed
    sum2 = sum((i+1)*x for i,x in enumerate(reversed(lst[idx2:idx2+length])))
    if sum1 == sum2:
        return True

def make_staff(lst):
    for cur_len in xrange(len(lst)/2, 1, -1):
        cur_len_sets = {}
        for idx in xrange(0, len(lst)-cur_len + 1):
            cur_sum = sum(lst[idx:idx+cur_len])
            if cur_sum in cur_len_sets:
                #maybe there's a match
                #copying the list, we will need to append to the original
                for other_staff_idx in cur_len_sets[cur_sum][:]: 
                    if sets_overlap(idx, other_staff_idx, cur_len):
                        #no good, save for later
                        cur_len_sets[cur_sum].append(idx)
                        continue
                        
                    if same_relative_weight(lst, idx, other_staff_idx, cur_len):
                        print 'found a match!: ', other_staff_idx, idx, cur_len
                        return
            else:
                #just add to cur length
                cur_len_sets[cur_sum] = [idx]

This seems like an homework assignment, you cannot remember the whole question as is, as a matter of fact even if they ask you such a long question it will take at least 15-20 minutes to get it and then 20 minutes to design a solution and 20 minutes to code it, depends on your typing speed. Stop asking solutions for your assignments.

1. Make a 2D matrix of size n*n where n is length of string
2. fill matrix while matrix[i][j] has sum of all values from i to j. can be done in n2 using bottom up approach of dynamic programming
3. traverse matrix and put all values in hash table. while key is matrix[i][j] and value is (i,j). if already present, append new (i,j) (dont replace)
4. sort hash table key values from high to low
5. for each key in sorted hash key values, get hash value.
6. if hash value has 1 value go to next. else go to step 7
7. for each (i,j) pair, check if any pair exists such that (j1-i1)==(j2-i2) and they are not overlapping. if exists. return with this pair

Here is my code:

#include <stdio.h>
#include <stdlib.h>
static  void centerweight2(unsigned int *wsum, unsigned int *asum, int len)
{
        int count1,count2,count3;
        int found;
        if(2>len)
                return;
        count1=len>> 1;
        for(found=0;count1;count1--)
        {
                for(count2=0;count2+(count1<< 1)<=len;count2++)
                {
                        int leftwsum=wsum[count2+count1-1]-wsum[count2-1];
                        int leftasum1=(asum[count2+count1-1]-asum[count2-1])-leftwsum*count2;
                        int leftasum2=(count1+1)*leftwsum-leftasum1;

                        for(count3=count2+count1;count3<=len-count1;count3++)
                        {
                                int rightwsum=wsum[count3+count1-1]-wsum[count3-1];
                                int rightasum1=(asum[count3+count1-1]-asum[count3-1])-rightwsum*count3;
                                int rightasum2=(count1+1)*rightwsum-rightasum1;
                                int temp=(leftwsum+rightwsum)*(1+(count1<< 1))-(count1<< 1)*rightwsum;

                                if(((leftasum1+rightasum1)<< 1)==temp||
                                   ((leftasum1+rightasum2)<< 1)==temp||
                                   ((leftasum2+rightasum1)<< 1)==temp||
                                   ((leftasum2+rightasum2)<< 1)==temp)
                                {
                                        found=1;
                                        break;
                                }
                        }
                        if(found) break;
                }
                if(found) break;
        }
        if(count1)
                printf("%d %d %d \n", count2, count3, count1);
         else
                printf("found non\n");

}
void centerweight(char*p)
{
        unsigned int *wsum, *asum;
        int count;
        int count2;
        if(NULL==p)
                return;
        if(!*p)
                return;
        wsum=malloc(sizeof(unsigned int)*501);
        if(NULL==wsum)
                return;
        asum=malloc(sizeof(unsigned int)*501);
        if(NULL==asum)
                {free(wsum); return;}
        asum[0]=0;
        wsum[0]=0;
        for(count=1;*p;count++, p++)
        {
                int temp;
                temp=*p-'0';
                if(temp>9||temp<0||count> 500)
                {
                        free(asum);
                        free(wsum);
                        return;
                }
                asum[count]=asum[count-1]+temp*(count);
                wsum[count]=wsum[count-1]+temp;
        }
        centerweight2(wsum+1, asum+1, count-1);
        free(wsum);
        free(asum);
}

I didn't test this code, but it should be simple to understand.
The question is really asking if there're two same sized continuous segments that has the same sum. so:
1. construct a table T[n/2][n] // longest segment is half the size
2. T[i][j] stores the weight of the segment starting at j, with size i
3. fill the table
4. searching from the last row (longest), if in the array T[i] there are two segment of the same weight, say T[i][k] and T[i][l], return k (first segment start), l (second segment start) and i (length).

Here's the code which I wrote without testing:

// assume it's easy to convert string into int array
void GetStaff(int A[], int N)
{
	int *T = new int[N/2][N];
	for (int i = 0; i < N/2; i++)
		memset(T[i], 0, N);

	// build table
	for (int i = 0; i < N/2; i++)
	{
		for (int j = 0; j < (N - (i-1)); j++)
		{
			// sum of weights for length i
			int s = 0;
			for (int k = 0; k < i; k++)
			{
				s += B[j+k];
			}
			T[i][j] = s;
		}
	}
	// check
	for (int i = N/2-1; i >= 0; i--)
	{
		int *t = T[i];
		int k = 0;
		while (T[k] > 0) {
			int l = k;
			while (T[l] > 0) {
				if (T[k] == T[l]) {
					// found
					cout << k << " " << l << " " << i << endl;
				}
			}
		}
	}

Move a summing box (window) throw the input digit array.
Start with max possible window size=N/2 and decrement it on the next step.

public static void main(String[] args) {
//        41111921111119 
//        11119 11119
        
//        131251141231
//        1312 1231
        
        String input = "41111921111119";
        
        int[] digits = stringToIntArray(input);
        
        StaffInfo staff = findLongestStaff(digits);
        
        System.out.println(staff == null ? "no staff found" : staff);
        
        if (staff != null) {
            printStaff(digits, staff.from1, staff.wsize);
            printStaff(digits, staff.from2, staff.wsize);
        }
    }
    
    private static void printStaff(int[] digits, int from, int wsize) {
        System.out.println(Arrays.toString(Arrays.copyOfRange(digits, from, from + wsize)));
    }
    
    private static int[] stringToIntArray(String input) {
        int[] digits = new int[input.length()];
        for (char i = 0; i < input.length(); i++) {
            int digit = input.charAt(i) - '0';
            if (digit < 0 || digit > 9) {
                throw new IllegalArgumentException("not a digit, ch=" + input.charAt(i));
            }
            digits[i] = digit;
        }
        
        System.out.println(Arrays.toString(digits));
        
        return digits;
    }

    private static StaffInfo findLongestStaff(int[] digits) {
        int count = 0; 
        
        // try to find from max possible window of pieces
        for (int wsize = digits.length / 2; wsize > 1; wsize--, count++) {
            // move 1st window
            int sum1 = 0;
            for (int from1 = 0; from1 <= digits.length - wsize * 2; from1++, count++) {
                if (from1 == 0) {
                    // calc start sum
                    sum1 = getSumForWindow(digits, from1, wsize);
                } else {
                    // move prev sum for 1 piece
                    sum1 = moveSumForWindow(digits, from1 - 1, wsize, sum1);
                }

                // move 2nd window
                int sum2 = 0;
                for (int from2 = from1 + wsize; from2 <= digits.length - wsize; from2++, count++) {
                    if (from2 == from1 + wsize) {
                        // calc start sum
                        sum2 = getSumForWindow(digits, from2, wsize);
                    } else {
                        // move prev sum for 1 piece
                        sum2 = moveSumForWindow(digits, from2 - 1, wsize, sum2);
                    }
                    
                    // stop when find window of pieces with the same length
                    if (sum1 == sum2) {
                            System.out.println("center weight, digits.length=" + digits.length + ", iterations count=" + count);
                            return new StaffInfo(from1, from2, wsize);
                    }
                }
            }
        }
        
        System.out.println("digits.length=" + digits.length + ", iterations count=" + count);
        return null;
    }
    
    private static int getSumForWindow(int[] digits, int from, int wsize) {
        int sum = 0;
        for (int i = from; i < from + wsize; i++) {
            sum = sum + digits[i];
        }
        return sum;
    }
    
    private static int moveSumForWindow(int[] digits, int from, int wsize, int sum) {
        int movedSum = sum - digits[from] + digits[from + wsize];
        return movedSum;
    }