CareerCup

Prroblem: write an algorithm to calculate the minimum cost to add new roads between the cities such that all the cities are accessible from each other

int numTotalAvailableCities = 6;
int numTotalAvailableRoads = 3;
int[,] roadsAvailable = { { 1, 4 }, { 4, 5 }, { 2, 3 } };
int[,] costNewRoadsToConstruct = { { 1, 2,5 }, { 1,3,10 }, {1,6,2} ,{ 5, 6, 5 } };
int numNewRoadsConstruct = 4;

public class MinimumCostToConstructNewRoad
    {
        public static int getMinimumCostToConstruct(int numTotalAvailableCities,
            int numTotalAvailableRoads,
            int[,] roadsAvailable,
            int numNewRoadsConstruct,
            int[,] costNewRoadsConstruct)

        {
            int totalCost = 0;
            bool[] Visited = new bool[numTotalAvailableCities];
            int[] Keys = new int[numTotalAvailableCities];
            int[] Parent = new int[numTotalAvailableCities];

            int[,] AdjMatrix = GetAdjecencyMatrix(roadsAvailable, costNewRoadsConstruct, numTotalAvailableCities);


            for (int i=0;i< numTotalAvailableCities;i++)
            {
                Keys[i] = Int32.MaxValue;
            }

            Keys[0] = 0;
            Parent[0] = -1;

            for(int i=0;i< numTotalAvailableCities-1;i++)
            {
                var u = FindMin(Visited, Keys);

                Visited[u] = true;
                for(int v=0;v< numTotalAvailableCities;v++)
                {
                    if(Visited[v]==false && AdjMatrix[u, v]!=Int32.MaxValue && AdjMatrix[u,v]<Keys[v])
                    {
                        Parent[v] = u;
                        Keys[v] = AdjMatrix[u, v];
                    }
                }

            }

           for(int i=1;i< numTotalAvailableCities;i++)
            {
                totalCost = totalCost + AdjMatrix[Parent[i], i];
            }
            return totalCost;
        }


        private static int FindMin(bool[] Visited, int[] Keys)
        {
            int min = Int32.MaxValue; int index = -1;
            for (int i = 0; i < Keys.Length; i++)
            {
                if (Visited[i] == false && Keys[i] < min)
                {
                    min = Keys[i];
                    index = i;
                }
            }
            return index;
        }


        private static int[,]  GetAdjecencyMatrix(int[,] roadsAvailable, int[,] costNewRoadsConstruct,int numTotalAvailableCities)
        {
            int[,] AdjMatrix = new int[numTotalAvailableCities, numTotalAvailableCities];

            for (int i = 0; i < numTotalAvailableCities; i++)
            {
                for (int j = 0; j < numTotalAvailableCities; j++)
                {
                    AdjMatrix[i, j] = Int32.MaxValue;
                }
            }


            int count = 0;
            for (int i = 0; i < roadsAvailable.GetLength(0); i++)
            {
                int start = roadsAvailable[i, count]-1;
                int end = roadsAvailable[i,count+1]-1;
                AdjMatrix[start, end] = 0;
            }

            for (int i = 0; i < costNewRoadsConstruct.GetLength(0); i++)
            {
                int start = costNewRoadsConstruct[i, count]-1;
                int end = costNewRoadsConstruct[i, count+1]-1;
                int cost= costNewRoadsConstruct[i, count + 2];

                AdjMatrix[start, end] = cost;
            }

            return AdjMatrix;
        }
    }

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ArrayProblems
{
public class MultiplyTwoLargeNumber
{
public static string MultiplyBigNumbers(string s1, string s2)
{
char[] num1 = s1.ToCharArray();
char[] num2 = s2.ToCharArray();
//string=99
//char--> 9 , val --> 57(48+9)
//so s[i]-'0' will give val 9 and char as horizontal tab

char[] result = new char[num1.Length + num2.Length]; // Default 0 '/0' 2 ==> 50 '2'
int carry = 0;
int offset = 0;

for (int i = num1.Length - 1; i >= 0; i--)
{
int tail = result.Length - 1 - offset;
for (int j = num2.Length - 1; j >= 0; j--)
{
int resval = 0;
if(result[tail]!=0)
{
resval = result[tail] - '0';
}
int sum = resval+ ((num1[i] - '0') * (num2[j] - '0')) + carry; //remember to add result before taking mode
result[tail] = (char)((sum % 10) + '0');
carry = sum / 10;
tail--;
}
if (carry > 0)
{
int res = (result[tail] != 0) ? (result[tail] - '0') + carry : result[tail] + carry;

result[tail] = (char)(res + '0');
carry = 0;
}
offset++;
}

return new string(result);
}


}
}

/**
You have list,which contains a DS(Data Structure) which have a list and a value (basically a list of list).
You need to write an iterator such that it will iterate over the numbers/integers whenever a .next() is called

1->2->3->4
|
6---->7------------->10
| |
8->9 11->12


Output
1 .next() -> 1
2..next() -> 6
3..next() ->7
4..next() ->8
5..next() ->9
6..next() ->10
7..next() ->11
8..next() ->12
9..next() ->2
10..next() ->3
11..next() ->4
12..next() -> throws Exception
**/