[bqe]

I remember being asked this during my interview at Google. It was the first time I heard it and I gave an answer that iterated over the list twice. The interviewer said that it wasn't good enough and I am only allowed to iterate over it once. He didn't let me write my O(2n) solution down so he returned a strong no as feedback.

[heleninboodler]

This type of interviewing style is bullshit. It means the interviewer knows a better solution that is "clever" and expects you to either have the same cleverness epiphany on the spot or to have studied this question. Neither is actually very useful as a hiring criterion.

Guy Steele gave an incredibly interesting guest talk[1] at google about four different ways to solve this exact problem, and the fact that it's an interesting enough topic for an hour long google talk should probably be a clue that you shouldn't be expected to invent the best solution on the whiteboard in 40 minutes.

[1] https://www.youtube.com/watch?v=ftcIcn8AmSY

[jodrellblank]

Guy Steele's talk came up here: https://news.ycombinator.com/item?id=30462835 with an APL solution of:

     +/((⌽⌈\⌽a)⌊⌈\a)-a

with comment that it could "be fully parallelizable and run fast on the GPU, as it's based on a couple scan (generalized prefix sum) operations". Some explanation in my reply there.

[jll29]

I have interviewed hundreds of scientists-engineers-developers, and I never use esoteric quiz questions or logic riddles.

I want to screen people for the skills that they will really need in their daily lives, so that's where I draw my pool of questions from. For example, processing data in the most simple ways (sorting, searching, extracting) quickly reveals if the candidates have actually _done_ what they claim they did. You'd be surprised how many Oxford PhDs struggle to write done a pipeline for extracting a simple word frequency list.

Now you might say "Maybe they're Windows people, or prefer Python." and my response is "I don't mind what tools you use - but you need to demonstrate that you can solve easy/common tasks on the spot, without wasting have a calendar day to re-invent the wheel."

[black_puppydog]

Thanks for the link, that made for entertaining watching!

Curious that he gave that talk about parallelism in the end of 2015, and talked about how we'll engineer more systems to enable parallelism.

First question at the end was actually whether we can get this into existing languages because new languages are "notoriously hard to get accepted."

I'm currently learning Rust and now I'm wondering how the iterator map() and other "accumulation style" functions are implemented and whether there's a way to make these parallel, since the map() call treats things independently and a sum() could be done in the proposed tree style way.

Guess I have a piece of code to look up in the standard library :)

[google234123]

this could be a good question. There’s nothing wrong with a candidate giving some less effluent answer and then progressing up to a better solution with some small hints or discussions

[lupire]

He probably got chastised for poor interviewing in Feedback on Feedback.

[google234123]

That almost never happens.

[Nuzzerino]

They had me do the same problem at Amazon too.