Data Structure and Algorithms Interview Questions for Programmers
hackernoon.com
hackernoon.com
It's kind of how in dating people have deal-breakers (e.g. no smokers, no kids, and so on) -- when looking for a job, this is one of mine.
Obviously, the caveat here is huge companies like GOOG, FB, AMZN -- these are big companies that need filters and I completely understand the reasoning behind their process. If I wanted to work there, I would certainly study data structures and algorithms before my interviews.
It's a decent reasoning and would only be able to get away with it if you have some decent years of experience OR some very good open source contributions. Or Both.
Most managers would reach for the algorithms/hackerrank/leetcode because it's the least risk to them.
You mean it's least effort. Least risk would probably be hiring a private investigator to dig up everything about the candidate for the past 10 years.
In other words, there is actually substantial long-term risk involved in simply electing for the default solution, but it feels safe on the short term and won’t make you look bad to your boss.
In a perfect world, HR would understand the position well enough to properly vet it but in practice they tend to revert to easier measures like the ones described.
For a medical doctor it suffices to gets one doctorate. I don't think hospitals will drill him on the core fundamentals of his craft similar to whiteboarding in cs. A patient arrives with a slight fever and a headache. Quick! Which lab tests would you assign him!
When is the last time a hiring manager had 200 good resumes for 3 positions?????
For most companies it is the opposite experience - many open positions, few good resumes, which makes me wonder why they work so hard on keeping people out
- can the candidate get the work we need to do done?
- what do they prioritise when doing the work? What do they value?
- can they do it well? In reasonable time?
- how well do they fit in with my team? Are they somebody my people want to work with? (Probably one of the most important things)
- how much will they grow? Are they open to feedback? Are they focused on getting better?
A whiteboarding session doesn't really tell me much here. But if all the answers to the above are positive, I'm sure the candidate has the flexibility to find and learn what they need to solve a problem.
I don't think anyone is especially fond of judging candidates by using riddles, trivia questions, and unrealistic tasks, but the constraints of the interview process rule out a lengthy and thorough assessment.
http://they.whiteboarded.me/companies-that-dont-whiteboard.h...
Not everybody can afford to be as picky as you regarding job choice (this is not meant derogatorily).
http://they.whiteboarded.me/companies-that-dont-whiteboard.h...
Now, I've seen my fair share of recruiters that did not really understand the topic at hand when asking theorical CS questions, let alone the desired answer. I do so always get really suspicious when they occur.
They're often trivia that I'll never learn from my job, so if I didn't go to school for programming I won't know. Or they're specific to a domain I'll never touch so I won't know.
I don't think they're fundamentally bad (I used to), but I've never read one of these without coming out the other side feeling lower about myself.
Not sure I have a point. Just wanted to share.
I had never done an "algorithms" type interview before, had done no specific preparation, and was a bit baffled by being asked to do a coding exercise in a text editor whilst talking on the phone.
Since I was an "internal recommend" they gave me a second chance. Presumably because they were surprised at how badly I did. But the second interview was worse than the first.
I came away feeling quite humiliated.
I was surprised how one dimensional their process was. And I believe it may have changed since then. My former colleague did apologise when I related my experience and admitted that Google knew they had a problem with the process.
It's like many companies have given up trying to rank applicants based on actual job experience and skills. "You've created and ran successful software for hundreds of thousands of paying customers? That's cool, but if you can't write a merge sort implementation on this whiteboard we'd rather hire the guy that learnt it by heart."
> It's like many companies have given up trying to rank applicants based on actual job experience and skills.
Yes.
> "You've created and ran successful software for hundreds of thousands of paying customers?"
They probably are taking credit for someone else's or their teams work. It's depressing to say aloud, but it's the norm rather than the exception.
Ask them how they identified a complex problem, what process they used to get to its root, what they thought was causing it but actually wasn't, which solutions they discarded and why, etc.
You don't need to have a better understanding of their project than they have. You just need to determine whether they have the ability to solve complex technicals problems in competent ways, and at what level.
For example a more junior person might talk more about solving the problem for today and less about solving the problem for tomorrow. Let them talk it out and see where their attention goes.
A more senior person might talk about similar problems they've seen on other projects and how they leaned on past experience to discard non-optimal solutions faster.
You don't need an algorithms test to determine if someone is likely to be able to "get stuff done" in their role. Talking through past problems and solutions might be a better predictor.
And it is surprisingly common.
Then it's a test, not an interview. I don't think interviews were ever supposed to be perfectly objective. If the interview is only based on CS textbook questions, they might as well replace the interviewer with an online test, which by the way increasingly happens for screening, but my point is that it filters out great engineers who worked and delivered solid products because the interviewers are just not interested in details of past work experience
Again, yes. It is hard to fire a bad candidate in case the interview was misleading. Companies would prefer false negatives over false positives. What you see in interviews is a product of laws about hiring and firing.
If this is the case (i.e. companies can afford this behavior), all the claims about skill shortage are a lie and should be called out.
in-depth questions
How is that any better than hiring a terrible dev that just spent 3 months memorizing Leetcode solutions? Aren't they essentially being dishonest about their skills?
>time-consuming Phone screens are already several hours over several days and on-sites are typically 8 hour affairs. Is this not already time consuming?
Genuinely confused by the Stockholm Syndrome-like mindset that devs have for Whiteboard interviews.
memorizing Leetcode solutions
I have my doubts. Indeed from my own experience with Leetcode is I can only do well on the questions that I think quite hard about. Recently I tried to do a Leetcode question marked Medium, but my 3 line solution (while correct, and working on my own test cases) always resulted in "Time Limit Exceeded". I studied their test cases, and realised that my brute-force solution was of exponential time complexity. I then read of the discussion of the problem, was so delighted with, and surprised by one of the proposed solutions (linear time) that I felt compelled to write down the loop invariant in Hoare logic! Fun evening, and I'll never forget this neat algorithmic trick. I think that practising enough Leetcode so as to do well on the Medium/Hard questions requires developing an understanding of algorithms which is highly useful in practise, in particular, if you work with large data sets, clever algorithms are unavoidable for getting anything done. Have a look at the list of past ACM coding contest winners, e.g. the 1993 winners [1] include Craig Silverstein (first hire at Google) and Tony Hsieh (Zappos, LinkEchange).
Summary: I don't believe that doing 3 months coding challenges is meaningfully described as memorisation.
On top of that, doing coding challenges is perfectly compatible with asking other questions.
I ended up landing the London gig and having a fantastic interview experience with the Bermudian company. They all had VASTLY different interview processes but it really made me realise how stupid that whole algorithm/whiteboard process is.
I think this perception that the big 3 use it as a filter is even a bit lame and lazy. I've heard they do it because it's more costly to hire a dummy than to miss a star, but I would love to see the data around that.
Unless of course they aren't interested in hiring "stars" and just want leetcode monkeys to file in and churn out code with perfect asymptotic behaviour.
My C++ interview is pretty easy. No whiteboarding, just a conversation. I want to know for example if this candidate uses templates judiciously or if they are a maniac. Either is fine btw, I’d just like to know.
But more times than you’d perhaps think, the candidate has admitted that they don’t know C++ at all, and then the really awkward questions come, such as why did they write it down, then apply for this job, then show up for the interview...
Another analogy is jiu-jitsu: grapplers can train strength and endurance by going to the gym, but many do not. Just working on useful technique also doubles as a workout that improves endurance - for a large number of athletes, this is preferred to a gym that targets muscles in unrealistic ways and has no skill-gaining benefits.
* Make a simple memory allocator.
* Make a simple HTTP Proxy
* Make a simple URL parser
* Make a simple CSV parser
* Make a threadsafe Queue
* Design a class to handle exponential backoff
None of these are particularly useful, but I think they can let a candidate show off how they can handle a simple problem, and how they modify their code as the problem grows in complexity. Sadly, most of these questions candidates have no familiarity with. I would much rather see it than more O() analysis.
You'd be surprised how many things can go wrong.
Also, the overlapping rectangles example has an error in the explanation. It says "If any of above four conditions is not true then two rectangles are overlapping with each other, as in following diagram first condition is violated, hence rectangle A intersects rectangle B." This somewhat nonsensical statement refers to a diagram that's not there, but furthermore, incorrectly indicates that the rectangles overlap if "any of [the] conditions is not true", when in fact all of them must be false. The code is correct on this point, but the explanation is wrong.
I'm not sure what you mean by complaining about a magic, invisible head to the linked list. If you can't access the head of a linked list, you can't access any other part of it either.
However, as another comment points out elsewhere in the thread, there is a bigger problem -- the solution offered uses more than one pass.
I'm starting to think I might have better luck having a pre-built some code with some poor practices and asking a candidate to refactor and improve it- evaluating their ability to at least know what clean code is supposed to look like.
That being said, I'm not willing to give up my whiteboard code interviews yet- they are too useful a filter. I still get candidates that sound fine talking about their previous experience and then say things like "oh man, its been a while since I've used arrays" when asked to code.
Python maybe?
It felt like good fair test of someone's day to day ability, isn't really something you can grind for, and presumably also gives quite a good quantitative measure of a candidate if you assign a weight to each bug/quality suggestion.
They get it.
Nope, Audition doesn't sound right.
A FB interview loop consists of a series of discrete interviews, starting with a phone screening (or two, for PE), followed by on site interviews consisting of coding tests, architecture tests, behavioural tests etc.
The coding tests usually consists of questions like "given foo, write a function that does bar". The questions are designed to extract a number of signals from you, including "do you know the language you picked", "did you pick a good language for the question asked", "how fast can you provide a solution". After you provided the initial solution, you might be asked variations of the question, like "given infinite memory and limited cpu, how will your approach change" or even point you to possible improvements. This is not a pass/fail test, just a way to extract some info about your capabilities. At the end of the loop, all feedback is collected and a panel will decide if you will get an offer or not. You might be bad at algorithms, but providing you know your way around the language(s) you picked, show at least a basic level of problem solving and did good in other fields, you will get an offer.
Imho, if you don't get an offer from Facebook, it means you are really bad or not enough experience. Luckily the recruiter will let you know the areas where you need improvements.
This single pass approach introduces a conditional branch inside a loop, which I've found to be generally slower on x86 - because I've made that mistake and years later found a huge performance benefit by using the "dumb" (multiple loop) approach.
They didn't ask for an algorithm with linear complexity. They explicitly asked for a solution "in one pass". That's highly misleading.
Edit (after the reply by zamalek): And you are perfectly right about the performance: it's probably slower than just doing two passes (one to find the length, the second to find the middle).
Convert the linked list to an indexed structure with dynamic capacity like a vector or a hash table. This is easy to do in one pass. ("Visit the node; add it to the hash table. Visit the next node...")
Once you're done, access the middle element.
You've reduced the number of passes from 1.5 to 1, and all it took was duplicating the entire input.
1. Intro: learning how to implement an algorithm
2. Algorithms+datastructures: learning about existing algorithms/datastructures and how to design your own, reasoning about complexity
3. Program design: how to write larger programs (OO, compiler construction, distributed algorithms, etc.)
4. Managing the development process: project management,...
Those interview questions are highly annoying because they only cover levels 1+2. Other important technical skills (able to quickly understand code written by others, how to organize programs, etc.) are not tested. The questions are also rather insulting if the candidate has already several years of experience because they suppose that the candidate is still stuck at those lower levels.
But even if the goal is to test those lower levels, the questions are highly ineffective. Many of them do not test skills, they test your memory. You either have already heard about the cycle-detection question or you haven't. I am surrounded here by very smart people and I doubt that anyone of them would be able to find the answer to that question by themselves in a few minutes.
* The following rant is slightly off-topic:
However, I have to say that I am encountering more and more people like the person who posted here yesterday: People who have been programmers for several years and who admit that they have problems with loops and simple datastructures. In my opinion, if you have problems with those levels 1+2, you should not even think about the other levels. Many problems that we have for example in performance and cybersecurity are caused by the fact that most programmers simply don't know what they are doing. If you have problems with loops, you will not understand what a buffer overflow is. If you don't know what pointers are and how main memory works, you will not understand why your program is slow. And I am saying this as somebody who hates low-level languages like C (although I am quite good at them).
I know that this is currently a highly unpopular opinion among certain teachers who are pushing for a "softer" introduction to programming (with a lot of GUI designing and project management right from the beginning) and I have some sympathy for their position (students should not get the impression that CS is only about programming). But at some point you have to learn how a computer works, otherwise you will copy-paste from stackoverflow for the rest of your life.
How do you find the missing number in a given integer array of 1 to 100? (solution) [1]
How do you land a job at "startups like Uber and Netflix; big organizations like Amazon, Microsoft, and Google; and service-based companies like Infosys or Luxsoft"?
Easy - by rote memorization. And a healthy sense that it's to best not question the basic idiocy behind cargo-cult interview tactics like these.
Because apparently genuinely useful critical thinking skills -- beyond such trivial matters such as how to get a better space-time tradeoff on that petabyte-scale fibanocci generator[2] our customer desperately needs you to design a viable POC for right now, on the whiteboard, before lunch -- basically aren't needed at these companies.
Notes:
[1] You think I'm just being snarky? It's famously common out in hedgefund-land for people to get hired more or less on the basis of being able to whip out a deadpan response to "gee-whiz" questions like these. And to get "flushed" for their inability to do the same. Startups aren't quite so naively reliant on shibboleth questions of this sort -- but but only slightly so.
[2] I'm being slightly hyperbolic with this example -- but only slightly. I've long since lost count of the number of times been asked "design" questions really only slightly more ridiculous than this example. And as a matter of fact I've been asked an "advanced fibanocci" question -- and apparently received a job offer to a large extent on the basis of my ability to "nail" it -- quite recently
A more "natural" sulution would be to sort the list first, and then look for consecutive array items where the difference is not 1.
I think questions like this are fun and novel and also have absolutely no place in an interview for software developers.
Edit: the slightest of arguments for a question like this is can they find novel runtime optimizations. A work sample test is better. Grab some crap code from the codebase like a double forloop that should have been a map look up and have them make it more performant.
I was asked this exact question at my on-campus interview with one of the Big Five software companies for a Program Manager internshi between my 3rd and 4th years of college.
I had done no “leetcode grinding”-style prep.
Subtract from 5050? No, I didn’t think of that. But I did think of summing the numbers 1..100 with a for loop, sum the numbers in the input array, and subtract.
Not the perfect solution. But it’s O(n).
And I did get the internship.
My point being not that I’m some kind of algorithmic prodigy: I’m very much not. But if a college kid can solve it without any prep, nor rote memorization as GP suggests...
Unless they can swear up and down that what they actually do at this company, for at least a significant part of the day, is throw each other against the wall (er umm, whiteboard) and insist that they solve problems like these (and do so elegantly) within 10 minutes or less...
... or get fired ...
... then what I'll be looking for is simply -- the door.
Q. Given X-Y coordinates of two rectangles, determine if they intersect or not.
I'll try for an answer -- I looked up nothing, and it took longer to type in the answer than it took to think of it!
A. Given positive integers m and n and m points A(i) = (a_i1, a_i2), i = 1, 2, ..., m and B(j) = (b_j1, b_j2), j = 1, 2, ..., n, determine if the convex hull of the points A(i) intersects the convex hull of the points B(j). So, look for a line that has all the points A(i) on one side and all the points B(j) on the other side.
Suppose we have numbers u, v, w, and consider the set of all (x,y) such that
ux + vy = w
Then those points (x,y) form a line, and every line can be written in this form.
Then we seek u, v, w so that all the A(i) are on one side of the line and all the B(j) are on the other side. So, without loss of generality, we seek u, v, w so that for all i
ua_i1 + va_i2 >= w
and for all j
ub_i1 + vb_i2 <= w
Or, we seek u, v, w to solve the linear program
maximize z = u + v + w
subject to
ua_i1 + va_i2 >= w
ub_i1 + vb_i2 <= w
for all i, j.
The simplex algorithm will determine if this linear program is feasible, that is, if u, v, w exist to satisfy the m + n linear constraints, or not feasible. If the program is feasible, then the two convex hulls are separated by the line the set of all (x,y) such that
ux + vy = w
Else the linear program is not feasible, no line exists separating the convex hulls, and the two convex hulls overlap.
Yes, we could tweak this simple formulation to something a little more involved and, then, determine if the two convex hulls just touch but otherwise don't overlap.
This solution solves the problem about rectangles in the OP as a special case.
Let's see: Given a closed convex set C with points A(i), is the convex hull of the points A(i) also in C?
Well, the intersection of any collection of closed sets is closed (the union of any collection of open sets are open). The intersection of any collection convex sets is convex. Then, the intersection of any collection of closed, convex sets is closed and convex.
The convex hull of a set of points is the smallest closed convex set that contains all the points, that is, the intersection of all closed convex sets that contain all the points and, thus, is closed and convex. Here convex hull is well defined since the intersection is unique. A line in X-Y and one side of that line is closed and convex. So the convex hull of a set of points on the line and some one side of it is closed, convex, and a subset of the line and that side of it. Our algorithm needs this result.
Is that a sufficiently good answer?
Looking at the "solution" in the OP, there was a HUGE assumption NOT stated, implied, etc. in the statement of the question: The assumption was that the sides of the rectangles were parallel to the orthogonal X-Y axes. So, the question was badly stated.
For how the question was STATED, my solution may be about the easiest.
> The overlap of two rectangles is an easy question with an easy answer
You have an "easy" answer to how the question was stated? Until I hear or think of a much easier answer, I have to conclude that your statement of an "easy question" is false.
The OP certainly did NOT have a solution to the question as stated.
> If I was an interviewer I wouldn't like this response for most jobs, although it would be fine for a small subset of jobs.
The interview questions were to be for "most jobs". Then "most jobs" should prefer a correct answer, that is, correct for the question as stated.
Or, the question could be important for many jobs working with graphics, rectangles, triangles, etc., and there commonly we won't have specific orientations, say, rectangle sides parallel to the X-Y axes.
> social queues about what is expected
The interview questions are supposed to be challenging and to let the candidate show their capabilities. In that context, "what is expected" should not limit the power of an answer.
If the company wants only people who know not much more and not much less than the people already there, then the company, should not be looking for new people, is on the way downhill, also because of that should not be hiring, and no good candidate should want to work there.
The OP questions were to be about "data structures and algorithms". Well, I used the simplex algorithm, seriously ranked as one of the best pieces of engineering in the 20th century. A special case of that algorithm is min cost capacitated flows on networks, and there is a really cute algorithm there and a cute use of a spanning tree on a network. So, my answer was good for "algorithms and data structures".
Step 1 - Find all pairs of line segments where there is overlap on the x and y planes. This step is O(n^2) but since we're dealing with rectangles it's only 16 checks.
Step 2 - For the line segments that do have overlap check to see if the intersection occurs within the line segments or outside of it. If there is a line intersection within a pair of segments then there is an overlap of rectangles.
For the question as STATED (4 sides) this will run quickly and a first year CS student could implement it, or read it and understand what is happening. I could use a whiteboard and explain this algorithm to high school students.
When you hire for a company you do want programmers that will have a correct code solution. You also want programmers that will write code that is easy for others to maintain, you want programmers who are pleasant to work with, aren't difficult people, etc. In an interview, the technical questions are only part of the interview process. There is also the underlying question of "is this a person I want to work with?".
But since I studied a lot of optimization, I saw my linear programming answer first. On an interview, typically want to give the first correct answer do find.
My answer is more general, and that is goodness. Indeed, you mentioned that your answer solves a more general question than intended in the OP. So, you seem to like the generality of your answer but not the generality of mine.
The generality of my answer applies to convex polytopes, convex hulls, in any finite dimension, and dimension 3 should be of interest in some cases, e.g., see if two objects intersect. That might be of interest in some of robotics.
If the polytopes are determined by points, then my answer solves the problem and we are looking for a separating hyper plane. If each polytope is determined by the intersection of half spaces determined by hyperplanes, then we are looking for a point in common, and again we can use linear programming. So, given points we are looking for a separating hyper plane, and given hyper planes we are looking for a point. Smells like a nice case of duality.
Farkas lemma, a special case of my solution, is central to the Kuhn-Tucker conditions in nonlinear optimization. Since the ML people are interested in optimization, they might welcome Farkas lemma and my more general solution.
And, again, my answer really is part of "algorithms and data structures" which was the focus of the questions.
So, now we are into what is commonly called computational geometry, commonly regarded as part of computer science, and heavily about algorithms. E.g., doing nearest neighbor searches via k-D trees (in Sedgwick) and cutting planes is part of computer science, computational geometry, trees, data structures, and algorithms.
For the linear programming, just call a subroutine, e.g., IBM's old OSL (optimization subroutine library).
My more general answer indicates that I would be a good person to work with.
The question is a separation problem. Well, so as to have readers be more comfortable, I did omit mention of the Hahn-Banach theorem. For curious readers, there are lots of applications of that classic result in D. Luenberger, Optimization by Vector Space Methods.
"Hard to work with ...". How 'bout hard to please?