Interview Code Snippet


  • :belt_onion:

    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? :D

    Not as clever, but a lot more readable :)

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


  • :belt_onion:

    @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.

  • :belt_onion:

    @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? :D

    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? :D

    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 :P

    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).


  • :belt_onion:

    @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


     


  • :belt_onion:

    @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).



  • @Aaron said:

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

    True, I likely wouldn't have done an interview at 1am either though :P Make that:

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

    Plus as I said, that's not my recommended method, just what I think they must've expected if they had to run off to find someone to confirm the other method's validity :P



  • @fyjham said:

    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).

     

    Um, no.  First of all, interfaces can't even have static members (what would they do?).  Second, even if they could, Count wouldn't be one of them, since it clearly depends on the instance.

    IList.Count won't compile, IList<T>.Count won't compile, ICollection.Count won't compile, and ICollection<T>.Count won't compile.


  • :belt_onion:

    @Aaron said:

    Did you copy it wrong, or did they really give you an invalid method signature?

    <snip>

    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

    <snip>

    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.

    Nah, I just typed this from memory directly into the forum editor after a stressful interview. I always suck at writing code by hand. I'm constantly switching between languages so I can never remember the specifics of a language. In this case, the interview was in C# but for the last year I've been doing DTS packages *ugh* and a lot of scripting: batch, VBScript and even a bit of bash. And the purpose of me implementing this method was not having a nice library function but seeing if I would fall in the reference passed by value trap. In real life I would just have called the Reverse method on the list.



  • @bjolling said:

    and then I made the kind of mistakes somebody makes when seeing a 0-index based array for the first time. .

    Oh, blimey, you must have learned to code on VB.  You have my deepest sympathies.   I'll never say a cruel word about you again!

    @Edsger W.Dijkstra said:

    • It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.

     



  • Oh, I misread your complaint, thought you were saying an instance of IList<T> wouldn't have a Count property only one of List<T>. I honestly didn't even see that mistake when I read it, variable name being so similar to the class name I just read what I knew should be there. You know what, I'm gonna give up posting till I'm more awake :P



  • @bjolling said:

    Nah, I just typed this from memory directly into the forum editor after a stressful interview.
     

    Fair enough.  We'll chalk that one up to memory.


  • :belt_onion:

    @Aaron said:

    List<T> tempList = new List<T>(list); tempList.Reverse(); list.Clear(); list.AddRange(tempList);
    Except that the use of built-in List.Reverse( ) method was explicitely forbidden by the interviewers when I asked if I could use it.


  • :belt_onion:

    @DaveK said:

    @bjolling said:

    and then I made the kind of mistakes somebody makes when seeing a 0-index based array for the first time. .

    Oh, blimey, you must have learned to code on VB.  You have my deepest sympathies.   I'll never say a cruel word about you again!

    @Edsger W.Dijkstra said:

    • It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.

    I never knew ...

    My history: BASICA, GWBasic, QBasic, C++, VB3, VB6, VB.NET, C# ...

     



  • @icklemichael said:

    I don't do .net, but isn't an in place sort a really bad idea in general?
     

    You need to go find an algorithm's book and look up how Quicksort works. You perform sort in place because creating a copy of an array is expensive (requires more memory and copying of the whole array).



  • Now, maybe I am going crazy, but we are not talking about arrays here, we are talking about lists. If you think doing a quicksort on a linked list in place is a good idea then I think you need to get an algorithm's book.


  • :belt_onion:

    @icklemichael said:

    Now, maybe I am going crazy, but we are not talking about arrays here, we are talking about lists. If you think doing a quicksort on a linked list in place is a good idea then I think you need to get an algorithm's book.
    In the OP's case, the reverse algorithm is executed on the IList interface. Arrays in .NET for example implement the IList interface. Am I right that working in place on an IList is an acceptable implementation?



  • @icklemichael said:

    Now, maybe I am going crazy, but we are not talking about arrays here, we are talking about lists. If you think doing a quicksort on a linked list in place is a good idea then I think you need to get an algorithm's book.
     

    There is simple algorithm for sorting a linked list.

    http://www.openasthra.com/c-tidbits/sorting-a-linked-list-with-quicksort-simple-algorithm/ 

     

     

     



  • @Aaron said:

    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();

    But this won't propagate the new value back to the caller. I think. My .NET knowledge is stuck somewhere between 1.1 and 2.0.



  •  @Spectre said:

    @Aaron said:

    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();

    But this won't propagate the new value back to the caller. I think. My .NET knowledge is stuck somewhere between 1.1 and 2.0.

    Which is why I said write the statement in place as opposed to branching out to a pointless method.

    If you really had to abstract it that way (why?) then a ref parameter will do the trick.  There are times when that wouldn't be appropriate (i.e. the list is already a data source for a grid, or something), but the question gives no background so there's no sense in assuming.

    And with respect to this really weird side-discussion about sorting (who said anything about sorting?), generic lists have O(1) indexed access.  Why anyone would entertain, even for a minute, the possibility that they might be implemented as naive linked lists, is beyond my comprehension.  Linked lists are generally only useful for simple stacks and queues and sometimes deques.



  • @bjolling said:

    @DaveK said:

    @bjolling said:

    and then I made the kind of mistakes somebody makes when seeing a 0-index based array for the first time. .

    Oh, blimey, you must have learned to code on VB.  You have my deepest sympathies.   I'll never say a cruel word about you again!

    @Edsger W.Dijkstra said:

    • It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.

    I never knew ...

    The only WTF we learn from history is that nobody ever learns from the WTFs of history. 

    @bjolling said:

    My history: BASICA, GWBasic, QBasic, C++, VB3, VB6, VB.NET, C# ...

    I started with BASIC too, but I got over it.  Anyway, I had a good textbook to learn from:

    Donald Alcock's classic "Illustrating BASIC" 



  • @Aaron said:

    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();

     

    Isn't List.Reverse()'s return type void?  really,

    public void reverse<T>(IList<T> list){
         list.Reverse();
    }

    would work.



  • @vt_mruhlin said:

    Isn't List.Reverse()'s return type void?  really,

    public void reverse<T>(IList<T> list){
         list.Reverse();
    }

    would work.

    No it wouldn't, since the parameter is an IList<T>, not a List<T> :)



  • @Aaron said:

    @fyjham said:

    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).

     

    Um, no.  First of all, interfaces can't even have static members (what would they do?).  Second, even if they could, Count wouldn't be one of them, since it clearly depends on the instance.

    IList.Count won't compile, IList<T>.Count won't compile, ICollection.Count won't compile, and ICollection<T>.Count won't compile.

     

    A.  Don't be a dick

    B.  If you are going to be a dick, don't be wrong.

     Count is a property on ICollection<T>. Nobody every said anything about Count being static or calling it statically.  

    This code will compile:

    IList<int> list = getIList();

    int count = list.Count;



  • @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;
    }
    }
     @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;
    }
    }
    Yes it WILL throw an exception in the first line:

     

     
    • It should be "Count" not "Count()"
    • Also, it has to be "list.Count" not "IList.Count"

     


    Thats 2 WTFs in a single line...


  • @BlackMan890 said:

    @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;
    }
    }
     @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;
    }
    }
    Yes it WILL throw an exception in the first line:

     

     
    • It should be "Count" not "Count()"
    • Also, it has to be "list.Count" not "IList.Count"

     


    Thats 2 WTFs in a single line...

     

    it's not WTFs, it's 1 typo and one example of something not knowing the language and the standard libraries with the language.



  • @BlackMan890 said:


    Yes it WILL throw an exception in the first line:
    • It should be "Count" not "Count()"
    • Also, it has to be "list.Count" not "IList.Count"

     

    No, it won't throw an exception, it just won't compile :)

    Further, if it's C# 3.0, Count() will also work, since that's an extension method on IEnumerable<T>, which I'm sure IList<T> will implement...


  • :belt_onion:

    @BlackMan890 said:

    Yes it WILL throw an exception in the first line:
    • It should be "Count" not "Count()"
    • Also, it has to be "list.Count" not "IList.Count"

    Thats 2 WTFs in a single line...

    Don't worry, I know. The other 2 were just typo's when writing the OP. Or like tster puts it: not familiar enough with the language. Personally I'd say I'm not meticulous enough to write software without the help of an IDE.

    The reason I posted my story is that I tried to outsmart the interviewers by side-stepping the obvious gotcha's but made at least 3 glaring mistakes (I forgot dividing the count by 2, I chose the wrong type for the temporary variables and the loop throws an "out of bound" exception on the first loop.)

    The lesson to be learned is that humble programmers are better programmers. Personal pride and emotional involvement in your code produces WTF's.

     



  • The reason I started the weird side discussion about whether doing this in-place was sensible, is that in Java there is no guarantee of O(1) indexed access on the List interface, if you want that you need to find a list which also implements RandomAccess. So where I said 'I would be surprised in IList required O(1) read and update.', consider me surprised.


  • :belt_onion:

    @icklemichael said:

    The reason I started the weird side discussion about whether doing this in-place was sensible, is that in Java there is no guarantee of O(1) indexed access on the List interface, if you want that you need to find a list which also implements RandomAccess. So where I said 'I would be surprised in IList required O(1) read and update.', consider me surprised.

    Seeing that IList is just an interface, I suppose you could have implementations with fast random access and other ones without...

    The more I think about it and read the replies to this OP, the more this interview question feels hypothetical and completely detached from reality. Implementing a stand-alone Reverse function while taking an interface as parameter is the wrong choice here. Suppose you've have to work with some collections library for which you don't have access to the code, you'd derive from a concrete collection and create the optimal implementation for that specific concrete class.

    The interviewers wanted to see if they could confuse the interviewee with a generic function, generic collection interface, passing reference by value and so on. The only correct answer would have been: "if anyone on my team would try to do this, he would be number one on my code-review ToDo list.



  • @DaveK said:

    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.
    Except if T happens to be not a fundamental type, but instead a user-defined class that can't be stuffed in a register and that has a custom constructor and assignment operator.  I don't know how it is in C#, but in C++ if a function is in another compilation unit, the compiler must assume that it may have side effects and generate the call.  So this kind of optimizations do matter.

    As a side note, calling something a list immediately reminds me of a linked list, and the best way to reverse those is to just reverse the links.  With specially encoded links the reverse operation can even be done in constant time, no matter the lenght of the list, but that encoding places some other limitations on the use of the list. 



  • Yes, but how do you change the caller's pointer to the first item in the list to point to the new first item? If you are using a simple linked list where the caller has a pointer to the first item (and you can't change that pointer or return a different one) then you will have to copy the contents of the last item into the first item, then reverse all the other links.



  • @Qwerty said:

    Yes, but how do you change the caller's pointer to the first item in the list to point to the new first item? If you are using a simple linked list where the caller has a pointer to the first item (and you can't change that pointer or return a different one) then you will have to copy the contents of the last item into the first item, then reverse all the other links.

    That would be true for a C-like language and a simple implementation of linked lists.  In such cases, the obvious choice is to return the pointer to the new first element.  However, here we have an object-oriented language and the function is getting its input by reference, so it can modify the caller's data.  Whether or not the IList class exposes enoug data to swap the links is another matter, but a reverse function certainly should have access to that data.

    The ability to index the "list" hints towards an array though, so perhaps it is not a linked list after all. 



  • @tdb said:

    The ability to index the "list" hints towards an array though, so perhaps it is not a linked list after all. 

    the IList<T> interface extends ICollection<T> which is a general collection interface and adds random access methods to it. List<T> implements IList<T> and does it with arrays so random access is O(1). There is also a class called LinkedList<T> which only implements ICollection<T> but not IList<T> so it is not possible to use random access with it.

    This is the way it is done in .NET and it seems pretty reasonable to me. In Java you had one interface List<T> and ArrayList<T> and LinkedList<T> both implemented it; this can create all sorts of problems when methods that use random access accept the List<T> interface, but LinkedList<T> is passed in. The people who designed .NET probably thought that ArrayList was the list that would be used in most cases and linked lists only for special cases.



  • @SlyEcho said:

    @tdb said:

    The ability to index the "list" hints towards an array though, so perhaps it is not a linked list after all. 

    the IList<T> interface extends ICollection<T> which is a general collection interface and adds random access methods to it. List<T> implements IList<T> and does it with arrays so random access is O(1). There is also a class called LinkedList<T> which only implements ICollection<T> but not IList<T> so it is not possible to use random access with it.

    This is the way it is done in .NET and it seems pretty reasonable to me. In Java you had one interface List<T> and ArrayList<T> and LinkedList<T> both implemented it; this can create all sorts of problems when methods that use random access accept the List<T> interface, but LinkedList<T> is passed in. The people who designed .NET probably thought that ArrayList was the list that would be used in most cases and linked lists only for special cases.

    Reasonable design, yes.  In a few cases I'd have liked to have a base class (std::container<T> or such) for containers in the C++ stdlib.  However, I'd have put a bit more thought to the naming to avoid confusion.


  • @vt_mruhlin said:

    Isn't List.Reverse()'s return type void?  really,

     

    Yes, but I explicitly mentioned .NET 3.5 and was therefore referring to the IEnumerable.Reverse() extension method.  As another person pointed out, your parameter is an IList<T>, not a List<T>, so you don't have access to List<T>.Reverse.  You also fail the interview. ;)


Log in to reply