I failed a Twitter interview (opens in new tab)

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

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

It's off-line for me and asking something about installing a 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.

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

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

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

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.

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?

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

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

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.