The sixth of the series of programming job interview challenge is out. Other then commenting the solution, I remind you that you can post the solution on your blog and get a link next week!

Here is the solution to the previous challenge:
Two-way merge sort (External Sorting) : The idea is breaking the big file into subfiles, sorting them and than merging them back together. In the first pass read one page at a time, the records in the page are sorted (quicksort for example) and the page is written back to disk. in subsequent passes, each pair of sorted output from the previous pass are read and merged to produce sorted subfile twice as long:

1. Read each page, Sort it, Write it back
2. while more than one sorted subfile:
while subfiles from previous pass left to merge:
– Choose next two subfiles from previous pass
– Read each subfile into a memory page (one page at a time)
– Merge the subfiles (remember each of them is already sorted), write output to a memory page
– Write output page to disk when needed.

Note that 3 pages are enough to run this algorithm. (do you see why?)

Heiko Hatzfeld provided a nice solution in his blog including c# implementation, notice you used 4 pages in the MergeSort stage, you could write one output file each time it is full.

Martin Ankerl also provided few correct and simple solutions, I liked his simple post.

From the commenters:

Kirill Sorokin, Jonathan Gilbert, Jonas Christensen, Heiko Hatzfeld, Tim C, Chris Jobson, and Sh4DoW provided a full and correct answer.

Amgel, Edward Shen,  Per, Kris Warkentin answered merge sort but didn’t provide the full algorithm.

Alex, Your solution will produce the correct answer, however it is much less efficient in terms of IO access. since you don’t know if values are uniformly spread across the file you might end up with some very small temp files and some very large once, and might cause lots of reduced disk accesses.

Mark Bradshaw provided a bubble sort variation, a bit less efficient than merge sort.

Poul Foged Nielsen the simple bubble sort would be very inefficient.

And now let’s head on to this week’s question:

Look at the following Code segment written in C#:

   1: ArrayList a = new ArrayList();
   2: ArrayList b = new ArrayList();
   3:
   4: a.Add(1);
   5: b.Add(1);
   6: a.Add(2);
   7: b.Add(2.0);
   8:
   9: Console.WriteLine((a[0] == b[0]));
  10: Console.WriteLine((a[1] == b[1]));

What will be typed into the console? And WHY? Hopefully you will “play fair” and  won’t type it in Visual Studio to see the output, you are in a job interview after all…

But the main issue of the question is the why.

The answer in now published in the 7th question in the series.

Good Luck!

Tags :

41 Responses to “A Programming Job Interview Challenge #6 – C# Games”


  1. Kirill Sorokin

    Said on June 2, 2008 :

    I don’t know about C#, but in Java 5.0 (and beyond, where auto-boxing is enabled), the output would be “true” and then “false”.

    Why? As the numeric primitives are added to the array list, they are auto-boxed to objects. So we have a = {new Integer(1), new Integer(2)} and b = {new Integer(1), new Double(2.0)}.

    Then, when we compare a[0] and b[0], we’re comparing two integer objects created via autoboxing. It turns out that == will return true, as for integers < 127 auto-boxed objects are cached, so in fact both a and b contain the same object instance.

    When comparing a[1] and b[1] we’re applying == to two different objects, and thus it will return false.

  2. leppie

    Said on June 2, 2008 :

    As expected both times it prints False.

    Reason: == defined on type object translates to ReferenceEquals. As every value type gets boxed, the reference will never be equal.

    Using Equals instead will make the 1st comparison True. The second remains False as the double is not automatically converted to an int or vice versa.

    IMO, using Equals instead of == would have been a better test.

  3. Heiko Hatzfeld

    Said on June 2, 2008 :

    I think the output should be false/false.

    The reason for this is the Arraylists are storing objects, and not value types. So a comparison invoked on the elements will allways be an object comparison. And since you are comparing pointer then, the results wont match.

    To avoid this you could use a generic list, that holds int/double (for a/b). Since the result of the generic List will return a value type. the comparison will be correct, and the result would be what you expect.

    Another option is to cast the stored object, prior to compaing it.

    Also nitpicking about the comment… We are allowed to use up to 10 pages, and the question was not to implement “the most memory efficient algorithem”, but one that fits within the given bounds. And opening and closing file handels is more liklely to have a bad effect on such a constrained system ;)

  4. Jason Kikel

    Said on June 2, 2008 :

    output:
    false
    false

    explanation:
    An ArrayList is a collection of System.Object. By default, System.Object.Equals only supports reference equality. This means ob1 == ob2 only if ob1 and ob2 both reference the same System.Object instance. In the above case, the arrays are populated with literal (value type) values which get boxed individually into different System.Objects and thus return false on equality tests.

  5. Damian Brady

    Said on June 2, 2008 :

    Hey,

    Nice test! – brings together a couple of important under-the-cover behaviours that .Net developers often don’t think about.

    I’ll leave my answer out of this comment so as not to ruin it for others, but see my site if you want my response.

  6. configurator

    Said on June 2, 2008 :

    false
    false

    The second answer is quite obvious: an object boxing an int will not equal to be an object boxing a float.

    But why is the first one false?

    Well, let’s see what happens here.
    a[0] is an object boxing an int. That means it is a reference to some memory location holding the value 1.
    b[0] is also an object boxing an int. But it’s a different object
    i.e. if we did
    object one = 1;
    a.Add(one);
    b.Add(one);
    a[0] == b[0] would return true.
    But we didn’t do that, we created two different object. And when we compare two objects, the comparison is (object == object) and not (int == int), causing it to be a reference comparison, returning a false answer.

  7. Jonathan Gilbert

    Said on June 2, 2008 :

    I would expect it to output “false” twice, as the ArrayList class returns System.Object references, and ‘==’ on System.Objects is a reference comparison. In this particular case, the objects are boxed ints and one boxed double, but System.Object’s operator== has no way of knowing that.

  8. Justin

    Said on June 2, 2008 :

    Just guessing here, I haven’t written C# for a couple of years but immediately I would say

    false
    false

    since the boxing of the primitives creates a new object every time and the output statement provides no inference as to what the contained types are and therefore the == operator is comparing objects which are all different.

  9. Ivan

    Said on June 2, 2008 :

    It will be typed
    false
    false

    because the comparison operator compares the references of boxed value types.

    If we instead write:

    9: Console.WriteLine((a[0].Equals(b[0])));
    10: Console.WriteLine((a[1].Equals(b[1])));

    the result will be:
    true
    false

    because in that case we are using the int overrided Equals method

  10. Alex

    Said on June 2, 2008 :

    Isn’t this an awfully language-specific question?

    It’s hard not to copy/paste code in… but I’m going with
    ——
    True
    False
    ——

    even though a direct comparison of (2 == 2.0) returns true.

    The “WHY” of it is that the integers are being abstracted into objects as soon as they’re added to the ArrayList. When comparing objects, obj.equals(obj2) is the way to determine if the two objects are logically equal. Using == just determines if the two variables are pulling from the same place in memory. a[0]==b[0] is going to return true, because each is referring to the constant “1”. a[1]==b[1] is going to return false, because since a[1] is an int and b[1] is a float, they can’t be referred to using the same reference address in memory. Since those don’t match up, it returns false, regardless of the actual values of a[1] and b[1].
    An easy way to test this theory would be using Generics, which are usable in .NET 2.0 and forward.
    —Code—
    List a = new List();
    List b = new List();

    a.Add(1);
    b.Add(1.0);
    a.Add(2);
    b.Add(2.0);
    ———-
    If I’m right and it’s a matter of the arraylist abstracting the numbers into vague objects, than this should return:
    —-
    True
    True
    —-

    Just checked. It did. Hooray!

  11. Kris Warkentin

    Said on June 2, 2008 :

    I’m assuming you will see something like:

    true
    false

    The why is complex and related to the IEEE implementation of floating point numbers. I often refer people to http://www.physics.ohio-state.edu/~dws/grouplinks/floating_point_math.pdf which explains the very complex subject of representing floating point numbers in computer hardware. The short answer is that in general 2.0 != 2 but rather something like 1.9999999999 or 2.00000000001 and there isn’t a valid way to compare the floating point and integer versions.

    The best understanding I had was that the decimal portion of the floating point is also represented in base 2 notation which means that not all numbers can be represented exactly in that format.

    My grasp of the whole subject is pretty limited though. It has always seemed strange to me that there wouldn’t be some sort of implicit cast one way or another that would give the ‘intuitively’ correct answer. I have a feeling the answer to this question may be implementation dependent too. The C# aspect may be important. I’m not sure if C will do it one way, the CLR or a JVM a different.

    Looking forward to see if any replies have a better explanation.

    cheers,

    Kris

  12. Justin - Web Development Blog

    Said on June 2, 2008 :

    My gut instinct on this is the output will be “TrueFalse”.

    Without testing this I dont’t know for sure but because 2 is an integer and 2.0 is a float or deciaml my guess is that even though they are both stored as objects in the ArrayList they are still different when compared.

  13. Justin - Web Development Blog

    Said on June 2, 2008 :

    Well, I am wrong. It is FalseFalse. I ran a test through VS. So because they are stored as objects each item in each ArrayList is different until it is cast to a specific type.

    The only way array list items would eb the same without casting is like a.Add(1); b.Add(a[0]);

    A comparision of a[0] == b[0] would be true because a[0] was copied into b[0].

    Thanks for the great questions. This is making me look harder into the details.

  14. Tobi

    Said on June 2, 2008 :

    The output:
    False
    False

    This is the case because the reference are not the same (that’s what matters, because a[x] and b[x] return object).

    The “expected” result would require:
    Console.WriteLine((a[0].Equals(b[0])));
    Console.WriteLine((a[1].Equals(b[1])));
    And would result in:
    True
    False

  15. Jon von Gillern

    Said on June 2, 2008 :

    Both will be false because both all of the value types are boxed when they’re placed inside the array list.

  16. Jonas Christensen

    Said on June 2, 2008 :

    An Arraylist holds objects so you check if it points to the same object and not the content of the objects.

  17. Ryan Emerle

    Said on June 2, 2008 :

    The output would be:
    false
    false

    The reason is:
    The values passed to the Add method are boxed into objects and, by default, the operator == tests for reference equality which will only return true if the two variables are pointing to the same object.

  18. Damian

    Said on June 2, 2008 :

    False
    False

    Reason: the Add methods takes an object, a reference type and the the numbers are value types, so they are boxed (converted to reference types) before being passed into the Add method. As they are differenct objects, the equality operator will return false.

  19. Shahriar

    Said on June 2, 2008 :

    Hi Dear

    please look at this code:
    ArrayList a = new ArrayList();
    ArrayList b = new ArrayList();
    a.Add(1);
    b.Add(1);
    a.Add(2);
    b.Add(2.0);
    Console.WriteLine(string.Format(“The Type of a[1] => {0}”, a[1].GetType()));
    Console.WriteLine(string.Format(“The Type of b[1] => {0}”,b[1].GetType()));
    Console.WriteLine(string.Format(“a[0]==b[0] => {0}”,a[0]==b[0]));
    Console.WriteLine(string.Format(“a[1]==b[1] => {0}”, a[1] == b[1]));
    Console.WriteLine(string.Format(“(int)a[0]==(int)b[0] => {0}”, (int)a[0] == (int)b[0]));
    Console.WriteLine(string.Format(“(int)a[1]==(double)b[1] => {0}”, (int)a[1]==(double)b[1]));
    Console.WriteLine(string.Format(“a[0].Equals(b[0]) => {0}”, a[0].Equals(b[0])));
    Console.WriteLine(string.Format(“a[1].Equals(b[1]) => {0}”, a[1].Equals(b[1])));

    I feeling .net framework just when you try to compare two decimal by Equals Method compare correctly , such as:

    object v = 12.0;
    Console.WriteLine(double.Equals(v,12.0));
    equal to:
    decimal v=12.0;
    Console.WriteLine(double.Equals(v,12.0));

  20. Jamie Penney

    Said on June 2, 2008 :

    false
    false

    Autoboxing occurs when you put the numbers into the ArrayList. Since a[x] and b[x] return Objects, they are compared using reference equality(==), and since the numbers are autoboxed they are different objects. Thus both of the comparasons are false as all 4 numbers are different objects in memory.

  21. Alex Shenoy

    Said on June 3, 2008 :

    If I am correct, the response in the console will be

    True
    False

    The first will check the value of 1==1. However 2 == 2.0 is not true b/c 2 is an integer and 2.0 is a float.

  22. ecco

    Said on June 3, 2008 :

    false in both cases

    why:
    is it comparing 2 addresses rather then values which compare method offers when using collections?

  23. Rob R

    Said on June 3, 2008 :

    Firstly, unless you include System.Collections that won’t even compile. But regardless, an ArrayList stores Objects. You are comparing POINTERS with a equality operator. Both will be false.

    For a more clever question, what would the following code return (and why):

    1: ArrayList a = new ArrayList();
    2: ArrayList b = new ArrayList();
    3:
    4: a.Add(1);
    5: b.Add(1);
    6: a.Add(2);
    7: b.Add(2.0);
    8:
    9: Console.WriteLine((a[0].Equals(b[0])));
    10: Console.WriteLine((a[1].Equals(b[1])));

  24. Mark Bradshaw

    Said on June 3, 2008 :

    I’m not entirely sure. From the hip I’d guess that both will equate to true, assuming that the second equality comparison will end up converting the float into an int.

  25. fred

    Said on June 3, 2008 :

    Both answers would be “false”.

    Reason: autoboxing

  26. Dan

    Said on June 3, 2008 :

    true and true, you used the “==” operator which does not test variable type. If it was a[1] === b[1], it would return false because of the type difference (a[1] is int, b[1] is float (or double).

  27. AdamC

    Said on June 3, 2008 :

    All false because identity != equality, we’re dealing with ref types here (implicit boxing).

  28. Rickyah

    Said on June 3, 2008 :

    In this entry I try to answer this’s week challenge:

    http://crazypointer.blogspot.com/2008/06/programming-job-interview-challenge-6.html

    My blog is in spanish, but the answers to the challenges are written in
    english.

    Best Regards!

  29. sood

    Said on June 3, 2008 :

    I tried the similar kindda code in java. I have to say that I used eclipse to cross check my answer before submitting, and one of my answer was incorrect(earlier :) ), but I was thinking on the right lines..

    I am not sure about how c++ works but considering that it is also an OO language the working should be similar to java.

    So when you create two new array lists and add 1 to them and compare the result is true. I guess this is because as arraylists take up only objects hence when primitive type 1 is added it is automattically boxed to an integer object before adding it to the list. ans reference to the same object is used when adding to the second list hence the first expression evaluates to true. But if u use new Integer(1) while adding to the list the expression will fail.

    Regarding the second expression m definite that it should be false. But all I am worried about it is how the == operator is making a comparison b/w an int object and a double object. Does it type cast one to another before making the comparison.

    Also one more thing that i noticed is how the .toArray method works for a list having objects of diff types….

    I hope I have not written too much of idioti stuff bcoz I am self taught JAVA person, so no wonder if my understanding of certain concepts is incorrect

  30. kuldip saini

    Said on June 3, 2008 :

    It will be
    false
    false

    while adding element to arralist will cause boxing which will result in different references for every value type.

  31. D.L

    Said on June 3, 2008 :

    false
    false

    because ArrayList is a ref type( located in the heap)

    the comparison is made by comparing two different places in memory (whice be in both cases false).

  32. Jelle Hissink

    Said on June 3, 2008 :

    It will return:
    False
    False
    Because the comparison will be preformed on the object (boxed values) and thus it will compare the references of those.

    Regards,
    Jelle

  33. AJ

    Said on June 3, 2008 :

    true
    false

    as arraylist will store 2 as int whereas 2.0 as float, hope i am thinking in right direction.

  34. Xerxes

    Said on June 3, 2008 :

    Without cheating – they will both return false, because the ArrayList boxes all items to the loose “object” type.

    Upon reference to a[0] and b[0], there is no type conversion to compare ints, so the object comparison returns false because they are different object references. Same goes for a[1] and b[1].

  35. Greg

    Said on June 3, 2008 :

    The results would be false false.

    The reason is an array list is an object array. Therefore, the value types would be boxed and added to the array. Each object in the array will have it’s own pointer; therefore, == will be evaluating the reference not the value.

  36. Chris

    Said on June 4, 2008 :

    ArrayList?! Who still uses ArrayLists? That’s so .NET 1.1!

  37. NMasao

    Said on June 5, 2008 :

    from VB view
    line 9 output – true ( both are integers)
    line 10 output – false ( integer double)

  38. pb

    Said on June 7, 2008 :

    Arraylist takes objects so comparison will be reference comparison, so two falses

3 Trackback(s)

  1. Jun 2, 2008: Damian Brady’s Blog » Programming Test
  2. Jun 6, 2008: ArrayList item comparison « Some Creativity
  3. Mar 14, 2009: C++ Tip: How To Get Array Length | Dev102.com

Post a Comment