Coding Interview Preparation in JavaScript
educative.io
educative.io
Where, in any of my day-to-day job duties, am I going to need to find the kth permutation of a set of numbers? or clone a directed graph? If someone presented me with these questions in an interview, I would be tempted to leave.
And in reflecting on my job as a coder, I find that most of the work I do is janitorial; clean this up, add support for this, fix this, talk with product about this, break this up into smaller pieces... Never once have I had to implement a feature that would require these types of algorithms. Like 98% of my challenges are "this needs to work this way, but that needs to work that way, how can we make them work together?".
I'm not picking at educative.io per se, they're just a symptom. It just really sucks that there are some companies out that believe that if you can rattle off an algorithm, then you must be a good coder.
It just really sucks that there are some companies out that believe that if you can rattle off an algorithm, then you must be a good coder.
The implication is (not able to do X) → (not a good coder), not the other way around.
They imply: "Doing this esoteric mathematical stuff is a requirement for being a good coder. And there are more requirements."
EDIT: strictly speaking, they don't even imply that. It may be they just consider this one of the many possible signals. Maybe they only count it if you pass.
Again, most cases may actually well be as you describe. But some might not be.
I ultimately joined that company as, I believe, the oldest engineer at the time. (At the time, I felt the remaining gauntlet of questions they asked were appropriate for the position I was applying for. And in retrospect, it was the younger interviewers, significantly junior to me, who were asking all the questions that required rote-memorization to answer, and the more experienced interviewers didn't.)
In another case, I was I getting interviewed (again, via phone) with a bunch of CS algorithm questions. Now, I have a CS degree, but none of this stuff comes up day to day. I told the interviewer that if these were the kinds of questions, then it didn't seem my 20 years of experience were what they were looking for. The interviewer, someone probably 15 years younger than me, was really flustered, since he was reading stuff right from some collection of questions they had previously prepared and this response didn't match any of the acceptable answers that were listed. The company recruiter called me back later and apologized because the feedback she got from the interviewer was that they were not prepared to interview someone with my experience. Oh, and any tips I could give their recruiting team to address this would be appreciated.
I told them I'd be happy to help improve their interview process, at my normal hourly rate.
I don't think these filters are explicitly designed to reject candidates based on age, but it does result in it as a side-effect due to the freshness of those topics in the younger candidates' mind. And it just ends up being "easier" to go with the candidate who can recite the answer they are looking for, vs actually evaluating the candidate's fitness for the given job. Or hiring someone and seeing how they work out. There's this need to "hit the ground running" with new hires, and a perception that somehow, those who can answer these random trivia CS questions are able to do that better. This isn't an excuse, however I think it does give us some information on how to address the existence/perception of age discrimination where it does exist.
(BTW, I took your use of "implicitly" as being unsavory, to mean "we won't need to reject people due to age, we'll just set them up to fail our test, and maintain our youthful culture", which is where a lot of the rhetoric around age discrimination is focused. That is, I don't necessarily consider it to be the result of bad actors, but inexperienced people who are forced into doing something they don't fully understand or appreciate the complexity of, and they just want to get it off their plate. Admittedly, you might have meant it as I describe in the former paragraph.)
If you know how quicksort works, I think this is a great question because it tests your ability to explain technical material to another human. I think that is a vital skill in all programming jobs.
Of course, if you happen to not know it yourself, you're sunk.
> I told the interviewer that I had not done that in years and I wouldn't implement a sorting routine from scratch these days because I'd use a sorting routine from a library.
Let's say you have a list of events. For each event, you know the year, month, and some other data. You want them sorted chronologically. Obviously you're not going to code the sort by hand. Maybe you'd consider:
1. First sort them all by month.
2. Now that the months are in order, sort again by year to group the years together.
But that does require you to know what a "stable sort" means, and it's likely you won't have a good intuition for that unless you're familiar with at least one unstable sort like quicksort.
> I don't think these filters are explicitly designed to reject candidates based on age, but it does result in it as a side-effect due to the freshness of those topics in the younger candidates' mind.
You say that like freshness is some immutable fact.
I'm a college dropout. Much of the stuff you learned 20 years ago in college, I never got a chance to learn.
So when I started interviewing, I hit Wikipedia and started learning and implementing some algorithms. It's not that hard to refresh your brain, and I'm a better programmer because of it.
Since then, I have often been able to apply that knowledge to my work. I'm continually surprised how often some seemingly muddle hairball of a problem is really just a graph traversal, or a topological sort, or a heap, etc. when you look at it right.
Algorithms and data structures are just new perspectives you can use to approach your work. Who wouldn't want more ways to be able to look at a problem?
> Let's say you have a list of events. For each event, you know the year, month, and some other data. You want them sorted chronologically. Obviously you're not going to code the sort by hand. Maybe you'd consider:
myList.sort(key=lambda x: castToTimestamp(x))
While this is true, that was not the context of how the question was asked.
Obviously you're not going to code the sort by hand.
Maybe you'd consider: 1. First sort them all by month. 2. Now that the months are in order, sort again by year to group the years together.
You've used a relatively massive number of words to describe radix sort (my favorite sort, incidentally).
However, the other response to your comment is exactly what I was talking about. No one is going to get extra points for reimplementing any sorting function while they're on the job (unless designing and optimizing sorting functions actually is the job, which is insanely rare). They're going to get recognized for getting the list of events persisted, queried, and displayed to the user in a meaningful way.
I'm a college dropout. Much of the stuff you learned 20 years ago in college, I never got a chance to learn.
That you didn't get a chance to learn it doesn't negate the fact that asking someone how to implement quicksort during an interview is a red-herring and misdirection from the actual work that will be done on the job. It is in no way representative of the tasks the wide majority of programmers, software engineers, software architects, and systems operations people are asked to do. The actual value in studying sorting algorithms is being able to calculate and recognize the work done and compare their complexity, aka Big-O notation. And, in fact, the different sorting algorithms are used in school explicitly to demonstrate measuring, recognizing, and studying complexity. Showing one implementation doesn't demonstrate that one knows how to do that (although, could be used as a lead in to further questions, as you point out, about, say, stability).
In my experience, this kind of interview question is not intended to demonstrate knowledge of measuring complexity; if they were, it would be phrased differently. "How would you implement quicksort" is a throwaway question on the part of the interviewer. It allows someone to check a box that shouldn't be there in the first place.
So when I started interviewing, I hit Wikipedia and started learning and implementing some algorithms. It's not that hard to refresh your brain, and I'm a better programmer because of it.
If this helps you get the job, then great. But it's not a great interview experience and it ends up excluding a lot of people, for whatever reason.
Rather, let's talk about specific times or experiences that the complexity of some system the candidate wrote or had to deal with presented a problem that needed to be solved.
Admittedly, that doesn't work if your candidates, for whatever reason, are young/fresh out of school, and don't have experience to be able to talk about. Then questions about the specifics of quicksort are applicable. The reason I related my second anecdote was to show that they recognized that the interview method they had were using ended up catering to a specific kind of candidate and wasn't inclusive enough to the wide range of candidates that were available and appropriate for the position. I don't know if they ended up changing their sourcing and interviewing process after that though.
Since then, I have often been able to apply that knowledge to my work. I'm continually surprised how often some seemingly muddle hairball of a problem is really just a graph traversal, or a topological sort, or a heap, etc. when you look at it right.
You shouldn't be: most things are. I think it's a problem in our industry that many people don't recognize that, and it leads to a lot of reinventing of the wheel. Maybe it's because they never learned it, and are not interested in continuing to brush up on it. If you're keeping the specifics of a specific algorithm fresh in your mind by cramming right before an interview, that's great (I, personally, don't have the time, nor interest, to cram for a single interview). Being able to recognize a graph traversal, or that a database implements a specific kind of b-tree and what that means for read and write performance is separate from being able to implement those things, or describe implementing them, on a white board or, ahem, over the phone.
Barriers to entry like the coding interview or ivyness of education often fail to identify the best candidates, reinforce monoculture, and could even indirectly support ageism, racism, and classism. But they persist because arbitrary barriers serve an important purpose in the minds of interviewers.
For example, many organizations may be hiring largely on experience and instinct, with the coding interview serving as confirmation or as a premise to reject.
Most job prep seems to focus on algorithms. The algorithms are easy to test, because there are clean metrics (does it work or not, efficiency, etc). Also they make people feel clever. Finding the most efficient way to transverse a bidirectional, weighted graph seems more important than finding the right function. This is amplified when implemention in some esoteric language like lisp or Haskell (sorry fanboys, its esoteric when its less than 1% on TIOBE). But most programs/apps/services may only implement one of these at their core. If you are building a database or search engine, you will run into these more often, but its limited for most people. CS seems to focus much more on this side of programming.
The second form of programming is API programming, and I use this every day. This includes both finding the right function to use (or close enough) or creating API functions with sane parameters and results. This is much less glamorous, and is theoretically covered by "read the manual." But it is much more nuanced than that. Parameters may not be named the same thing or have the same form between APIs. Handling sync for async function calls are important. Hell, even defining the problem before finding a function for it can be difficult. APIs are the meat of programming. Designing and using them is definitely a required skill.
Being self taught, I learned much more about APIs than algorithms. I am not bad at Math, got a minor in it, but some of the algorithms blow my mind. But I am glad I learned APIs, as I use them every day. If I need to deep copy a map, I use a function.
What little documentation there is typically `TODO: FIX THIS` or `This was the only way this will work and I don't know why.`
Then you realize how much of the world's code is like this and wonder how anything ever works at all. I absolutely love this story [0] for explaining it in a way anyone can understand.
Actually I'd say Lisp and Haskell programmers are much more likely to be "find the right function" programmers.
People who don't know algorithms and data structures tend not to see them where they exist, so it becomes a subjectively self-fulfilling prophecy. You may not need to clone a graph in your day to day work, but seeing graphs where graphs exist can lead you to better solutions in a way that might seem "magical" to others. Even if it isn't too significant, that small edge can make a difference sometimes. Employers rightly want that.
But, you are correct: "a small edge can make a difference sometimes." To some employers that matters. To others? Maybe not so much. Maybe they are happy with a few folks that can deal with the algorithm issues, while the rest of team cranks out APIs and fixes bugs and supports old products.
Completely agree, and you might even learn something during the interview, especially if you were previously the "API" programmer group. I'm entirely self-taught, so I will readily admit that my algorithms and data-structures knowledge is not where I feel it should be.
I did an interview somewhat recently where we talked about a problem that required the use of a data-structure that I had literally read about in preparation for said interview two days earlier, but did not really understand a solid use case for it. As we discussed the problem that was presented, I ended up arriving at the correct solution and everything was happy, but that's not the cool part. The cool part was that as a result of that conversation, all of the sudden the use for that data-structure "clicked", and an entire class of problems suddenly became obvious in how to optimally solve. I will actually be using that exact solution in a side project that's in the planning phase
I haven't done the on-site interview yet, but regardless of whether or not I get an offer (or even accept the offer if one is made), I know that I'm going to walk away from this interview a better engineer for having learned about these algorithms and data-structures just to interview.
Looking back at that phone interview, I wonder just how many other problems I've encountered and solved that would've been better served if I knew more about algorithms and data structures.
After discussing design decisions with people though, I often feel that they think everything will be very difficult and keep hemming and hawing over concerns about how long things will take to implement. I've had to write down pseudo-code for them showing how everything can be done in a single loop and dictionary lookup or something like that to get them to actually agree to their half of the design.
I think the biggest benefit of a strong theoretical background is just knowing beforehand how easy so many problems actually are.
No they don't. Employers heard that Google asks questions like these, and Google is worth eleventy skrillion dollars, so if we ask the questions Google asks we'll be worth eleventy skrillion dollars too!
In much the same way, last decade everybody knew Microsoft asked riddles, and Microsoft was worth more money than anyone could imagine, so obviously asking riddles is the way to end up worth more money than anyone can imagine.
It's basically this comic, but implemented in tech interviews instead of in schooling:
http://smbc-comics.com/index.php?id=3978
Meanwhile the only reason these things seem to "work" for Google et al. is that they get so many applicants they can afford to turn down huge numbers of perfectly intelligent, perfectly-qualified people who might not do so well on an algorithms pop quiz. And at the same time they've made the process easy to game: you can literally get books of Google-style interview questions, study them, and then pass tech interviews without the underlying knowledge/experience the questions are allegedly selecting for.
I just wonder which company will be the next big breakout hit and what irrelevant thing they'll do in interviews that everyone will hurry to nod their heads and sagely agree with as a great indicator of the kinds of things "employers want".
I.e: "So you want to join our product security team and say that you know xml. How would you go about finding an exploit in an app that you can get to parse an xml file?"
And I have heard several stories from several people doing interviews, where the candidate failed this sort of question particularly badly :)
So simple questions in vein of "I see you tell us you know x, that might help you solve problem y we deal in our team often, how would you do it?"
During the hour-and-a-half or so of interview, I was asked to do a few things:
1. explain my technical background, projects I've worked on 2. explain one project in depth, from entry-point to client 3. discuss future features of that project 4. let me implement one feature in that list while they go have some coffee 5. show off my new feature!
Even though the technology I used was not the technology they use, I think my employer wanted to see how well I communicate technically, how well I understand, and how fast I can put things together. He seemed to like the fact that I had a lot of failed iterations and Googled to get through snags.
Another interview process I was quite fond of had me working on one of _their_ pet projects; looking through their code base, identifying possible improvements/features, and implementing those improvements in a new git branch.
Of course, that process may not work with EVERY technical interview, but my bet is that practical interviews like these are more likely to show an employee's technical prowess than a person simply memorizing algorithms. While I agree that there is a place for algorithms, it should not be the focus of an interview.
The example is a checkout register at a store.
They submit their example, and we review it, make notes, and when they come in, we go over it and talk about it. What we look for is the code itself and also how they explain their decisions along the way.
We find that this really paints a very vivid picture of the candidate, far more than white boarding exercises, stand behind them coding exercises or trivial bs questions.
I will freely admit my algo knowledge isn't where it needs to be. But I know an algorithm's need where I see one, and consistently. The problems always contain a very specific problem space:
1) sorting
2) Large tables of information
3) categorizing
In nearly every case, the appropriate, well researched, proofed, Ph.D approved answer is a quick google away. If you're asking algorithm questions in your interviews, all you're looking for is someone's ability to conjure from memory an appropriate approach. Congratulations, you hired a flash card.
You know who I want to hire? Someone who shows creativity and drive through their experience (usually surfaces as having their hands in a lot of disciplines both CS and non), and someone who learns quickly. If they can implement an algorithm (not needing to conjure it on the spot), that's all I need. By the way, no self respecting algo researcher/analyst sits down for 45 minutes to come to a correct and efficient solution to an algorithm problem.
Enjoy your grad students. I'll take a maker any day.
So, it's worth mentioning that there are two types of algorithm questions.
You seem to be complaining about the "show me merge sort" style, where the interviewer picks a commonly-taught well-known algorithm. I have, in practice, seen this style exactly once (maybe I'm missing a broader trend, though) and it thus comes off as a strawman.
The other type involves solving problems that most interviewees, by shear numbers, can't possibly have seen before. Here, you're testing for on-the-spot thinking, not memorization. This is what I actually see when I interview.
Because in practice, how many people need to implement merge sort? 99% of them should call `List.sort` and be done. But the algorithm for traversing this strange dual-tree structure or whatever probably isn't in the standard library, and I do need someone who can do that.
And why do you think this is the best way to test for on-the-spot-thinking? I know I personally need a bit of time to soak in an algorithmic question to arrive at a viable conclusion. I might have some theories or hypotheses at first, but in the context of a 45 minute interview, it's simply testing nothing other than whether or not I've been exposed to this particular problem before. I happen to be great at thinking on the spot when I need to improvise through a problem or debug a problem, but that would fail your metric because you asked the wrong question.
I know this may come as a great surprise to you, but not all questions of a person's abilities can be answered by whether or not they can write a joint scheduling implementation in the amount of time it takes to get through a short lunch.
I just wrote this comment on another thread here, I think it is relevant:
yea, and in a huge coincidence, you're not going to hire most interviewees...
Off the top of my head, or at least where I've used them recently:
> kth permutation of a set of numbers?
Producing all pairs of a collection, e.g. for computing the minimum distance between elements (via map/reduce).
> clone a directed graph
Any object in an OO language (like JavaScript) is essentially a directed graph, so, cloning one of those.
It knows what it needs to extract, but when it's done, it needs to delete rows from the DB. Naturally, we use foreign keys; and we're not turning those off, because we don't want to risk losing data. That means we need to walk the foreign key graph of the schema for all tables who have rows scheduled for deletion, determining a partial order for the graph so we can delete in the correct order.
Graph walking, partial orders - basic discrete math - and practical tasks in everyday programming.
Last month, I was implementing a filtering mechanism for our result tables. That involved converting a predicate created by auto-filter style dropdowns into SQL, in an efficient way, analyzing the predicate to determine which tables needed to be joined to solve the problem. Recursive parsing of JSON, expression tree walking, elementary code generation - basic compiler theory, and not that unusal a task in everyday programming.
Seems like every bit of work I do beyond a very basic level of functionality involves a bunch of computer science fundamentals. Why shouldn't I screen for this in interviews?
I have had some need for this, while implementing tool for populating our database with test data :) But I have to admit that I went out of my way to snag that task, because I really wanted to utilize a non-trivial graphing algorithm one-day at my work.
I agree to an extent that programming interviews are bad at filtering out candidates, but to an extent knowledge of data structures and algorithms go a long way in defining an ability of a programmer to solve the problems (often faced when dealing with systems like Databases, Operating Systems, Build Tools, Compilers) at hand in a reasonable way. One might not realise but knowing CS Fundamentals helps in orthogonal ways. Of course, coding is just a small part of software engineering-- there's design, planning, team work, testing, infrastructure and seemingly endless list of things to care about.
I think a better judge of a programmer is really in "projects" they've accomplished. The ability to get done is so much important, I cannot emphasize more. Some companies, like Google, do try to identify and hire people based on their contributions to open-source and participation in projects of interest. Whereas, others, such as Stripe, have a very different kind of an interview process altogether (take home assignments, pair programming, presentations etc).
A realistic example was when we were working on speeding up some chart rendering, and we realized that we were wasting a lot of time attempting to render things that were not visible on the screen. We saw it was too slow, and then thought: Is there something out there for occlusion culling? We looked at videogame literature, found quadtrees, and wrote our implementation. But would it make any sense to ask any interviewee about their knowledge of quadtrees? It'd be unfair, as none of us would have passed that interview in the first place.
Never in my career did I have to do any of the things some of the "interview prep" material out there is geared towards (even though I understand this is supply and demand as some companies are notorious for this CS exam type line of questioning).
That's not to say that I didn't have to deal with algorithms - things like strategies for cache cold starting and invalidation, custom encryption, high volume batch tokenization of sensitive information etc etc.
The thing is - every time I faced a task that would require a reasonably involved algorithmic approach I would do research, prototype the solution, functional/perf test different approaches etc etc.
For that reason I would take someone who can outline these steps for me preferably with the tools/frameworks involved over someone who happened to remember a specific CS algorithm I asked them about. And if they can tell me how they would go about automating their testing, how they would react to unexpected events like message delivery mechanism failures that would be even better :)
Cloning a directed graph seems like a perfectly reasonable interview question. It requires no specialized knowledge, just being able to navigate a fairly common data structure. I can't imagine a competent programmer not being to solve that problem on a whiteboard, which is precisely the point.
It's problems like that which terrify newbies.
I would venture to say there are a small set of positions where you'd use these exact skills on a fairly frequent basis.
20% of our applicants pass this, and they all go through a phone screen first..
I think it's a fair question..... but "())))(((" would fail in the second condition
Would something like this pass (maybe with some comments and test cases)?
1 @tailrec
2 def hasBalancedParens(s:String, open:Int):Boolean = {
3 if(s.length == 0) open==0
4 else if(s.charAt(0) == '(') hasBalancedParens(s.tail, open+1)
5 else if(s.charAt(0) == ')') open>0 && hasBalancedParens(s.tail, open-1)
6 else hasBalancedParens(s.tail, open)
7 };
If this answer fails (modulo any stupid mistakes; idk if it even compiles), you might consider being much more specific about the desired average runtime complexity.
If this answer passes but would fail if line 4 was modified, you might consider re-writing your problem text to include either "Feel free to ask for clarifications" or "A string has balanced parentheses only if every closing parenthesis is preceded by an opening parenthesis". People tend to not treat interviews like normal interactions, and interview questions don't have a surrounding context so it's hard to determine what it means for an answer to be correct.
function getBalance (parenStr) {
var count = 0;
for (var i = 0; i < parenStr.length; i++) {
if (parenStr[i] === '(') { count++; }
else if (parenStr[i] === ')') { count--; }
}
return count === 0;
}In a previous job, a question like that would not even get a 20% pass rate, but it also have a lot to do with where we were sourcing our employees: If you are talking to generic contracting firms that employ people in giant, generic behemoths, you WILL get a lot of terrible candidates from them. From the powerpoint architect that hasn't written a line of code in weeks, to people that just had a job at big megacorp, and did the minimum possible not to get fired (and, in some of those corps, that's really little).
It got that bad that there were employer patterns that we considered resume black flags: Spent one year in MasterCard? Well, they hire pretty much anyone for a year, and they just don't get renewed, so we will understand that experience as 'you weren't good enough to work there, and most people there suck'.
For example, your code would return true for ")())((" even though nothing is balanced. I was thinking more of a stack; push to stack only on opens, pop on closes, if we get a close before an open is on the stack, then we return false.
But I only thought about it for a few minutes so it's rather rudimentary.
I see this work better with non-entry level positions, assuming candidates apply to fewer companies and companies have fewer candidates to interview.
School is also a filter for future scientists.
In my country school was always about learning the fundamentals. What you will actually do on the job you will learn... on the job. Nowadays there are more and more voices asking for more practical classes but I feel this is risky: if you know the fundamentals you can quickly adapt. If you only learn how to do one practical thing you will have to retrain when that thing becomes obsolete.
The problem is that we tend to lump all programmers together by assuming they should all know the same things. The reality, however, is that there are different kinds of programmers who need to be proficient at different skills. Wide receivers, quarterbacks, kickers, and linebackers all have different coaches, diets, and training regimens for a reason.
Companies who realize this and incorporate this into their hiring will be at an advantage. Companies who don't will be at a disadvantage (unless they are so hot that they get 100s of resumes from over-qualified applicants every day, in which case it doesn't particularly matter what they do).
If the role is JavaScript-centric, how about a question specific to the language like Describe the difference between var and let, and when you would use one over the other?
Traversing JSON, or cloning an object or array is actually somewhat common. But I find it funny that the solution is to make a Class, having a "for in" loop, and variable declarations in a loop. It's clear that the one who made that solution has never done any serious JS coding silly smile
I could make another rant about making a new Class for each problem. You want to write code that is easily removed, not complexed!
Edit: In safari, javascript error in web inspector ironically.
To be a bit more specific about this issue we are actually using an outdated version of a dependency 'pace' that uses local storage (they have taken it out in new version) so hopefully with an upgrade this issue will be resolved. Based on your feedback we will make sure to prioritize fixing this.