6

In compiling some interview test questions, I'm currently taking examples from various sources and running through them to gauge their difficulty level and correctness. I've come across one that I think is broken, but it's also possible I'm missing something: if I am, I want to know, not only for my own knowledge but then it would also indicate that this is potentially a good, tricky question. I'd like you to help me regain my sanity and re-affirm the trust I have placed in myself. :D

What is the correct way to cast p at the placeholder "???" in the following code?

#include <iostream>

using namespace std;

uint16_t hash(void *p)
{
    uint32_t val = ???;
    return (uint16_t)(val ^ (val >> 16));
}

int main(int argc, char *argv[])
{
    uint32_t a[20];

    for(uint32_t i = 0; i < 20; ++i)
    {
        a[i] = i;
        cout << hash(a + i) << endl;
    }
}

Choose one:

  • static_cast<uint32_t>(p)
  • dynamic_cast<uint32_t>(p)
  • reinterpret_cast<uint32_t>(p)
  • const_cast<uint32_t>(p)

Ignoring for a moment that the call to hash must be ::hash to guarantee disambiguity with the standard library (e.g. this line doesn't compile for me in GCC 5.3.0, C++14 mode), I have a problem with the question.

Firstly, it's not clear what the program's supposed to do. Hash the array values, or hash the element locations? Because at the moment the function is receiving pointers-to-elements, but all the available answers assume that those pointers are to be themselves converted to uint32_t and used as the hash value. If that's the case, then even if you use a reinterpret_cast then there is a bug because sizeof(void*) may not be sizeof(uint32_t); val in that function should be intptr_t instead. The use of uint32_t for the type of the array elements themselves just confuses matters further if that's effectively a co-incidence.

Or the function is supposed to hash the value and the correct answer is not in the list: *static_cast<uint32_t*>(p).

The "correct" answer is apparently reinterpret_cast<uint32_t>(p), which makes me think the intention of the program is to hash the array element addresses.

Am I imagining these problems?
Is the question clear and is the solution one of the four choices offered?

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • Can't really post this as an answer, but to me it looks as if your analysis is correct and the interview question is misguided, unless I'm missing something crucial here. – Cubic Feb 19 '16 at 14:07
  • 2
    Why would you hash arbitrary pointers? What purpose does that serve? I think you're right in presuming it takes the form `*x_cast(p)`. – tadman Feb 19 '16 at 14:07
  • I don't think this question is answerable; only the person who wrote the code knows the intention of it. He may have meant to hash the address values, or hash the elements themselves. – Colonel Thirty Two Feb 19 '16 at 14:08
  • 1
    @tadman It would serve that you can find if an object instance is currently present in the hash, though it's hard to imagine where that would be useful. – Neil Feb 19 '16 at 14:09
  • 4
    Looks like a trick question to get you to engage with the interviewer. – NathanOliver Feb 19 '16 at 14:09
  • 1
    @neil Considering how cheap copies are intended to be for some C++ objects, stashing the pointer seems reckless and broken. Hash the element in your stack, then the one on the heap is "not there"? I find everything about this interview question to be severely misguided. – tadman Feb 19 '16 at 14:15
  • @Neil: Funnily enough, just the other day I added a `unordered_map num_visits_to_a_certain_construct_in_a_script` (to implement a naive maximum bound on loop iteration). But I agree it's got to be pretty rare, and the code must be clearer than this. – Lightness Races in Orbit Feb 19 '16 at 14:15
  • 7
    @PreferenceBean Let's get to the real crux of the problem... what happened to lightness racing? – Barry Feb 19 '16 at 14:16
  • I agree with both of you. If we're scratching our heads as to what the intended meaning is, then it is no metric to use to judge programmers in an interview. – Neil Feb 19 '16 at 14:17
  • What should we objectively tell you? – edmz Feb 19 '16 at 14:23
  • @Barry: [SV23 malfunctioned](http://www.itnews.com.au/news/satellite-failure-caused-global-gps-timing-anomaly-414237) and ruined my orbit. Waiting for a hydrazine delivery then will boost back up. :) – Lightness Races in Orbit Feb 19 '16 at 14:25
  • @Neil: Then my follow-up question becomes whether it's a worthy discussion point in such an interview: do they identify the problems I mention here? If they give one of those four answers without qualification then perhaps there's a problem there, I say. On the other hand, trick questions are a bit evil. – Lightness Races in Orbit Feb 19 '16 at 14:26
  • @black: All these comments are the level of objectivity I was hoping for. :) Someone oughtta summarise them as an answer, I guess. – Lightness Races in Orbit Feb 19 '16 at 14:27
  • 2
    The other strange thing is that `hash` doesn't do anything to `val`s under 65536. – Paul Evans Feb 19 '16 at 14:29
  • 1
    @PreferenceBean Most new programmers will falter on a fizzbuzz question, unfortunately. No need for the cloak and dagger unless you're Google. – Neil Feb 19 '16 at 14:30
  • @Neil: Why would _anyone_ hire someone who can't even implement fizzbuzz? – Lightness Races in Orbit Feb 19 '16 at 14:36
  • @PreferenceBean In fact! If you can eliminate half of all candidates just asking them to implement fizzbuzz. If you ask me, a programmer that doesn't even have the time to *google* a solution to the fizzbuzz problem prior to the interview should not have a job involving computers whatsoever. – Neil Feb 19 '16 at 14:40
  • 2
    Companies that interview candidates tend to be interested in people that can get stuff done instead of being constantly paralyzed by a language standard that doesn't give enough guarantees. There is no "yes, but" choice here so you pick the most-likely-to-work version of course. – Hans Passant Feb 19 '16 at 14:40
  • 1
    @HansPassant: Point taken in general, though in this case the language is providing all the necessary guarantees; it's the question that is not. – Lightness Races in Orbit Feb 19 '16 at 14:42

2 Answers2

5

Just to summarize all the points you made in the question and the comments. Basically, the answer to this question is probably:

The correct cast to use is reinterpret_cast1†‡.

That's a lot of footnotes! I guess that's what makes it a real C++ question. In any event, I wouldn't ask it in an interview – it's too trick question – and there's plenty of real questions with real, direct answers that you can ask instead.

1 On a 64-bit system, you can't any_kind_of_cast a void* to a uint32_t. So they're all wrong.

† There's a name lookup issue in C++11 between the user-provided hash() and the the class template std::hash<T>. You should obviously link them to why is using namespace std; considered bad practice?

‡ Even if the above weren't problems that prevented the code from compiling in the first place, is the intent here to actually hash the pointers into a and not the values of a? The most-likely-correct answer should be:

auto val = *static_cast<const uint32_t*>(p);

If it is about hashing pointers, then reinterpret_cast would be the correct cast but not to uint32_t (as per (1)). We would want to use uintptr_t:

auto val = reinterpret_cast<uintptr_t>(p);

In the case of 64-bit, you'd probably want to do something either than val ^ (val >> 16), since you're effectively ignoring the upper 32-bits, but at least this would get you to a correct cast that would compile everywhere.

Community
  • 1
  • 1
Barry
  • 286,269
  • 29
  • 621
  • 977
  • 2
    Hmm, I find it more likely to be about hashing the pointer value. If the intention is to hash a `uint32_t`, shouldn't it be `hash(uint32_t)` or at least `hash(uint32_t*)`? OTOH, `hash(void*)` is a reasonable signature for something that can hash every kind of pointer value. – T.C. Feb 19 '16 at 15:12
  • 1
    Yeah, if it's a "trick" question then you also need to know the "trick" which is often not the case. – Ludwig Feb 19 '16 at 15:43
4

  1. IMHO you are imagining these problems :) The example was taken from here : reinterpret_cast So it is better to look at example in context of that article.

  2. Question is clear but when I finished reading it and all comments I've started doubt in my 1st minute solution to use reinterpret_cast (I would use it anyway as an answer even without context)

StahlRat
  • 1,199
  • 13
  • 25
  • 2
    Woah, points for finding the original, original source. Okay so it's ultimately a MSDN documentation bug (or, at the very least, a dangerously non-portable formal example). Figures. – Lightness Races in Orbit Feb 19 '16 at 14:41
  • In what sense am I imagining the problems, though? I think together the group has generally found that they are technically accurate? – Lightness Races in Orbit Feb 19 '16 at 16:42
  • @PreferenceBean I looked at the question as if it was one out of many questions on interview. You looked at the question as if the question is the ONLY question on interview. – StahlRat Feb 19 '16 at 16:58
  • Yeah but I'm the one giving the interview. I know that none of the other questions are even remotely related to this question. And, even if they were, how would guessing at their content enable you to conclude that I'm imagining all the technical problems described above? From what I can tell you're basically saying "the code is fine and I'd use it even after reading what all of you lot said", even though I've provided links to a live demo showing that it doesn't even compile in the general case, let alone work properly. Perhaps if it were an interview for 32-bit Visual C++ specifically, but.. – Lightness Races in Orbit Feb 19 '16 at 16:59
  • Then ask me something like "what's wrong in this code and want type of cast should I use?" not only "What is the correct way to cast p at the placeholder?". – StahlRat Feb 19 '16 at 17:02
  • I'm not asking for you to rewrite the interview question. I'm asking you to confirm that it's broken in its current form (and, if not, to explain why)! The others have said "yes, it's broken"; you've said "no, it's fine". And I'm trying to determine which is true. – Lightness Races in Orbit Feb 19 '16 at 17:03
  • Could you tell right at the interview table that code won't compile? btw question doesn't specify environment. Rename the "hash", use reinterpret_cast and it will work – StahlRat Feb 19 '16 at 17:06
  • Yes; while reviewing the question for potential inclusion in interviews we'll be hosting next week, I realised I couldn't answer it unambiguously. This in itself is not a showstopper for an interview question (indeed, it may even have value as a discussion point!) but then I realised that — given what seemed to be the most likely interpretation of the question — it had a fatal flaw. Not specifying the environment means it must be valid in all environments. Renaming the function achieves nothing. Using reinterpret_cast does not work for the reasons stated above. – Lightness Races in Orbit Feb 19 '16 at 17:16
  • 1
    Renaming hash fixes ambiguity when `using namespace std;` left. btw the `#include ` is missed too (frankly I never pay attention to includes in books and in articles, some includes always missed or just omitted) – StahlRat Feb 19 '16 at 17:27
  • Mmmm yeah both true! – Lightness Races in Orbit Feb 19 '16 at 17:56