Interview Code Snippet



  • During an interview at a potential new client, I got interviewed by two members of their Quality department. They basically follow a script with questions and answers and try to see how far you can navigate their question tree. (That was my impression of their process). The first question was to write a function to reverse elements in a IList. They gave me this declaration in C#

    //For input 4, 8, 2, 6 the expected ouput is 6, 2, 8, 4
    static void reverse(IList<T> list)

    You'll notice that the return type is void so I could quickly see what pittfalls they were testing for so without thinking too long about other things, I handed in this "solution". I explained it as follows: "I loop from the first element until half-way through the list while swapping the first element with the last, the second element with the second to last, the third element with the third to last, and so on.."

    static void reverse(IList<T> list) {
    int count = IList.count();
    for(int i = 0; i < count; i++) {
    int left = list[i];
    int right = list[count-i];

    list[i] = right;
    list[count-i] = left;
    }
    }


    Their eyes glazed over and they couldn't figure out what I was trying to achieve. I was a bit smug about myself thinking I gave them a really clever solution that they didn't expect.

    Stop reading here and start commenting the code if you want to be smug at my expense 🙂

    Eventually they had to call in their .NET guru to understand the code. He just remarked: "this code will throw an exception on your first execution of the loop and btw I can't see in your code where you would loop just until the middle of the list."

    I reviewed the code and immediately spotted several errors but I didn't see why there would be an exception. So I handed in this corrected version:

    static void reverse(IList<T> list) {
    int count = IList.count();
    for(int i = 0; i < count/2; i++) {
    T left = list[i];
    T right = list[count-i];

    list[i] = right;
    list[count-i] = left;
    }
    }


    The .NET guru then explained that [count-i] would be an overflow and should've been [count-1-i]. So as an alternative to 0-based and 1-based indexes, I have discovered the hybrid version!

     



  • And? Did they hire you?



  • Wouldn't it have been easier if you had created a temporary list (List<int> temporaryList = new List<int>(list).Reverse() ), cleared the original list and copied the elements back? 😃

    Not as clever, but a lot more readable 🙂

    Edit: This is assuming that performance is not a huge issue, of course



  • @Shinhan said:

    And? Did they hire you?

    They would get back to me early next week. After the interview, I had a casual chat with the  .NET guru and he was interested in knowing a bit more on my background. He told me that the interview wasn't too bad and that he appreciated that I knew how things work behind the scenes. I hope he is the type of guy that doesn't give praise too easily.



  • @M-bird said:

    Wouldn't it have been easier if you had created a temporary list (List temporaryList = new List(list).Reverse() ), cleared the original list and copied the elements back? 😃

    Not as clever, but a lot more readable 🙂

    Edit: This is assuming that performance is not a huge issue, of course

    Yup, that was the solution for the pittfall they were going for: how to get the locally created reversed list out of the scope of the function. I circumvented it by swapping the elements directly in the original list and felt really clever about it. That's why I think the two Quality people weren't able to assess my solution - I didn't solve their expected problem because I didn't have that problem.

    It was forbidden to use built-in reverse function as they wanted to test my ability to build the reverse algorithm.



  • I don't do .net, but isn't an in place sort a really bad idea in general? I would be surprised in IList required O(1) read and update.



  • @bjolling said:

    static void reverse(IList<T> list) {
    int count = IList.count();
    for(int i = 0; i < count; i++) {
    int left = list[i];
    int right = list[count-i];

    list[i] = right;
    list[count-i] = left;
    }
    }


    Their eyes glazed over and they couldn't figure out what I was trying to achieve. I was a bit smug about myself thinking I gave them a really clever solution that they didn't expect.

    Stop reading here and start commenting the code if you want to be smug at my expense 🙂

    Well, no.  At this point I thought you were just trolling them. 

    @bjolling said:
    static void reverse(IList<T> list) {
    int count = IList.count();
    for(int i = 0; i < count/2; i++) {
    T left = list[i];
    T right = list[count-i];

    list[i] = right;
    list[count-i] = left;
    }
    }


    The .NET guru then explained that [count-i] would be an overflow and should've been [count-1-i]. So as an alternative to 0-based and 1-based indexes, I have discovered the hybrid version!

    Now I'm not so sure that you were trolling.

    If the index is 0-based, as your code appears to assume by starting i at 0 and immediately using it to index list[...], then the maximum element is indeed at [count - 1], and your code is wrong because it accesses list[count - 0] the first time round the loop.  If the index is 1-based, you're in trouble even earlier.

    You haven't, however, invented a 'hybrid 0/1-based index'.  You've just rediscovered the plain old bog-standard off-by-one error. 

    Also, I don't speak C#, so can somebody explain to me whether "IList<T> list[...]" is passed by reference or value in this situation?



  • @bjolling said:

    @M-bird said:

    Wouldn't it have been easier if you had created a temporary list (List temporaryList = new List(list).Reverse() ), cleared the original list and copied the elements back? 😃

    Yup, that was the solution for the pittfall they were going for: how to get the locally created reversed list out of the scope of the function. I circumvented it by swapping the elements directly in the original list and felt really clever about it.

    Ah, I should have continued reading.  I'm now going to take a guess: list[..] is a reference, passed by value?



  • Yeah, reference passed by value. Btw you can simplify the middle to:

      T temp = list[i];
    list[i] = list[count-i-1];
    list[count-i-1] = tmp;

    Of course, if you really wanted to confuse the interviewer you could always implement an IComparer to flip it 😛

    I suspect though they were expecting would've been the simple version like:

    static void reverse(IList<T> list) {
    IList<T> tmp = new IList<T>(list);
    for(int i = 0; i < list.Count; i++) list[i] = tmp[tmp.Count - i - 1];
    }

    (Far more wasteful of RAM though :P)



  • @fyjham said:

    (Far more wasteful of RAM though :P)

    RAM and CPU, I would have thought.  That's what we call really falling in the wrong quadrant of the time-memory trade-off graph.

    Why would anyone ever not reverse an array in place?  (Well, assuming they wanted the original reversed in the first place, rather than just a reversed copy).



  • actual working version:

    static void reverse<T>(IList<T> list)
    {
        for (int i = 0; i < list.Count / 2; i++)
        {
            T temp = list[i];
            list[i] = list[list.Count - i - 1];
            list[list.Count - i - 1] = temp;
        }
    }



  • Oh, BTW:
    @fyjham said:

    Yeah, reference passed by value. Btw you can simplify the middle to:

      T temp = list[i];
    list[i] = list[count-i-1];
    list[count-i-1] = tmp;
    That's the kind of simplification you should leave to the compiler.  Bear in mind that in either way of doing it, only list[x] itself is ever in memory, the rest are temporaries that the compiler will allot to registers.  Odds are you'd get the exact same assembly code generated.



  • RAM and CPU, I would have thought. That's what we call really falling in the wrong quadrant of the time-memory trade-off graph.

    From a code performance perspective: yes.

    From a maintenance perspective: Only if time/memory usage is an issue. If not, I would always choose the copying solution, though, since that's readily readable for just about anyone.

    It's a shame that the Reverse()-function is not available or I would replace the for (int i...)-loop with a foreach (...) { list.Add(...); }, though: no chance of off-by-one errors ( or just call list.Reverse() and leave it at that, of course :D).



  • @SlyEcho said:

    actual working version:

    static void reverse<T>(IList<T> list)
    {
        for (int i = 0; i < list.Count / 2; i++)
        {
            T temp = list[i];
            list[i] = list[list.Count - i - 1];
            list[list.Count - i - 1] = temp;
        }
    }

    I wanted my code to clearly show the algorithm so I deliberately split everything over more steps than I would in real production code. In the end your code is more or less the code I presented in the next step but I didn't want to make the post longer than it already was.

    The .NET guru also wanted me to add a test for null on the list object, but I preferred an assert as it was a private function and not something exposed to other libraries. I suppose this is debatable.

    Someone mentioned O(1). I was wondering what would be the big-O for SlyEcho's version? I've always been quite good at writing fast algorithms but I was very bad at proving it. At university, the exam questions were like:

    • Q1.a: write an algorithm to ...
    • Q1.b: what is its big O
    ... I never got the ".b" questions exactly right


     



  • @DaveK said:

    Now I'm not so sure that you were trolling.

    If the index is 0-based, as your code appears to assume by starting i at 0 and immediately using it to index list[...], then the maximum element is indeed at [count - 1], and your code is wrong because it accesses list[count - 0] the first time round the loop.  If the index is 1-based, you're in trouble even earlier.

    I wasn't trolling but I made the mistake of trying to outsmart the interviewers, like "You fools! The traps you mere mortals have laid for me are way to obvious to worry somebody with MY kind of knowledge!" and then I made the kind of mistakes somebody makes when seeing a 0-index based array for the first time. That'll teach me to stay humble. The "hybrid" thing is just me trying to be funny and laughing with my own mistakes

    If anyone wonders what is the WTF of this story and I why I felt it appropriate for the sidebar: TRWTF was me.



  • The complexity of the algorithm depends entirely on the implementation of the list, if it is basically an array then it is O(n), if it is basically a linked list then it is O(n^2).

    Copy to array, reverse, copy, is always O(n), although if the original supports random access then you're actually going to be slower. 🙂



  • @DaveK said:

    RAM and CPU, I would have thought.  That's what we call really falling in the wrong quadrant of the time-memory trade-off graph.

    Yeah, I just mean if an inline copy confused them they likely expected that approach. Not that I'd implement it that way.

    @DaveK said:

    That's the kind of simplification you should leave to the compiler. 
    Bear in mind that in either way of doing it, only list[x] itself is
    ever in memory, the rest are temporaries that the compiler will allot
    to registers.  Odds are you'd get the exact same assembly code
    generated.

    I know they'd compile to the same thing, I said simplified not optimied. It's just shorter and imo more readable because it's more akin to the standard approach for swapping variables. If you find the former more readable... each to their own I guess. (If I'd started playing around with XOR to try to swap them in place I'd agree with your point that it's just convoluting it for no reason - not sure if you can get a C# object reference as a numeric reference to XOR against though... never tried which is probably a good thing :P)



  • @bjolling said:

    //For input 4, 8, 2, 6 the expected ouput is 6, 2, 8, 4
    static void reverse(IList<T> list)

     

    Did you copy it wrong, or did they really give you an invalid method signature?  When writing generic methods, the generic parameters need to be added to the method name as well as the parameter.  In other words:

    static void Reverse<T>(IList<T> list)

    (I also took the liberty of correcting their capitalization problem)

    I guess one exception is if this method is a member of a generic Class<T> (the same T), but I can't think of any situation where it would make sense to have a static method like that.  Mind you, I can't think of any realistic situation where you'd need a mutable reverse method and not be using a List<T>, which already has a Reverse method, or some sort of wrapper, which should just expose a Reverse method that calls the underlying List<T>.Reverse method.

    Yes, I realize I'm being pedantic here, and that it's just an interview question. There's nothing wrong with asking someone to write code to reverse a list.  It's the fact that they abstracted it into a method signature that bothers me because it implies that the method has a reason to exist.  Just say "write me a code snippet that reverses the elements of a generic list".  The code can be inline.  If they want to write it as a method, that's fine too, but a full method should probably be doing things like null checks.

    Also, the first line in your "corrected" version is still wrong, it's not just the index issue.  Count is a property, not a method, and it's a property of the "list" instance, not the IList interface.  Are you coming from a Java background perhaps?  Either way, no offense, but it's hard to imagine a more poorly-executed solution.



  • @fyjham said:

    I suspect though they were expecting would've been the simple version like:

    static void reverse(IList<T> list) {
    IList<T> tmp = new IList<T>(list);
    for(int i = 0; i < list.Count; i++) list[i] = tmp[tmp.Count - i - 1];
    }

     

    IList<T> is an interface.  You can't create an instance directly.  I'd have kicked you out of the interview for that.

    The wasteful method you are probably thinking of is:

    List<T> tempList = new List<T>(list);
    tempList.Reverse();
    list.Clear();
    list.AddRange(tempList);

    Or better yet, with .NET 3.5 (I refuse to go back to 2.0), you could avoid the whole method altogether and just write in place:

    list = list.Reverse().ToList();

    Which I would almost always do unless I knew it had the potential to be a really huge list and that performance could actually be an issue.



  • @Aaron said:

    Also, the first line in your "corrected" version is still wrong, it's not just the index issue.  Count is a property, not a method, and it's a property of the "list" instance, not the IList interface.  Are you coming from a Java background perhaps?  Either way, no offense, but it's hard to imagine a more poorly-executed solution.

    That's a bit harsh... and also incorrect. Count is indeed a property, true, but it's part of the ICollection interface which IList implements, so calling it is perfectly fine on an IList object (So long as it's called like a property).


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.