9 ms·
Computer Science Interview Questions with C++ Solutions
- Jare 13y agoThis is a mess: lack of comments, inconsistent coding style, and outright wrong answers. If I got this from a candidate I would reject it outright as a bad example of uninformed copy & paste. [Edit]: not trying to sound mean, that's just my raw and unfiltered reaction.
- jzwinck 13y agoEach question seems to come with just an uncommented code dump. Not any discussion of the actual algorithms, why it works, what the trade-offs are, etc. If I happened to ask all these questions in an interview and got all these answers, I would reject the candidate.
- fruneau 13y agoMoreover, I think that some answers are not doing what we should expect from the subject. For example the "Detect Multiple Of Two" detects powers of two, not multiples.
- deleted 13y ago[deleted]
- yajoe 13y agoAgree on needing comments. My C++ is a bit rusty, but I think the code is in fact checking if the number is divisible by 2 (i.e. n % 2 == 0). I think it's using the bitwise and operator (single &) to AND each bit in n and (n-1) and then checking if the least significant bit is 1 or 0. The code would need to shift (<< or >>) to check if the number were a power of 2. I thought there was another bitwise NOT operator, not the !, but I think, and this is the part I'm hazy on after getting home, that the ! applied to an int is intended to flip each bit. Here's why: ------------ n = 6 = 110 n-1 = 5 = 101 n & (n-1) = 110 & 101 = 100 !(110) = 001 => true ------------ n = 5 = 101 n-1 = 100 n & (n-1) = 101 & 100 = 101 !(101) = 010 => false only if the least significant bit is used for logic decisions... this seems non-portable for some reason, just like using the ! as a bitwise NOT. It may actually be that ! only looks at the least significant bit, but I can't find c++ docs to say one way or another. Whatever the code actually does, this is exactly the kind of example to use as a poster child for adding just a few comments.
- ColinWright 13y agoThe GP is correct, this is bit-twiddling code to test for a single bit being set in the int, and therefore being a power of 2, not simply a multiple of 2. Broadly speaking, and ignoring edge cases, if N is a power of 2 then it has a single bit set. Subtracting one unsets that bit, so the AND of N and (N-1) is zero. On the other hand, if N is not a power of two then subtracting 1 leaves the top bit still set, so the AND is non-zero. Therefore taking the boolean NOT gives the right answer. 00010000 Power of 2 00001111 N-1 -------- 00000000 -> 0 00010110 Non power of 2 00010101 N-1 -------- 00010100 -> Non 0 Thus power of 2 is NOT( N & (N-1) ). Your examples are wrong because "!" is not bit-wise NOT, but boolean NOT. !0 = True, !N = False when N is non-zero. It's actually wrong on the edge case of N=1, which is a power of 2.
- yajoe 13y agoThanks, you're right. I don't know why I would have ever thought "!" was bitwise... only on a Saturday night. It just goes to show that sleep is very important for interviews!
- mden 13y agoI have the opposite opinion. Writing comments for (in-person) interviews is silly and a sign of wasting time. Interviews in general are not designed to check your coding style, but your ability to solve problems, whether they be reasonable or not. Your comment is a little bit along the lines of, "if you the candidate didn't use a versioning system, I wouldn't hire him". It's just not what is being tested. Now, if it was a "here are some problems, solve them and get back to us" type of interview, then sure, I would agree with you.
- lmartel 13y agoAs a side note: never interview in C++. For these types of problems java is just so much easier to work with, and it's easy to learn enough java to interview with in a weekend from a C++ base. In my experience, interviewers always prefer a good easy solution (java) to a so-so difficult one (C++). Ruby and python are worth a try too, but often they make things so easy that the interviewer disregards the answer--many common string manipulation interview questions are one-liners in ruby.
- catnaroek 13y agoJava is your blub? Why not go for Haskell or ML?
- adamnemecek 13y agoBecause neither is a language commonly used in interviews.
- yohanatan 13y agoMaybe they're not commonly used in interviews because too few people refuse to take the sort of interviews where they wouldn't be allowed?
- grogenaut 13y agohaving trouble following your nested negative set logic sentence structure here.
- adamnemecek 13y agoYeah, it reads a lot like that "Has Anyone Really Been Far Even as Decided to Use Even Go Want to do Look More Like?" thing.
- pjscott 13y agoRestructured: "Maybe they're not commonly used in interviews because too few people insist on being able to use them in interviews?"
- th3iedkid 13y agoi don't know why but statistically the number of times i've written code to BFS on a binary-tree given the day-hour experience i've had, is zero.So why don't interview patterns change too. If we expect the person to design,code,execute with you , why don't we check those aspects instead of pure-academic questions on integrity of a tree-search for high-performance solutions delivered in a 10-minute conversation. Also may be am wrong & am the one with a green toe and rest of work-places do want only academicians with linked-list experience.
- 10098 13y agoSince when is tree traversal "pure academic"? It's like one of the most mundane things, it's like sorting or hashing, it's something you run into on a regular basis, and the fact that it's wrapped into a library doesn't give you an excuse to not know it, because that knowledge is necessary to use the library correctly (i.e. answering questions like "do I use TreeSet or HashSet here?"). It irritates me because it's not even remotely "academic". Category theory is academic, this is mundane things. It probably is the bare minimum one has to know if they hope to work on anything interesting.
- th3iedkid 13y agoits the same point that am trying to make.my use of pure-academic was in the pun-sense of it. Interviews shouldn't be checking bare minimum, when we spend a 10minute time talking to each other , i would rather prefer to spend it on something rather less mundane.To check for bare-minimum we could screen via their previous assignments.But again it depends on what level we are looking for.like the above comment , if we are looking for fresh grads it better be focused on basics.
- Negitivefrags 13y agoIt's very difficult to find questions of the correct difficulty for an interview that don't require arbitrary knowledge that the candidate might not have. The binary tree question has a short definition, requires only knowledge that any candidate will have, and is easy for any logical thinker. If I am administering a practical test for a junior programmer position, as in, a fresh graduate, the binary tree test is a great one. I put them in front of an IDE, sit with them, and ask them to write a unbalanced binary tree container with insert, find and delete functions. Watching a candidate do this tests basic implementation skill, API design, debugging and testing methodology. By the end of it, I have a pretty good idea if they will make a good hire.
- NAFV_P 13y ago>Implement a simple linked list in C (not C++). It can be compiled on a C++ compiler, but do not use any feature of C++. Er, which standard of C?
- kps 13y agoYou get the job if you can think of a non-trivial way in which in matters.
- Danieru 13y agoThat's pretty easy. Pre-C89 did not have void pointers, thus a generic linked list would have to use char pointers. Beyond the wrong-ness of using an incorrect dereferencer type you would also force any users of your linked list to make an explicit cast. Meanwhile a post-C89 linked list could return void *. Thus taking advantage of C's implicit cast of void pointers. Meanwhile if you compiled this second void pointer returning linked list under a C++ compiler would have to make an explicit cast just like in the pre-C89 case.
- kps 13y agoK&R (V7) cc happily handles implicit casts of char* ; void* is just char* with a new name and a pair of handcuffs. If you're writing a linked list, though, you'd be using a 'struct listnode *next' in any dialect.
- NAFV_P 13y agoSorry I should have explained myself better: I am referring to the C-standards, and I don't consider K&R to be one of them. I tried compiling the source with: gcc file -std=c89 -Wall -o out && gcc file -std=c99 -Wall -o out I get a score of errors thrown at me. Not one of them mentioned a void* or char, they don't appear in the code. The float which holds the data is located within the struct itself. The first nine errors were all practically identical: error: unknown type name 'LL_Element' I don't know much c99, but when it comes to c89 whenever an instance of a struct some_type* is declared the keyword struct also has to precede the type: ie. struct some_type some_instance;. The only way I am aware of that overcomes this is the use of typedef in the original declaration. I'll have to check whether it is mentioned in the 1988 edition of The C programming language or another text, but if I recall correctly the term tag is used to refer to struct declarations. Also the original code had the headers <cstdlib> && <cstdio>. I think these headers have all their functions declared as inline, a non-existent keyword with regards to c89. I had to change the headers to the traditional .h style header in order to have a chance of getting the code to fit through the slot, so to speak. I don't have a CS degree, I teach myself, so if I have missed something or made a faux pas, please say so.
- thomasfedb 13y agoI really wonder if this sort of rote learning has anything to do with being a decent programmer, and if sensible companies that I want to work for are really asking these sorts of questions. Personally, I could probably tell you the uses for heaps, trees, tries, and hashes before I wanted to check something in a book or look something up on the net. I would think that I am better placed to write sensible code because I have an understanding of complexity and I'm prepared to go and think about the problem, find or invent an algorithm, and then prove the complexity of that algorithm. Rather than rote learning 12 different types of trees.
- ColinWright 13y agoThere is little use in being able to integrate functions, or to solve trigonometric equations, or to rearrange equations. However, being able to do these sorts of things without thinking too hard then releases the mind to think about other things with freedom. Similarly, effortless recall of the pros and cons of different algorithms and data-structures means that you don't have to think twice about many of the things that should be purely mechanical. It then lets you recognize things when they show up in disguise, and to concentrate on the higher level work, where the real work begins.
- analog31 13y agoI treated college math and physics as symbolic manipulation games, and graduated cum laude with majors in both subjects. I can still fly through those exercises today, a quarter century later. My only misgiving is that the emphasis on closed form solutions, at the time, was exclusive. It distorts the choice of problems that students are given. Not being a CSist, I don't know if a similar distortion exists in CS.
- ColinWright 13y ago> I treated college math and physics as symbolic manipulation > games, and graduated cum laude with majors in both subjects. Interesting. I'm not saying this about you, but I've met several people who treated math as largely just symbol manipulation, and indeed, they ended up being great at solving the sorts of problems set, but I've sometimes had a feeling that they're sort of "barking at print". I've heard people reading perfectly well, but with no sense they they understand what they've read, despite the perfect production. Similarly, some people can "do the math," but sometimes there's no sense of any real understanding. It's hard to explain. This is one of the problems with interviewing. Some people can really talk the talk. They know all the words, all the phrases, can solve the problems, can produce the code for the set problems. And yet, after conversation, you start to feel that there's something just not quite right. This is just one reason why interviewing is hard.
- KiwiCoder 13y agoThere's no harm in brushing up on CS 101 questions, but I wish more candidates spent time preparing for questions about code quality.
- droptableusers 13y agoI am just a student but do interview questions come without any concrete problem to solve? Or are they really like "Which data structure would you use for repetitive look-ups?", "Implement FizzBuzz" and so on instead of something like "You need to look up a words in a English dictionary for a spelling program, how would you solve it?".
- ColinWright 13y agoIt depends. In many cases it's impossible to give sufficient context to provide a real-world problem that will let the candidate show their understanding of algorithms and data structures. Sometimes it's necessary to ask these sorts of questions in isolation, without a concrete problem. Not least, sometimes a real world problem is better solved in a different way anyway, which subverts the intent. Understand, most real world programming jobs don't need in-depth knowledge of algorithms and data structures. Most real world programming jobs are implementing the algorithms devised by someone else, using data structures that are "obviously" the right structure for the job. When companies are asking these sorts of questions they usually have a somewhat inflated view of their own importance. Either that, or those interviewing have no real idea about the work done by their programmers. The very best interviewers, when using these questions, don't worry too much about the detail of the solution, but in the discussion of the pros, cons, benefits, drawbacks, and possible development of the code in context. Even with FizzBuzz there is much to be explored once a coder has written it.
- droptableusers 13y agoI see, thanks for your perspective on the matter.
- deleted 13y ago[deleted]
- discardorama 13y agoHaving been in the industry for a while, I've come to realize that the sad reality is that (IMHO) the vast majority of the companies would be quite happy if the candidate was able to regurgitate such answers in an interview. I know (acquaintances) who keep working on interview questions and, basically, keep interviewing. Hopping from job to job, they have done very well financially.
- sergiotapia 13y agoI have a question, I consider myself a great software developer with a proven track record. I have open source code, lots of completed and shipped websites and software. Do interviewers really care about this sort of interview knowledge outside of the San Fransisco start up bubble? I've been programming and making a great living for more than 8 years now, and not once did I have to implement a b-list tree or something CS-y like that.
- ColinWright 13y agoAs I said here in https://news.ycombinator.com/item?id=6950242 https://news.ycombinator.com/item?id=6950242 : Similarly, effortless recall of the pros and cons of different algorithms and data-structures means that you don't have to think twice about many of the things that should be purely mechanical. It then lets you recognize things when they show up in disguise, and to concentrate on the higher level work, where the real work begins. And here in https://news.ycombinator.com/item?id=6950235 https://news.ycombinator.com/item?id=6950235 : ... most real world programming jobs don't need in-depth knowledge of algorithms and data structures. Most real world programming jobs are implementing the algorithms devised by someone else, using data structures that are "obviously" the right structure for the job. When companies are asking these sorts of questions they usually have a somewhat inflated view of their own importance. Either that, or those interviewing have no real idea about the work done by their programmers. The very best interviewers, when using these questions, don't worry too much about the detail of the solution, but in the discussion of the pros, cons, benefits, drawbacks, and possible development of the code in context. Even with FizzBuzz there is much to be explored once a coder has written it. When I'm hiring I care to know the strengths and weaknesses of the candidates, and that includes whether you know about algorithms, or not. Not knowing about them is a gap in your knowledge, but you have evidence of other skills. If you can actually get things done, that's a skill many don't share. Most people have gaps in their skills and abilities. That's not a problem. But to answer your question directly, yes, some interviewers really care about this sort of interview knowledge outside of the San Francisco start up bubble.
- thomasfedb 13y ago
- robomartin 13y agoI really don't find these questions to be useful indicators of the things that make-up a good software engineer. I am using "software engineer" here on purpose and as something distinct from "programmer" or "coder". One will design and develop good reliable products that are maintainable and extensible. The other will just crank out code and is likely to not really add value beyond that. I want to know how a person thinks and reasons, how good he or she is about data representation or the formulation and communication of a strategy in creating a solution. I want to know how a person thinks at the abstract, code, project and product levels. I don't really care to learn that he or she can memorize 150 CS interview tests. In fact, if someone aced the CS tests I'd pretty much assumed they memorized a whole pile of them for the interview. That, to me, is useless as it isn't an indicator of the kind of professional you might be hiring. If what you are after is a coder, an assembly-line worker, then puzzles might work. If, on the other hand, you are looking for a true software engineer, you need a different approach.
- analog31 13y agoI'm surprised, in an industry that is founded upon automating repetitive tasks, that the coding interview can't be automated. Isn't that what standardized testing is all about?
- ColinWright 13y agoThis comment nails it: > I really don't find these questions to be useful indicators > of the things that make-up a good software engineer. I am > using "software engineer" here on purpose and as something > distinct from "programmer" or "coder". > One will design and develop good reliable products that are > maintainable and extensible. The other will just crank out > code and is likely to not really add value beyond that. > I want to know how a person thinks and reasons, how good he > or she is about data representation or the formulation and > communication of a strategy in creating a solution. I want > to know how a person thinks at the abstract, code, project > and product levels. https://news.ycombinator.com/item?id=6942548 https://news.ycombinator.com/item?id=6942548 Standardized testing will quickly get subverted, with people "studying for the test." It's almost a theorem that any proxy for assessment will become subverted, with people passing the test without actually possessing the necessary underlying skill. In math people keep complaining about "teaching to the test" and that people pass the tests, and yet don't have the skills. Same will happen if you try to standardize computer recruitment.
- analog31 13y agoVery good point, and I realize that I was being a bit sarcastic about standardized testing. In fact it's possible that if a particular set of coding questions gains widespread use, then it will function as a de facto standardized test, with the result that you predict. This could already be the case if both employers and applicants are searching online for lists of the best interview questions.
- vonmoltke 13y agoStandardized testing will quickly get subverted, with people "studying for the test." It's almost a theorem that any proxy for assessment will become subverted, with people passing the test without actually possessing the necessary underlying skill. In math people keep complaining about "teaching to the test" and that people pass the tests, and yet don't have the skills. Same will happen if you try to standardize computer recruitment. Hasn't the industry effectively done that already? Doesn't the fact that almost anyone of reasonable ability[1] can pass an interview after studying something like Cracking the Code Interview indicate that you can successfully "study for the test"? [1] I am assuming that, even when "teaching to the test", a certain amount of baseline ability is still required to actually pass.
- platform 13y ago20 year veteran here (although experience does not really equal the 'years in business', it is a multiple of years in business and ability to 'accumulate' and 'apply' the experience). Interview is a negatives filter, not a 'successful employee' indicator. As a filter, it should be adjusted depending on the job markets, salary/benefit brackets and the type of effort a company/team is willing to put into a hire. A retained hire is a hire who passed the negative filter and then passed the 'successful hire' assessment, which should be done in a 3 month period. A company that is not willing to let a bad hire go after 3 month assessment, will eventually accumulate a horrible baggage, that will bring their productivity and morale. No interview (negative filter) can be good enough to avoid the 3 month assessment. If you do not accept this thinking, and still assume that you can construct an interview that will be good enough to avoid the 3 month assessment -- then you are a likely looking to hire candidates that mimic you, and in general (regardless how average/special you are) -- you will hard time finding the candidates, and actually scaling up your hiring effort. Back the actual interview. Programmers need to know which algorithms are sensitive to data sets and in which way (memory consumption, disk consumption, run time cost) Programmers need to be able to find good implementations for the specified constrained. this is important -- they need to be able to find the existing solutions, not build them themselves (unless you are hiring researches to work out things that have not been done before). So a good test would be to present a problem, and ask a candidate to do a quick internent research, and find analogies/approaches for a given problem. Asses which one of the found on the net solutions fit better to the problem space. And then describe how they would incorporate what they have found into an implementation, and how much effort they think it should take. Programmers need to be able to reason about maintainability and testability of the code base, using both previous experience, and analogies from open source projects. Having references to popular books on this topic is helpful is well. This is largely non-formal topic based on empirical evidence or personal experiences. So they do not need to match interviewer's expectations, but must be well argued. Programmers need to be able to articulate how they react to business decisions that require weighting various trade offs. Finally, important to see how they relate to the team members that they worked with, from the company they are coming from. The interview questions posted by the OP address not more than 10% of the criteria I outlined above, so in my view these are poor examples of the CS interview questions.
- kenster07 13y agoHow much does one need to understand how a car's engine works to drive a car? I believe there is some relevance to a deep understanding of algorithms, that relevance being a function of the job. But in situations where the relevance is CLEARLY low for the job, they serve as nothing more than projections of the egos of CS grads, and reduce the value of their company.