6 ms·
Some of this is straightforward. The rest.... eesh. I mean, yeah, I guess you can quiz your candidates on their knowledge of stuff like enable_if and ability
by ajross 8y ago
Some of this is straightforward. The rest.... eesh.
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?
- flafla2 8y agoA "max heap" is a heap that has O(1) access of the maximum priority element, as opposed to a "min heap" which returns the lowest priority. It's largely a semantic distinction, as a max heap = a min heap with negative keys. Also a heap isn't just a packed tree, it's referring specifically to a heap data structure [1] (which is often implemented using a packed tree, but not necessarily). 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. [1] https://en.wikipedia.org/wiki/Heap_(data_structure) https://en.wikipedia.org/wiki/Heap_(data_structure)
- ajross 8y ago> I'd expect any CS grad past an sophomore undergraduate level to understand exactly what a max heap is 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.
- banachtarski 8y agoSurely you've heard the distinction between the max-heap and a min-heap before... 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.
- dev_dull 8y agoSounds like their would be mutual filtering.
- gcb0 8y agosounds like all those people are filtering for is who went to the same university, at around the same time as they did.
- stochastic_monk 8y agoI don’t think so. Heaps are a bread-and-butter data structure typically covered in an undergraduate Data Structures course and then used in an undergraduate introductory Algorithms course. I’d expect someone to know heaps the same way I’d expect them to know about hashmaps or quicksort.
- jdlyga 8y agoTrue, but so many excellent programmers, people with 10 years of experience, typically don't remember all the details of classes they took a decade ago. I remember heaps, but I'd have to look up the details since it's not something I work with everyday. Once you're deep into your career, it's much more about practical real world style programming.
- ajross 8y agoBut as mentioned multiple times, I do know heaps. I've written heaps that were deployed in production software even. Yet given a question that asks without context "Write a max heap" I'd be lost. That's not a term I know. 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.
- sdegutis 8y agoI've had dozens of interviews for mid-level and senior-level engineer positions in the past 10 months at many diverse companies and gotten offers from most of them (retracted for unrelated reasons), and none of them asked about data structures even close to this. So it seems like it's probably really obscure. Or maybe only interviews for certain positions look for this kind of knowledge?
- AstralStorm 8y agoAlmost nobody writes heaps anymore, they're not even the best structure for priority queues now, that typically taken by skiplists or more advanced balanced trees like red-black tree. 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.
- jstimpfle 8y agoI'm curious, what's wrong with array based heaps? I've implemented both Red-black trees and array based heaps in the past. If I had to take a guess I would say the latter should be noticeably faster. In any case Red-black trees are much harder to implement.
- AstralStorm 8y agoThe problem with heaps is cache locality if you have anything different from tiny types like pointers stored inside. Plus that they do have to be resized more often than the other structures and you're forced to allocate a continuous chunk of memory if they're big. (And for small, you actually cannot beat a simple list with a one item sort by a heap.) 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.
- kadoban 8y agoRed-black trees aren't known for having good spatial locality of reference (heaps aren't either, but I fail to see how this is a point in favor of RB trees). Is there a particular implementation that doesn't share this shortcoming that you had in mind? That would be interesting to me. 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.
- ItsMe000001 8y agoThis is the first time ever I hear about "max heap", or quite possibly I heard it and promptly forgot it. No, I don't accept your implication about my credentials and how I fared in practice since getting the degree in 1997 supports me (it's quite algorithm-heavy for the last few years). Some people take their own favorite subjects waaayyyyy too seriously. 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.
- OskarS 8y agoAnyway, 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. 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.
- ItsMe000001 8y agoYou are not saying anything that I did not already respond to. I know trees, I know priority queues, I completely understand the data structure. What's the point of being able to assign some completely made-up and arbitrary name to it? If you think being a walking lexicon is an achievement, okay. That's spelling contest kind of "knowledge". I get it - some people really like it. Everybody is different and that is fine. Names (by themselves) mean a lot to many people. It's a low-effort signaling thing I guess. It is fine if I was ever selected against in such an interview - it would be entirely mutual. I do not believe it tests what you think it does. If you need a priority queue and don't happen to be able to come up with a good data structure on your own - or if you are too lazy to think about it - you can just google it. As long as you understand the basics of the underlying data structures - trees, arrays, lists, graphs (in general) - you easily understand the nuances of the particular variation of the base structure.
- jki275 8y agoI've had a BSCS for years, an MS in a related field and working on an MSCS and I've never heard of "max heap" or "min heap". Your explanation makes it quite clear and I guess now I know -- but it's not been common in anything I've ever seen.
- isaachier 8y agoI just don't understand how this is possible. The only way to implement Dijkstra's algorithm in less than O(|V|^2) time is using a min-heap. In practice it might be rare to use heaps over ordered sets but it is one of the first tree structures I was taught in my data structures course.
- Iv 8y agoI had an interview with a C++ guru while I was just a user of C++, among other languages and not really into language pedantry. So I failed at most questions, even some that are actually classic like the difference between struct and class (I was not even aware you can have member functions in struct in C++) 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.
- izacus 8y agoOn the other hand it's really hard to figure out the limits of a interviee's knowledge if you never ask the hard questions. Obviously, as an interviewer, you mustn't penalize people for not knowing obscure parts of the language, but asking easy questions will not give you an idea of the persons aptitude.
- Iv 8y agoYes, that's probably a good way to start a conversation to gauge knowledge. But the article linked proposes recruiters who have no knowledge of C++ should use these questions as tests. I don;t think this is a good idea.
- ryandrake 8y agoI think these questions are good to choose from when you have an obviously talented candidate and you are looking for an advanced question that probes the depth of someone’s knowledge. Most interviews I’ve conducted would never get that far. When I interviewed C++ programmers, people would struggle through things like when do destructors get called and how to iterate through every other array element. R-value references and move semantics? LOL. Let’s start with the difference between a set and a list and see if we get through that! 99% of the candidate flow I’ve seen would never have gotten any of these questions right.