« mmmmlispy
I have lost my faith in humanity. »

nvidia test

edit: fixed an error in test Question #1
So, yet another fall career fair has gone by, but this year’s turnout seemed a bit…well…crappy (for computer science, at least). A few of the bigger players were there (Microsoft, nvidia), but most companies were small New York companies that just wanted college students because they can’t afford to pay real people.

I went to the nvidia booth, and, lo and behold, found the guy who interviewed me last year. I saw him after the interview (ironically, getting on a plane to Seattle to interview with Microsoft), and so we’ve talked relatively extensively on topics like software development, career paths, Microsoft (he was the technical lead of directx 5 or 6, I forget which), and nvidia. I joked around with him and another guy working the booth, showed him my resume, and took another one of the (infamous!) nvidia tests. He gave me the hardest one, which was exciting. It looked something like this:

Question #1: What is different about these two segments of code?
a)
int Clocks(unsigned short* p) {
    int val = *p;
    val |= (*p << 16);
    return val;
}

b)
int Clocks(volatile unsigned short* p) {
    int val = *p;
    val |= (*p << 16);
    return val;
}

Question #2: What is wrong with the following code segment?

char* SaveString(const char* s) {
    char* p = (char*)malloc(strlen(s));
    while(*s)
    {
        *p++ = *s++;
    }

    *p = 0;
    return p;
}

Question #3: Write atoi.  Ignore all leading and trailing non-numeric characters,
e.g. "abcd1234defg" will return 1234.  If no number can be read, return a -1.
Ignore all '-' characters (no negative numbers), and assume the conversion
will not overflow.

int atoi(char* s) { ....

I’ll post some solutions later in the week. Oh, he originally gave me a different test, but the last question was the same from the test I took last spring (count the number of on bits in an integer), and I didn’t feel it was honest for me to take it again. That test just had a few questions like:

Question #1:
unsigned short a = 0xa3b7
unsigned short b = 0x3f4c

show the results of:
a + b
a & b

(I forget what the second question was).

I’ll also post an answer for the “count the number of on bits in an integer” with the other solutions. It’s a fun little problem, and kudos to Sidney Marshall for showing me a few nice ways of doing it.

This entry was posted on Tuesday, September 26th, 2006 at 12:49 pm and is filed under general. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

  • Gatacoma
    What's a "nice way" of counting bits?
  • Warren

    edit by noah: fixed up the spacing for the code


    Here's my lunch break solution to atoi. (and here's hoping WordPress has intelligent handling of whitespace...)



    int atoi ( char *s )
    {
      while ( ! isnum ( *s ) )
      {
        ++s;
        if ( ! *s)
          return -1;
      }
      char *left = s;
      while ( isnum ( *s ) )
        ++s;
      int sum = 0, place = 1;
      while ( --s > left )
      {
        sum += ( (*s) - '0' ) * place;
        place *= 10;
      }
      return sum;
    }

    For #1, I'm not famliar enough with volatile to say... it always connotes scary mental images of concurrency and nasty hardware issues like caching...


    For #2, every C programmer should have a mental concept of what allocating a buffer to hold a string should look like, and this doesn't match. Need a "+1" after the call to strlen to make room for the terminating NUL.


    Score me!


    Peace,

    Warren

  • Your atoi looks like it will work in most cases (although it may do strange things in the case where s[0] = 0, since I'm not sure how isnum('\0') will work), although its a bit more complicated than it needs to be (hint: instead of multiplying the digit you are adding to the sum by the place of the digit, can you a similar operation to the sum instead, i.e. working left -> right?). Also, I think you might leave off the largest digit by accident (with:

    --s > left

    and left being the first numeral, then you will skip over it on the way back).


    As for question#2, that is only one of the errors. From my count, there are at least 3.


    For #1, you are on the right track, you just need to use your imagination at what the compiler can do with the code that is there.


    I would give you near full credit for atoi (near full credit for workingness, partial credit for being a bit over-complicated), 1/3 credit on #2, and a bit for #1. And, of course, my love and affection for being the Warren. Cheers!

  • mwoz
    For the atoi, I felt that supporting the -1 return value would be a bit inelegant, so mine returns 0 on error instead.
    int atoi( char* s )
    {
    int i = 0;
    while( !( ( *s - 0x0030 )
  • mwoz
    (It seems my previous comment was cut off due to the presence of <, here is it again)

    For the atoi, I felt that supporting the -1 return value would be a bit inelegant, so mine returns 0 on error instead.
    int atoi( char* s )
    {
    int i = 0;
    while( !( ( *s - 0x0030 ) < 10U ) && *++s );
    while( *s && ( *s - 0x0030 ) < 10U )
    i = ( i << 3 ) + i + i + *s++ - 0x0030;
    return i;
    }

    One of the other errors in #2 is the fact that it returns a pointer to the end of the string not the beginning.

    In number 1 the without the volatile the compiler is likely to optimize this statement:
    val |= (*p << 16);
    to something like this:
    *p |= (*p << 16);
    Which will overflow (because *p is only a short), whereas val is an integer.
  • mwoz:

    First, returning -1 for a function that can only return integers >= 0 makes much more sense than returning the legal value, 0. I'm not sure what you mean by inelegant, but I think following the paradigm of most other functions of the same type makes much more sense, as well as returning an illegal value.

    As to your answer for atoi, that is probably some of the most illegible C/C++ code I've seen in awhile. First of all, use '0' to get the value of the character 0, not a literal hex value. Second, your initial while will have major issues. If you take any character less than '0' in the ascii range, that value - 0x0030 will be less than 10U. So your function would include, for example, most punctuation as a number. The same holds true for the other loop.

    The whole i = (i << 3) + i + i is just plain silly. Multiply by ten. Multiplying by 8 and adding twice just looks ridiculuous. Never mind the fact that you just killed the compiler's ability to produce code and the processor's ability to pipeline, the code is just plain inelegant. You are closer to the right idea, but please, for the sake of humanity, never _ever_ write anything like that.

    For Question #2, that is one of the other errors.

    For Question #3, you are working in the wrong direction. val is a copy of *p, and the compiler can't magically assign to *p what it was going to assign to val. The compiler can cache reads of the thing, but it can't magically change it in one case but not the other.
  • well making something volatile in question #1 im pretty sure tells the compliler not to optimize anything out about that variable. So in that examble, part a would probably optimize out the assignment part in "int val = *p;" (assuming we are using gcc 3.3 and not 2.X). This would seem probably harmless except for the fact that we may actually want to do this b/c that may be mapped to a device of some sort, so that statement is explisitly needed. This would mean that only part B would work correctly under such conditions.

    I also think the volatile modifier also has something to do w/ multithreaded programming in
    C++ which probably has the same idea as above but just in a different context?

    For question #2, because s was declared const, you cannot actually modify it, which you are doing when you say s++. instead maybe use a index variable and do something like s[i];i++;

    im not sure about this, but wouldnt you want to set your variable p back to the start of the string and not at the very end of it?

    For question #3.... im lazy and someone already answered it :-P let me know how i did :-P
  • #1 - You have the right idea, now you just have to say what exactly the compiler could do about it, and what you have written isn't entirely correct.

    #2 - s++ modifies s, but s itself isn't const; it was declared "const char*", which is a (non-const) pointer to constant characters. The second thing you mentioned (setting p back to the start of the string) is correct, as mwoz pointed out in his comment.
  • Warren
    For #3, there's also a fair bit of sloppiness in checking variables for validity, making sure malloc returns a valid pointer, etc, but even assuming all that, Alexandrescu and Raymond Chen are still unhappy with you, because your caller doesn't know with what API/operator/incantation that dynamic memory was allocated...

  • For the memory part, are you talking about question #2? If so, it is an extremely valid point that we shouldn't forget, _ever_. If you create functions that are quasi-public, you should almost never be allocating memory for the caller (unless it is an explicit part of the API, e.g. malloc/calloc/realloc/etc.). I don't think that is what nvidia wanted as part of the answer, but it definitely crossed my mind. As to the Raymond Chen reference, I searched for a bit but couldn't find the article (it was recent, if I remember correctly) where he talked about how important it is to match up allocators/deallocators.


    Checking for a valid result from malloc is the last of the major problems, I believe. I may have missed some, so please feel free to point out any others that you find.

  • mwoz
    "Second, your initial while will have major issues. If you take any character less than ‘0? in the ascii range, that value - 0?0030 will be less than 10U. So your function would include, for example, most punctuation as a number. The same holds true for the other loop."
    Actually 10U forces the operation to be unsigned:
    "If either operand is of type unsigned int, the other operand is converted to type unsigned int." - MSDN C++ reference (http://msdn2.microsoft.com/en-us/library/09ka8b...)

  • mwoz:


    Quote the C++ or C standard if you want, but don't quote MSDN. It isn't the standard and has never been.


    You are correct and my initial criticism was not: primitives are casted towards unsigned-ness, not away from. In addition, according to the C standard (6.3.1.3.2):

    "Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value". This means that the cast would leave you with a number greater than 10, and therefore that part of your solution will work.


    Regardless, its rather unclear what you mean in the code - you are relying on an implicit (and probably unassumed, as in why it is one of the more prevalent warnings created with "g++ -Wall") cast to bring a number into a range that makes no sense conceptually, but happens to work technically. I'm probably not the only person who at least had to think about where the implicit cast was, and what effect it would have on the resulting statement.


    This style is consistent with your use of "(i << 3) + i + i", and using "0x0030" instead of (the character) '0'. All of these work technically, but are semantically (in reference to the problem) meaningless. In the same respect, I could have written (for the in-range check):


    while(*s / 0x10 > 2 && *s / 0x10 < 5 && *s % 0x10 < 0xa)


    Which will probably also work, but looks like it came out of my ass instead of my head. The point is still that you should write what you mean, not what you think looks cool. Remember that.

blog comments powered by Disqus