Computer Science Interview Questions with C++ Solutions
grokit.ca
grokit.ca
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.
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.
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.
> I treated college math and physics as symbolic manipulation
> games, and graduated cum laude with majors in both subjects.
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.
I've realized for a long time that what's gotten me through school and life is a series of accommodations for the brain that I happen to possess.
Oddly enough, things "clicked" for me in terms of developing the deep understanding underlying the symbols, but not always concurrently with whatever course I was taking.
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.
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.
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.
... 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.
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.
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)
* 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)
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.
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).
I ask people to code something trivial, on a whiteboard, in any pseudo-code they care to invent on the spot. Then we talk about the strengths and weaknesses of the code they wrote. We end up talking about algorithms, data structures, project management, quick hacks, technical debt, comments, function and method size, functional programming, and more.
The idea is to find their strengths, to make sure their weaknesses are covered by people we already have, and to see if we could work together. Sometimes we don't even agree, and it's the way they discuss the points that matters.
I'd love to see it made into a science, but I'm nowhere near clever enough to do that.
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.
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
It's actually wrong on the edge case of N=1, which is a power of 2.
It just goes to show that sleep is very important for interviews!
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.
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.
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.
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.
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.
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.
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.
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.
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.
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!
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.
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.
Regardless of which language you use, whether it's pseudo or not, you still have to solve problem...
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.
Knowing how to write code in functional languages has helped me write Java, too.
> 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.
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.
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.
Something like "cracking the code interview" could become an upper bound.
Er, which standard of C?
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.
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
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'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.
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.
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.
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.