CODEWITHSUNDEEP
javamultithreading
Alan
Alan

Reputation: 527

Use Parallel Thread to sum up 1 billion consecutive numbers, return one single number?

Faced this question in my interview.

What I answerred is that:

  1. divide 1b numbers into 10 group

  2. Use threadpool to create one thread for each group, 10 totally

  3. each thread sum up the result for the group passed and retrun the value

  4. use Barrier to sum up all results after 10 threads end, return the final value

My doubt is what's the expected answer for this question ? And if it's running in single-cpu (no multi-thread mode), should single thread be faster than multi-thread ?

Thanks a lot.

Upvotes: 1

Views: 2391

Answers (6)

inf3rno
inf3rno

Reputation: 26139

What do you mean by consecutive? If there is a regular gap between them and then you can use the average of the first and last values total = n*(last+first)/2.

If the gap is not regular, then one method to group numbers by index and add them together that way. If they are big numbers, then you can split them up by every i digits and add together only that i digit in a single thread. Instead of keeping the whole thing in memory I would rather add together smaller chunks and save the partial result, so the process could be paused and continued.

Having 10 cores does not necessary mean that using 10 threads is the optimal solution. The OS might use a core, your program that creates the groups might use one too (but I guess it is paused until the threads are working) and by hyperthreading you can use double the threads than cores.

Upvotes: 0

Ed Staub
Ed Staub

Reputation: 15690

A trick question, perhaps - to see if you can think outside the box you're given?

If they're consecutive, as noted in the title, and they begin with n, then: 

final long BILLION = 1000000000;
long answer = (BILLION * n) + ( BILLION*BILLION + BILLION ) / 2;

This works for n up to somewhere around a billion - after that it will overflow.

Needless to say, I don't see how multithreading would be of any benefit at all!

Upvotes: 7

Steve J
Steve J

Reputation: 2674

http://businessmajors.about.com/od/gmatpracticequestions/a/GMATtest1.htm

I think faced with this question, I would have answered with "I would research the problem first, since I'm guessing there is a formulaic solution that would give me the answer faster than a brute force approach. Mathematicians have come up with formulas to solve all sorts of clever little questions. No shame in finding an expert to solve a problem quickly and efficiently."

Of course, in an interview, who has time to frame an answer like that?

UPDATE: Oops, I read your question again, and I see the interviewer was compelling you to use threads and such. Still, I might have pointed out that many brute force problems are solved far more elegantly with a bit o' math. Tell him to use the parallel thread to run a browser, call up Google, do a search, and solve the problem in about 20 seconds.

Upvotes: 1

emory
emory

Reputation: 10891

I am extremely unimpressed with your answer. (Perhaps I am misunderstanding the question.)

Would not a more approriate answer be: given parameters i and j where I want the sum of i, i+1, i+2, ..., j-2, j-1, j be

  1. in thread 1 calculate i*(i+1)/2 and
  2. in thread 2 calculate j*(j+1)/2
  3. join the threads and calculate the sum

Be sure to use BigInteger for the arithmetic.

I would guess if i and j are extremely large numbers multithreading would be faster than single threading. But i don't see the advantage of more than 2 threads

Upvotes: 2

Ian Macalinao
Ian Macalinao

Reputation: 1668

You should have said that you would add the numbers in each thread as BigDecimal objects. Once each thread is completed, add the numbers to an ArrayBlockingQueue. When there are 10 objects in the queue, dump the queue and iterate through each BigDecimal, adding each number.

Multi-thread should be faster if you have multiple cores. If you have one core, it'll be slower.

Upvotes: 0

Pintobean77
Pintobean77

Reputation: 1415

In each thread, use a BigInteger to keep running totals.
Have a centralized BigInteger that is properly protected (by Barrier or Synchronized). When a thread is done with its run, it gets a lock on the centralized BigInteger, adds in the threads sum, then releases lock.

..At least that's how I'd have done it. But Andrey is right, the 'answer' is only half of what they are looking for :)

Upvotes: 0

Related Questions