C++ Programming Questions to Ask on Interview (2017)
tests4geeks.com
tests4geeks.com
Your problem when interviewing someone is that in real life, you are relying on the person being quick to learn, since they are unlikely to have the answer in cache. Maybe if they'd just read Stroustrup they'd know some of the specifics, but most coders would know what the point was and google it.
You have to wonder that a fair question is. I supposed you should know of a bunch of things about c++ (why you're using it, major features like templates), without knowing all the specifics (SFINAE/CRTP examples). For instance it's fair to ask someone what a memory barrier is. But not to list all the varieties (relaxed, acquire, etc).
I've hired a number of c++ devs in the last few months, and all of them have turned out fine. I never asked anything particularly specific like this list of questions, just poked around the very large house that is c++. What does the candidate think changed in c++11? Why are we using it for HFT? What kind of thing will slow us down?
I think if I'd asked these questions I'd have dropped a lot of perfectly fine candidates.
I mean, yeah, I guess you can quiz your candidates on their knowledge of stuff like enable_if and ability to write templates based on traits like is_integer, but don't expect that to be a good filter for anything but language minutiae.
And question 10... what on earth is a "max heap". I'm gathering from context that they are asking about a heap in the sense of the packed tree data structure. I've used those, and written those on multiple occasions, so it's not an impractical subject. But (1) if you asked me the question the way it's phrased here I'd look at you blankly and wonder if you were talking about some kind of custom allocator, and (2) they don't even want the candidate to talk about the data structure! They just want a class definition written for the thing with a handful of obvious interfaces (add, get maximum, y'know... it's just a heap). How is that useful to anyone?
This is very common terminology, and honestly I'd expect any CS grad past an sophomore undergraduate level to understand exactly what a max heap is, especially in an interview setting.
Never once heard the term, and I've written several heap-based priority queues over the course of more than two decades of professional work.
So... yeah, I'm too dumb for that filter I guess.
And honestly, I'm sure if you asked what it was in an interview, you would get a straight answer and not be dinged for it. I would filter based on your saltiness level though.
I’d expect someone to know heaps the same way I’d expect them to know about hashmaps or quicksort.
Conflation of terminology (about which heaps are already a terribly confusing example) with expertise is kinda the essence of why this kind of list is garbage.
And in any case, I retreat the broader point that has nothing to do with my personal vocabulary: the question wasn't even asking about how heaps work! It just wanted to know you could write a class declaration with the API.
A class declaration with an API (and no implementation) would be rather simple: insert, top, remove, and a constructor.
I will say that I typically hear “heap” and whether it’s max or min is largely implicit in the task, so perhaps the comparator qualification is unneeded.
Out of curiosity, what terminology would you use to distinguish between a heap that offers up the lowest value first and one that offers the highest value first?
Like any word, it's shorthand for a longer set of words.
> The difference is the direction of the pointy end in the comparison operator...
That's not descriptive of what the thing is, that's descriptive of how one part of it will be implemented.
I get that you don't think it is important, but I am surprised that you are acting defensive about the fact that it's a term practitioners ordinarily use. It's the first thing someone who looks up a binary heap is likely to see in Wikipedia, captioning the top two illustrations in that article. It's not just Stanford-cult algorithmic knowledge.
It is one of those stupid questions. The good question would be to task them to implement a priority queue (also a bit rough as they are in standard library now or boost, but for old C++ you may get to write one) and see what they come up with. Discuss a bit too.
Both skiplists and rbtrees allow for a tricky but efficient colored pointer implementation and also if you need fine grained locking or lock free implementations.
If allocating a heap as a big chunk were a problem, you could certainly do it as nodes and pointers like a RB tree is traditionally done (reify the tree instead of array-encode it). Though the array-encoding is itself usually an optimization, so I wouldn't think you'd want to do that. Doing one big allocation (and copy) every once in a while (in a table-doubling-esque manner) should be a win over individually allocating nodes, if you can amortize over many operations. And again if that's not true or undesireable, you can just allocate a heap like you'd allocate a tree normally.
B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.
That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.
Both of these things are significantly more complex than just implementing a simple max-heap, which will almost certainly perform well enough for most any practical purpose. A red-black tree will probably have significantly worse cache behaviour than a max heap, since every dereference is jumping around in memory. In a max-heap, you can count on having at least a couple of the first levels in cache when you start.
Van Emde Boas trees are better but yet more complex still. (And colored pointer variant is not available for them)
The tradeoff is speed of write vs read in case of heaps. They have pretty bad write performance.
I have no intention of becoming or finding good becoming a walking lexicon of obscure algorithms and minutiae. Thank god I'm really good at forgetting stuff I don't need - as well as learning stuff I do need but never did before, but only when I actually need it. Dynamic learning capability (let's just call it that) seems far superior to me than static learning. We have Google to outsource a lot of that to.
Anyway, looking up max heap it's trivial, no idea what my benefit would be if I knew every variation of a tree structure somebody came up with by heart. Often it's just a name for something that anyone who needs it would come up with by themselves anyway if they understand the greater concept because it's kind of obvious. I have used plenty of data structures for which I'm sure someone invented a name for without knowing that name.
It's not just any other tree structure. It's the tree structure that is by far the most common way of implementing a priority queue, and it's the tree structure at the heart of the algorithm "heap sort", which is not exactly obscure. It's also the tree structure that gives "the heap" its name (though modern operating systems and allocators don't use heaps for this purpose anymore). I've personally implemented heaps in a variety of languages and contexts throughout the years as part of my work.
I don't want to sound too dismissive here, but this is not some obscure data structure with only theoretical interest. It's perfectly fine to not know off the top of your head what splay trees, Fibonacci trees or skip lists are or how they work. But if you have a degree in computer science, you should know what a heap is.
I understand that it is highly unpopular that some particular knowledge is unnecessary - for every piece of knowledge there are people who feel very strongly about it. I guess that's partly because getting the knowledge was quite an effort, and then psychology kicks in, what was hard to obtain has value by that proxy. Makes it hard to talk rationally and calmly about what is actually needed. That's why questions such as what children or students need to learn are so hard, the discussion always becomes extremely heated, and removing anything from the list can only be done against lots of screaming. So sure, me saying that being able to immediately connect some name and immediately have the respective thing, here some algorithm, available without looking it up is not popular maybe not with everybody, but those who are opposed to what I see feel very strongly about it. Unfortunately that includes interpreting things into what I say/write that is not really there. I mean, obviously, a good and thorough education in algorithm fundamentals is extremely valuable.
> I have no intention of becoming or finding good becoming a walking lexicon of obscure algorithms and minutiae.
This implies that you think that heaps are obscure and minutiae. If that wasn't what you meant I'm not sure why you brought it up in a discussion about heaps.
> I understand that it is highly unpopular that some particular knowledge is unnecessary -
what is highly popular today is the idea that knowledge is unnecessary because you can always google it. You can't google what you do not know it exist.
> This implies
Why don't you stick to what I wrote? You respond to the straw man your own imagination creates.
> is the idea that knowledge is unnecessary
See above. You are being quite ridiculous.
EDIT: I knew it, you narcissist use alt accounts for voting manipulation. LOL, I won't even report you, sick little child (no sane person would go through such trouble for literally nothing). I knew it was only you all along, and this comment was a provocation test - nobody else is reading this any more at this point. The only way to get such a quick within-minutes reaction to this comment is if you cheat (and use a notification service, which was already likely in your case so I counted on it). Got you! My own personal troll, I feel honored!
Your explanation makes it quite clear and I guess now I know -- but it's not been common in anything I've ever seen.
I still got hired, probably because I did not go to that interview with a high expectation of being hired (I was actually curious about what they were doing and would have been happy to just chat about that). So I would typically say I don't know, propose an hypothesis (usually wrong) and suggest that in the real world I would just google it real quick or write a test program.
They later told me that some interviewees were really stressed out by these questions (I can understand, they were hard!) and that no one could really answer a lot. They liked that I was actually curious about the things I learnt about C++ and would ask follow up questions ("Really? struct and class are almost the same in C++? Are they packing the same way as well?"). I realized how unfair this situation was: I was good at getting hired because I was not in a dire need for a job at the time. Would have I been desperate for this job, the temptation to try and fake it would have been great. And would have backfired quickly as the interviewer still is to this day the C++ programmer with the deepest knowledge of the language that I have ever met.
99% of the candidate flow I’ve seen would never have gotten any of these questions right.
True story: once interviewed a guy who claimed to know C++; set him a challenge that he couldn't answer, simplified it a bit, still couldn't answer, we iterated down until I discovered he didn't even know how to declare an int variable. Turns out he had been a tester on a system written in C++ ...
I also agree with the other reply that the strongest learning experience is basically in the chronology of the language development. It takes running into a case where they are the best solution to really grasp "why include guards?", "why templates?", "why smart pointers?", "why iterators?" and so on, and you also gain a lot of appreciation for what compilers in other languages do for you behind the scenes.
I also highly recommend https://godbolt.org/, which allows you to see what machine code is produced in the end. Seeing all the template magic getting distilled to clean asm is quite amazing.
"A conforming implementation may provide more versions of main(), but they must all have return type int." ~ Bjarne Stroustrup - http://www.stroustrup.com/bs_faq2.html#void-main
And in the followup, they assume the candidate will just assume that "SearchQuery", whose header is not shown, will have a copy constructor.
Just no.
However, understanding that SearchQuery is broken is pretty important. Breaking the Rule-of-3 is probably the #1 mistake made by junior C++ developers trying to write object-oriented code, and the consequences are pretty nasty. You'll get corruption and crashes from use-after-free and double-free errors and nothing will make sense because the problem will move around as you create temporary copies while trying to debug.
That being said, I wasn't familiar with that sort of stuff when I was first hired as a C++ developer. I was very fortunate to start my career with a company that was willing to hire people and train them.
I'm pretty sure business do not like to actually train people nowadays. :)
It's now called the rule of 5.
RAII basically assumes that your objects are always going to be in the init-use-free pattern (you read a file, you use it, and close it after you’re finished) In reality not all things work this way, as objects have various different states according to their state machines and will use and free resources depending on that state. But in Modern C++ you’re forced to think only in the on/off paradigm, which results in lots of small unnecessary classes with their own on/off state. (If you try graphics programming you’ll understand right away...) Now when you add rule-of-five this becomes a monstrosity to handle, as you have to ensure about memory copying/moving for every little RAII class you make.
So why not let normal assignment be shallow copy by default, but have an explicit copy() method? Why is everything so implicit in Modern C++ where you can’t assure that by simply looking at a = b you can’t tell how memory is allocated/freed...
Nowadays I have lost hope in Modern C++ and are looking for alternatives: Rust (complex but at least memory safe) Orthodox C++ (not memory safe but at least sane for graphics/game programming), or Jai/Zig/other experimental lnguages (which claim to be a better C)
You could say, "well, developers can just adopt a uniform semantics for what parts of objects are considered 'shallow' vs. 'deep'", but now the compiler can generate correct default copy operations in many fewer cases, since the rule is arbitrary vs. simply "copy everything".
You're right that the RAII model sometimes feels a bit limiting for the complexity sometimes found in graphics, but I think part of that was self-inflected by our API design. That seems to be changing. The best-looking technique I've seen for handling Vulkan/DX12 is to make your program more like a compiler. You take a scene as input and you compile it into a command buffer to give the GPU. Your resource handling for stuff like texture slots thus looks more like register allocation. State shadowing is a trivial optimization pass when your GPU code is data.
The problem is that when you write RAII classes for GPU resources in the traditional way, C++ sees the GPU state through a tiny pinhole and thus can't optimize very well. When you treat your GPU commands as a program that your C++ program is building, you have more global information about GPU state available, which allows you to make more efficient choices.
For example, it's trivial to have shallow copies by default - just wrap it in std::shared_ptr (or a thread-unsafe homebrew version if you can prove that synchronization is a performance problem).
I admit to not having done a lot of graphics programming, but I can't shake the feeling that you are using modern C++ wrong if your complaint is "too many small RAII classes".
No, it really isn't. The whole point of a unique pointer is to ensure that the pointer is in fact unique. Thus, std::unique_ptr is specifically designed to disallow any form of copying.
This is not minutae. This is a test if you understand the theory behind ownership semantics.
No.
Those utilities weren't standardized before C++11. People wrote their own implementations before that. People had to understand stack unwinding and scoping, memory, RAII, design patterns that relate to allocation/de-allocation of memory, ownership transfer.
Then came in the people that decided it'd be a great idea to start quizzing others about C++11 concretions.
So it has been almost a decade. How much longer before the whole move semantics addition to the language specification becomes relevant to you?
As a veteran of three decades of C++, I've seen a lot of new hotness turn into old and busted and removed. There's plenty of dark corners where you don't need to look to get a job done.
I'm not debating the usefulness of move semantics. I'm debating the weight being placed on them in these so-called "C++ interview questions". Wouldn't it be better to discuss the actual problem, rather than a concrete solution we ended up having in C++11?
That's quite a disigenuous statement. Work on C++11 started after the approval of c++98, and the c++0x smart pointers have been implemented and available for quite a while before C++11 was finalized.
In the max heap question, I'd argue that add should take a parameter by value, rather than a const reference, since this prevents having to needlessly copy temporaries (and is less verbose than overloading for T&&).
List of iterator categories is missing input iterators.
Basically they do std::swap on query field. In that case you are relying on the destructor of the moved object performing the delete (if necessary). I would argue that that falls into the “too clever” spectrum, and also kind of assumes that no one is going to refactor the destructor at some point in such a way that some other property will result in them incorrectly thing that the query is null, and so leaking it.
Having now read through this, I agree with others assessment - these questions are questionable at best. What is it they’re proven to do?
Swap is additionally risky because someone can ADL specialize it for their own purposes. (which is the point) And suddenly your move assignment is broken.
So people work around it by adding using std::swap clause there...
And then you're calling all those destructors.
e.g. (pseudo-ish code)
operator=(vector&& foo) {
delete [] elements;
elements = foo.elements;
foo.elements = nullptr;
}
what the example code they have as an answer does is something morally equivalent to this:
operator=(vector&& foo) {
swap(elements, foo.elements);'
}
relying on the knowledge that because it's being moved the ~vector is going to be called immediately afterwards.
This strikes me as being "clever" in the "potentially confusing code, for no real reason" sense
The idiomatic copy and swap is like this:
T& operator =(T x) // note pass by value { std::swap(this, x); return this; }
This acts both as a normal and move assignment operator (if T is not copy constructible);
edit: how do you get HN to show asterisks? There should be one before each 'this'
T& operator =(T x) // note pass by value
{ std::swap(*this, x); return *this; }It's an invariant of the 'DirectorySearchResult' class that query is non-null, as the destructor deletes it without checking it for nullity. The most straight-forward and efficient way to achieve both the stealing and the valid state is to swap the pointers.
Deleting a null pointer is a fully specified no-op in C++.
To make the question clearer they should have added a function on the original class that checks (or doesn't check) the pointer before dereferencing it, thereby clarifying whether query being null is valid or not.
But was it that hard before? Constructors, destructors and operators were fine... weren't they?
> The interview candidate might think that returning a noncopiable object from a function is also a compiler error, but in this case it’s allowed, thanks to copy elision. You can ask the candidate under what conditions copy elision is performed.
This isn't copy elision. Copy elision isn't even permitted here because the returned expression is the name of a function parameter. The two-stage overload resolution that tries a move constructor first is defined in the same section of the spec, [class.copy.elision], as copy elision but the rules are different and it is always performed, even if the implementation doesn't do copy elision.
Most C++ code found in college books is outdated and not idiomatic, driving students away from the language.
But it is true that C++ can also be your worst nightmare if you don't have discipline.
C++ will turn your bad coding habits into infinite frustration... and that is great. C++ is the proof you really like programming.
This makes me hope I never have a need to go near that language ever again.
However, it's quite hard to come up with good C++ interview questions. You want to test for fundamental knowledge of C++, for the practice of using C++ for developing code, but avoid impractical cases that nobody remembers in their right mind.
Every interviewer has his own favorite C++ trick. The fact that an interviewee doesn't know or use that trick doesn't mean that his C++ skills are inadequate. It means that the interviewer's trick may not be as commonly used as he may think.
1 - knowing this is 100% useless information, in reality I have a compiler to tell me that.
2 - Seriously? new/delete in 2018? In very rare cases when I need a raw pointer I call unique_ptr::release().
5 The question is so-so but the answer's wrong. Iterators don't need to point anywhere. You can make an iterator generating values instead of referencing container. Not necessarily a good idea but still.
6 Same. Just because it's not specified in C++ standard doesn't mean it's bad, or should be avoided. E.g.
const uint32_t n = 11;
printf( "Eleven: %d\n", n );
8-9 IMO template metaprogramming should be avoided. If you want your template data structure to behave differently for pointers and non-pointers, expose another template argument for that, there's too many corner cases like handles (technically pointers, logically values) and smart pointers (the opposite).
10 I don't think the sorted vector listed in "possible answer" is a max heap.
Conclusion: if the OP claims the questions are "Proven", I'm curious about provement methodology.
A clever compiler might tell you that adding std::move will make the code compile. But if you do not understand what std::move does it will lead to more bugs as you might not expect the ptr to suddenly be empty in main.
They're asking "What happens when?" giving code that doesn't compile.
Nothing happens.
Strongly disagree - I'd never let that through code-review. When living in C/C++ land, we should be extremely aware of the differences between the integer types, and handle their conversions carefully and explicitly.
Given that the "%d" format-specifier maps to `int`, not to `int32_t` (let alone `uint32_t`), that code really could wreck things if your platform has an `int` type which isn't 32 bit - https://stackoverflow.com/a/3168293/
Similar about %d and unsigned. Technically UB, practically works fine in 100% of cases. If you ask “but how do you know it works?” I’ll answer “because I read assembly”.
Because they aren't assured to be the same. They might happen to be the same on your current platform.
C++ isn't like Java. It's the programmer's job to be very aware of these sorts of platform-specific points of variation.
I don't see why you'd deliberately write undefined behaviour when there's no benefit to doing so. This isn't a purely academic concern - I've seen a malformed printf call wreak absolute havoc, presumably because it was stripping too much or too little data off the stack. Was a nightmare to track it down.
I don't want to think about which particular families of dangerous type-based mistakes are permissible in my codebase -- I'd rather write code which is correct.
> The only cases when I encounter these differences, they look like broken C++ compiler
If you write dangerous, non-portable code that invokes UB, you may well find that it works on plenty of real-world platforms. Your code is still wrong. For the specific case of assuming that `int` is 32-bit, you'll probably get away with this sort of clumsiness, yes, but 'ILP64' targets exist, even if they're rare.
Additionally, using `int` as a dangerous alias for `int32_t` is not expressive when it comes to readability.
> Technically UB, practically works fine in 100% of cases
UB can bite you in bizarre, unpredictable, intermittent ways, especially with optimising compilers.
Why argue that a bad habit isn't that bad, when you could just avoid doing it?
> If you ask “but how do you know it works?” I’ll answer “because I read assembly”.
That's a very fragile assurance of correctness. Unless you explicitly embed that assembly code, the compiler is free to generate different code at any point in future. Can you guarantee that you'll never change or upgrade your compiler, tweak its flags, or target another platform? Can you guarantee the optimiser will never change its mind and generate different code for that function?
Good, and I’m not writing STL. I develop user-facing software, and I know the platforms I support. It just happened so that in the last couple of decades, all my current platforms have 32-bit integers, and I don’t expect that to change within my remaining lifetime.
> It's the programmer's job to be very aware of these sorts of platform-specific points of variation.
Exactly. I’m writing platform-specific code in C++, and I don’t expect compiler to interfere. When I want to abstract these things away I don’t code C++, there’re better languages out there for such requirements.
> why you'd deliberately write undefined behaviour when there's no benefit to doing so.
Read the comments in the link I’ve posted. Because clang authors share your opinion on the subject, I had to write a couple of pages of boilerplate code, changing ~50 C++ functions for absolutely no value. That’s one of the reasons why I prefer MSVC, by the way.
> ILP64 targets exist, even if they're rare.
Why should I care? As you see from this example, caring is not free, it has costs.
> Additionally, using `int` as a dangerous alias for `int32_t` is not expressive when it comes to readability.
Additionally, typing int is 3 keypresses, typing int32_t is 8. Given how much code I type every day, and how many integers are there in my code, the difference is not insignificant. Even Nintendo did it better on CodeWarrior toolchain, with u8, u32, u64, etc.
> UB can bite you in bizarre, unpredictable, intermittent ways, especially with optimising compilers.
I think you’re demonizing UB. Different cases are different. Some will crash your app right away, the worst of them will silently give incorrect results with 0.001% probability, but the code from my original comment is harmless.
Also C++ compilers aren’t perfect, couple times in my career I found bugs in them. Many times, I found bugs in standard libraries or OSes. If you think writing 100% standard compliant C++ code guarantees correct programs, I have bad news for you.
> Can you guarantee that you'll never change or upgrade your compiler, tweak its flags
Do you have an example of specific compiler version, or flags, that will break my code above, when targeting i386, amd64 or arm32 platforms?