Computer Science Interview Questions with C++ Solutions(grokit.ca)
grokit.ca
Computer Science Interview Questions with C++ Solutions
http://www.grokit.ca/spc/computer_science_review/
72 comments
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.
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.
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.
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.
Well, I certainly can't plead innocent. ;-)
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.
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.
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.
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.
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.
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.
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.
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.
As I said here in https://news.ycombinator.com/item?id=6950242 :
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.
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.
Good point regarding getting things done. I would add to that list that the things should work.
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)
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)
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)
* 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)
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.
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.
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).
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).
So what do you think is an effective way to interview for a person's ability to get things done?
I don't know, but if you hunt through my comments on HN you'll see what I do. Mostly it seems to have been successful - the guys on my teams are pretty good. Mostly I've only gone wrong when I've put too much faith in paper qualifications.
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.
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.
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?
because apparently parts of america are an insane sellers market where you can command 100k+ fresh out of school. If you don't want to deal with these questions there's ten more jobs down the street that won't ask you any hard questions.
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.
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.
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.
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.
The 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.
It's actually wrong on the edge case of N=1, which is a power 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
It's actually wrong on the edge case of N=1, which is a power of 2.
Thanks, 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!
It just goes to show that sleep is very important for interviews!
[deleted]
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
There's no harm in brushing up on CS 101 questions, but I wish more candidates spent time preparing for questions about code quality.
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.
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.
> 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.
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.
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.
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.
If you cannot use libraries in a typical dynamic language, stuff is almost always just as inconvenient as in Java or C++.
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!
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!
> 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.
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.
I don't know Clojure, too much time in the MS ecosystem, I don't even have a JVM installed anymore. (I got tired of the constant security holes and updates that try to bundled software.)
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.
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.
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.
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...
Regardless of which language you use, whether it's pseudo or not, you still have to solve problem...
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.
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.
Java is your blub? Why not go for Haskell or ML?
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?
Because neither is a language commonly used in interviews.
Maybe they're not commonly used in interviews because too few people refuse to take the sort of interviews where they wouldn't be allowed?
having trouble following your nested negative set logic sentence structure here.
Restructured: "Maybe they're not commonly used in interviews because too few people insist on being able to use them in interviews?"
Yeah, 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.
And that will continue to be the case, because the overwhelming majority of programmers even in really cutting-edge areas don't need it, so being able to speak Java is still valuable.
Knowing how to write code in functional languages has helped me write Java, too.
Knowing how to write code in functional languages has helped me write Java, too.
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.
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?
This comment nails it:
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.
> 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.
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.
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.
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.
Here's my observation about "teaching to the test," having two kids who are now in middle school. Since every kid has to pass, the test is written to the lowest common denominator. Drilling the test over and over, to boost the school's average by a few points, short-changes the kids who have already mastered the material and need more challenge.
Something like "cracking the code interview" could become an upper bound.
Something like "cracking the code interview" could become an upper bound.
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.
[deleted]
>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?
Er, which standard of C?
You get the job if you can think of a non-trivial way in which in matters.
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.
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.
Sorry 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:
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:
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.
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.
K&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.
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?".
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.
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 see, thanks for your perspective on the matter.
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.
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.
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.
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.
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.