IMO, the first thing one needs to do in order to be high functioning with challenge is take the mindset that it is ok to underperform in an interview session and not get a particular job. Taking the stress out and focusing on clarity of deep thought helps almost everyone in almost all situations (I hesitate to say everyone since some people do thrive under pressure).
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 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 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).
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's not "good" versus "bad" engineer/coworker. It's a different way of functioning.
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.
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.
strong and silent is fine, as long as they are on the same page as you and you as them. It might take magic to do that. Communicating effectively is an important thing to avoid wasting time in red herrings.
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'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.
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.
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?
Depends what you're testing for. If I'm testing for problem-solving skills, I will pick increasingly harder problems, until you can't solve them. I will judge you on how well you performed on the one you couldn't solve.
The problem is that you can't just solve the hard problems (e.g. those from hackerrack) like that by just thinking about it for some time (it would probably need hours or days of research).
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.
> The problem is that you can't just solve the hard problems
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).
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.
That's why he can ask if he doesn't know what we expect. Silence is the worst option - we're there to form an impression on you (an accurate one, hopefully) - if you just sit there silently, it won't help us.
(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)
Please be comfortable and be yourself...but we'll have you vocalize your thought process even though this is something you never do while working, you have no experience doing and it makes it tougher to think while you're talking.
If someone was a great coder but a mute, your process would weed them out.
But why do you assume such extreme inflexibility? I actually interviewed a blind person, and believe me, I didn't write/draw stuff and expect him to be able to read it.
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.
There is a whole class of people you will miss - those who can solve problems, but can't vocalize effectively while solving them.
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.
It matters a lot! If I could reduce your toast-based problem solving technique to something we could implement on silicon and gluten, imagine the applications!
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.
On the other hand, if you're cargo-culting interview practices from third-hand accounts of what BigCo tech companies do, you've demonstrated that you're probably not someone I want to work for.
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.
There are other thinking styles beside verbal. You're basically throwing out a large portion of candidates, including very talented ones (as having visual/logical thinking style comes with its own perks, sometimes very valuable).
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.
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.
I would guess the time complexity is the crux with this issue: Without knowing the nature of what the algorithm is used for in practice, you're left guessing. If you assume continuous memory "lists", cheap comparisons and a relatively small set of lists, you're not necessarily wrong to pick a brute-force approach, since maintaining the heap will result in much bigger constant factors in the complexity formula (even due to prefetching and so on).
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).
You have to do K comparisons unless you keep track of the ordering of the other K-1 indices every time you pick a new element. Keeping a heap makes this log(K), yielding a KNlog(K) instead of K^2N. The naive solution is probably better when the number of lists to merge is small.
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
It can be done on O(nk log k) if you always merge two shortest list. If all the lists have length k initially it can be easily done with couple of loops as all the lists will have the same length - n in the beginning, 2n after fist iteration, 4n after second.
A systematic approach like this or others (Gayle Laakmann Macdowell’s BUD) seem to reduce the risk of underperforming, but I haven’t had success with it. Instead, problem identification has been most helpful to me.
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.
This. I tanked an interview once because the problem was phrased in a way that it wasn't apparent to me that it's basically a graph. Once I realised that it was also clear why a simple BFS would solve that problem. Sadly this happened just as the interview was over. I think I sort of blacked out because I couldn't identify the underlying problem, and my mind "unlocked" the moment that the stress of the interview ended. Which reminds me - another important thing is not to get stressed if the solution is not apparent immediately.
// 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.
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
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.
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.
I'm not sure what your point is. Parent says that the article signals it isnt credible by employing a dishonest sales tactic. Your answer is to ignore the potentially valuable signal?
I tend to find problems like this one, where the brute force solution is straightforward and then you can improve it by using a special data structure, easy. The ones I struggle with are the puzzle-like ones, where solving the problem depends on having some single flash of insight.
Conversely, if you just happen to know the answer because you saw it before, it feels a little bit like cheating. Quite honestly, I wonder how useful those kind of questions are to test someone's capacity to do the job.
Yeah, I do not think they are very useful. I know a lot of people, myself included, who perform worse than their true ability during interviews. It can be an anxiety thing, but also some people just prefer to take their time and deliver solutions in writing vs. work things out in real time on a whiteboard.
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.
That's better, but probably still not exactly indicative of real-world work... so much of on-the-job work is teamwork. Perhaps you could interview a group of candidates together and as a group assign a project that you know no one person could finish on their own, but would be manageable broken up. The people that form groups and work well together could presumably bubble up.
Didn't Google do a massive study on this and determine these tests weren't effective in determining success on the job?
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.
This is the basic core of a sort-merge. It depends if the sorted lists are on disk (usually are with each about as big as memory), and how many you merge at once (which is about dividing all available memory into disk buffers, or the disk bandwidth, whichever is the bottleneck), and merging the memory resident lists using a treelike structure to be compute efficient. Also depending on the OS it can take parameter twiddling to achieve full sequential bandwidth.
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.
With all do respect, I think the author is missing an important point: he is talking about communication, but he seems to be the only one talking... IMHO you should first figure out why it's needed, and optimise for it's use case. F.e. if it's only used once a year and a simple merge+sort takes half an hour, it wouldn't be worth implementing it yourself.
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.
In my experience, when interviewers do grade based on algorithmic performance, they want to see low time complexity, and care much less about space complexity.
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;
But you have to quantify the max-min, cause it's quite easy for the data to make that way more expensive then "merge then sort". I.e., run your algo on [[0, 1000000000], [1, 2]]
What about continuous data (real numbers, strings)? Your approach has rather limited application. On a different note, merge/sort approach (O(n log n)) is in general less efficient than the heap approach (O(n log a)), and may be impractical or wasteful of space (O(n) vs O(a)) if dealing with realtime data for example.
Why are those interview questions mostly random algorithms?
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.
Yeah, I was reading through and when he talked about the output being sorted it jumped out at me as a "Wait, what? No, probably not" thing. Perhaps his definition of "merge" is different from mine.
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.
This is not new advice. People have been giving this same advice for years. And frankly, people are sick of hearing it, and it borders on patronizing.
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.
It is one thing to read disciplined approaches to solving a problem - it is another thing to control oneself while under strong emotional states.