Use case for scripting that's not better satisfied by using a scripting language:
Ed reads the entire file. If you need to move back and forth through the file, or move lines from one place to another, or reprocess the same line repeatedly, it can be far more convenient than a scripting language.
I almost always prefer some kind of balanced tree to a hash table, because no matter the original specifications, sometime during the development of a program I usually need the elements in order.
I may have spoken un-artfully, but there is an important point here that is being missed. I bet that every civil engineer, if asked at an interview, could explain the basic design of Galloping Gertie and the flaws that caused it to fail. I bet that every architect, if asked at an interview, could explain the basic design of the Twin Towers, and discuss why it was less resilient to heavy lateral impacts than other skyscrapers. I bet that every journalist, if asked at an interview, could quote some of the advice of Strunk and White.
As a broad statement, certainly not always true, computer programmers seem to be less knowledgeable of their professional culture than other professions. There is no equivalent to <em>Architectural Digest</em> or <em>Journal of Accountancy</em> or <em>Morbidity and Mortality</em> for programmers, so programmers have to work harder to keep up with their profession. If you can demonstrate that at an interview, you have a leg up on the candidate who can't.
Do you have to know the linear solution to the maximum sum subsequence problem to get hired? Of course not. But if you know it, and the other guy doesn't, then all other things being equal, you get hired, not him.
I should also have mentioned that there must be some context to the programming questions being asked at an interview. There are probably better questions to ask a PHP web developer.
Oofabz: Bentley recounts the history of the problem. Several experienced computer scientists believed for several weeks that the O(n log n) solution was optimal. If you think the linear solution is immediately obvious, you're special.
DannoHung: It may be that I have not fully specified the problem, but an empty sequence has a sum of zero, which is the maximal sum if all elements of the sequence are negative.
Abyssknight: I've never shipped anything. I've always worked in an internal support position, never on a shipping product. But I regularly develop and install new programs for my internal customers, in addition to supporting vendor code; I guess you could say I've shipped those programs.
Goombastic: I'm not a stupid HR guy. I'm a programmer who has stopped asking this kind of programming questions because I don't think they tell me much about the candidate. But it seems other folks do ask this kind of programming questions, so I put them on my blog from time to time.
Programming Praxis (http://programmingpraxis.com) provides a collection of etudes, updated weekly, for the education and enjoyment of the savvy programer. Although there is some math content (the current exercise uses the chinese remainder theorem), Programming Praxis is much less math-oriented than Project Euler.
programming Praxis (http://programmingpraxis.com) offers a series of exercises, similar to Project Euler, but with more emphasis on programming and less emphasis on mathematics. There are new exercises every Tuesday and Friday.