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 find it's best to ask easy questions (like fizzbuzz) and very hard questions. For easy questions you gauge fundamental competence, those should be things that decent devs can solve as fast as they can write, it makes it easy to weed out the folks who are clueless and somehow have trumped up resumes. For hard questions you go in with the expectation that you're not going to get a solution to the problem, so you concentrate on observing the process the candidate uses, their problem solving skills, communication, the sort of problems they're comfortable with tackling, and so on.
the word you are looking for is insight problem. Insight problems are problems in which people unable accurately predict their progress. As in if you asked someone to continually report their progress on a problem as they attempted to solve it they would say something like, "0% 0% 0% oh I'finished". Insight problem solving is a topic of significant interest in cognitive science right now and most recently it was found that applying a small amount of electric current to the right side of the brain greatly increase our capacity for insight problem solving. It is pretty dope.
This all came to light in 2011 so pretty recent. Also not only may it be possible, but the term 'thinking cap' has already been used to refer this very invention, namely transcranial direct current stimulation (tDCS). If you are interested check out this article, http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjourna...
However I would not get your hopes to high up. It is unlikely that prolonged exposure would be particularly healthy and i imagine you would get diminishing returns.
Is there a definition of ah-ha moment? Seems like what strikes one person as an "ah-ha" insight might be a baseline assumption of another person's thought process.
It means (I think) that the trough between the "good answer" and the "bad answer" is too big. So basically either you know it or not and can't "grow" toward a solution easily
I think it can be summed up to; you're expecting a specific final solution. Open ended questions that don't have a best solution will require you to pay more attention to the process, rather than the result. In this article, the guy was smart enough to figure it out, but during the pressure of the interview, didn't stumble upon the right solution or fully verify his initial solution, but was able to as soon as the pressure was off. With an open ended solution it's not about getting it right, but how you try to come up with an answer.
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.
No offence to Twitter, but this is a seriously bad way of hiring developers. What are you trying to recruit mathematics scholars as developers? When will companies like Twitter learn not all great developers are math geniuses? I didn't even get a college education to get where I am, I failed maths in school as well, but I can code, so what does that mean? I think it means nothing in the greater scheme of things. By the sounds of it the author got a better position in the end, I'd rather be working at Amazon who are solving much better problems than Twitter ever will likely solve anyway.
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.
I have no idea why a bunch of people here keep saying these questions are good for recruiting 'mathematics scholars'. Fact: I am a mathematics graduate student and I would not be able to solve this problem. I hope there isn't a notion that people studying mathematics spend all their time solving Project Euler type questions.
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.
"this is a seriously bad way of hiring developers"
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.
I have hard time imagining what position, at least if we're talking about software engineering, would require solving abstract toy problems in a timeframe of less than an hour without a chance to ever go back and improve your solution. I'd say it's "did you see this problem before" kind of question. Which means Twitter probably lost a capable and smart hire because he couldn't quickly give a perfect answer to useless puzzle (unless of course he was hired to repair the roof in Twitter's office and solving this puzzle is required for Twitter to survive the rainy season). Hardly a "perfect" way.
What made you say that twitter is trying to recruit math genius? The author's solution involves calculus while the intended solution is only a loop and some if statements. I actually like interview problems like that. It requires critical thinking which shows how the candidates think and it is also almost impossible to google.
> The next day I showed this question to my TA, who's a PhD student in theoretical computer science. After 40 minutes he was also stuck with nothing.
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.
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.
Not all theoretical CS is focused on algorithms, and if this were specifically for an algorithm focused position, I would ask a more in depth and relevant question. This question might be suited for a small subset of jobs, but considering that the guy is still in school doing internships, I would assume the position was a generic software developer position, which makes this a bad question.
While I do not think that the problem is hard in a sense that if you came to me and wanted it solved for you I couldn't do it. I do think that it is a horrible interview question.
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's a test question, duh. You struggle with it - you clearly lack field experience. It doesn't make you an idiot, it doesn't disqualify you as a programmer, it merely tests whether you have a particular basic skill or not.
I had two phone screenings with Amazon recently and they decided not to continue with my application.
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
I applied to a couple jobs in the bay area and didn't do well. I had about the same reaction you did.
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?
Agreed. Instead of "I Failed a Twitter Interview" you could have just as well called this "Twitter Failed an Interview with Me."
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.
It's not you, it's them. A rather brilliant acquaintance of mine did the whole fly-to-SF song and dance with them and didn't make the cut either. (He got snagged by a wonderful startup soon after though.)
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.
;-) I'm back, and I hopefully fixed it in the gist, adding a second pass (still O(N) but more complex implementation). Probably there are simpler ways, and indeed now I'm going to read the solution proposed in the blog post.
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.
Did they actually call you back with a rejection? Sorry if I missed that in the article. Anyway, at the end of the day, what matters is that you solved it on your own :)
This pseudo-code seems to be with only one pass no ? Can someone find a counter-example ?
overall_max=0
index_of_overall_max=0
Second_max=0
index_of_second_max=0
Array_of_cumulated_Sum=0
Total=0
for i from left to right
if Height(i)>overall_max
//Water Area between new max and old max
Total+=overall_max*(i-index_of_overall_max+1)-(Array_of_cumulated_Sum(i)-Array_of_cumulated_Sum(index_of_overall_max))
overall_max=Height(i);
index_of_overall_max=i;
Second_max=0;
index_second_max=i+1;
else
if Height(i)>Second_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
Second_max=Height(i);
index_second_max=i
end
end if
Array_of_cumulated_Sum(i)=Array_of_cumulated_Sum(i-1)+Height(i)
end for
//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))
return Total
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.
I think this is a terrible way to conduct a phone interview. I think about code visually, and this is a very visual question, so thinking about this entirely in my head is way harder than writing it down. I'd be worried that having a computer in front of me would give the wrong impression, if typing sounds are heard on the phone, and I wouldn't want to discount a potential great developer just because they were too nervous to ask if it were ok to grab a pen and paper. With all the ways we can communicate now, it seems archaic to ask someone to think through and explain their code over the phone.
Wait. I fail to understand why this counts as a reason for rejection. You attempted a solution, which the interviewer backed up (I assume if you were heading in a completely incorrect direction, he would have told you that), you showed quick thinking (connecting local maximas to the problem) as well as coding competence and basic testing knowledge.
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.
Algorithmic interview questions should ideally have multiple solutions of varying complexity. The "brute force" solution should be obvious to anyone competent enough. If they are able to code it up with reasonable clarity and test cases, that is a good start (think of it as the fizzbuzz level). Good candidates should be able to get to the "ideal/aha" solution with some hints. In fact, that process reveals a lot about the candidate. If the candidate doesn't "get" to the ideal solution on their own, it shouldn't be held against them IMO.
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.
In interviews and in general, it usually is a good idea to get a correct yet inefficient solution and then try to optimize it. This usually yields better insights in my experience. Here is a quadratic solution:
it's not "more than one puddle"; it's that i don't count the second puddle because i don't ever "close" it by encountering it's level again. if i go off the edge, i should close it as best i can.
Ah, right. Now that I actually read your code, that's the real bug :p
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.
This is an extremely common ACM question. This would heavily bias toward anyone who has competed in the ACM, which is probably the worst metric for hiring ever.
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.