Minimum time to assemble multipart object

I’ve been asked to do this task in an online assessment. I’ve passed, so my solution is supposedly correct, but I am unable to prove it. The task is:

Given a set of parts (array of integer part sizes), worker must put them all together. Parts are assembled in pairs. To put together two parts of sizes A and B worker needs A+B minutes. The resulting part’s size is also A+B. Write a program to determine the minimum time required to put together given set of parts.

My solution was:

MinHeap h for p in parts:   h.push(p) time = 0 while h.size() > 1:   v1 = h.pop()   v2 = h.pop()   time += v1 + v2   ### assembly time   h.push(v1 + v2)   ### adding new part return time 

This solution passed all tests.


Does this solution produce correct min time, and if yes, how to prove it?

Multipart ranges in Nginx reverse proxy

I am trying to setup Nginx as a reverse proxy. The upstream server is serving some media files.

Because of the large amount of requests for these files and also since these files are not going to change for at least a couple of weeks, I’m caching the upstream responses in Nginx and serving all subsequent requests from the cache.

proxy_cache_path /home/bandc/content levels=1:2 keys_zone=content_cache:10m max_size=10g inactive=15d use_temp_path=off;  upstream mycdn {     server; }  location / {      proxy_cache content_cache;     proxy_pass http://mycdn;     proxy_cache_methods GET HEAD;     proxy_cache_valid 200 302 7d;     proxy_cache_valid 404    10m;     add_header x-cache $  upstream_cache_status;     .... } 

The clients can send Range requests for large media files. The upstream server does support range requests.

The problem is if I send a request with multiple byte ranges before sending any GET or single Range request (i.e the response hasn’t been cached before this multiple byte ranges request), Nginx delivers the whole file with 200 OK instead of the requested ranges with 206 Partial Content. But once the content has been cached, all multipart range requests work flowlessly.

I looked around a bit and found this blog post:

How Does NGINX Handle Byte Range Requests? If the file is up‑to‑date in the cache, then NGINX honors a byte range request and serves only the specified bytes of the item to the client. If the file is not cached, or if it’s stale, NGINX downloads the entire file from the origin server. If the request is for a single byte range, NGINX sends that range to the client as soon as it is encountered in the download stream. If the request specifies multiple byte ranges within the same file, NGINX delivers the entire file to the client when the download completes.

Is there any way to ensure that if the file is not cached yet, multipart range should be served from upstream alone (without caching) and eventually from local cache after Nginx caches it when GET or a Range request with a single byte range is performed?