[msohcw]

Definitely agree. As a problem, this is pretty easy. Ask anyone that does competitive algorithmic programming. The linear solution is obvious, I wouldn't say that it requires a eureka moment, even though I didn't bother thinking of the one pass because the difference would be minimal at best (for most inputs.) OP should share what his internship was about, I'd disagree if it had more to do with understanding practical implementation and development than efficency and algorithms. Both are valid skillsets equally useful to twitter.

EDIT:apologies to whoever had to kill the extra posts, my mobile hn client is on the fritz.