CareerCup

There should be one modification, if the next character is the same as the last character in the merged result, and the last character is chosen from a different string, the next character can be skipped.

Interval tree is also fine

How does solving the problem in 1D lead to solution in 2D? Consider three groups with equal number of people, forming a triangle, the solution is the Fermat point, which is clearly inside the triangle. How to find that point based on the x and y picked individually?

The question is for identifying problems in this setup. If having 1 mutex only is causing problem, we should address the issue and change the design.

We can sort the array from smallest to largest, then for each element i, we are looking for a subset in the range [0, i) with sum equals to arr[i], which is the subset sum problem and it is NP-complete.

However, we can generate solutions with DP:
Solution(sum, i) = Solution(sum, i-1) || Solution(sum-arr[i], i-1)

The DP algorithm can be implemented bottom-up, and it's basically enumerating all possible combinations.

Need to take care of cases when number < 1
sqrt(0.5) = 0.7071

void increase_by(int nums[], int size, int inc) {
    if (size == 0) { return; }
    int sum = nums[size-1] + inc;
    int val = sum % 10;
    int carry = (sum - val) / 10;
    if (size > 1) {
        increase_by(nums, size - 1, carry);
    } else {
        cout << carry;
    }
    cout << ' ' << val;  // Suppose we are just printing to the console   
}

void increase_by_one(int nums[], int size) {
    increase_by(nums, size, 1);
}

Tested with "EGEGEGEE", returns "EEGEGEGE"

One problem is that same cum_sum may appear more than twice, using a key_dict is not enough

You're right, the worst case complexity is O(N^2), and i made some mistakes in step 3. after finding a target.

Mukesh: You should make that clear in the problem, since subsequence does not need the elements to be continuous in the array. [1, 2, 4] is a subsequence of [1, 2, 3, 4]

void print_subarray(int* data, int start, int end) {
    for (int i = start; i <= end; i++) {
        cout << data[i];
        if (i < end) { cout << ", "; }
    }
    cout << endl;
    return;
}

void find_subarray_partial(int* data, int* buffer, int* indexes, int start, int end) {
    if (start > end) { return; }
    if (start == end) {
        if (data[start] == 0) {
          print_subarray(data, start, start);
        }
        return;
    }
    int middle = start + (end - start) / 2;
    
    find_subarray_partial(data, start, middle - 1);
    find_subarray_partial(data, middle + 1, end);

    // Sub problem in which data[middle] must be part of the subarray

    // 1. Calculate the sum around data[middle]
    buffer[middle] = data[middle];
    int sum = data[middle];
    for (int i = middle - 1; i >= start; i--) {
        sum += data[i];
        buffer[i] = sum;
    }
    sum = data[middle];
    for (int i = middle + 1; i <= end; i++) {
        sum += data[i];
        buffer[i] = sum;
    }

    // 2. Sort the sums on left and right side of data[middle] separately, and record indexes before sort. Insertion sort used here for simplicity but real implementation should be replaced by a sorting algorithm with complexity O(nlogn)

    for (int i = start; i <= end; i++) {
        indexes[i] = i;
    }
    for (int i = start; i < middle; i++) {
         for (int j = start; j < i; j++) {
            if (buffer[i] < buffer[j]) {
                swap(buffer[i], buffer[j]);
                swap(indexes[i], index[j]);
            }
         }
    }

    for (int i = middle + 1; i <= end; i++) {
         for (int j = middle + 1; j < i; j++) {
            if (buffer[i] < buffer[j]) {
                swap(buffer[i], buffer[j]);
                swap(indexes[i], index[j]);
            }
         }
    }

    // 3. Get pairs from left and right side of middle whose sums add up to -data[middle]
    int left = start;
    int right = end;
    int target = -data[middle];
    while (left < middle && right > middle) {
        int sum = buffer[left] + buffer[right];
        if (sum == target) {
              // Found a pair, output the sequence
              print_subarray(data, indexes[left], indexes[right]);
              left++;
              right++;
        } else if (sum < target) {
              left++;
        } else {
              right--;
        }
    }
}

void find_subarray(int* data, int* indexes, int size) {
    int* buffer = new int[size];
    int* indexes = new int[size];
    find_subarray_partial(data, buffer, 0, size - 1);
    delete [] buffer;
    delete [] indexes;
}

If the problem is looking for subarrays, then it can be solved by divide and conquer;

Split the problem into three subproblems:
1. All subarrays in array A[0...n/2 - 1] that sum to 0
2. All subarrays containing element a[n/2] that sum to 0
3. All subarrays in array A[n/2 + 1..n] that sum to 0

The time complexity is O(n (logn)^2)
T(n) = 2T(n/2) + nlogn

Space complexity is O(n)

Otherwise it is subset sum problem.