Need help on interview challenge question on 2D arrays in C#

Question

1.44/5 (2 votes)

See more:

Hi,
I was given with the below coding challenge in C# in one of the interviews with top tier tech company. Could anyone help me with the optimized solution for this?

/*
The objective of this exercise is to build a road network connecting every pair of cities.Each city should be connected to each other city once.
*/
public class Program
{
/* Your function RoadBuilder should return a list of new roads required to be built,
if the existing roads are given by builtRoads and the total number of
cities is nCities. Roads should not connect cities to themselves.
*/
public static int[][] RoadBuilder(int nCities, int[, ] builtRoads)
{
//implement the function here
return new int[0][];
}

public static void Main()
{
int[, ] test1 = new int[3, 2]{{0, 1}, {1, 2}, {3, 2}};
Console.WriteLine(RoadBuilder(4, test1)); // expected result should be {{0,2}, {0, 3}, {1, 3}}
}
}

What I have tried:

I tried converting the array to list and retrieving the possible combinations from it. But couldn't find an option to remove the already existing connections.

Posted 21-May-17 20:04pm

Member 13214692

Updated 21-May-17 22:21pm

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2017-05-21T20:15:00

We do not do your homework: it is set for a reason.
And interviews are homework - the interviewer needs to know how you think, how work, not me.
Giving you a solution improves your apparent ability falsely, and gives you an advantage over people who can do the job themselves - which is what the company is looking for! We can't support you through your whole career with the company if you get the job, not if yiu get the salary rather than us, anyway, so it would be unfair on everybody. You, in the long run; the genuine applicants; the company.

Try it yourself, you may find it is not as difficult as you think!

If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!

Robert Welliever · Answer 2 · 2017-05-21T22:21:00

Solution 2

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:

C#

public static int[][] RoadBuilder(int nCities, int[,] builtRoads)
{
    // Build lookup of existing connections
    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);
    }

    // Identify missing roadways
    List<int[]> toBuild = new List<int[]>();
    for(int i = 0; i < nCities; i++)
    {
        for(int j = 0; j < nCities; j++)
        {
            if(i == j) // ignore a city to itself
                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);
            }
        }
    }

    // Fill formatted results
    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.

Posted 21-May-17 22:21pm

Robert Welliever

Comments

F-ES Sitecore 22-May-17 4:33am

I hope he gets the job using your code and becomes your co-worker where you will need to continue to carry him, doing all of his tasks as well as your own.

F-ES Sitecore 22-May-17 5:50am

If a co-worker was given a task to do and simply asked me how to do it I'd probably look to get them fired, or at a minimum removed from my team. If you are employed it is to do a job, if you can't do that job you shouldn't be employed. Helping people to fraudently obtain a job doesn't help anyone. How would you like it if you went to the doctor and that doctor didn't really have the knowledge to help you, he got other people to sit his exams and answer his interview questions?

F-ES Sitecore 22-May-17 6:14am

Sometimes you get interview questions to complete in your own time. Or maybe he has a friend also about to take the interview and wants to prepare them in advance.

As for getting people fired I make no apologies for ensuring people are capable of doing the job they were hired for. When you're running a team on a deadline and one person always needs others to do their work for them maybe you'll change your opinion.

F-ES Sitecore 22-May-17 7:21am

We're not talking about questions or helping...we're talking about someone who has been given a task and doesn't have the ability to do it, to even start it, and instead wants other people to do their job for them. If you can't see the difference between the two then good luck yourself.

F-ES Sitecore 22-May-17 8:18am

When you've been here a little bit longer you'll grow to know when you're actually helping someone to learn and when you're just doing someone else's job for them. Given three long-term members have one opinion and you have a different one maybe you should consider the fact that those members have experience you do not and that maybe we're right.

F-ES Sitecore 22-May-17 10:17am

That's a straw-man argument, I said that it was the level of experience that gives you insite and the fact that I have more experience with this site than you do (as do Griff and Richard) is an undenyable fact. If you want to claim that experience does not drive insite then good luck with that.

F-ES Sitecore 22-May-17 10:58am

I said experience was the driver and you changed that to "membership seniority" and argued against "membership seniority" (whatever that means). When you argue against an argument that is weaker than what the other person said, and is not what they actually said, then that is by definition a straw-man argument. You are now following that up ad ad hominem arguments. If your position held any weight at all you'd stick to the facts.

F-ES Sitecore 22-May-17 11:40am

If you think my "membership seniority" does not equal greater experience then, as I said, you are conducting a straw-man arguement.

Richard MacCutchan 22-May-17 5:08am

You do not help people by doing their work for them. OP could easily have found some answers by using initiative and brain power, rather than expecting someone else to do it for him/her.

Robert Welliever 22-May-17 5:58am

That's quite a disprovable assertion. I've been helped countless times by looking at other people's answers. I've also specifically been helped by reading answers to interview questions.

Richard MacCutchan 22-May-17 6:38am

May not be provable, but it's certainly based on experience.

Robert Welliever 22-May-17 7:17am

You are incorrect. Your statements are actually easily disprovable regardless of your experience. You make gross generalizations to which I only have to produce a single counterexample, which I did. I'm pretty sure that's how you do science.

Richard MacCutchan 22-May-17 7:19am

Yes, you are right and I am wrong.

George Swan 22-May-17 11:41am

I’m confused. Can someone please point out where in the rules https://www.codeproject.com/Articles/64628/Code-Project-Quick-Answers-FAQ#rules does it state that homework questions must not be answered?

[no name] 22-May-17 12:00pm

Where do you see that anyone said that homework questions wouldn't be answered? Homework questions are answered here all the time.

George Swan 22-May-17 12:55pm

It was just that Griff said that we don’t do your homework. So I assumed that it must be against the rules. But I looked at the rules and couldn’t see it, then I sought clarification -which you kindly gave me. Thank you. So, now that you have replied and it’s clear that we have a right to post solutions to homework, another question arises. Namely, who are the ‘we’ in, ‘we do not do your homework’?

[no name] 22-May-17 13:12pm

Yes I can see your confusion. What Griff is really trying to say is that "We are not here to do your homework or real work assignment for people. Especially when the person has made zero effort to do his own work first." "We" meaning the CodeProject community as a whole. The OP has made no effort to attempt this himself and instead expects someone here to just do it for him. Most people here know that doing peoples jobs for them is not "helping" them in any way other than teaching them that all the have to do is come here and someone will do their job for them. Then, they get out into the real world, can't do the job, and have to continually try and get others to do it for them. I am one of the lucky few that have actually been in that position, doing my own job and then having to do someone else's job for them because they cheated their way through school. Not a fun time.

George Swan 22-May-17 14:19pm

I agree with your sentiments entirely. However, my approach would be to pass onto the next question without reprimanding the poster who is acting within the forum rules. It has been good chatting with you. Best wishes, George.

[no name] 22-May-17 14:30pm

Actually, IMO this posting violates "rule" #2 of the FAQ. It is not specific and does not detail exactly what help the OP needs (except the OP thinks we should do his work for him).