11 ms·
Data Structure and Algorithms Interview Questions for Programmers
- stevew20 8y agoEw Java...
- soulwatcher 8y agoI find these questions are a bit too simple and direct. Some of the interview questions I've seen are much more nuanced and often more indirect.
- kamaal 8y agoA more exhaustive list is here: https://www.geeksforgeeks.org/fundamentals-of-algorithms/ https://www.geeksforgeeks.org/fundamentals-of-algorithms/ https://www.geeksforgeeks.org/data-structures/ https://www.geeksforgeeks.org/data-structures/
- Waterluvian 8y agoI feel frustrated by the concept of software interview questions but only recently do I think I've figured out why. They feed my impostor syndrome. 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.
- kayoone 8y agoI know what you mean. Even if you think you are fairly competent, have a CS degree that is a few years back, reading these articles you only realise how many seemingly simple questions you probably could not answer correctly in an interview scenario. I try to let it motivate me, to try to stay on stop and play with these questions a bit, like going to the gym to stay fit and healthy, but imposter syndrome is real.
- r_c_a_d 8y agoYou have a perfectly valid point. After a PhD and 10 years of industry experience I interviewed at Google, mostly out of curiosity and because a former colleague recommended me. 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.
- wolfgke 8y agoJust out of curiosity: Are these kind of questions relevant/representative for the type of work that one does at Google?
- r_c_a_d 8y agoWell, my reasoning at the time (2007) was that since my areas of expertise were machine learning and parallel processing, then if they wanted to hire people who knew low-level sorting and searching algorithms by heart, it wasn't the place for me. 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.
- slimshady94 8y agoI feel like the interviewing grind has become akin to gymming - you go to your mental gym, build up your 'muscles' by doing pointless repetitive tasks AKA algorithms you'd never use in real life (probably like how bodybuilders would never need to deadlift 125kgs in their daily life). It doesn't directly help you do your job but you know bodybuilders have higher than average fitness levels. So in the same manner, devs grinding leetcode probably have higher 'fitness' levels than devs who don't.
- yalnix16 8y agoI grinded a significant portion of my time on leetcode. I would rather have worked on programming projects during this time.
- jammygit 8y agoI can spend my time learning a new skill or technology, or I can do quizzes on algorithms I will never use. Since I'd like to work for myself in 5-6 years, I resent the time I waste on quizzes. 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.
- MRD85 8y agoProfessional competitors in the majority of physically demanding sports supplement their training with gym work. Tennis, cycling, golf, etc all do. Targetting muscles in gyms have all sorts of benefits. If you are an amateur who competes for fun then you probably don't but if your paycheck is determined by performance than it's likely you're in the gym.
- LaserToy 8y agoI’ve never heard of a pro athlete being evaluated by their ability to bench press. Very good analogy that demonstrates how silly those interviews are.
- CzechTech 8y agoThese are always so funny to me. Primarily in the sense that the absolute VAST majority of programmers on earth will never use many of these in their job, given how extensively are high level languages used and how extensive web development is. And once in a blue moon, when you actually do need an efficient tree algorithm, you can get the gist in 10 minutes off Wikipedia. 90% of "but muh CS science" is just bullshit so people have shit to teach. If it wasn't for ML, I don't know what the academic world would be doing... probably reinventing UML (lol).
- WalterGR 8y agoI’ve started telling non-techie people that you don’t interview for software engineering jobs: you audition for them. They get it.
- LaserToy 8y agoI’m too old. I’m telling recruiters that I will not spend even 5 minutes preparing for the interview. I believe that interviews should be based on what you did, not on your ability to memorize a book of CS problems and solutions.if you a company with good BS department (like google, db,...) you can be arrogant and still have candidates, but if you not them, I highly recommend to rethink how you interview people.
- pbalau 8y agoI think you are mislead here. I was trained by Facebook for their interview loop and yes, these are the kind of questions interviewers might ask (with the caveat that the middle of the linked list problem would be formulated as "given a list of items, find the middle"). But they are not the only ones. 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.
- LaserToy 8y agoI worked at Google and I failed onsite interview at FB once. I guess I’m too bad as I have plenty of experience and didn’t get an offer. Could be I came across as an arrogant asshole, as I was itritated by questions I was asked and folks I met (was told that one group will do an interview, but was talking to engineers with 5 years in the industry and the only company they worked was FB) When I interview, I never ask questions from the book, no coding on the whiteboard. Those questions answer only 1 questions - how much free time you have to prepare for them.
- jfultz 8y agoThere are various answers which seem a bit sloppy to me. For example, "How do you find the middle element of a singly linked list in one pass?" The answer, without comment, makes a presumption about how to define the "middle" of a list with even length. And it defines a linked list implementation with a magic, invisible head that requires extra code beyond the loop to compensate for. In the "How do you check if two rectangles overlap with each other?" answer, the code will determine that the rectangles which merely coincide at edges or corners are overlapping, without noting that distinction. The vending machine example tries to drive home the point of requirements definition, but the point applies equally to these much simpler examples. I only gleaned maybe 10 examples...maybe I just got "lucky". 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.
- thaumasiotes 8y ago> For example, "How do you find the middle element of a singly linked list in one pass?" The answer, without comment, makes a presumption about how to define the "middle" of a list with even length. And it defines a linked list implementation with a magic, invisible head that requires extra code beyond the loop to compensate for. 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.
- jfultz 8y agoI mean that the LinkedList class is defined so that "new LinkedList()" returns not a list of length zero, but a list of length 1 with the first element containing the string "head". The actual list it creates is {"head", "1", "2", "3", "4"}, despite the fact that the output claims the list has 4 elements.
- dvt 8y agoI officially refuse to do these in interviews (along with whiteboard coding) anymore and I'm very upfront about it with hiring managers and recruiters. My reasoning is twofold: (a) I'm generally not great at these kinds of questions so I think it's an unfair disadvantage and (b) I think that my experience, open source contributions, Apress book that my name is on, blog that I often post to, etc. speaks for itself. However, I will gladly do your take-home assignment. I'd be even more thrilled if we can discuss it during my interview. 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.
- tomcam 8y agoAre you able to get good jobs that way? Not criticizing, just genuinely curious.
- iKevinShah 8y agoAnd the hiring managers buy that reasoning? 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.
- dvt 8y agoSome do, some don't. Some women don't want to date me, either, but I don't stay up worrying about it :P
- EZ-E 8y agoWhy do interviews for dev jobs increasingly becomes a game beaten by "grinding" leetcode or other websites listing questions? 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."
- denormalfloat 8y agoIt's because lying on a Resume is extremely easy. I do interviews for a large software company about once a week. The relationship between what a candidate says they did and actually doing simple programming problems is non-existent. > 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.
- newsbinator 8y agoAsk them non-trivial questions about the problems they solved and how they solved them.
- kamalkishor1991 8y agoThey are likely to know more about the project they were part of then you do. Even if they are really bad.
- newsbinator 8y agoThat's okay. The important thing is their knowledge of common problem patterns and solution patterns. 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.
- iKevinShah 8y agoI wish I had seen this yesterday. I had an opportunity (interview) and a had a lot of "Oh I know this" but when asked to explain further I was like "Oh...?"
- denormalfloat 8y agoData structures and Algorithms are fun, but more and more I see that general software engineering is something we need. Several useful questions venture too deeply into domain specific things, making them difficult to give to candidates. For example: * 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.
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- est 8y agoMy recent favorite question is how to design a proper login page, store the password and authenticate them. You'd be surprised how many things can go wrong.
- topkai22 8y agoI've been trying to weed out a lot of these problems from my team's interviewing set- they filter for CS students, not practical development knowledge. I can honestly say I've never used a linked list in 15 years of being paid to develop software. I've been pushing interviewers to come up with a problem based on code they've actually written in the past and use that for their interview question. 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.
- topkai22 8y agoI will add on- no, I didn't find out how its possible to professionally program for 5 years and not use arrays. But the poor guys response showed he hadn't.
- jon_richards 8y ago>I didn't find out how its possible to professionally program for 5 years and not use arrays Python maybe?
- Aozora7 8y agoProbably depends on what you mean by "arrays". If you use high-level languages like Java, you probably don't use arrays often, if at all, in almost all cases you use collections that provide you with convenient abstractions for everything, even if they are still arrays underneath.
- W-_-D 8y agoI was really impressed with one of the interview rounds I was given at Microsoft - I was shown a mock code review and asked to comment on bugs (ranging from easy to spot like null reference exceptions, to harder like race conditions and edge cases) and code quality. 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.
- gpderetta 8y agoThe "one pass" solution to find the middle of a linked list visits each element twice (or more precisely, it visits half of the elements twice). It is hardly one pass.
- zamalek 8y agoThis often trips up people who don't know how big O works (loops are not directly correlated to N), or why it works that way (in general a constant before N is negligible, the curve is more interesting). 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.
- tralarpa 8y ago> This often trips up people who don't know how big O works 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).
- zamalek 8y agoAs the root comment points out, both solutions (the second being two loops) are 1.5 passes.
- thaumasiotes 8y agoProposal: 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.
- 8y ago
- graycat 8y agoApparently one of the questions was: 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?
- MRD85 8y ago
- tralarpa 8y agoTo teach programming, many universities structure their courses "bottom-up": 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.
- ricardoreis 8y agoHere are some of the popular array-based coding interview questions for your practice: 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
- Double_a_92 8y agoWould you be looking for the solution where you subtract every number in the array from 5050? If anyone says that they 99% studied it. A more "natural" sulution would be to sort the list first, and then look for consecutive array items where the difference is not 1.
- sethammons 8y agoI just woke up (still in bed). I've not seen this question before. For about 2 seconds I thought of iterating through and creating a map and... Wait a second, if one number is missing, I can just find the sum and subtract! Admittedly, I would have had much more trouble in a high pressure situation. 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.