"Fast Response" Locating a Proxy Server for the network

Question

"Fast response". A series of client machines are located along a linear network. The i-th client generates amount of traffic that is given by w[i]. You want to put a server somewhere along the linear network that minimizes the total amount of traffic carried by the network. Provide an O(n) algorithm to identify the location of the server.

Answer 1

Greedy algorithm works fine.

1. Iterate the weight array from left to right and find out the TOTAL weight.  // This step takes O(n) time
2. Iterate the weight array again from right to left and find the point at which the accumulated weight meets or exceeds half of total weight.  Put the proxy server on that location.

Examples:

Given [1, 1, 1, 1], put the proxy server on the 2nd server

Given [1,2,3,4], put the proxy server on the 3rd server.

Given [1,2,3,10], put the proxy server on the 4th server.

Given [10,1,1,1,1,1,1], put the proxy server on the 1st server.