I failed a Twitter interview | Hacker News Reader

I failed a Twitter interview

qandwhat.apps.runkite.com

60 pointsmostelato73 comments

This question involves an "a-ha" moment (for the linear-time solution) and was thus banned from interviews at Google last year.

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.

No, it doesn't involve the "a-ha" moment.

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.

How much current? Do you think it would be doable to make a "thinking hat" to wear at job interviews?

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 hate this kind of problems.

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.

I think this explains it.

http://en.wikipedia.org/wiki/Eureka_effect

> Is there a definition of ah-ha moment?

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.

Twitter interview puzzle creator?

You can take months to create puzzles, there's no pressure here.

The problem is that this is a bread and butter ACM problem. Anyone who has competed will know the solution. And biasing for ACM competitors is awful.

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.

Well, you may want to hire math scholars. I think it's important to have some in your team.

But it's also important to focus on other aspects as well.

Google cache: http://webcache.googleusercontent.com/search?client=ubuntu&c...

It's off-line for me and asking something about installing a server.

Hi creator of runkite.com here -

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.

Thanks, I'm not familiar with Kite, so when I saw it, I thought it going to give me some kind of coding test (that OP failed).

Yeah, Kite is being very unreliable :( I keep manually restarting the server.

> 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.

I didn't know about CareerCup. If I ever try my hand at interviews in the U.S. I'll probably use it :)

http://www.careercup.com

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 really don't get these coding interviews.

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?

Twitter failed you with that interview. Unless the job actually does involve performing computational parlour tricks.

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 did not read the final solution but this was a little stimulating quiz, so this is my Ruby solution:

https://gist.github.com/antirez/7231559

ehm, no it is not so simple :-) I'll try better after lunch!

Thank you for posting this and demonstrating how absolutely pointless these questions are for finding qualified candidates.

For those of you who didn't notice, antirez[1] makes a data storage system called "Redis"[2]

[1]: https://twitter.com/antirez

[2]: http://redis.io/

;-) 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.

So glad Twitter is continuing the tradition of useless interview questions.

FYI this algorithm is called the "Water filling algorithm" and is used extensively in Communications to optimize the allocation power for channels.

You can get a solution with simple Lagrangian method (which I believe is the linear solution).

http://www.eecs.berkeley.edu/~dtse/Chapters_PDF/Fundamentals...

(pages 183 - 185)

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 :)

Yeah, I received a rejection letter the next day. Solving it on my own definitely made me feel better though!

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

Cheer up, kid. That Justin probably didn't even know what you were talking about. Calculus is not for everybody. :-j

Once I failed at a google interview... I got 2 answers right but I couldn't answer a third math related question (because the time was over).

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 have my phone interview with Twitter next week.

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.

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.

They generally have you code on a shared pad like collabedit. It's not over the phone for that part.

I wonder if Jack Dorsey could solve rhat right.

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.

For a single pass from left to right, I think you need to maintain a counter for each y-value:

http://codepad.org/W16O9vUB

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:

https://gist.github.com/isbo/7239007

I have coded up one pass solution in ruby, check it out!

https://gist.github.com/pencilcheck/7252934

A lot of solutions here doesn’t seem to take account of multiple puddles, my solution does take that into account.

Here is a novel solution.

  make stack
  water = 0
  for n in columns
    while stack not empty and n > stack top
      water += min(stack bottom, n) - stack top
      pop stack
    stack push n

This is a really nice and elegant solution: https://gist.github.com/orukusaki/bb189d9f69ad09e2cd5a

Here is my solution in PHP: https://gist.github.com/paugay/7262417

Here's my attempt, in java.

https://gist.github.com/Joist/7229807

How will this solution work for cases like [1,2,1], when there will be no water held?

His final solution will return 0.

you could solve this with a simple state machine; there's no reason to resort to parlour tricks...

https://gist.github.com/igor47/7228586

Your solution doesn't work when there is more than one "puddle":

https://gist.github.com/alexchow/7228746

Try the case: ([2,5,1,2,3,4,7,7,6,3,5], 12)

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.

oops, sorry! i meant the "parlour tricks" part in response to this comment: https://news.ycombinator.com/item?id=6640033

not in response to the author!

try this test case ([5,1,0,1],1)

Try the list(reversed()) of the cases and this finds more bugs:

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)

Another mismatch: MISMATCH: [2, 0, 1] holds 1 (got 0) TRUE: [1, 0, 2] holds 1

thanks! i updated the gist (https://gist.github.com/igor47/7228586/revisions), but the solution is not nearly as simple as before.

Fails for [3,0,1,0,2]

imo, interesting and fun question. Difficult to solve on the spot but not bad when you dive into it with a cup of coffee. Always just keep it simple.

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.

Reply on news.ycombinator.com