Don't use questions involving eureka moments. They reveal nothing about the candidate.
Edit: It should be noted that this question was used for a long time at Google, Microsoft, and many other places. It's a terrible question.
Two-pass solution is obvious, just look at the final state. Once you are at that, the one-pass is a run-of-the-mill optimization of switching from accumulating and then processing the state to doing it all in parallel. The ability to recognize when this is doable is a good way to tell someone who's done it before (in some other context) from those who merely wrote a functional prototype of Tic-Tac-Toe in TurboPascal.
I hate this kind of problems.
Not an exact definition, no. But if a question is exceedingly simple after one tiny bit of insight that doesn't require much analytical thinking to arrive at, that certainly falls into the category.
If a company (no matter how great they were) tried asking me these kinds of questions, I would immediately stop the interview and thank them for the opportunity.
In fact I would be thrilled if they are recruiting for math people. They are not. I have been in the job market for a while now and recruiters literally stop listening when they don't hear "CS" in the first sentence.
We can't reasonably assume that Twitter uses this sort of question in all their developer interviews. We don't have enough data for that. Perhaps this guy was going for a role where solving problems quickly and under pressure was a key requirement. If that were the case, this is pretty much a perfect interview question.
But it's also important to focus on other aspects as well.
It's off-line for me and asking something about installing a server.
We currently host development environments so seeing this on the front page was a bit crazy. We just couldn't handle the load.
Sorry about that - working on making it better.
That just doesn't speak well of this particular PhD. The one-pass solution is rather obvious. I hate puzzle-based interviews with passion, but this is actually a very reasonable question and it does help to tell apart people with "theoretical" computer science skills from those with a bit more practical experience.
EDIT:apologies to whoever had to kill the extra posts, my mobile hn client is on the fritz.
I fail to see why one would ask this kind of question and what one would take away from the answer.
How does being able to solve problem like this help make Jack Dorsey richer and more respected? How does it help Twitter users have a better experience? How does it help the interviewer assess whether this dude on the other side will make his life more bearable by not shitting all over the carpet?
I think it is mostly a form of geek bullying and intellectual mastrubation for its own sake. I have a message for the people running companies where these kinds of hiring practices are taking place. You have some insane geeks on the loose and you should catch them and lock them into the darkest dungeon as they __will__ ruin your company.
It was depressing to me and I felt down for quite a bit, mainly because on the second phone screening I just couldn't do the coding task asked. My mind went blank and I probably sounded like a 5 year old struggling through the simplest of questions.
It's my own fault though, I just got more and more stressed over the preceding weeks reading algorithms textbooks and "CareerCup" tests I think I just burned out.
I totally understand that top companies like Amazon and Google can afford to be ruthless and choosy in their interview process, after all, they're top companies for a reason, but I guess it just wasn't for me
The result was that I started working really hard on side projects to see if I was really capable of working up there. That was the beginning of last year, and that pattern of work hasn't stopped. I've learned and built a lot.
About phone interviews though, I've been requesting Google Hangout interviews in place of them. And I've been a lot more comfortable I think because of the face-to-face interaction. Something to think about.
The few interviews I've had here are quite different, since most everyone comes with recommendations and the interviewer has a general idea of what work is at other companies. (I did have a test interview once, where I showed I was completely clueless about CSS, it really wasn't a position for me)
I can't imagine a construction engineering company asking their applicants to do a construction calculation in an interview, and in this case, bad design can actually kill people (as opposed to a bug at twitter).
What else does it bring apart from some amusement to the interviewer?
There's no telling why Twitter didn't make the job offer, but it's probably not because you didn't get the optimal solution to this one particular problem. More likely, Justin just didn't feel that chemistry that made him fall in love with you. Had he felt that immediate bond, he would have unconsciously overlooked any number of sub-optimal answers.
Maybe he didn't like the way you pronounced "max'm'm". More likely, and I'll put money on this, he was in the middle of doing something he thought was important when he was pulled out of it at the last minute to do an interview that some idiot forgot to remind him about, and for a position he doesn't think really needs to be filled, and in any case doing this stupid interview pales in comparison to the task he just got pulled out of, and so he was already in a funk, at which point it wouldn't matter how you answered because Justin was just plain in a rotten mood.
What is important to understand here is that these processes are highly variable and there is an element of luck involved. It's just the nature of a human-driven process and a complicated organization.
For those of you who didn't notice, antirez makes a data storage system called "Redis"
Edit: now that I read the solution, what I found is indeed the two passes solution and not the optimal one with the two pointers going in opposite directions.
You can get a solution with simple Lagrangian method (which I believe is the linear solution).
(pages 183 - 185)
for i from left to right
//Water Area between new max and old max
//All the parts on second max is only to not miss the kept water at the end between the overall_max and another local max
//At the end : water area between second max and overall max
Total += Second_max*(index_of_second_max-index_of_overall_max+1)-(Array_of_cumulated_Sum(index_of_second_max)-Array_of_cumulated_Sum(index_of_overall_max))
The recruiter asked me what was the maximum number of edges on a graph without cycles.
When I was on my way home (in a bus) I had this "a-ha" moment.
Well, they lost a great computer scientist in their team! :P
I remember last year I got a similar question from both Twitter and Fb. It's really just a buckshot. Sometimes you'll get a problem that comes easy and sometimes you'll be sitting there dumbstruck.
Best of luck with your future interviews.
Is this not what Twitter desires through its interviews?Because time and again I have heard that companies look and focus on people's thought processes more than their exact results.
PS: I'm a college student so I'm really keen to know how important being 100% accurate is.
I actually think this is a good interview question, as playing devils' advocate and coming up with testcases that will break your initial code is a key programming skill, rather than assuming it is done and moving along.
A lot of solutions here doesn’t seem to take account of multiple puddles, my solution does take that into account.
water = 0
for n in columns
while stack not empty and n > stack top
water += min(stack bottom, n) - stack top
stack push n
Try the case: ([2,5,1,2,3,4,7,7,6,3,5], 12)
The issue with this "state machine" approach is you don't have "lookahead".
In the two pass approach (approach from one side, then the other), you essentially have two machines, one implicitly serving as the "lookahead" for the other.
not in response to the author!
MISMATCH: [6, 7, 7, 4, 3, 2, 1, 5, 2] holds 10 (got 0)
MISMATCH: [5, 3, 6, 7, 7, 4, 3, 2, 1, 5, 2] holds 12 (got 2)
MISMATCH: [2, 0, 1] holds 1 (got 0)
TRUE: [1, 0, 2] holds 1