I failed a Twitter interview • Hacker News Board

Re: I failed a Twitter interview

#61

Post by stefan_kendall » Wed, Oct 30, 2013, 2:43 PM UTC

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.

Re: I failed a Twitter interview

#62

Post by stefan_kendall » Wed, Oct 30, 2013, 2:45 PM UTC

onion2k wrote: post #42

DigitalSea wrote: post #12

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 t…

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

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.

Re: I failed a Twitter interview

#63

Post by GFischer » Wed, Oct 30, 2013, 2:47 PM UTC

djhworld wrote: post #26

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…

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)

Re: I failed a Twitter interview

#64

Post by antirez » Wed, Oct 30, 2013, 2:47 PM UTC

pearkes wrote: post #52

antirez wrote: post #51

Earlier quoted context omitted.

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.

Re: I failed a Twitter interview

#65

Post by JavascriptMan » Wed, Oct 30, 2013, 3:03 PM UTC

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

Re: I failed a Twitter interview

#66

Post by susi22 » Wed, Oct 30, 2013, 3:55 PM UTC

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)

Re: I failed a Twitter interview

#67

Post by twiceaday » Wed, Oct 30, 2013, 4:02 PM UTC

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

Re: I failed a Twitter interview

#68

Post by [deleted] » Wed, Oct 30, 2013, 4:17 PM UTC

[deleted]

Re: I failed a Twitter interview

#69

Post by huangc10 » Wed, Oct 30, 2013, 4:32 PM UTC

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.

Re: I failed a Twitter interview

#70

Post by ledave123 » Wed, Oct 30, 2013, 4:37 PM UTC

huhalu wrote: post #15

igor47 wrote: post #9

you could solve this with a simple state machine; there's no reason to resort to parlour tricks... https://gist.github.com/igor47/7228586

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