Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to solve a hard programming interview question

dailycodingproblem.com

Post reply on HN
Print view View original

61–70 of 84 posts

Re: How to solve a hard programming interview question

#61

Post by twelve40 »

virgilp wrote: post #29
mattm wrote: post #19

Earlier quoted context omitted.

Does it really matter though? What if I solve problems by eating a piece of toast? There's really no way you can understand how someone else thinks in an hour. All you're really going to look for is "Does this person think the same way that I do?"

I concur - it does matter. I'm not looking for "thinks the same way that I do" - I'm looking for "thinks". And specifically, how. I want to see you evaluate & discard ideas. I want to know that you quickly identified the "brute force"solution and discarded it, rather than sitting there for 10 minutes, not knowing how to even start. You must realize, if the problem is hard, I don't even expect you to solve it. You're…

and that's what makes it ridiculous. In my whole career I have not been forced to vocalize hard problems on a whiteboard in one hour, getting judged for how good of a dog and pony show I put on with "evaluating and discarding ideas" on the fly, out loud, in an interrogation setup. This is so artificial. Not even close to how real teams work. My best ideas start to really form after thinking about a hard problem for days, including in off hours, background mode. Often I have to talk to many people, including non-programmers, to cover all angles of a hard problem.

These "hard interview problems" that must be solved through some artificially staged contemplation really are useful for two reasons:

* it's sadly the only way to quickly try to get a random reading of a person in a semi-standardized way while minimizing time commitment, kind of like fast food is the quickest way to fill oneself, and

* people who pass these at least demonstrate that they can drill/memorize or otherwise prepare for a challenging activity, which takes time and discipline, which in general are desirable characteristics

that's it, pretending like this in any way models real work or has any other benefits is not right.

Re: How to solve a hard programming interview question

#62

Post by urgoroger »

theossuary wrote: post #2

Am I missing something, or couldn't you just merge the lists like you would in merge sort? Begin with a pointer at the start of each list, find the minimum of the elements being pointed at and increment that pointer, until all pointers are at the end of their respective lists. You could possibly even do it in place. That was my first thought anyway.

This is correct, and I think it's mentioned in the article. I think this is probably what most people would think of too rather than the heap based solution. Using the heap solution also requires you to know how to use a heap in whatever language your interviewing in, or you could implement one (which would probably a lot more effort), so I prefer this one.

EDIT: Ah, I didn't read your comment carefully enough. I thought you were referring to a divide and conquer approach when you meant 'like merge sort', where you the list of lists in half for each recursion, the recombine the sorted halves using a standard merge sort list merge.

What you describe is basically the same as the solution given by the author. However, you don't give a way to find the minimum pointer, in the case of the author, a heap is used. Using a more naive data structure/algorithm (e.g. just finding the min over all pointers every time) will probably give worse asymptotic complexity than using a heap to maintain the least element

Re: How to solve a hard programming interview question

#63

Post by abhirag »

reyg wrote: post #48
suyash wrote: post #33

Earlier quoted context omitted.

Care to elaborate how do you go about problem identification?

Hm, here is an example: // 1. Explore the possibility of a recurrence relation. If the problem can be solved as a function of sub problems, then candidate techniques are DP, backtracking, greedy, and divide/conquer // 1a. Explore DP. If it’s DP, then optimal solutions of its subproblems are all that’s necessary. Confirm that subproblems are repeated so that I can reason for memoization and later leave room for a bott…

I think your example can be simplified :)

Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time and well backtracking is recursion so the strategy can very well be -- Explore the possibility of a recurrence relation, if the possibility exists, try recursion :D

Re: How to solve a hard programming interview question

#64

Post by [deleted] »

CobrastanJorji wrote: post #17

> I often find it’s not enough to just be able to solve the question; you really need to vocalize your thought process. I interview candidates regularly, and I can't overstate how important this is. If I ask you a hard interview question, and you sit silently for 10 minutes and then write out a perfect solution on the board without any discussion of how you got there, all I've learned is that you knew the answer. I h…

[deleted]

Re: How to solve a hard programming interview question

#65

Post by Steve-_-Jobs »

CobrastanJorji wrote: post #17

> I often find it’s not enough to just be able to solve the question; you really need to vocalize your thought process. I interview candidates regularly, and I can't overstate how important this is. If I ask you a hard interview question, and you sit silently for 10 minutes and then write out a perfect solution on the board without any discussion of how you got there, all I've learned is that you knew the answer. I h…

If I speak anything while solving the problem, this will distract me greatly from actually solving it and also embarass me a lot because I usually immediately recognize that an attempt of solution I'm thinking about is not right, so I don't want to sound like an idiot speaking about stupid solutions which don't work.

Re: How to solve a hard programming interview question

#66

Post by Scarblac »

mplewis wrote: post #39
zaptheimpaler wrote: post #25

Earlier quoted context omitted.

Problem solving is pattern matching/recognition. Many of us solve problems wordlessly in our head with no explainable "thought process". After solving it, i can explain quite clearly but not during. One does NOT need to be able to simultaneously solve & explain how you solve an abstract algorithm problem to be a good engineer either. Dont kid yourself its only an "important skill" because you like to test for it.

Part of hiring is finding out if someone can work well with a team. Lots of teams need everyone to be able to communicate well during collaborative problem solving sessions. I've worked with the strong, silent type of coworker who has a solution in their head. But because they don't vocalize what they're thinking, I can't participate or help. That's not what I'm looking for in a good engineer and a good coworker.

It depends on who you already have in your team.

Having a few members who can solve hard problems on their own is great, and they usually have to be silent and focused while doing it. You also need people who are good at participating and helping and explaining their thought process. A team that has only one type isn't going to be the most effective team.

Re: How to solve a hard programming interview question

#67

Post by Scarblac »

virgilp wrote: post #29
mattm wrote: post #19

Earlier quoted context omitted.

Does it really matter though? What if I solve problems by eating a piece of toast? There's really no way you can understand how someone else thinks in an hour. All you're really going to look for is "Does this person think the same way that I do?"

I concur - it does matter. I'm not looking for "thinks the same way that I do" - I'm looking for "thinks". And specifically, how. I want to see you evaluate & discard ideas. I want to know that you quickly identified the "brute force"solution and discarded it, rather than sitting there for 10 minutes, not knowing how to even start. You must realize, if the problem is hard, I don't even expect you to solve it. You're…

And the candidate has no way of knowing what you expect, he's just been given a problem to solve.

One time I was rejected for not identifying and discarding some particularly stupid attempt at doing something (it involved assuming that it was safe to trust input coming to the server over HTTP), but I have explained to people not to do that so many times that I really don't consider doing things that way in the first place.

Re: How to solve a hard programming interview question

#68

Post by Double_a_92 »

CobrastanJorji wrote: post #17

> I often find it’s not enough to just be able to solve the question; you really need to vocalize your thought process. I interview candidates regularly, and I can't overstate how important this is. If I ask you a hard interview question, and you sit silently for 10 minutes and then write out a perfect solution on the board without any discussion of how you got there, all I've learned is that you knew the answer. I h…

If the problem is too hard it's not always possible to talk or draw something while thinking about it. You go through dozens of possible solutions in your head, to find a good one.

That's like asking a champion chessplayer to explain what he's thinking about while trying to make a move.

So this only works if the candidate already knows the solution, and knows which way is right and just explains that one (and maybe a few bad alternatives on purpose). Or if the problem is relatively easy.

Re: How to solve a hard programming interview question

#69

Post by half-kh-hacker »

TheSmoke wrote: post #36

disregarding the performance, if someone asked me to write it pythonic i'd just do: sorted([i for i in chain(*lists)])

Yeah, this is what I thought too.

I guess in an interview you'd have to ask whether to favour performance or readability, though.

Re: How to solve a hard programming interview question

#70

Post by virgilp »

twelve40 wrote: post #61
virgilp wrote: post #29

Earlier quoted context omitted.

I concur - it does matter. I'm not looking for "thinks the same way that I do" - I'm looking for "thinks". And specifically, how. I want to see you evaluate & discard ideas. I want to know that you quickly identified the "brute force"solution and discarded it, rather than sitting there for 10 minutes, not knowing how to even start. You must realize, if the problem is hard, I don't even expect you to solve it. You're…

and that's what makes it ridiculous. In my whole career I have not been forced to vocalize hard problems on a whiteboard in one hour, getting judged for how good of a dog and pony show I put on with "evaluating and discarding ideas" on the fly, out loud, in an interrogation setup. This is so artificial. Not even close to how real teams work. My best ideas start to really form after thinking about a hard problem for d…

> This is so artificial.

Right. It's an interview - artificial by definition, not meant to be perfect; in fact perfection in hiring (or in anything) is unachievable - we aim for the "good enough".

> Often I have to talk to many people, including non-programmers, to cover all angles of a hard problem.

Here we are - me and my colleague - there to answer questions, reflect on your thoughts, etc. Talk to us, that's exactly what I expect. Not just to give solutions, but to clarify the problem (for you and for us). Make us understand how you're looking at it - we'll also share our perspective and see if we can come up with something together.

Is this really something that you don't see happening, in practice?

Post reply on HN