Addition of elements of Two Arrays

Question

You have Two arrays

int[] a = {......} // Total elements 1 million
int[] b = {......} // Total elements 1 million , Length is same for both arrays.

Q1. I have to create an array

int[] c 

whose elements are sum of corresponding indexes of a[] and b [] Ex.

 c[0] = a[0] + b[0];
 c[1] = a[1] + b[1];
 c[2] = a[2] + b[2];

Solution : -> I can take advantage of Multithreading. Divide the whole array in 10 or more parts and assign each segment to a thread to perform the calculation. Note-> Interviewer suggested to use Multithreading

Q2. Now its little bit changed.Elements of array C will have values like this :->

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + c[0]; // At this line c[0] is Sum of a[0] + b[0]; The Above Line
c[2] = a[2] + b[2] + c[1]; // At this line c[0] is Sum of a[1] + b[1]+ a[0] + b[0]; The Above Line

MySolution-> Solve Part 1 (Q1) and create a temporary array and after that we have to perform addition like this.

C[1] = temp[1]+temp[0]
C[2] = temp[2]+temp[1]

Note :-> We really don't need temp[], we can do this only using Array c Also. Just to explain this on SO in easy way.

Problem-> I dont think that in question 2 we can use multithreding. Is there a better way to solve Q2 ? Can we take advantage of multithreading in this.

Answer 1

In my opinion for question two you have two techniques:

First should be done in two steps. step-1 using threads you can add

 c[0] = a[0] + b[0];
 c[1] = a[1] + b[1];
 c[2] = a[2] + b[2];

as you suggested.

But step-2 should be done sequentially. because c[ i + 1] value depends on updated value of c [i]

Second technique is bit complex but can be fast.

What you are asked to do in second question is do something like:

 c[0] = a[0] + b[0];
 c[1] = a[1] + b[1] + a[0] + b[0];
 c[2] = a[2] + b[2] + a[1] + b[1] + a[0] + b[0];

This can be parallel.

c[i] =  thread1( sum(a[0]...a[i] )) + thread2( sum(b[0]...b[i] ))
         for i >= 0

Good is in this technique, you can calculate c[i] parallely for all i (its two like level threaded model).

You can further improve thread1/thread2 functions as multithread with child threads to perform sum – but remember sometime multi-threaded code runs slow then single-threaded code because of thread context-switching time (So you should give sufficient amount of task to each thread).

A point that is unlike about second technique is "most of what the threads for c[i] do is the same as what the threads for c[i-1] do as well".
Thanks to @jogojapan to let me know about this drawback point.

For better technique read updated answer by Mr.Jogojapan.