Necessary and Sufficient

Q1: Does C# allow classes to have multiple inheritance?

C# allows you to to have multiple interface inheritance, but it does NOT allow you to have multiple implementation inheritance like C++. Get over it - this design decision actually makes things easier most of the time.

Q2: Can you add static methods to an interface?  

NO. Although other languages like PHP have this (Late Static Binding), in C# the designers stuck with the OOP principle that interfaces define behaviour of instances - that is they define a contract but not the implementation, hence static methods should be excluded. Java also prevents this. From a technical standpoint it is certainly possible for both Java and C# to add this feature but I suspect the respective language designers would need to be convinced before that happens.

Q3: Can you add operator overload definitions to an interface?

NO because operator overload definitions are static methods and static methods are not allowed in interfaces.

Q4: Can you add accessibility modifiers to interface members?  

NO. The point of an interface is to describe a contract between an implementing type and users of the interface. Outside callers aren't going to care and shouldn't have to care about implementation. If an interface is public then every part of that contract has to be public, otherwise it would mean one thing to friend/internal classes and a different thing to everything else. If you need default implementation then it's best to use an abstract class.

Q5: What's the difference between explicitly and implicitly implemented interfaces?

Unlike C++, in C# we can implement an interface implicitly as well as explicitly. Explicitly implemented interfaces are only available when the instance is cast to that interface. In contrast, implicit interfaces are available via the instance and via a cast of the instance to the interface in question. Explicit interfaces also help skirt the classic diamond problem associated with multiple inheritance and they are allowed to be private if necessary, but they cannot be virtual or abstract. Implicitly implemented interface member functions can be virtual or abstract, but they have to be public.

Q6: Can you define a default, parameterless constructor for a struct? 

NO. Structs provides value-type semantics, while classes provide reference-type semantics. So for efficiency in creating a struct, the rule adopted by the C# team was "the default value for any type can't rely on any initialization". Instead, the C# team resorted to the same trick they use to default value and reference types - doing a bitwise zeroing of the storage location. This results in 0 being assigned to value types used in structs and you can't do anything in the default constructor to change this since you're prevented from creating one.

Q7: Can structs implement interfaces?

Yes they can, but beware - when you cast a struct to an interface it implements you are implicitly boxing the struct since the interface reference is a reference type. This can lead to subtle issues in code as can be seen here.

Q8: Can structs be sub-classed?

NO they are implicitly sealed.

Q9: What sort of static constructors are you allowed to define on non-static classes?

Only a parameterless one - with the same name as the class obviously. Why? Well, a static constructor is run once per type, rather than once per instance, and it is guaranteed to run before any instances of the class are created, before any other static methods are accessed, but after static field initialization occurs although we don't know exactly when it runs - that part is non-deterministic. Since we don't explicitly call the constructor there is no way for the programmer to pass in parameters which is why the compiler ensures you don't waste your time writing static constructors that take parameters.

Q10: Can static constructors of non-static classes be called explicitly?

NO. They are only ever called implicitly by the runtime, and the timing of these calls is non-deterministic.

Q11: Can static classes be sub-classed?

NO. Static classes are implicitly sealed.

Q12: What is meant by the statement "References in C# are polymorphic"?

It means that a reference to a base class can point to an instance of a sub-class. That allows the developer to have methods parameters defined as the base type which accept any sub-class of that base type! Extremely handy.

Q13: Why is calling virtual-methods in a constructor a bad thing?

Consider the case where you have a base class and a derived class and the constructor of the base class calls into a virtual method which is defined in the base class but also overridden by the derived class. In C++, the base class is guaranteed to be created before the derived class so when the constructor of the base class is run it sees the most derived function as the one it has defined. In C# the base class constructor will also run before the constructor of the derived class but calls to virtual methods are always passed to the most derived version which will be the overridden function in the derived class. The problem with this is that the derived class has not been fully initialized at this point and it's constructor hasn't even been run. This is because initializers run in the opposite order as constructors. The fact that the derived class running the virtual override is not fully initialized leads to subtle side-effects that confuse the hell out of people and eventually breaks code. For these reasons it's good practice to avoid calling virtual methods from constructors, unless the class is sealed. IMHO this is one behavior where C++ is more intuitive than C#.

Q14: Is an overridden class member virtual? 

YES. If B is a sub-class of A and overrides a virtual function in A, the function can be overridden again by C, a sub-class of B. This pattern exists unless you use "override sealed" which is equivalent to the "final" keyword in Java - it prevents further overriding thus ending the virtual chain for that specific method.

Q15: Are instance members virtual or non-virtual by default in C#?

Non-virtual. Interestingly, unlike C# which requires the virtual keyword, instance methods in Java are virtual by default. C# went against this for performance and versioning reasons. They figured Java developers often forget to use the final keyword.

Q16: Can you declare a virtual static method in C#? 

NO. Makes no sense. To quote Eric Lippet... the core design principle of static methods, the principle that gives them their name, states that static methods can always be determined exactly, at compile time, what method will be called. That is, the method can be resolved solely by static analysis of the code. Virtual is the exact opposite - the virtual keyword tells the compiler that the method to be called will be determined at run time and based on run time type information.

Q17: Can you have abstract static methods in C#?

No. Abstract methods are implicitly virtual so the same argument applies as given above. See Section 10.6.6 in the C# spec... "When an instance method declaration includes an abstract modifier, that method is said to be an abstract method. Although an abstract method is implicitly also a virtual method, it cannot have the modifier virtual."

Q18: Does the "protected internal" access modifer mean OR or AND?

protected **OR** internal. Not both.

Q19: Can you override static methods in sub-classes?

No - in both Java and C#. It makes no sense to have virtual and overridden static methods.

Q20: Can abstract and virtual methods of a class be marked as private?

No because it makes no sense. The purpose of virtual and abstract methods is to permit/force a derived class to override the base functionality. Hence allowing these to be private defeats that purpose and is disallowed. Note that abstract methods are implicitly virtual.

Q21: Which of these must be done explicitly: upcasting to a base class, or downcasting to a derived class?

Downcasting to a derived class. Since upcasting to a base class is a safe operation that is guaranteed to work it is done implicitly. Conversely, downcasting is not a safe operation which is why the compiler requires you to do it as an explicit cast so it is clear on your intent.

Q22: When you upcast a reference type what happens to the object instance that you apply the cast to?

Nothing. Casting affects only the references. The object instance is not touched.

Q23: Do sub-classes automatically expose the same constructors as their base types?

NO, you have to manually re-declare them.

Q24: Does C# support covariant return types?

NO it doesn't - that's a CLR restriction, not something specific to C# - but they can be simulated using explicit, generic interfaces. Bill Wagner has a good article on that here. This is definitely one thing C++ developers find frustrating when moving over to C# since covariant return types are supported in C++ and Java. [According to this, Microsoft has no plan to change this in the future, however C# 4.0 is planned to allow co- and contra-variance on parameterized interface and delegate types.]

Q25: Can you declare a generic property in C#?

NO, only methods and types can introduce new generic parameters. Properties can of course use existing generic parameters defined in the containing class.

Q26: How do you define a concrete class that implements both an interface and a base class in C#?

You need to specify the base class first after the colon before listing any interfaces implemented.

Round 1C began with the "Text Messaging Outrage" problem which basically asks that we identify the most efficient letter-to-key assignment on a phone to minimize the number of key presses needed by users. Google quite helpfully provide a frequency distribution for each letter. Given the frequency distribution it's obvious what the optimal assignment is - for the letters that are most frequently used assign them key press combinations that require the fewest key presses. Technically speaking this is a greedy approach and it should be intuitively obvious why it produces the optimal assignment.

This was one of the easiest problems encountered so far! Here's the code in C#:

using System;
using System.IO;

namespace GoogleCodeJam.TextMessage
{
    class Program
    {
        static void Main()
        {
            string basePath = "";
            StreamReader infile = new System.IO.StreamReader(basePath + "large.txt");
            StreamWriter outfile = new System.IO.StreamWriter(basePath + "output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                long minKeyPressCount = 0;

                // read in the input data
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                int P = Int32.Parse(data[0]); // max number of letters to place on a key
                int K = Int32.Parse(data[1]); // number of keys available
                int L = Int32.Parse(data[2]); // number of letters in the alphabet

                // read in the letter frequencies
                int[] frequencies = new int[L];
                int[] indexes = new int[L];

                string[] freqData = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                int i = 0;
                foreach (string s in freqData)
                {
                    indexes[i] = i;
                    frequencies[i] = Int32.Parse(s);
                    i++;
                }

                int nextKfree = 0;      // the one-based index of the key with the next lowest key press combo
                int nextPfree = 1;      // the one-based index of the letter on the "low key" with the next lowest key press combo

                // map the most used letters to the shortest key press routines available
                Array.Sort(frequencies,indexes);    // ~ O(n log n) on average since it uses an unstable QuickSort internally
                Array.Reverse(frequencies);         // ~ O(n)
                Array.Reverse(indexes);             // ~ O(n)
                int ii = 0;
                foreach (int x in indexes)  // from greatest- to least-used index
                {
                    // find the next available key press combo walking through from cheapest to dearest
                    nextKfree++;
                    if (nextKfree > K)
                    {
                        nextKfree = 1;
                        nextPfree++;
                    }
                    checked
                    {
                        minKeyPressCount += (frequencies[ii] * nextPfree);
                    }
                    ii++;
                }

                // write out the results
                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, minKeyPressCount));
            }
            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}

Following on from the fun of Minimum Scalar Product, Milkshakes, and Numbers in Round 1A is three more interesting but rather challenging problems in Round 1B. I first one I attempted was the "Number Sets" problem. This problem requires that we group numbers that have common prime factors thus it involves 3 challenges: managing sets, finding prime numbers within a given range, and finding common factors.

What makes this problem slightly easier is the fact that the numbers are consecutive integers, with a spread no larger than 1 million. This means that when we construct sets we can use a direct-access (indexed) data structure so lookup of a given value is O(1) since we can use it's index. As well, we are never going to have the same number in multiple sets - each number can only be in 1 set at any given time. A useful data structure in this case is Disjoint Sets (see Chapter 21 in Introduction to Algorithms). These can be implemented using an internal linked list, or a rooted tree structure. The later is slightly more efficient if you employ path compression and union by rank.

In the "large" variety of this problem the B parameter which is the upper bound on the range of integers that are to be examined is 10¹². This makes for a huge number of elements to check if you go through each one, find all the factors for that number, then figure out which of those factors are prime, then check every pair of integers in the range for common prime factors. How big is huge? Well given that the range of integers to check is 10¹², in the worst case, the number of integer pairs is approx. 10²⁴/2 [= 10¹².(10¹²-1)/2], since ⁿC_r = n! / (n-r)! r! . Thus it isn't computationally feasible to try this approach.

A better approach is to attack the problem the other way round. That is, find the prime numbers in the range, then for each prime number find every multiple of it and group them into a common set using the aforementioned disjoint set data structure. Furthermore, we know that for a given interval of consecutive integers [a,b] = {x ∈ ℜ, a ≤ x ≤ b} the "spread" of the interval is (b-a+1). Any prime number greater than or equal to the spread can only have, at most, 1 integer which is a multiple of the prime that falls within the range [a,b]. Why? Because after you have found a multiple of the prime that falls within the range, and then added that prime to this number, it must fall outside the range since the prime is greater than the spread of the interval. The fact that we can have, at most, one factor means no set union will ever take place in this case. Hence we need to only find the prime numbers less than the size of the spread of the interval. For a given upper interval bound, the bigger the interval spread, the fewer the number of prime numbers we need to evaluate.

There are several well published, efficient methods to produce a series of prime numbers, including Sieve of Eratosthenes and the Sieve of Atkin. The running time of Eratosthenes is O((nlogn)(loglogn)), although it has a memory requirement of O(n) in order to store the work-in-progress results. In other words, it's sublinear. I chose the slightly less efficient sieve of Eratosthenes over the Atkin sieve since it is simple to code.

   1:  using System;

   2:  using System.Collections.Generic;

   3:  using System.IO;

   4:   

   5:  namespace GoogleCodeJam.NumberSets

   6:  {

   7:      public enum NumberType : byte

   8:      {

   9:          Unknown = 0,    //the default

  10:          Prime = 1,

  11:          Composite = 2

  12:      }

  13:   

  14:      //Sieve of Eratosthenes

  15:      public class PrimeSieve

  16:      {

  17:          NumberType[] _values;   // NB: this is a zero-based array

  18:   

  19:          public PrimeSieve(ulong max)    //umax is the upper range limit to check

  20:          {

  21:              if (max < 2) throw new ArgumentException();

  22:   

  23:              _values = new NumberType[max];      // 0 -> max-1

  24:              _values[0] = NumberType.Composite;  // one is not prime

  25:          }

  26:   

  27:          public List<ulong> ComputePrimes()

  28:          {

  29:              List<ulong> primes = new List<ulong>();

  30:   

  31:              for (ulong i = 2; i <= (ulong)_values.Length; i++)

  32:              {

  33:                  if (_values[i - 1] == NumberType.Unknown)

  34:                  {

  35:                      //The next unknown value must be prime

  36:                      _values[i - 1] = NumberType.Prime;

  37:                      primes.Add(i);

  38:   

  39:                      //All multiples of this prime must be Composite

  40:                      //but we can start at i squared

  41:                      for (ulong j = i * i; j <= (ulong)_values.Length; j += i)

  42:                      {

  43:                          _values[j - 1] = NumberType.Composite;

  44:                      }

  45:                  }

  46:              }

  47:              return primes;

  48:          }

  49:      }

  50:   

  51:      public class DisjointSets

  52:      {

  53:          private int _elementCount;   // The number of elements in the DisjointSets data structure.

  54:          private int _setCount;       // The number of sets  in the DisjointSets data structure.

  55:          private List<Node> _nodes;   // The list of nodes representing the elements

  56:   

  57:          // Create an empty DisjointSets data structure

  58:          public DisjointSets() : this(0) { }

  59:   

  60:          // Create a DisjointSet data structure with a specified

  61:          // number of elements (with element id's from 0 to count-1)

  62:          public DisjointSets(int count)

  63:          {

  64:              _elementCount = 0;

  65:              _setCount = 0;

  66:              _nodes = new List<Node>();

  67:              AddElements(count);

  68:          }

  69:   

  70:          // Returns the number of elements currently in the DisjointSets data structure.

  71:          public int ElementCount

  72:          {

  73:              get { return _elementCount; }

  74:          }

  75:   

  76:          // Returns the number of sets currently in the DisjointSets data structure.

  77:          public int SetCount

  78:          {

  79:              get { return _setCount; }

  80:          }

  81:   

  82:          // Find the set identifier that an element currently belongs to.

  83:          // Note: some internal data is modified for optimization even though this method is constant.

  84:          public int FindSet(int elementId)

  85:          {

  86:              if (elementId >= _elementCount)

  87:                  throw new ArgumentOutOfRangeException("elementId");

  88:   

  89:              // Find the root element that represents the set which `elementId` belongs to

  90:              Node curNode = _nodes[elementId];

  91:              while (curNode.Parent != null)

  92:                  curNode = curNode.Parent;

  93:   

  94:              Node representative = curNode;

  95:   

  96:              // Walk to the representative, updating the parents of `elementId`. Make those elements 

  97:              // the direct children of `representative`. This optimizes the tree for future 

  98:              // FindSet invocations.

  99:              curNode = _nodes[elementId];

 100:              while (curNode != representative)

 101:              {

 102:                  Node next = curNode.Parent;

 103:                  curNode.Parent = representative;

 104:                  curNode = next;

 105:              }

 106:   

 107:              return representative.Index;

 108:          }

 109:   

 110:          // Combine two sets into one. All elements in those two sets will share the

 111:          // same set id that can be gotten using FindSet.

 112:          public void Union(int setId1, int setId2)

 113:          {

 114:              if (setId1 >= _elementCount) throw new ArgumentOutOfRangeException("setId1");

 115:              if (setId2 >= _elementCount) throw new ArgumentOutOfRangeException("setId2");

 116:   

 117:              Node set1Rep = _nodes[setId1];

 118:              while (set1Rep.Parent != null)

 119:                  set1Rep = set1Rep.Parent;

 120:   

 121:              Node set2Rep = _nodes[setId2];

 122:              while (set2Rep.Parent != null)

 123:                  set2Rep = set2Rep.Parent;

 124:   

 125:              if (set1Rep.Index == set2Rep.Index)

 126:                  return; // already unioned

 127:   

 128:              Node set1 = _nodes[setId1];

 129:              Node set2 = _nodes[setId2];

 130:   

 131:              // Determine which node representing a set has a higher rank. The node with the higher rank

 132:              // is likely to have a bigger subtree so in order to better balance the tree representing

 133:              // the union, the node with the higher rank is made the parent of the one with the lower

 134:              // rank and not the other way around.

 135:              if (set1.Rank > set2.Rank)

 136:              {

 137:                  set2.Parent = set1;

 138:                  ++set1.Rank;

 139:              }

 140:              else if (set1.Rank < set2.Rank)

 141:              {

 142:                  set1.Parent = set2;

 143:                  ++set2.Rank;

 144:              }

 145:              else // set1.Rank == set2.Rank

 146:              {

 147:                  set2.Parent = set1;

 148:                  ++set1.Rank; // update rank

 149:              }

 150:   

 151:              // Since two sets have fused into one, there is now one less set so update the set count.

 152:              --_setCount;

 153:          }

 154:   

 155:          // Add a specified number of elements to the DisjointSets data structure. 

 156:          // The element id's of the new elements are numbered

 157:          // consecutively starting with the first never-before-used elementId.

 158:          public void AddElements(int addCount)

 159:          {

 160:              // insert and initialize the specified number of element nodes to the end of the `_nodes` array

 161:              for (int i = _elementCount; i < _elementCount + addCount; ++i)

 162:              {

 163:                  Node newNode = new Node();

 164:                  newNode.Parent = null;

 165:                  newNode.Index = i;

 166:                  newNode.Rank = 0;

 167:                  _nodes.Add(newNode);

 168:              }

 169:   

 170:              // update element and set counts

 171:              _elementCount += addCount;

 172:              _setCount += addCount;

 173:          }

 174:   

 175:          // Internal Node data structure used for representing an element.

 176:          private class Node

 177:          {

 178:              public int Rank;    // This roughly represent the max height of the node in its subtree.

 179:              public int Index;   // The index of the element the node represents.

 180:              public Node Parent; // The parent node of the node.

 181:          }

 182:      }

 183:   

 184:      public class Program

 185:      {

 186:          static void Main()

 187:          {

 188:              StreamReader file = new System.IO.StreamReader("large.txt");

 189:              StreamWriter outfile = new System.IO.StreamWriter("output.txt");

 190:   

 191:              List<ulong> primes = (new PrimeSieve(1000001)).ComputePrimes();

 192:   

 193:              int testCases = Int32.Parse(file.ReadLine());

 194:              for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based

 195:              {

 196:                  

 197:                  string[] d = (file.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);

 198:                  ulong a = UInt64.Parse(d[0]); // interval start

 199:                  ulong b = UInt64.Parse(d[1]); // interval end

 200:                  ulong p = UInt64.Parse(d[2]); // minimum prime factor

 201:   

 202:                  int elementCount = (int)(b - a + 1);

 203:                  if (elementCount < 2)

 204:                  {

 205:                      outfile.Write(String.Format("Case #{0}: {1}\r\n", caseNo, 1));

 206:                  }

 207:                  else

 208:                  {

 209:                      DisjointSets sets = new DisjointSets(elementCount);

 210:   

 211:                      // using a sieve find all prime numbers between P and A

 212:                      foreach (ulong i in primes)

 213:                      {

 214:                          if (i > (ulong)elementCount) break;

 215:   

 216:                          if (i >= p)

 217:                          {

 218:                              // find all integers in the given range which have this prime factor

 219:                              for (ulong x = (a % i == 0) ? a : (a + i - a % i); x + i <= b; x +=i )

 220:                              {

 221:                                  // i is a prime factor of x

 222:                                  sets.Union(sets.FindSet((int)(x-a)), sets.FindSet((int)(x+i-a)));

 223:                              }

 224:                          }

 225:                      }

 226:                      outfile.Write(String.Format("Case #{0}: {1}\r\n", caseNo, sets.SetCount));

 227:                  }

 228:              }

 229:   

 230:              file.Close();

 231:              outfile.Flush();

 232:              outfile.Close();

 233:          }

 234:      }

 235:  }

 236: