7 ms·
I failed a Twitter interview
- muxxa 13y agoFor a single pass from left to right, I think you need to maintain a counter for each y-value: http://codepad.org/W16O9vUB 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.
- seg 13y agoCheer up, kid. That Justin probably didn't even know what you were talking about. Calculus is not for everybody. :-j
- acchow 13y agoThis 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.
- InclinedPlane 13y agoI 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.
- asveikau 13y agoIs 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.
- acchow 13y ago> 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.
- raverbashing 13y agoIt 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.
- daGrevis 13y agoI think this explains it. http://en.wikipedia.org/wiki/Eureka_effect http://en.wikipedia.org/wiki/Eureka_effect
- etler 13y agoI 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.
- huhtenberg 13y agoNo, 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.
- peterwiese 13y agohahaha, great answer.
- nick_ok 13y agothe 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.
- Camillo 13y agoHow much current? Do you think it would be doable to make a "thinking hat" to wear at job interviews?
- nick_ok 13y agoThis 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%2Fjournal.pone.0016655 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.
- curiousDog 13y agoDid 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 :)
- mostelato 13y agoYeah, I received a rejection letter the next day. Solving it on my own definitely made me feel better though!
- noelwelsh 13y agoTwitter failed you with that interview. Unless the job actually does involve performing computational parlour tricks.
- brent_noorda 13y agoAgreed. 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.
- johnchristopher 13y agoGoogle cache: http://webcache.googleusercontent.com/search?client=ubuntu&channel=fs&q=cache%3Ahttp%3A%2F%2Fqandwhat.apps.runkite.com%2Fi-failed-a-twitter-interview%2F&ie=utf-8&oe=utf-8 http://webcache.googleusercontent.com/search?client=ubuntu&c... It's off-line for me and asking something about installing a server.
- mostelato 13y agoYeah, Kite is being very unreliable :( I keep manually restarting the server.
- deleted 13y ago[deleted]
- guynamedloren 13y agoThanks, 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).
- jeffdm 13y agoHi 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.
- deleted 13y ago[deleted]
- iliaznk 13y agoI wonder if Jack Dorsey could solve rhat right.
- igor47 13y agoyou could solve this with a simple state machine; there's no reason to resort to parlour tricks... https://gist.github.com/igor47/7228586 https://gist.github.com/igor47/7228586
- igor47 13y agooops, sorry! i meant the "parlour tricks" part in response to this comment: https://news.ycombinator.com/item?id=6640033 https://news.ycombinator.com/item?id=6640033 not in response to the author!
- huhalu 13y agotry this test case ([5,1,0,1],1)
- igor47 13y agothanks! i updated the gist (https://gist.github.com/igor47/7228586/revisions https://gist.github.com/igor47/7228586/revisions), but the solution is not nearly as simple as before.
- lelf 13y agoFails for [3,0,1,0,2]
- ledave123 13y agoTry 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
- acchow 13y agoYour solution doesn't work when there is more than one "puddle": https://gist.github.com/alexchow/7228746 https://gist.github.com/alexchow/7228746 Try the case: ([2,5,1,2,3,4,7,7,6,3,5], 12)
- DigitalSea 13y agoNo 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.
- raverbashing 13y agoWell, 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.
- bloometal 13y agoI 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.
- codenut 13y agoWhat 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.
- onion2k 13y ago"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.
- jjacobson 13y agoSo glad Twitter is continuing the tradition of useless interview questions.
- huhtenberg 13y ago> 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.
- msohcw 13y agoDefinitely 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.
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- etler 13y agoNot 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.
- deleted 13y ago[deleted]
- djhworld 13y agoI 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
- undershirt 13y agoI 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.
- GFischer 13y agoI 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 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)
- deleted 13y ago[deleted]
- softbuilder 13y agoIt'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.
- dhruvarora 13y agoWait. 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.
- deleted 13y ago[deleted]
- xentronium 13y agoHow will this solution work for cases like [1,2,1], when there will be no water held?
- Joister 13y agoHis final solution will return 0.
- pjan 13y agoI 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?
- antirez 13y agoI 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 https://gist.github.com/antirez/7231559
- antirez 13y agoehm, no it is not so simple :-) I'll try better after lunch!
- pearkes 13y agoThank 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 https://twitter.com/antirez [2]: http://redis.io/ http://redis.io/
- antirez 13y ago;-) 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.
- Joister 13y agoHere's my attempt, in java. https://gist.github.com/Joist/7229807 https://gist.github.com/Joist/7229807
- granttimmerman 13y agoI 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.
- bartkappenburg 13y agoThis is a really nice and elegant solution: https://gist.github.com/orukusaki/bb189d9f69ad09e2cd5a https://gist.github.com/orukusaki/bb189d9f69ad09e2cd5a
- tiagobraw 13y agoOnce 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
- stefan_kendall 13y agoThis 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.
- JavascriptMan 13y agoThis 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
- susi22 13y agoFYI 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_Wireless_Communication_chapter5.pdf http://www.eecs.berkeley.edu/~dtse/Chapters_PDF/Fundamentals... (pages 183 - 185)
- twiceaday 13y agoHere 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
- deleted 13y ago[deleted]
- huangc10 13y agoimo, 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.
- isb 13y agoIn 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 https://gist.github.com/isbo/7239007
- isb 13y agoAlgorithmic 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.
- etler 13y agoI 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.
- bpicolo 13y agoThey generally have you code on a shared pad like collabedit. It's not over the phone for that part.
- pencilcheck 13y agoI have coded up one pass solution in ruby, check it out! https://gist.github.com/pencilcheck/7252934 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.
- paugay 13y agoHere is my solution in PHP: https://gist.github.com/paugay/7262417 https://gist.github.com/paugay/7262417