Computer Science Interview Questions with C++ Solutions

http://www.grokit.ca/spc/computer_science_review/

by nothing1212 • 13 years ago

82 67 13 years ago

jzwinck• 13 years ago

Each 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• 13 years ago

Moreover, 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.

yajoe2• 13 years ago

Agree 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.

mden• 13 years ago

I 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• 13 years ago

As 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.

catnaroek3• 13 years ago

Java is your blub? Why not go for Haskell or ML?

adamnemecek2• 13 years ago

Because neither is a language commonly used in interviews.

CoryG892• 13 years ago

Because in all likelihood, the jobs most of us will be interviewing for will never require us to touch Haskell or ML. I haven't worked with it, but I've worked with Lisp/Scheme/PROLOG and others. I'm always down for learning something new, but I doubt many people here get paid to write Haskell on a regular basis. Or maybe I'm wrong?

catnaroek3• 13 years ago

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.

The problem is not that they are one-liners, the problem is that the algorithm is already implemented for you as a library function, and you just call it.

OTOH, in Haskell a one-liner could perfectly contain the whole description of an algorithm.

cronin101• 13 years ago

I don't think that this is a deal-breaker though. In my opinion the best response you could give in this situation is: "I would use <Library function> [showing you know libraries], however if this was not available I would implement it operating on characters as follows... [showing you understand algorithms]".

A good interviewer isn't going to huff because you have "foiled his master plan to trick you", since they are exploring the limits of your understanding.

yeukhon• 13 years ago

Google's interviews always claim "assuming you have these functions there, now just do the rest." I think in all fairness, C++ isn't making interview harder, it is the type of problem that people need to solve that makes the interview harder. Well, I think that's "no duh..."

Regardless of which language you use, whether it's pseudo or not, you still have to solve problem...

grogenaut3• 13 years ago

I would suggest that you pick the language that you and the interviewer are both the most comfortable that doesn't make you look like an idiot because you barely know it. So for instance if you know java/c++/javascript and the interviewer is a Java coder, go with java. Don't pick some language you are messing around with on the weekend.

It may be a bit counter-intuitive but the person doing the interview can have about as much mental overhead as you while solving the problem. They are likely writing down the answer you are giving and their thoughts on how you are doing. They also have to see where they think you are going to make a mistake and decide if/how to guide you to keep you on track. They also have to handle different styles of answering the question and have to know very quickly if it will work. So using a language they are comfortable with makes it easier on them and since in then end the job comes down to how they "feel" about your performance, making them feel better during the interview is going to help.

That said I did do an interview for a gaming company in ruby because I didn't want to embarrass myself in c++ (which I barely knew at the time). They said after I took the job that it was hard to evaluate me because I was coding in ruby on the board and they were unfamilliar with it. Also I got several "You can do that in ruby?" questions. And one shake of the head when I defined a ease of use method on Hash on the fly to make the solution read nicer.

com2kid2• 13 years ago

I always tell candidates "I am multi-lingual, feel free to answer in any language you want, with bonus points for Lisp or Scheme."

So far no one has taken me up on the latter option. :(

Everyone ends up coding in straight C, rather annoying really. I'd kill for someone to pull out Python or some other language more suited to the problem.

All that said, straight Java is also likely a horrible choice. Boilerplate code sucks. If the interviewer allows it (and some are super strict about these things...) ask if it is OK to mix and match syntax. If someone wants to pull in C# lambda syntax along with making up their own multi-valued return syntax, fine.

Some problems are about demonstrating language mastery (especially for some positions!), other problems are about determining candidate problem solving abilities. For general problem solving ability questions, I'd prefer the candidate demonstrate the ability to think outside the bounds of any one language!

kaoD• 13 years ago

So far no one has taken me up on the latter option. :(

That's weird. I always thought Clojure would be great for these kind of questions if allowed. I guess Clojurians are scarce.

Oh, and it's real fun too! http://www.4clojure.org has lots of riddles to solve.

100982• 13 years ago

Eh, I don't know. Always interviewed with C++ with great results. Probably because I know the language and the standard library well enough to be able to write out the solution without looking into google or a textbook. ALWAYS use the language you're most comfortable with. If it's Java, let it be Java. If it's Python, let it be Python. Also, NEVER try to show off by programming your solution in some language you read about on the internet the day before because it's just asking for trouble.

rbonvall• 13 years ago

I was interviewed twice this year. In both interviews I answered a question by saying "first, let me cheat a bit" and providing a Python one-liner. Then, I'd proceed to develop a longer version in C. Both times my interviewers were impressed.

I think knowing how to solve a problem in Python (or any high-level language) demonstrated pragmatism and knowledge of the language and its stdlib.

th3iedkid2• 13 years ago

i 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.

100982• 13 years ago

Since 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.

th3iedkid2• 13 years ago

its 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• 13 years ago

It'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.

Jare• 13 years ago

This 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.

NAFV_P2• 13 years 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?

kps2• 13 years ago

You get the job if you can think of a non-trivial way in which in matters.

Danieru• 13 years ago

That'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.

thomasfedb3• 13 years ago

I 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.

ColinWright8• 13 years ago

There 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.

analog315• 13 years ago

I 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.

CoryG892• 13 years ago

I agree with Colin. I think knowing these types of things is great and studying them before an interview shows effort. I'm not sure I would ask someone to implement a B+ tree or BST or something on the spot, but knowing what one is, having worked with one before, knowing what they are useful and commonly used for is something I would definitely someone working for me to know.

thomasfedb3• 13 years ago

I suppose I approach this from a background of Computer Science, rather than a background of Software Engineering. As such I'm interested in computation rather than "Mr Jones needs to manage his cats, etc".

If you described to me some scenario I could probably tell you I wanted a data-structure that offered constant time lookups, or that your graph was sparse and therefore I would prefer an algorithm that ran in O(E) over one that ran in O(V).

I certainly couldn't tell you the right class out of the Java Collections library.

In any case, it's holiday work.

KiwiCoder• 13 years ago

There's no harm in brushing up on CS 101 questions, but I wish more candidates spent time preparing for questions about code quality.

droptableusers2• 13 years ago

I 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?".

ColinWright8• 13 years ago

It 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.

droptableusers2• 13 years ago

I see, thanks for your perspective on the matter.

discardorama• 13 years ago

Having 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• 13 years ago

I 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.

ColinWright8• 13 years ago

As I said here in 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 :

    ... 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.

thomasfedb3• 13 years ago

Good point regarding getting things done. I would add to that list that the things should work.

tjbiddle• 13 years ago

Personally, I'd walk out of an interview if they started asking me these types of questions.

Unless of course, if it's a job where it'd be very algorithm-heavy to begin with, but that isn't where my interest lies.

ColinWright8• 13 years ago

That's your right (of course) and I have no argument with it. But let me offer another point of view.

To my mind, the point isn't whether or not the job is algorithm-heavy. If you don't have this stuff under your belt, there are limits to what you can do. If you have to concentrate on working out which algorithm to use, or which data structure to use, if you have to spend time researching these things, that doesn't make you a poor programmer, but it stops you from spending time on the real problem solving aspects of the job.

The programmers I hire don't often have to do major algorithm stuff, and some of them are not comfortable with algorithms and data structures, but that's OK. They have other strengths.

But even if the job doesn't require deep knowledge of algorithms and data structures, knowing them helps more often than you think. One needs to know these things to recognize them when they turn up unexpectedly and in disguise. Well, in my experience anyway. Your mileage may|will vary.

But when I hire, I interview for, and care most about people's abilities to get things done, to work constructively with others, and to extend their knowledge, skills, and abilities. To walk away when someone asks about something you don't (yet) know, says that we wouldn't be a good fit anyway, and not because you don't know about algorithms.

Edited to remove some unintentional snark.

Additional edit: I don't know why you've been down-voted. Many people feel the way you do, and while I don't agree, you're entitled to your opinion, and I'm pleased you voiced it. I've up-voted you to try to offset the down-vote(s).

rnd33• 13 years ago

I don't understand this attitude. There must be lots of great companies to work at where the interview process is a bit flawed and the questions a bit unrealistic. Why let that stop you? Why handicap yourself when you can just learn it?

umanwizard• 13 years ago

I work for a well-known large tech company in the Puget Sound area. My phone and in-person interviewers asked me a balanced mix of the following:

* General questions to probe how well I knew the technologies on my resume. (What does "virtual" mean in C++? What is the difference between inner and outer joins in SQL?). Generally if I got something right they would keep probing until they got to something so esoteric i couldn't answer.

* Basic operations on fundamental data structures. (What is one way std::map could plausibly be implemented? Implement depth-first search on a tree. Implement insertion and deleting of elements in a heap.) I got stuck on deleting elements from a heap but they gave hints.

* Very simple OO design questions (would it make sense to have Employee inherit from Boss?)

* Traditional tricky algorithmics stuff (stuff where the correct answer depended on figuring out the right sorting algorithm to use, or whatever). But not TOO tricky.

* Coding problems that involved implementing some moderately complicated logic that involves thinking through a lot of edge cases (Implement the basic functionality of the wc command, write a function to convert from a string with a roman numeral to a native integer)

Piromancer• 13 years ago

I'm outside the SF startup bubble, and I interview a lot of mostly recent college grads. I like to ask theoretical questions, especially of college grads. It's not because I expect that they'll need hard CS skills, but it's because I want to know the following things:

Can they effectively break down a hard problem into sub-problems? Can they compare the difficulty of sub-problems and prioritize? Can they, while working on one sub-problem, think about the effects that their solution will have on the other parts of the problem? Can they keep track of the big picture of what they're trying to solve while working on a small part of it? Can they translate their ideas into code fluently? Can they adapt to change and fix their system cleanly? Are they interested in computing? Have they spent their own time on learning?

These are not theoretical results - these are the qualities that make or break an entry-level engineer. I ask formal CS questions because formal CS is a context that the candidates should be comfortable in, and thus I can ask a hard question quickly. However, I'm far more interested in the meta-questions than if they can get through the solution to Problem X.

I try to avoid measuring a candidate with a single question: if I'm doing a phone interview, I'll try to hit many areas (I'm sure you're familiar with Steve Yegge's post on phone screens), so the formal CS part is rarely more than 20 minutes. On the other hand, for an on-site interview, we tend to each focus on specific areas, so I can happily spend an entire hour on one or two hard theoretical questions (if I get to cover the algorithms/data structures section).

So - your mileage may vary, and given that you have a significant track record, I don't think that hard theoretical questions would be the best way to measure your ability. But for some categories of candidate (mostly recent college grads), I think that formal CS questions are a good meterstick.

(Edited for formatting)

robomartin• 13 years ago

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.

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.

analog315• 13 years ago

I'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?

ColinWright8• 13 years ago

This 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

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.

analog315• 13 years ago

Very 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• 13 years ago

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• 13 years ago

20 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• 13 years ago

How 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.

Computer Science Interview Questions with C++ Solutions

Related Stories