Определить максимальное количество последовательных мест - PullRequest
Новая
       3

Определить максимальное количество последовательных мест

1 голос
/ 18 марта 2020

У меня был интервьюер, попросивший меня написать программу в c#, чтобы выяснить максимальное количество семей из 4 членов, которые могут сидеть последовательно в одном месте, принимая во внимание, что 4 члена должны быть последовательно размещены в одном ряду , со следующим контекстом:

  • N представляет количество доступных строк.
  • Столбцы помечены буквой от «A» до «K», намеренно пропуская букву «i». «(другими словами, {A, B, C, D, E, F, G, H, J, K})
  • M представляет список зарезервированных мест

Быстрый пример: 

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

enter image description here

В представлении вы можете видеть, что с учетом оговорок и размера только три семейства из 4 можно сидеть в последовательном порядке.

Как бы вы решили это? Можно ли не использовать для петель? (Решения Linq)

Я запутался в циклах for, пытаясь справиться с резервированием aray: моя идея состояла в том, чтобы получить все резервирования, которые есть в строке, но тогда я действительно не знаю, как разберитесь с буквами (преобразование непосредственно из буквы в число - это не go, потому что отсутствует «Я»), и вам все равно нужны буквы, чтобы расположить зарезервированные места.

Любой подход или понимание того, как go об этой проблеме было бы неплохо. Заранее спасибо!

Ответы [ 3 ]

1 голос
/ 18 марта 2020

Удачи на собеседовании

Как всегда, вас спросят, как вы могли бы это улучшить? Таким образом, вы должны учитывать такие сложности, как O (N), O (wtf).

Базовая реализация всегда будет нуждаться в for или foreach. Просто важно , никогда не делайте ненужных в oop. Например, если в ряду осталось только 3 места, вам не нужно продолжать охоту в этом ряду, поскольку невозможно найти ни одного.

Это может немного помочь: 

    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 и foreach - похожие вещи. Возможно, вы могли бы обернуть вышеупомянутое в пользовательский итератор как: 

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

Тогда вы могли бы начать использовать LINQ.

1 голос
/ 18 марта 2020

Вот еще одна реализация.

Я также пытался объяснить, почему были сделаны определенные вещи.

Удачи. 

    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" });
    }
0 голосов
/ 18 марта 2020

Если вы представите свою матрицу в простом для разработчиков формате, это будет проще. Вы можете выполнить sh либо по словарю, либо выполнить не очень сложное отображение вручную. В любом случае будет подсчитано количество свободных последовательных мест: 

    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);
    }
...