Figure out max number of consecutive seats

Question

I had an interviewer ask me to write a program in c# to figure out the max number of 4 members families that can sit consecutively in a venue, taking into account that the 4 members must be consecutively seated in one single row, with the following context:

• N represents the number of rows availabe.
• The Columns are labeled from the letter "A" to "K", purposely ommiting the letter "i" (in other words, {A,B,C,D,E,F,G,H,J,K})
• M represents a list of reserved seats

Quick example:

N = 2
M = {"1A","2F","1C"}
Solution = 3

In the representation you can see that, with the reservations and the size given, only three families of 4 can be seated in a consecutive order.

How would you solve this? is it possible to not use for loops? (Linq solutions)

I got mixed up in the for loops when trying to deal with the reservations aray: My idea was to obtain all the reservations that a row has, but then I don't really know how to deal with the letters (Converting directly from letter to number is a no go because the missing "I") and you kinda need the letters to position the reserved sits anyway.

Any approach or insight on how to go about this problem would be nice. Thanks in advance!

Answer 1

If you represent your matrix in simple for developers format, it will be easier. You can accomplish it either by dictionary or perform not so complex mapping by hand. In any case this will calculate count of free consecutive seats:

    public static void Main(string[] args)
    {
        var count = 0;//total count
        var N = 2; //rows
        var M = 10; //columns
        var familySize = 4;
        var matrix = new []{Tuple.Create(0,0),Tuple.Create(1,5), Tuple.Create(0,2)}.OrderBy(x=> x.Item1).ThenBy(x=> x.Item2).GroupBy(x=> x.Item1, x=> x.Item2);
        foreach(var row in matrix)
        {
            var prevColumn = -1;
            var currColumn = 0;
            var free = 0;
            var div = 0;

            //Instead of enumerating entire matrix, we just calculate intervals in between reserved seats. 
            //Then we divide them by family size to know how many families can be contained within
            foreach(var column in row)
            {
                currColumn = column;
                free = (currColumn - prevColumn - 1)/familySize;
                count += free;
                prevColumn = currColumn;
            }
            currColumn = M;
            free = (currColumn - prevColumn - 1)/familySize;
            count += free;
        }


        Console.WriteLine("Result: {0}", count);
    }

Answer 2

Here is another implementation.

I also tried to explain why certain things have been done.

Good luck.

    private static int GetNumberOfAvailablePlacesForAFamilyOfFour(int numberOfRows, string[] reservedSeats)
    {
        // By just declaring the column names as a string of the characters
        // we can query the column index by colulmnNames.IndexOf(char)
        string columnNames = "ABCDEFGHJK";


        // Here we transform the reserved seats to a matrix
        // 1A 2F 1C becomes
        // reservedSeatMatrix[0] = [0, 2] -> meaning row 1 and columns A and C, indexes 0 and 2
        // reservedSeatMatrix[1] = [5] -> meaning row 2 and column F, index 5
        List<List<int>> reservedSeatMatrix = new List<List<int>>();

        for (int row = 0; row < numberOfRows; row++)
        {
            reservedSeatMatrix.Add(new List<int>());
        }

        foreach (string reservedSeat in reservedSeats)
        {
            int seatRow = Convert.ToInt32(reservedSeat.Substring(0, reservedSeat.Length - 1));
            int seatColumn = columnNames.IndexOf(reservedSeat[reservedSeat.Length - 1]);
            reservedSeatMatrix[seatRow - 1].Add(seatColumn);
        }

        // Then comes the evaluation.
        // Which is simple enough to read.
        int numberOfAvailablePlacesForAFamilyOfFour = 0;

        for (int row = 0; row < numberOfRows; row++)
        {
            // Reset the number of consecutive seats at the beginning of a new row
            int numberOfConsecutiveEmptySeats = 0;

            for (int column = 0; column < columnNames.Length; column++)
            {
                if (reservedSeatMatrix[row].Contains(column))
                {
                    // reset when a reserved seat is reached
                    numberOfConsecutiveEmptySeats = 0;
                    continue;
                }
                numberOfConsecutiveEmptySeats++;
                if(numberOfConsecutiveEmptySeats == 4)
                {
                    numberOfAvailablePlacesForAFamilyOfFour++;
                    numberOfConsecutiveEmptySeats = 0;
                }
            }
        }

        return numberOfAvailablePlacesForAFamilyOfFour;
    }


    static void Main(string[] args)
    {
        int familyPlans = GetNumberOfAvailablePlacesForAFamilyOfFour(2, new string[] { "1A", "2F", "1C" });
    }

Answer 3

Good luck on your interview

As always, you will be asked how could you improve that? So you'd consider complexity stuff like O(N), O(wtf).

Underlying implementation would always need for or foreach. Just importantly, never do unnecessary in a loop. For example, if there's only 3 seats left in a row, you don't need to keep hunting on that row because it is not possible to find any.

This might help a bit:

    var n = 2;
    var m = new string[] { "1A", "2F", "1C" };

    // We use 2 dimension bool array here. If it is memory constraint, we can use BitArray.
    var seats = new bool[n, 10];
    // If you just need the count, you don't need a list. This is for returning more information.
    var results = new List<object>();

    // Set reservations.
    foreach (var r in m)
    {
        var row = r[0] - '1';
        // If it's after 'H', then calculate index based on 'J'.
        // 8 is index of J.
        var col = r[1] > 'H' ? (8 + r[1] - 'J') : r[1] - 'A';
        seats[row, col] = true;
    }

    // Now you should all reserved seats marked as true.
    // This is O(N*M) where N is number of rows, M is number of columns.
    for (int row = 0; row < n; row++)
    {
        int start = -1;
        int length = 0;

        for (int col = 0; col < 10; col++)
        {
            if (start < 0)
            {
                if (!seats[row, col])
                {
                    // If there's no consecutive seats has started, and current seat is available, let's start!
                    start = col;
                    length = 1;
                }
            }
            else
            {
                // If have started, check if we could have 4 seats.
                if (!seats[row, col])
                {
                    length++;
                    if (length == 4)
                    {
                        results.Add(new { row, start });

                        start = -1;
                        length = 0;
                    }
                }
                else
                {
                    // // We won't be able to reach 4 seats, so reset
                    start = -1;
                    length = 0;
                }
            }

            if (start < 0 && col > 6)
            {
                // We are on column H now (only have 3 seats left), and we do not have a consecutive sequence started yet,
                // we won't be able to make it, so break and continue next row.
                break;
            }
        }
    }

    var solution = results.Count;

LINQ, for and foreach are similar things. It is possible you could wrap the above into a custom iterator like:

class ConsecutiveEnumerator : IEnumerable
{
    public IEnumerator GetEnumerator()
    {
    }
}

Then you could start using LINQ.