How to solve a hard programming interview question
dailycodingproblem.com
dailycodingproblem.com
It is one thing to read disciplined approaches to solving a problem - it is another thing to control oneself while under strong emotional states.
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 have very little evidence for why I should hire you.
Talking through your problem solving out loud does not come naturally to a lot of people, but it's an important skill to master for interviewing (as well as for working through real problems in small groups).
Also yes, hearing you reason also matters a lot. I need to see how you refine my lousy problem statement into a solvable problem. Do you make a lot of assumptions about the problem without noticing? Can you consider alternatives or do you get completely stuck on the first solution you encounter? Can you explain a technical idea to someone reasonably clearly and concisely?
I don't need you to be like me, but if we can't brainstorm together about technical problems, we're going to have trouble working together as a team.
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 suspicious if you do. I don't have half an hour to sit on a single problem - that's not the purpose of the interview.
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.
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?
1. It's easy enough so you can talk and explain while solving it.
2. It can show your ability to split problems into smaller subproblems.
3. It maybe filters people that just memorize a bunch of solutions, since it's open how exactly you solve it.
You just have to learn and remember some obscure algorithm to solve them. That just filter for "unexperienced" people that have enough time to actually learn a lot of algorithms by heart.
I.e. that would be fresh graduates. But then you could just look at their uni grades, if you want people who are good at learning.
Which is why I said I don't expect them to solve the problem, I'm interested to see:
- the general thought process - whether the candidate is inclined to jump at the solution or clarify the problem (neither approach is "disqualifying", btw! but for a senior position I do kinda' expect the candidate to recognize when a specification is incomplete, and I will provide increasingly ambiguous problems/questions to see when he stops making assumptions) - that the candidate is capable to identify some "leads"/ subproblems that need to be solved first/ to reduce the problem to a different one/ etc.
> But then you could just look at their uni grades, if you want people who are good at learning.
If only it was so simple... some people are good at learning, they just don't have good grades (e.g. they have to work to support themselves and don't care much about some grades); while others are good at getting generally good grades without actually being good learners (extreme example: cheaters).
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.
(I actually ask the candidate to talk us through his thinking process if I see him sitting there; I start asking questions if he still refuses. I realize that it's an artificial setting, where many people feel pressure to "perform well" rather than just be themselves; unfortunately, I have found no better solution to hiring, that would make the interview unnecessary in all situations)
If someone was a great coder but a mute, your process would weed them out.
Process is about the rule, not the exception. If you don't have killer credentials, and don't do well on the "whiteboard interview", what will happen is that we assume you might not handle pressure well/ are timid, and we'll give you a fairly consistent "homework" (e.g. "fix this Firefox bug, or at the very least analyze the root cause/ how it should be fixed. Send us a log of what you did to narrow down on the issue and on the solution"). If you don't have time to do that (which is possible)... yes, we may not hire you - but, please propose a better alternative if you have one, for I have not found it. I'd actually be very grateful if you can help me find a way to improve this process.
And its frustrating to be one of those people in interviews like that.
And there are plenty of solutions to evaluating a candidate. One, let them take 5-10 minutes of silence to solve if they need it, and discuss AFTER that. You say you want to see a "thinking process" or the candidate evaluating & throwing out ideas, but all of that is possible after a 5-10 minute silence period too.
Its frustrating because I suspect either that you are really just uncomfortable with silence, or have a certain idea of how people SHOULD approach the problem, and your interview process penalizes everyone who doesn't approach it that way. Its a recipe to selecting a certain type of person only and wasting everyone else's time.
I'm acutely aware that there's a degree of arbitrariness in hiring. That's why I was quite honest in saying that I'd appreciate suggestions for better process.
> One, let them take 5-10 minutes of silence to solve if they need it, and discuss AFTER that.
I do that; as you mentioned, people are diverse - some are bothered/ inhibited by silence. If they are silent, I say something like "I can leave you think about it for a few minutes in silence, but it's best if you can just talk to us about how you'd approach the problem, even about the approaches that you know are not good enough; and you can ask clarifying questions if you need to".
Thing is... if you kept silent for more than 30s without writing anything on paper, and I felt the need to intervene, it's either a problem that I consider "easy" and you should've figured out already - or it's one that is probably "hard" and you stand little chance of figuring out by yourself during the interview/under pressure (I've had a few people ask for silence, but can't remember a single one of them that found a good solution in due time). At that point, the only solution is to fall back to the "homework", because while you may be a good programmer, you're not giving me the information to assess that during the whiteboard/in-person interview.
[edit] I should also note that this is valid for algorithmic questions; and not all jobs require that sort of questions to be asked - for some, I might ask some basic stuff to figure out that you know the basic algorithms, but I won't go into hard stuff if I'm asked to hire a junior frontend dev.
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.
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.
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.
Some people (I'd guess introverts, although I'm not sure) need to internalize to think and can't interact much at this point. Some can think and discuss at the same time.
From these two sets of people, some can afterward verbally explain the reasoning and the solution, some can't. Some may also only require a context warm-up.
That makes 4 sets of people already.
"Technical" phone interviews that screen candidates that can solve whatever riddle, filter for a very specific set of people. Not necessarily the best in any context. But a specific set that works for them. Just admit/accept it.
So it evens out!
Smells like cargo-culting of BigCo whiteboard interviews to me.
Perhaps you can simply ask how they arrived to their solution, you owe them at least that. Or be upfront that they should reason aloud.
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.
The approaches for solving Dynamic Programming problems are different than those that require a fundamental data structure (like a heap). Recognizing the heart of the problem is harder, probably what the interviewer is really testing for, and in my opinion differentiates oneself better than following a step by step guide.
// 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 bottom up implementation.
// 1b. Explore backtracking. If it’s a backtracking problem, then I should be able to test for the viability of a partial solution quickly.
...and so on
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
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.
Can you describe how you would do this and talk about how it would impact the time complexity of the algorithm?
It's basically the same problem that peeks its head in every std::vector vs linked list discussion (and it's really amazing how many items you need before std::vector ceases to be a good pick for almost any problem).
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
What relevance does the question actually have to do with the job in question?
The second question to ask is:
Will this be of benefit for the end-user population?
I find that I have no wish to join an IT related part of the organisation when it becomes obvious during the interview that they have no interest in serving the end-user community. They rather want to dictate what the end-user will be using, irrespective of all end-user needs.
So for many years, I have worked on behalf of the end-user to get them to a point that they can do their actual jobs. With the advent of large corporate IT systems, one has seen an increasing amount of null work being required of the company staff (its purpose is to feed the egos of management, instead of actually getting things done). What was that movie??
If what you are doing doesn't enable the end-user to be more productive then what on earth are you doing? Interviewers who are not focussed on building teams to solve end-user problems are failing in their jobs.
End rant.
>Only accepting 98 more subscribers.
>Subscribe for $9.99 / month
Which then slowly ticks down. I was very sceptical about this and refreshed and I found that it just resetted to 100 again and started ticking down again. In other words, it's just a timer.
I thought the article was of good value and that you provide a good service, but then this is contrasted by this scummy, predatory, and dishonest advertising trick.
Thoughts?
I think a good alternative is to give the candidate a nontrivial project that should take around 8 hours, and pay them a day's wage to do it.
It was a long article, but I remember they found success was more a function of the proper team more than anything else. You can take the same 20 people, and have them fail miserably or succeed depending on how you divided them up on projects. Sort of an obvious, but not so obvious result.
If the lists are on other nodes, like in a petabyte sort, that’s where it gets complicated because you need to recover from node failures during the sort.
IME good (10x?) developers are way more efficient because they reason from first principles: don't start from the solution space, but from the problem space, and optimise based on constraints and requirements.
1. Draw the input list on a sheet of paper
2. Try some solution methods on paper, writing them down so I can later re-examine them with new findings.
In this example, you could actually accomplish the solution in linear time using a hashmap and keeping track of the min/max vals; O(max-min)
Something like...
let map = {};
let minVal = null;
let maxVal = null;
for (let a of arrays) {
for (let v of a) {
if (minVal === null) minVal = v;
else minVal = Math.min(minVal, v);
if (maxVal === null) maxVal = v;
else maxVal = Math.max(maxVal, v);
if (!map[v]) map[v] = 0;
map[v]++;
}
}
let result = [];
for (let i = minVal; i <= maxVal; i++) {
for (let n = map[i] || 0; n > 0; n--) {
result.push(i);
}
}
return result;
Perhaps add a check to see if min-max is greater than K*N, and if so then use alternative method (e.g. merge sort)
Wouldn't it be more sensible to ask for design patterns? At least you can use them in real life.
Or refactoring patterns. Like give them a page of shitty code and ask them to make it nice.
Forcing people to memorize obscure algorithms and solve them on a whiteboard seems like the worst possible solution. Unless you are really looking for some expert on algorithms.
Even for his example I don't believe it's correct - he comes out with 10, 12, 15, 15, 17, 20 but I believe if it's basically zipping the lists I'd expect it to be 10, 12, 17, 15, 15, 20.
sorted([i for i in chain(*lists)])
I guess in an interview you'd have to ask whether to favour performance or readability, though.
However, that's not to say that it's a bad idea to aim for. The problem with this kind of advice though, is it only tells you what proficiency to aim for, and not how to get there.
People only have so much brainpower to use during an interview. If you have to use every ounce of it in order to solve a "hard" problem in the first place, then diverting some of it to explaining things will distract the candidate.
The real secret here is to make sure that you have that extra brainpower, so that you do not have to expend your brain's full capacity while solving that hard problem. So the first step is to practice interview problems until they're second nature. The second step is to practice doing those same problems, while explaining a thought process. Once that is second nature, you can further practice by throwing in unique types of explanations, or using the opportunity to make the conversation more interesting, to make the interviewer more impressed.
I hope that some readers out there understand as well as I do, that the entire job interview process is a farce, and selects for sales skills more than it does for engineering skills. The pervasive idea that you have to explain your work only serves those who learn the type of methodology I described above. There are many brilliant candidates out there who believe that it would be a huge waste of their time to refine these skills, instead of engineering skills or other things that they may want to learn. After all, it would only serve to increase your odds of getting your foot in the door at those companies that use such irrational means to select their employees, and why would a brilliant engineer want to join such a team?
This is the ultimate tragedy for (some, but not all) who are passionate about engineering and rationality, but not necessarily passionate about money. I think we can do better, folks.