Wow, I couldn't disagree more with wet blanket OriginalGriff. I've found one of the best ways to learn is looking directly at a solution and then reverse-engineering it and improving on it. In that spirit, here is a sub-optimal solution that would pass in an interview situation:
public static int[][] RoadBuilder(int nCities, int[,] builtRoads)
{
HashSet<string> alreadyBuilt = new HashSet<string>();
string hereToThere, thereToHere;
for(int i = 0; i < builtRoads.Length / 2; i++)
{
hereToThere = builtRoads[i, 0] + "|" + builtRoads[i, 1];
thereToHere = builtRoads[i, 1] + "|" + builtRoads[i, 0];
if(!alreadyBuilt.Contains(hereToThere))
alreadyBuilt.Add(hereToThere);
if(!alreadyBuilt.Contains(thereToHere))
alreadyBuilt.Add(thereToHere);
}
List<int[]> toBuild = new List<int[]>();
for(int i = 0; i < nCities; i++)
{
for(int j = 0; j < nCities; j++)
{
if(i == j)
continue;
hereToThere = i.ToString() + "|" + j.ToString();
thereToHere = j.ToString() + "|" + i.ToString();
if(!alreadyBuilt.Contains(hereToThere) &&
!alreadyBuilt.Contains(thereToHere))
{
toBuild.Add(new int[2] { i, j });
alreadyBuilt.Add(thereToHere);
}
}
}
int[][] results = new int[toBuild.Count][];
toBuild.CopyTo(results);
return results;
}
On a personal note though, I would caution you to stay alert if you went to work there. They want a function that takes a multidimensional array as a parameter and returns a 2d array. In real life that makes no sense, and increases bug probability astronomically. A Java programmer coming to C# would be stumped and even seasoned C# programmers would likely scratch their heads.