CareerCup

@Nayan Good solution Nayan.

I generalized it a bit for the array size. Now, you can pass in any sum limit and this will work (obviously not if the limit sum causes a MemoryOutOfRangeException:)).

public static int GetPossibleCoordinates(int limitSum)
{         
    Stack<Coordinate> coordinates = new Stack<Coordinate>();
    coordinates.Push(new Coordinate(0, 0));
    return GetQuadrantCoordinates(coordinates, limitSum);
}
public static int GetQuadrantCoordinates(Stack<Coordinate> coordinates, int limitSum)
{
    int count = 0;
    int arraySize = GetRequiredArraySize(limitSum) + 1;
    int[,] accessibleCoordinates = new int[arraySize, arraySize];
    while (coordinates.Count != 0)
    {
        Coordinate current = coordinates.Pop();
        int x = current.XValue;
        int y = current.YValue;
        if (accessibleCoordinates[x, y] == 1)
        {
            continue;
        }
        else
        {
            accessibleCoordinates[x, y] = 1;
        }
        if ((GetSumOfDigits(x) + GetSumOfDigits(y)) > limitSum)
        {
            continue;
        }
        if (x == 0 && y == 0)
        {
            count += 1;
        }
        else if (x == 0 || y == 0)
        {
            count += 2;
        }
        else
        {
            count += 4;
        }
                
        // Add elements to stack, it not already.
        if(accessibleCoordinates[x + 1, y] != 1)
        {
            coordinates.Push(new Coordinate(x + 1, y));
        }
        if (accessibleCoordinates[x, y + 1] != 1)
        {
            coordinates.Push(new Coordinate(x, y + 1));
        }
    }
    return count;
}
public static int GetSumOfDigits(int num)
{
    int sum = 0;
    num = Math.Abs(num);
    while (num > 0)
    {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}
public static int GetRequiredArraySize(int limitSum)
{
    int requiredSize = 0;
    while (limitSum > 9)
    {
        limitSum -= 9;
        requiredSize = (10 * requiredSize) + 9;
    }
    requiredSize = ((limitSum + 1) * (requiredSize + 1)) + requiredSize;
    return requiredSize;
}

The correct answer is "102485". The only logic that has changed in my code [method GetAccessibleCoordinateCount] is to calculate the whole quadrant and then subtract common coordinates of one axis (to not be counted 4 times) and then add the start element.

public class MonkeyCoordinates
{
    private HashSet<string> _accessibleCoordinates;
    private int _limitSum;
    public MonkeyCoordinates(int limitSum)
    {
        _limitSum = limitSum;
        _accessibleCoordinates = new HashSet<string>();
    }
    public int GetAccessibleCoordinateCount()
    {
        _accessibleCoordinates.Clear();
        Coordinate start = new Coordinate(0, 0);
        AccessNorthEastQuadrantCoordinates(start);
        // Remove the start element.
        _accessibleCoordinates.Remove(start.Key);
        // Get the count of coordinates on one of the axis.
        string[] commonCoordinates = (from northEastCoordinate in _accessibleCoordinates
                                    where (northEastCoordinate.StartsWith("0:"))
                                    select northEastCoordinate).ToArray();
        int count = 1 + ((_accessibleCoordinates.Count - commonCoordinates.Length) * 4);
        return count * 4;
    }
    private void AccessNorthEastQuadrantCoordinates(Coordinate current)
    {
        if (current.CoordinateSum > _limitSum)
        {
            return;
        }
        if (!_accessibleCoordinates.Add(current.Key))
        {
            return;
        }
        // We have two directions to move. North and East.
        Coordinate east = current.Move(Coordinate.Direction.East);
        AccessNorthEastQuadrantCoordinates(east);
        Coordinate north = current.Move(Coordinate.Direction.North);
        AccessNorthEastQuadrantCoordinates(north);
    }
}
internal sealed class Coordinate
{
    private const string KEYFORMAT = "{0}:{1}";
    internal enum Direction
    {
        North,
        South,
        East,
        West
    }
    internal Coordinate(int x, int y)
    {
        XValue = x;
        YValue = y;
        Key = string.Format(KEYFORMAT, x, y);
        CoordinateSum = Sum(x) + Sum(y);
    }
    internal int XValue
    {
        get;
        set;
    }
    internal int YValue
    {
        get;
        set;
    }
    internal string Key
    {
        get;
        set;
    }
    internal int CoordinateSum
    {
        get;
        set;
    }
    internal Coordinate Move(Direction direction)
    {
        int x = XValue;
        int y = YValue;
        switch (direction)
        {
            case Direction.East:
                x += 1;
                break;
            case Direction.West:
                x -= 1;
                break;
            case Direction.North:
                y += 1;
                break;
            case Direction.South:
            default:
                y -= 1;
                break;
        }
        return new Coordinate(x, y);
    }
    private int Sum(int val)
    {
        val = Math.Abs(val);
        int sum = 0;
        while (val > 0)
        {
            sum += val % 10;
            val = val / 10;
        }
        return sum;
    }
}

I agree and that is why I listed the drawbacks of the solution.

I did find some bugs in my solution and have hence fixed it in the original code. I have also changed the solution to calculate only one quadrant (North-East) and then multiply the solution by 4. The result is "87700". This is exluding the starting coordinate of {0,0}.

Why do you need 2 for loops?
I haven't worked with C++ much, but will give it a shot in terms of algorithm.
Moreover, I don't think that using the collection size in the for loop is a good practice when that collection is being modified in the loop itself.

Anyways, here is what I think should be the solution.

// Please insert a start coordinate {0,0} in the map before the for loop.
for(int index = 0; index < int(my_map.Size()); ++index)
{
    // Get the coordinate at the current index.
    // Please add a method to get the value at a desired index in the map.
    mapCoordinate = GetElementAtIndex(my_map, index);

    // For this mapCoordinate.
    my_map = AddGoodNeighbors(mapCoordinate.x, mapCoordinate.y, my_map);
}
// once you are out of the loop, you should have the map of all possible coordinates.
int count = int(my_map.Size());

@Kingmaker The logic is incorrect. {199, 0} is not the last coordinate the monkey can visit. {200, 0} is a valid coordinate as well.

Moreover, the second for loop should start from 1 and not 0. As of now, you add {0,0} 4 times in the count, which is incorrect.

Please note the following:

1. The code does not have error checks.
2. There is a possiblity of a stack overflow if the limit sum is really high.
3. This is not an optimized solution. We could reduce it to 1/4th by processing only one quadrant and one axis. The result can then be multiplied by 4. If the starting coordinate needs to be included, add 1 to the result.

Most of the logic seemed to be the one that I coded with. The only issue that I see is the while loop in Main.

int i=0;
    while (true)
    {
        my_map = obj1.addGoodNeighbours(i, i, my_map);
        i=i+1;
        if (i >= int(my_map.size()))
        {
            break;
        }
        else
        {
            continue;
        }
        std::cout << "Size of my_map: " << my_map.size() << '\n';
}

After adding good neighbors, you are incrementing i by 1. Therefore, you are moving diagonally in the map.
i.e. Starting Point {0,0}
{1,1}
{2,2}
{3,3}
This logic seems to be totally incorrect. The more logical solution with this approach should be (algorithm).
- Add the starting node to the map.
- While(current position does not reach maps end)
- get the node (current position)
- Add valid members to the map.
- Increment current poition.
- the size of the map should have the number of nodes.

The question needs some clarifications. There are a few questions I would ask the interviewer. For e.g.
1. What count is required? All combinations of movements or the max path that the monkey can take.

Anyways, I "ASSUMED" that the count of all the possible coordinates is expected.

In that case, the answer to this is "87700".
Algorithm:
For each coordinate that the monkey is on, there are four possible routes that he can take. North (y+1), South (y-1), East (x+1) and West (x-1). Recursion seems to be the solution to take. The catch is the base condition that should be applied.
- If the sum of the coordinates is more than the limit, return.
- If this coordinate has already been visited, return.

Where should we store the coordinates that have been visited. I took the liberty of using a HashSet<string> type to store this. A string, because I wanted to make sure that the coordinate 'key' should be unique (There are other ways to get a unique key, but for the ease, I used a string key of the format "{0}:{1}", this arguments are the x and y value).

The rest is self explanatory. If you want to print-out the coordinates, just add another method to print-out all the values in the hashset.

The code is below.

public class MonkeyCoordinates
{
    private HashSet<string> _accessibleCoordinates;
    private int _limitSum;
    public MonkeyCoordinates(int limitSum)
    {
        _limitSum = limitSum;
        _accessibleCoordinates = new HashSet<string>();
    }
    public int GetAccessibleCoordinateCount()
    {
        _accessibleCoordinates.Clear();
        Coordinate start = new Coordinate(0, 1);
        AccessNorthEastQuadrantCoordinates(start);
        return (_accessibleCoordinates.Count * 4);
    }
    private void AccessNorthEastQuadrantCoordinates(Coordinate current)
    {
        if (current.CoordinateSum > _limitSum) { return; }
        if (!_accessibleCoordinates.Add(current.Key)) { return; }
        // We have two directions to move. North and East.
        AccessNorthEastQuadrantCoordinates(current.Move(Coordinate.Direction.East));
        AccessNorthEastQuadrantCoordinates(current.Move(Coordinate.Direction.North));
    }
}
internal sealed class Coordinate
{
    private const string KEYFORMAT = "{0}:{1}";
    internal enum Direction{North, South, East, West}
    internal Coordinate(int x, int y)
    {
        XValue = x;
        YValue = y;
        Key = string.Format(KEYFORMAT, x, y);
        CoordinateSum = Sum(x) + Sum(y);
    }
    internal int XValue { get; set; }
    internal int YValue { get; set; }
    internal string Key { get; set; }
    internal int CoordinateSum { get; set; }
    internal Coordinate Move(Direction direction)
    {
        int x = XValue;
        int y = YValue;
        switch (direction)
        {
            case Direction.East:
                x += 1;
                break;
            case Direction.West:
                x -= 1;
                break;
            case Direction.North:
                y += 1;
                break;
            case Direction.South:
            default:
                y -= 1;
                break;
        }
        return new Coordinate(x, y);
    }
    private int Sum(int val)
    {
        val = Math.Abs(val);
        int sum = 0;
        while (val > 0)
        {
            sum += val % 10;
            val = val / 10;
        }
        return sum;
    }
}